How the Disk Scheduler Works
When multiple processes need to read or write data from a hard disk, the requests pile up in a queue. The disk scheduler decides the order in which these requests are serviced. A good scheduling algorithm can dramatically improve disk throughput and reduce wait times.
Hard disk drives (HDDs) have a physical read/write head that must move across the disk surface to reach different tracks. This movement takes time — known as seek time — and it's the primary bottleneck in disk performance. The disk scheduler's main job is to minimize seek time.
First-Come, First-Served (FCFS)
The simplest approach: service requests in the order they arrive. No optimization, no priority — just FIFO.
The problem: If requests are scattered across the disk, the head bounces back and forth wildly. Imagine a librarian who runs to the far left shelf, then the far right, then the middle, then the far left again — exhausting and inefficient.
FCFS is fair but performs poorly when the disk head has to make large jumps between consecutive requests.
Shortest Seek Time First (SSTF)
SSTF selects the request that requires the least head movement from the current position. It's like picking the nearest book on the shelf rather than running to the far end of the library.
The advantage: Dramatically reduces total seek time compared to FCFS.
The problem: Starvation. Requests far from the current head position might never be serviced if new requests keep arriving closer to the head. A request at the far end of the disk could wait indefinitely.
SCAN (Elevator Algorithm)
SCAN works like an elevator. The disk head moves in one direction, servicing requests along the way. When it reaches the end of the disk (or the last request in that direction), it reverses direction and services requests on the way back.
This ensures that all requests are eventually serviced — no starvation. The head sweeps back and forth across the disk, handling everything in its path.
Variation — C-SCAN: Instead of reversing, the head jumps back to the beginning and starts sweeping in the same direction again. This provides more uniform wait times because requests near the edges don't have to wait for the head to reverse and come back.
LOOK and C-LOOK
LOOK is an optimization of SCAN. Instead of going all the way to the disk's physical end, the head only goes as far as the last request in each direction. It "looks" ahead to see if there are any more requests before changing direction.
C-LOOK is the same optimization applied to C-SCAN — jump back to the first request instead of the physical beginning of the disk.
These algorithms are more efficient in practice because most disks don't have requests at their extreme edges.
SSD Scheduling: A Different World
It's worth noting that solid-state drives (SSDs) don't have moving parts — there's no disk head to move. Seek time is essentially zero. This makes traditional disk scheduling algorithms less relevant for SSDs.
SSD schedulers focus on different concerns: wear leveling (distributing writes evenly across cells to extend lifespan), garbage collection (reclaiming blocks with stale data), and command queuing (processing multiple I/O requests efficiently).
As HDDs become less common in consumer devices, the focus of I/O scheduling is shifting from seek time optimization to flash-specific concerns.