Disk scheduling algorithms determine the order in which I/O requests from different processes are served by the disk. The primary goal of these algorithms is to minimize seek time—the time the disk head takes to move to the right track—while maximizing throughput and ensuring fairness.
Without scheduling, disk requests would be handled randomly, causing the read/write head to jump inefficiently across the disk. The right algorithm can dramatically reduce average seek time and improve system performance.
Key Terminology
- Seek Time: Time for the disk head to move to the required track.
- Rotational Latency: Time for the disk to rotate to the required sector.
- Transfer Time: Time to actually transfer data once positioned.
- Disk Queue: List of pending I/O requests waiting to be served.
Types of Disk Scheduling Algorithms
| Algorithm | Full Name | How It Works | Seek Pattern | Best For |
|---|---|---|---|---|
| FCFS | First Come First Served | Requests served in arrival order | Random/Wild | Light load, fairness |
| SSTF | Shortest Seek Time First | Serves nearest request first | Local optimization | Low seek time needed |
| SCAN | Elevator Algorithm | Head moves in one direction, serves all requests, then reverses | Sweeping | General purpose |
| C-SCAN | Circular SCAN | Like SCAN but returns to start without serving on way back | One-directional | Uniform wait times |
| LOOK | LOOK Algorithm | Like SCAN but only goes as far as last request | Optimized sweep | Better than SCAN |
| C-LOOK | Circular LOOK | Like C-SCAN but jumps to first request, not disk start | Circular optimal | Best overall balance |
Algorithm Performance Comparison
| Algorithm | Average Seek Time | Fairness | Starvation Risk | Complexity |
|---|---|---|---|---|
| FCFS | High | High | None | Very simple |
| SSTF | Low | Low | Yes (for far requests) | Simple |
| SCAN | Medium | Medium | Low | Moderate |
| C-SCAN | Medium | High | Very low | Moderate |
| LOOK | Low-Medium | Medium | Low | Moderate |
| C-LOOK | Low | High | Very low | Moderate |
Detailed Algorithm Walkthrough
FCFS (First Come First Served): The simplest approach. Each request is served in the order it arrives. Easy to implement and completely fair, but highly inefficient when requests are spread across the disk. Head movement is unpredictable and often excessive.
SSTF (Shortest Seek Time First): Always picks the request closest to the current head position. Reduces seek time significantly but can starve requests far from the head if nearby requests keep arriving.
SCAN (Elevator Algorithm): The head moves in one direction, serves all requests in its path, reaches the end of the disk, then reverses. Like an elevator in a building. Efficient and prevents starvation.
C-SCAN (Circular SCAN): Like SCAN, but when the head reaches the end, it jumps back to the beginning without serving requests on the return trip. This provides more uniform wait times across all requests.
LOOK and C-LOOK: Optimized versions of SCAN and C-SCAN. Instead of going all the way to the disk edge, the head only travels to the farthest pending request before turning or jumping back. Less unnecessary movement.
Which Algorithm Is Used in Real Systems?
Modern operating systems typically use variations of LOOK and C-LOOK. Linux uses the CFQ (Completely Fair Queuing) scheduler for HDDs and the deadline scheduler for SSDs. For SSDs, traditional disk scheduling is largely irrelevant because SSDs have no physical read head, making seek time essentially zero.
- HDDs: LOOK or C-LOOK variants are most common in practice.
- SSDs and NVMe: Scheduling is minimal; NOOP or simple FIFO is used since physical positioning does not apply.
- Databases: May implement their own I/O scheduling optimized for their specific access patterns.
Understanding disk scheduling algorithms is fundamental to operating systems coursework and helps explain why disk-intensive workloads behave differently on HDDs versus SSDs.
