Disk Scheduling Algorithms

Theory

Disk scheduling is done by operating systems to schedule I/O requests arriving for the disk. Disk scheduling is also known as I/O scheduling.

Disk scheduling is important because:

• Two or more request may be far from each other so can result in greater disk arm movement.
• Multiple I/O requests may arrive by different processes and only one I/O request can be served at a time by the disk controller. Thus other I/O requests need to wait in the waiting queue and need to be scheduled.
• Hard drives are one of the slowest parts of the computer system and thus need to be accessed in an efficient manner.

There are many Disk Scheduling Algorithms but before discussing them let’s have a quick look at some of the important terms:

• Seek Time : It is the time taken to locate the disk arm to a specified track where the data is to be read or write. So the disk scheduling algorithm that gives minimum average seek time is better.
• Rotational Latency: Rotational Latency is the time taken by the desired sector of disk to rotate into a position so that it can access the read/write heads. So the disk scheduling algorithm that gives minimum rotational latency is better.
• Transfer Time: Transfer time is the time to transfer the data. It depends on the rotating speed of the disk and number of bytes to be transferred.
• Disk Access Time: Disk Access Time is: Disk Access Time = Seek Time + Rotational Latency + Transfer Time
• Disk Response Time: Response Time is the average of time spent by a request waiting to perform its I/O operation. Average Response time is the response time of the all requests. Variance Response Time is measure of how individual request are serviced with respect to average response time. So the disk schedliing algorithm that gives minimum variance response time is better.

Disk Scheduling Algorithms

FCFS

FCFS is the simplest of all the Disk Scheduling Algorithms. In FCFS, the requests are addressed in the order they arrive in the disk queue.

Advantages

• Every request gets a fair chance
• No indefinite postponement

Disadvantages

• Does not try to optimize seek time
• May not provide the best possible service

SCAN

In SCAN algorithm the disk arm moves into a particular direction and services the requests coming in its path and after reaching the end of disk, it reverses its direction and again services the request arriving in its path. So, this algorithm works as an elevator and hence also known as elevator algorithm. As a result, the requests at the midrange are serviced more and those arriving behind the disk arm will have to wait.

Advantages

• High throughput
• Low variance of response time
• Average response time

Disadvantages

• Long waiting time for requests for locations just visited by disk arm

C SCAN

In SCAN algorithm, the disk arm again scans the path that has been scanned, after reversing its direction. So, it may be possible that too many requests are waiting at the other end or there may be zero or few requests pending at the scanned area. These situations are avoided in CSCAN algorithm in which the disk arm instead of reversing its direction goes to the other end of the disk and starts servicing the requests from there. So, the disk arm moves in a circular fashion and this algorithm is also similar to SCAN algorithm and hence it is known as C-SCAN (Circular SCAN).

Advantages

• Provides more uniform wait time compared to SCAN

Disadvantages

• It causes more seek movements as compared to SCAN Algorithm.
• It causes the head to move till the end of the disk even if there are no requests to be serviced.

Shortest Seek Time First (SSTF)

In this algorithm, the shortest seek time is checked from the current position and those requests which have the shortest seek time is served first. In simple words, the closest request from the disk arm is served first.

Advantages

• Average Response Time decreases
• Throughput increases

Disadvantages

• Overhead to calculate seek time in advance
• Can cause Starvation for a request if it has higher seek time as compared to incoming requests
• High variance of response time as SSTF favours only some requests

LOOK

It is similar to the SCAN disk scheduling algorithm except for the difference that the disk arm in spite of going to the end of the disk goes only to the last request to be serviced in front of the head and then reverses its direction from there only. Thus it prevents the extra delay which occurred due to unnecessary traversal to the end of the disk.

Advantages

• It does not causes the head to move till the ends of the disk when there are no requests to be serviced.
• It provides better performance as compared to SCAN Algorithm.
• It does not lead to starvation.

Disadvantages

• Overhead of finding the end requests is present.
• Cylinders which are just visited by Head have to wait for long time.

C-LOOK

This algorithm is also the same as the LOOK algorithm. The only difference between LOOK and C-LOOK is, it moves in a particular direction till the last request is found and serves the requests in its path. Then, it returns in the opposite direction till the last request is found in that direction and doesn't serve the request while returning. Then, again reverses the direction and serves the requests found in the path. It also moves circularly.

Click here for simulation