0% found this document useful (0 votes)
53 views11 pages

Seek Time and Latency in Disk Scheduling

Uploaded by

rachitsihwe77
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
0% found this document useful (0 votes)
53 views11 pages

Seek Time and Latency in Disk Scheduling

Uploaded by

rachitsihwe77
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Disk Scheduling

A process needs two type of time, CPU time and IO time. For I/O, it requests the Operating
system to access the disk.

However, the operating system must be fare enough to satisfy each request and at the same
time, operating system must maintain the efficiency and speed of process execution.

The technique that operating system uses to determine the request which is to be satisfied next
is called disk scheduling.

1. Seek Time
Seek time is the time taken in locating the disk arm to a specified track where the read/write
request will be satisfied.

2. Rotational Latency
It is the time taken by the desired sector to rotate itself to the position from where it can access
the R/W heads.

3. Transfer Time
It is the time taken to transfer the data.

4. Disk Access Time


Disk access time is given as,

Disk Access Time = Rotational Latency + Seek Time + Transfer Time

5. Disk Response Time


It is the average of time spent by each request waiting for the IO operation.

Purpose of Disk Scheduling


The main purpose of disk scheduling algorithm is to select a disk request from the queue of I/O
requests and decide the schedule when this request will be processed.

Goal of Disk Scheduling Algorithm


o Fairness
o High throughout
o Minimal traveling head time
Disk Scheduling Algorithms
The list of various disks scheduling algorithm is given below. Each algorithm is carrying some
advantages and disadvantages. The limitation of each algorithm leads to the evolution of a new
algorithm.

o FCFS scheduling algorithm


o SSTF (shortest seek time first) algorithm
o SCAN scheduling
o C-SCAN scheduling
o LOOK Scheduling
o C-LOOK scheduling

FCFS Scheduling Algorithm


It is the simplest Disk Scheduling algorithm. It services the I/O requests in the order in which
they arrive. There is no starvation in this algorithm, every request is serviced.

Disadvantages
o The scheme does not optimize the seek time.
o The request may come from different processes therefore there is the possibility of
inappropriate movement of the head.

Example
Consider the following disk request sequence for a disk with 100 tracks 45, 21, 67, 90, 4, 50,
89, 52, 61, 87, 25

Head pointer starting at 50 and moving in left direction. Find the number of head movements
in cylinders using FCFS scheduling.
Solution

Number of cylinders moved by the head

= (50-45)+(45-21)+(67-21)+(90-67)+(90-4)+(50-4)+(89-50)+(89-52)+(61-52)+(87-61)+(87-
25)

= 5 + 24 + 46 + 23 + 86 + 46 + 39 +37+ 9 + 26 + 62

= 403
SSTF Scheduling Algorithm
Shortest seek time first (SSTF) algorithm selects the disk I/O request which requires the least
disk arm movement from its current position regardless of the direction. It reduces the total
seek time as compared to FCFS.

It allows the head to move to the closest track in the service queue.

Disadvantages
o It may cause starvation for some requests.
o Switching direction on the frequent basis slows the working of algorithm.
o It is not the most optimal algorithm.

Example
Consider the following disk request sequence for a disk with 100 tracks

45, 21, 67, 90, 4, 89, 52, 61, 87, 25

Head pointer starting at 50. Find the number of head movements in cylinders using SSTF
scheduling.

Solution:

Number of cylinders = 5 + 7 + 9 + 6 + 20 + 2 + 1 + 65 + 4 + 17 = 136


Scan Algorithm
It is also called as Elevator Algorithm. In this algorithm, the disk arm moves into a particular
direction till the end, satisfying all the requests coming in its path,and then it turns back and
moves in the reverse direction satisfying requests coming in its path.

It works in the way an elevator works, elevator moves in a direction completely till the last
floor of that direction and then turns back.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head movements
in cylinders using SCAN scheduling.

Number of Cylinders = 40 + 14 + 65 + 13 + 20 + 24 + 11 + 4 + 46 = 237


C-SCAN algorithm
In C-SCAN algorithm, the arm of the disk moves in a particular direction servicing requests
until it reaches the last cylinder, then it jumps to the last cylinder of the opposite direction
without servicing any request then it turns back and start moving in that direction servicing the
remaining requests.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head movements
in cylinders using C-SCAN scheduling.

