Disk Scheduling Algorithms

In a multi-programming, when the disk controller is busy servicing a request from a process, any new requests from other process are placed in a queue. When the disk controller finishes the current request it has to decide which request from the queue should be processed next. How does the OS make this choice? It can choose one of the many disk scheduling algorithms to make the decision. Some of the common disk scheduling algorithms are:

First Come First Serve (FCFS)

In FCFS the disk controller chooses the next request in the queue to service.

e.g. On a disk with 200 cylinders (0-199), find the number of cylinders the disk arm must move considering a disk queue with requests for I/O to blocks on cylinders

   98, 183, 37, 122, 14, 124, 65, 67

  Assume the current Head pointer (position) is 53rd cylinder

Ans:

The order of request serviced will be:
53 -> 98 -> 183 -> 37 -> 122 -> 14 -> 124 -> 65 -> 67
Thus, the total head movement is |98-53|+|183-98|+|37-183|+|122-37|+|14-122|+124-14|+|65-124|+|67-65| = 45+85+146+85+108+110+59+2=640

Shortest Seek Time First (SSTF)

SSTF selects the request with the least seek time from the current head position. SSTF chooses the pending request closest to the current head position.

e.g. for the same question (as in FCFS), the order of request serviced using SSTF will be:
53 -> 65 -> 67 -> 37 -> 14 -> 98 -> 122 -> 124 -> 183
Thus, the total head movement is |65-53|+|67-65|+|37-67|+|14-37|+|98-14|+|122-98|+|124-122|+|183-124| = 12+2+30+23+84+24+2+59 = 236

SCAN

The disk arm starts at one end of the disk and moves towards other end, servicing requests as it reaches each cylinder. At the other end, the direction of head movement is reversed, and servicing continues.

e.g. for the same question (as in FCFS), the order of request serviced using SCAN will be:
53 -> 37 -> 14 -> 0 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183
Thus, the total head movement is |37-53|+|14-37|+|0-14|+|65-0|+|67-65|+|98-67|+|122-98|+|124-122|+|183-124| = 16+23+14+65+2+31+24+2+59=236

LOOK

Same as SCAN but with the difference that the arm goes only as far as the final request in each direction. Then, it reverses direction immediately without going all the way to the end of the disk.

e.g. for the same question (as in FCFS), the order of request serviced using LOOK will be:
53 -> 37 -> 14 -> 65 -> 67 -> 98 -> 122 -> 124 -> 183
Thus, the total head movement is |37-53|+|14-37|+|65-14|+|67-65|+|98-67|+|122-98|+|124-122|+|183-124| = 16+23+51+2+31+24+2+59=208

PPT

The above discussion is summarized in the form of a PPT with animations below.
Note: Click within the slide area for animations. Clicking on the “next” slide button will not display any animation

Previous                            Next
Disk Management            Inter Process Communication