1. The Queue of Requests

When an operating system is running a modern workload, it is rarely serving one file request at a time. The system's virtual memory manager may be swapping pages, a database might be writing transaction logs, and a web browser could be downloading images simultaneously.

As these operations stack up, they form a Request Queue at the storage driver layer.

For a simplified hard disk model, suppose the controller receives a queue of read/write requests targeting specific LBA cylinder tracks:

And the physical read/write head is currently positioned at:

To complete these tasks, the operating system must decide the order in which to visit these locations. This coordination is known as Disk Scheduling.

2. The Physical Structure of a Hard Disk

To understand why the order of serving requests matters, we must look at the physical architecture of a traditional mechanical Hard Disk Drive (HDD):

The device is composed of the following physical units: * Platter: Magnetic circular disk spinning at high speeds (e.g., 7200 RPM). * Spindle: The central shaft that rotates the platters. * Tracks: Concentric logical rings on the platter surface where data is recorded. * Sectors: Segments dividing each track. Each sector holds a fixed amount of data (traditionally 512 bytes or 4 KB). * Read/Write Head: A tiny sensor that floats just above the platter surface, reading magnetic orientations. * Actuator Arm: A mechanical arm that moves the head radially inward or outward to target different tracks.

3. HDD Access Performance

Because of this mechanical design, reading or writing data from a physical track requires mechanical movements that introduce physical delay:

Seek Time The time required for the actuator arm to physically move the read/write head from its current track to the target track.

Rotational Latency The time the head must wait for the platter to spin around until the target sector passes directly underneath the read/write head.

Access Time The total time elapsed from the moment the OS requests a block to the moment it is retrieved. Conceptually:

$$\text{Access Time} \approx \text{Seek Time} + \text{Rotational Latency} + \text{Transfer Time}$$

Mechanical seek time and rotational latency take milliseconds—an eternity compared to CPU registers or memory. If the head must repeatedly jump between distant tracks, the actuator arm spends all its time seeking, causing overall I/O performance to plummet.

4. First-In, First-Out (FCFS)

The simplest scheduling policy is First-Come, First-Served (FCFS):

* Advantage: It is simple to implement and perfectly fair. Requests are served in the exact order they arrive, ensuring zero starvation. * Problem: It completely ignores the head's physical location. The head is forced to sweep wildly back and forth across the platter, resulting in massive cumulative seek distance (640 cylinders for our sequence).

5. Shortest Seek Time First (SSTF)

To minimize seek overhead, Shortest Seek Time First (SSTF) prioritizes proximity:

At each step, the algorithm calculates the distance from the head's current position to all pending requests and moves to the closest one. * Advantage: Considerably reduces total seek distance (cut from 640 to 236 cylinders in our example), boosting throughput. * Problem: Prone to starvation. If the queue constantly receives new requests located near the active middle tracks, distant requests (such as LBA 183) may wait indefinitely.

6. SCAN: The Elevator Algorithm

To combine efficiency with fairness, SCAN sweeps the disk symmetrically:

Like a building elevator, the head moves in one direction (e.g., inward toward track 0), servicing all requests encountered along the way. Upon reaching the edge, it reverses direction and sweeps outward toward the other edge (track 199). * Advantage: Eliminates starvation because the head always completes its sweep to both boundaries, ensuring every sector is eventually reached. * Problem: Uniformity. Sectors near the middle are visited twice as often as those at the extreme edges, making response times uneven.

7. C-SCAN (Circular SCAN)

C-SCAN improves on SCAN by moving in one direction only:

The head services requests while moving in a single direction (e.g., increasing track numbers). Once it reaches the outer edge (199), it jumps straight back to the inner edge (0) without servicing requests on the return run, then starts another sweep. * Advantage: Provides a much more uniform waiting time distribution across all tracks. * Problem: The return sweep is a wasted movement (though on real drives, a full reset sweep is optimized to be extremely fast).

8. EdgeCase: Disk Scheduling Simulator

Use the simulator below to select an algorithm tab and compare how FCFS, SSTF, SCAN, and C-SCAN schedule the same sequence of cylinder requests:

9. Algorithmic Comparison

Below is a summary of the trade-offs involved in each strategy:

10. Physical Cost Differences: HDD vs. SSD/NVMe

The physical characteristics of the underlying media dictate whether these scheduling algorithms are used:

Mechanical Hard Drives (HDDs) These algorithms were designed for HDDs. Because physical seek movement and rotational delays are mechanical actions that take milliseconds, optimizing head sweeps is the most effective way to maximize I/O operations per second (IOPS).

Solid State Drives (SSDs & NVMe) SSDs have no mechanical heads or platters. Blocks are accessed electrically via flash memory gates, meaning there is zero physical seek penalty. Consequently, the traditional mechanical seek-distance minimization problem that motivated algorithms such as SSTF and SCAN largely disappears.

However, storage request scheduling does not disappear completely. Modern solid-state storage stacks still must optimize: * Queueing & Fairness: Ensuring multiple active processes get fair shares of device bandwidth. * Request Merging: Grouping contiguous block requests into larger sequential I/O commands to reduce controller transaction overhead. * Latency & Controller Pipelines: Coordinating writes and reads to leverage the controller's internal device-level parallelism without bottlenecks.

The focus changes from reducing physical arm motion to maximizing throughput in electronic controllers.

11. Important Conceptual Distinction

As you study storage, be careful not to confuse the roles of filesystem allocation and device scheduling:

* File Allocation: Decides which blocks represent a file (e.g., extents, indexed structures, or linked lists). * Disk Scheduling: Decides in what order pending read/write blocks should be sent to the physical device.

12. The Next Question

Disk scheduling can decide which waiting request should be served first.

But storage systems have another problem.

What happens when the system loses power or crashes in the middle of a write?