Disk Scheduling Algorithms

When a computer runs multiple programs, its storage drive receives dozens of input/output (I/O) requests every second. If the drive's read/write head had to jump randomly across the disk platter to fulfill these requests, system performance would grind to a halt. Disk scheduling algorithms are the intelligent traffic controllers that decide the order of these requests, optimizing physical movement to minimize wait time and maximize overall system throughput. Understanding these algorithms is essential for grasping how operating systems manage one of their slowest—yet most critical—components: the hard disk drive.

The Core Problem: Seek Time

The primary performance bottleneck in traditional Hard Disk Drives (HDDs) is seek time. This is the time required for the disk arm to move the read/write head to the cylinder (track) containing the desired sector. The physical movement is mechanical and slow compared to CPU or memory speeds. The total seek time for a set of requests is directly related to the total distance the disk arm must travel. Therefore, the goal of any disk scheduling algorithm is to minimize this total seek distance. We measure distance in terms of cylinders or tracks. For example, moving from cylinder 15 to cylinder 45 involves a seek distance of $D=|45-15|=30$.

First-Come, First-Served (FCFS)

The First-Come, First-Served (FCFS) algorithm is the simplest approach: it services I/O requests in the exact order they arrive in the queue. It is inherently fair and easy to implement, as it requires no complex logic to reorder requests.

Example: Assume the disk arm starts at cylinder 50, and the request queue is: [98, 183, 37, 122, 14, 124, 65, 67]. The arm movement would be: 50 → 98 (distance 48) → 183 (85) → 37 (146) → 122 (85) → 14 (108) → 124 (110) → 65 (59) → 67 (2). Total seek distance = 48 + 85 + 146 + 85 + 108 + 110 + 59 + 2 = 643 cylinders.

While fair, FCFS often results in inefficient, wide-ranging arm movement, leading to high average seek times. It makes no attempt to optimize the schedule.

Shortest Seek Time First (SSTF)

The Shortest Seek Time First (SSTF) algorithm prioritizes the pending request that is closest to the disk arm's current position. This is a greedy algorithm that selects the optimal choice at each step with the hope of finding a global optimum.

Example: Using the same starting point (50) and queue [98, 183, 37, 122, 14, 124, 65, 67]. From 50, the closest request is 65 (distance 15). From 65, the closest is 67 (2). From 67, the closest is 37 (30? No—98 is 31, 122 is 55, 124 is 57, 14 is 53, but 37 is 30). The sequence becomes: 50 → 65 (15) → 67 (2) → 37 (30) → 14 (23) → 98 (84) → 122 (24) → 124 (2) → 183 (59). Total seek distance = 15 + 2 + 30 + 23 + 84 + 24 + 2 + 59 = 239 cylinders.

SSTF significantly reduces total and average seek time compared to FCFS. However, it can lead to starvation. If a steady stream of requests arrives for cylinders near the arm's current location, requests for distant cylinders may be postponed indefinitely.

Elevator Algorithms: SCAN and C-SCAN

To address SSTF's fairness issue while maintaining efficiency, SCAN and C-SCAN algorithms were developed. They mimic an elevator's movement.

The SCAN Algorithm

Often called the elevator algorithm, SCAN moves the disk arm in one direction, servicing all requests in its path until it reaches the highest (or lowest) cylinder. It then reverses direction and services requests along the return path.