No. of cylinders crossed = 40 + 14 + 199 + 16 + 46 + 4 + 11 + 24 + 20 + 13 = 387


Look Scheduling
It is like SCAN scheduling Algorithm to some extant except the difference that, in this
scheduling algorithm, the arm of the disk stops moving inwards (or outwards) when no more
request in that direction exists. This algorithm tries to overcome the overhead of SCAN
algorithm which forces disk arm to move in one direction till the end regardless of knowing if
any request exists in the direction or not.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head movements
in cylinders using LOOK scheduling.

Number of cylinders crossed = 40 + 51 + 13 + +20 + 24 + 11 + 4 + 46 = 209


C Look Scheduling
C Look Algorithm is similar to C-SCAN algorithm to some extent. In this algorithm, the arm
of the disk moves outwards servicing requests until it reaches the highest request cylinder, then
it jumps to the lowest request cylinder without servicing any request then it again start moving
outwards servicing the remaining requests.

It is different from C SCAN algorithm in the sense that, C SCAN force the disk arm to move
till the last cylinder regardless of knowing whether any request is to be serviced on that cylinder
or not.

Example
Consider the following disk request sequence for a disk with 100 tracks

98, 137, 122, 183, 14, 133, 65, 78

Head pointer starting at 54 and moving in left direction. Find the number of head movements
in cylinders using C LOOK scheduling.

Number of cylinders crossed = 11 + 13 + 20 + 24 + 11 + 4 + 46 + 169 = 298


Numerical on SSTF and SCAN
Question:

Suppose the following disk request sequence (track numbers) for a disk with 100 tracks is
given: 45, 20, 90, 10, 50, 60, 80 and 70. Assume that the initial position of the R/W head is on
track 50. The additional distance that will be traversed by the R/W head when the Shortest Seek
Time First (SSTF) algorithm is used compared to the SCAN (Elevator) algorithm (assuming
that SCAN algorithm moves towards 100 when it starts execution) is _________ tracks

(A) 5
(B) 9
(C) 10
(D) 11

Using SSTF Algorithm


Number of track are 100.

Initial Position of R/W head is 50.

The requests are: 45, 20, 90, 10, 50, 60, 80 and 70

Number of crossed cylinders = 5 + 15 + 10 + 10 + 10 + 70 + 10 = 130


Using SCAN Algorithm

Number of cylinders crosses = 0 + 10 + 10 + 10 + 10 + 10 + 55 + 25 + 10 = 140

Therefore the answer is (C). The SCAN algorithm travels for 10 additional tracks.
Numerical on Disk Scheduling Algorithms
Q. Consider a disk with 200 tracks and the queue has random
requests from different processes in the order:
55, 58, 39, 18, 90, 160, 150, 38, 184

Initially arm is at 100. Find the Average Seek length using FIFO, SSTF, SCAN and C-SCAN
algorithm.

Solution :

Common questions

Powered by AI

Fairness in disk scheduling algorithms ensures each request gets a reasonable chance to be processed without undue delays, which is crucial in multi-user or multi-process environments to maintain system responsiveness and overall user satisfaction. Minimal head movement is integral to optimizing disk performance since reducing the physical movement of disk components decreases access times and improves throughput. Balancing these objectives influences algorithm choice; for instance, FCFS is fair but inefficient in minimizing head movement, SSTF minimizes movement but risks starvation, and SCAN provides a balanced approach with predictable performance. Operating systems often choose algorithms based on workload requirements, seeking to optimize these factors' trade-offs while maintaining service guarantees and system efficiency .

Using the SSTF algorithm in a system with high disk I/O activity can swiftly minimize the immediate seek time by addressing closer requests first. This optimizes performance on a per-request basis and can lead to improved short-term throughput. However, it poses significant risks of starvation for requests that aren't nearby, particularly in busy systems where closer requests continuously arrive, effectively blocking distant requests from being serviced. This can create performance bottlenecks. Conversely, SCAN reduces starvation risk by systematically serving requests in one direction, providing a more balanced throughput with consistent head movement patterns. While not as quick in minimizing individual seek times, SCAN helps ensure fairness, stability, and overall reliability in high-demand environments .

