Disk Scheduling

Explore how operating systems manage disk I/O requests through scheduling algorithms. Learn about shortest seek time first, elevator (SCAN) methods, and how disk rotation impacts request timing. Understand methods to reduce delays and starvation, improving storage performance.

We'll cover the following...

- SSTF: shortest seek time first
- Elevator (a.k.a. SCAN or C-SCAN)
- SPTF: shortest positioning time first

Because of the high cost of I/O, the OS has historically played a role in deciding the order of I/Os issued to the disk. More specifically, given a set of I/O requests, the disk scheduler examines the requests and decides which one to schedule next1- “Disk Scheduling Revisited” by Margo Seltzer, Peter Chen, John Ousterhout. USENIX 1990. A paper that talks about how rotation matters too in the world of disk scheduling. 2- “Disk Scheduling Algorithms Based On Rotational Position” by D. Jacobson, J. Wilkes. Technical Report HPL-CSP-91-7rev1, Hewlett-Packard, February 1991. A more modern take on disk scheduling. It remains a technical report (and not a published paper) because the authors were scooped by Seltzer et al..

Unlike job scheduling, where the length of each job is usually unknown, with disk scheduling, we can make a good guess at how long a “job”, i.e., disk request, will take. By estimating the seek and possible rotational delay of a request, the disk scheduler can know how long each request will take, and thus (greedily) pick the one that will take the least time to service first. Thus, the disk scheduler will try to follow the principle of SJF (shortest job first) in its operation.

SSTF: shortest seek time first

One early disk scheduling approach is known as shortest-seek-time-first (SSTF) (also called shortest-seek-first or SSF). SSTF orders the queue of I/O requests by track and picks requests on the nearest track to complete first. For example, assuming the current position of the head ...