Disk Scheduling Algorithms with Examples

Relatively speaking, retrieving data from hard disk drivers is always slow compared to CPU and memory access due to the mechanical nature of the magnetic disk. Disk arm movement is very expensive operation therefore operating systems use disk scheduling algorithms to reduce seek time. Below you can find a summary of some of the well known disk scheduling algorithms. The algorithm receives a queue of request positions (track numbers) and the current head position. The output of the algorithm is the order in which the requests are serviced.

First Come First Serve (FCFS)

1. 1. Requests are serviced in the order in which they arrive
   2. The algorithm is easy to implement
   3. Bad algorithm as it may involve lots of unnecessary seek distance

Here is an example assuming we have 200 cylinders:

Shortest Seek Time First (SSTF)

1. 1. Service request with the shortest seek time from the current head position
   2. May starve some requests
   3. Good algorithm for a small list of requests

Here is an example:

Scan or Elevator Algorithm

1. 1. Disk arm starts at one end of the disk and moves towards the other end
   2. It services the requests as it moves then reverses the direction when it hits the other end
   3. Scan algorithms are good for heavy loads and more fair

Here is an example:

C-Scan

1. 1. Similar to scan algorithm but the head returns to cylinder 0 when it reaches the end of the disk
   2. Treats the cylinder list as a circular list that wraps around the disk
   3. Waiting time is more uniform for cylinders near the edge of the disk

Here is an example:

C-Look

1. 1. Similar to C-Scan but the head only travels as far as the last request in each direction

Here is an example:

Summary

Here is a tabular summary of what we have mentioned:

Disk scheduling algorithms PDF

You can find this article in PDF format here

Please use the comments section below for questions, corrections or feedback. Thanks for reading.