DISK SCHEDULING

10/12/2002

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:

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.