SSTF (Shortest Seek Time First) selects the disk I/O request closest to the current head position to minimize seek time. However, this can lead to starvation, as requests far from the current head position might be neglected if closer requests keep arriving. Despite potentially reducing seek time, frequent direction changes may slow down the algorithm's execution. On the other hand, the SCAN algorithm reduces starvation risk by moving the disk arm to the end of the disk and then reversing direction like an elevator. This consistent direction reduces inefficient head movements and generally provides a more predictable performance. Although SCAN does not always yield the shortest seek time, its systematic approach lessens starvation at the cost of possible extra movement at the disk's ends .

The evolution from FCFS to sophisticated algorithms like LOOK and C-LOOK highlights a strategic balance between optimizing seek time and ensuring fair access. FCFS guarantees fairness but often results in inefficient head movement. Advanced methods like LOOK and C-LOOK were developed to address this inefficiency by minimizing unnecessary seek time through directional limits and reducing rotational latency. These algorithms enable more intelligent head movements, enhancing overall system performance while preventing starvation through structured request processing. This progression in algorithm development reflects a nuanced trade-off approach, aiming to meet the dual goals of operational efficiency and equitable access in diverse workload conditions .

The proliferation of disk scheduling algorithms such as FCFS, SSTF, SCAN, C-SCAN, LOOK, and C-LOOK reflects the continuous evolution of disk scheduling to address limitations and adapt to varying needs. As different algorithms offer unique strengths like fairness, seek-time minimization, and reduced starvation, this diversity demonstrates a commitment to optimizing system performance across different contexts and workloads. This adaptability suggests that disk scheduling systems must be flexible to incorporate advancements, accommodate hardware innovations, and adjust to diverse operational demands, ensuring sustained improvement and performance alignment with technological progress .

Disk access time comprises three main factors: seek time, rotational latency, and transfer time. Seek time is the period needed to position the disk arm to the desired track; it heavily influences the efficiency of scheduling algorithms, as minimizing seek times can enhance throughput. Rotational latency follows, representing the time for the required disk sector to rotate to the position for read/write operations. Both seek time and rotational latency together significantly impact the performance of algorithms since improvements in these can reduce delays. Finally, transfer time is the duration to actually read or write data, which contributes to total access time but is less variable than the other factors. In disk scheduling algorithms, optimizing these times, especially seek time through strategic request ordering, directly improves efficiency and response time .

C-LOOK scheduling is advantageous because it restricts head movement solely to the requested tracks, avoiding travel to the disk's physical boundaries unless necessary. This approach reduces unnecessary seek time and limits the head's wear and tear by avoiding non-essential movements. By only moving between the actual highest and lowest track requests, C-LOOK minimizes access time per operation, enabling improved average throughput compared to algorithms that extend movement to disk boundaries, such as C-SCAN, which involves additional rotational latency and potential idle head activity at non-requested locations .

C-SCAN (Circular SCAN) and C-LOOK (Circular LOOK) algorithms both provide advantages by treating the disk as a circular queue, but they differ in handling movement at disk ends. C-SCAN moves the head to the end of the disk each time before reversing direction, then jumps back to the beginning to continue. C-LOOK, however, only moves between the highest and lowest request track; it doesn't travel to the physical end unless necessary, lessening unnecessary movements. This difference means C-LOOK reduces overhead associated with accessing unused end tracks, optimizing head movements by limiting them to actual data positions. Therefore, C-LOOK is generally more efficient in accessing data, whereas C-SCAN ensures more uniform wait times but at slightly higher movement costs .

The choice of initial direction for disk head movement in the SCAN algorithm significantly affects performance by determining the immediate distribution of pending requests across available directions. If the initial direction aligns with more pending requests, it can reduce wait times for multiple processes at once and enhance throughput, leading to efficient resource utilization. Conversely, choosing a direction with fewer requests can lead to more frequent changes in direction and increased idle time, reducing effective throughput. Thus, effectively choosing the operation's initial direction based on real-time request patterns can optimize seek time and resource allocation, demonstrating the algorithm's sensitivity to starting conditions .

The FCFS (First-Come, First-Served) disk scheduling algorithm processes I/O requests in the order they arrive. Its primary disadvantage is that it does not minimize seek time since requests could require significant and inefficient head movement across the disk platter. This inefficiency can lead to longer wait times and increased response times for tasks, significantly affecting throughput and overall system performance, especially when varied processes generate I/O requests. The lack of optimal seek time particularly impacts scenarios with frequent requests and can lead to suboptimal performance in environments where reducing latency is critical .

You might also like