Disk Scheduling Algorithms are techniques for ordering multiple disk requests in order to optimize disk responses. They are not very relevant to simple PCs, but are used in servers. The algorithms vary from First Come First Served -- i.e. no algorithm at all -- to elaborate prioritized mechanisms that try to balance the cost of each access against the need to provide data to applications in a timely fashion.
The underlying issue is that track seeks are time consuming and the amount of time consumed depends on the number of tracks moved. Thus, if disk requests are outstanding for data on cylinders 0, 1, and 800, it is preferable to access it in the order 0,1,800 or 800, 1, 0 (total motion 800 tracks) rather than 0,800,1 (total head motion 1601 tracks). This is harder than it looks. Two concerns must be balanced -- maximizing throughput, and achieving some degree of fairness. First Come First Served is inefficient, but fair. All requests experience the same delays. Other algorithms may yield greater throughput, but favor servicing some areas of the disk over servicing others. Requests to access remote areas of the disk may be delayed for very long times if an efficient, but unfair, algorithm such as minimum seek distance is used.
Some common algorithms include:
- First Come First Served -- inefficient but fair. All requests are delayed equally.
- Shortest Seek Time First -- Maximizes throughput. But under high load, requests with high seek times may be rarely or never serviced.
- SCAN -- Sweeps the heads across the disk and back servicing the first active request encountered. Efficient, but favors repeated operations in mid-disk over repeated operations near the edges.
- Circular SCAN (C-SCAN) -- Like SCAN, but requests are serviced in only one direction. Efficiency lower than SCAN, but the mid disk preference is eliminated.
- LOOK. Like SCAN but reverses direction when there are no further request to be serviced in the current direction rather than at the limit of the disk.
- Circular LOOK. Like LOOK, but honors requests in one direction preferentially, and when forced to move in the non-preferred direction, goes to the most distant track rather than the closest.
Some OSes depend on task scheduling rather than (or as well as) disk scheduling to achieve fairness. They may attempt to increase the priority of tasks whose disk requests are not being serviced or decrease the priority of tasks whose requests are being serviced preferentially.
Return To Index
Copyright 1994-2002 by Donald Kenney.