Example: Start at 50, moving towards higher cylinder numbers (right). Queue: [98, 183, 37, 122, 14, 124, 65, 67]. While moving right from 50, it services requests at 65, 67, 98, 122, 124, and 183. At the end (cylinder 199, assuming that's the max), it reverses. On the leftward sweep, it services 37 and then 14. Sequence: 50 → 65 (15) → 67 (2) → 98 (31) → 122 (24) → 124 (2) → 183 (59) → 37 (146) → 14 (23). Total seek distance = 15+2+31+24+2+59+146+23 = 302 cylinders.

SCAN provides more uniform wait times than SSTF and avoids starvation. A request just passed will have to wait for a full sweep in the opposite direction.

The C-SCAN Algorithm

Circular SCAN (C-SCAN) treats the cylinders as a circular list. The arm moves in one direction only, servicing requests. When it reaches the end, it immediately "jumps" back to the opposite end without servicing requests, and begins moving again in the same direction. This creates a more uniform service distribution than SCAN, as the maximum wait time is bounded by the time for one full pass plus the jump back.

For our example, moving right from 50: 50 → 65 → 67 → 98 → 122 → 124 → 183. Jump to start (cylinder 0), then continue right: 0 → 14 → 37. Total distance includes the jump from 183 to 0.

The LOOK Algorithm

Both SCAN and C-SCAN move the arm all the way to the physical end of the disk. The LOOK algorithm (and its variant, C-LOOK) improves efficiency by looking ahead in the queue. The arm moves in a direction only until there are no more pending requests ahead in that direction. It then reverses (LOOK) or jumps (C-LOOK) to the furthest waiting request in the opposite direction.

In our example, a LOOK algorithm moving right from 50 would service requests up to 183, see no requests beyond that, reverse, and service 37 and 14. This eliminates the unnecessary travel to the physical end cylinder (199), reducing total seek distance.

Comparing Algorithm Performance

When evaluating algorithms, we calculate the average seek distance by dividing the total seek distance by the number of requests. For our ongoing example:

• FCFS: 643 / 8 = 80.4
• SSTF: 239 / 8 = 29.9
• SCAN: 302 / 8 = 37.8

These numbers illustrate the typical performance hierarchy: SSTF often provides the lowest average seek time for a given queue, followed by LOOK/SCAN variants, with FCFS being the least efficient. However, the choice involves a trade-off between throughput (seeks per second) and fairness (variance in response time). SSTF maximizes throughput but risks starvation. SCAN and C-SCAN offer a better fairness guarantee at a potential minor cost to throughput.

The Modern Context: Solid-State Drives (SSDs)

The fundamental assumptions of disk scheduling change dramatically with Solid-State Drives (SSDs). SSDs have no moving parts; data is accessed electronically from flash memory cells. Therefore, there is no "seek time" in the mechanical sense. A request to read sector 1000 takes no longer than a request to read sector 10,000.

This negates the primary purpose of traditional seek-optimizing schedulers. For SSDs, the operating system's I/O scheduler focuses on different goals: managing wear leveling (distributing writes evenly across memory cells), handling the unique latencies of erase-before-write operations, and optimizing for parallelism across multiple internal flash channels. While an OS might still use a form of SSTF or C-LOOK for historical or hybrid-system compatibility, the performance gains are negligible compared to HDDs. The study of classical disk scheduling remains vital for understanding system performance history, managing legacy HDD systems, and optimizing for hybrid storage environments.

Common Pitfalls

1. Confusing Seek Time with Rotational Latency: Seek time is only one component of total I/O service time. Rotational latency—the time for the desired sector to rotate under the head—is also critical. Advanced algorithms sometimes consider both, but introductory scheduling focuses solely on seek optimization.
2. Overlooking Starvation in SSTF: It's easy to see SSTF's efficiency and deem it the "best." The critical drawback is its potential for indefinite postponement (starvation) of distant requests, which is unacceptable in multi-user systems where fairness is required.
3. Misapplying SCAN/C-SCAN End Behavior: A common error is forgetting that SCAN services requests all the way to the end cylinder before reversing, while LOOK reverses as soon as there are no more requests ahead. Similarly, C-SCAN's immediate jump back to the start (without servicing) is often mistaken.
4. Applying HDD Algorithms to SSDs: Assuming that optimizing seek order will significantly improve SSD performance is a fundamental misconception. It leads to wasted development effort. The correct approach is to understand the SSD's internal architecture and queue commands to exploit its internal parallelism.

Summary

• Disk scheduling algorithms order pending I/O requests to minimize the mechanical seek time of an HDD's read/write head, which is the dominant factor in I/O performance.
• FCFS is simple and fair but inefficient. SSTF minimizes average seek time but can cause starvation of distant requests. SCAN and C-SCAN (elevator algorithms) offer a better balance of efficiency and fairness by sweeping back and forth across the disk.
• The LOOK and C-LOOK algorithms are practical optimizations of SCAN/C-SCAN that reverse direction when no more requests lie ahead, avoiding unnecessary travel to the physical disk end.
• The choice of algorithm involves a direct trade-off between total throughput and fairness; no single algorithm is optimal for all workloads.
• The rise of SSDs, which have no mechanical seek time, fundamentally changes the importance of these algorithms. OS schedulers for SSDs must optimize for wear leveling, write amplification, and internal chip parallelism instead of seek distance.