Disk Scheduling Algorithms

In computer operating systems, the disk is a critical storage device, and its read/write speed directly impacts the overall system performance. Since the heads of Hard Disk Drives (HDDs) must move across the platters to access data, the latency caused by this physical movement is known as "seek time." When multiple processes simultaneously request different disk blocks, frequent random access causes the head to spend excessive time moving back and forth across the platters, resulting in slower system response. To address this issue, operating systems introduced disk scheduling algorithms designed to optimize the head's movement path, reduce average seek time, and thereby improve I/O efficiency. Common scheduling algorithms include FCFS, SSTF, SCAN, C-SCAN, and LOOK, each with its own advantages and disadvantages, making them suitable for different scenarios.

FCFS Algorithm and Its Limitations

The first algorithm introduced is First-Come, First-Served (FCFS). The core logic of this algorithm is straightforward: process requests in the order they arrive at the system. Assuming the disk head is currently located at cylinder 20, and the subsequent I/O request sequence is {8, 15, 24, 30, 6, 9, 17}, FCFS will access them strictly in this order: 8 -> 15 -> 24 -> 30 -> 6 -> 9 -> 17.

The advantage of this algorithm is fairness; every request is treated equally without any request being disadvantaged due to others being prioritized. However, its fatal flaw lies in its inability to predict future requests and its tendency to cause "starvation." If a request's cylinder number is far from the current head position while other requests are clustered elsewhere, the head must perform long-distance movement, causing the wait time for subsequent requests to increase dramatically. Furthermore, for systems with frequent random access, FCFS is often not the optimal solution because it does not consider the principle of spatial locality, implying that adjacent requests typically have a higher probability of access.

SSTF Algorithm and Starvation Issues

To address the inefficiency of FCFS, the Shortest Seek Time First (SSTF) algorithm was developed. The decision rule for SSTF is: always select the request closest to the current head position for processing. Using the request sequence {8, 15, 24, 30, 6, 9, 17} as an example, if the head starts at cylinder 20, it will first access the nearest one (15), followed by 9, then 6, then 8, then 17, and finally the farther ones (24 and 30).

SSTF significantly reduces average seek time because it always selects the "nearest" target, minimizing the distance the head moves. However, it suffers from a severe defect as well—the starvation problem. If there is a request sequence on the disk where most requests are clustered on one side (e.g., near cylinder 10) and another request is located on the opposite side (e.g., cylinder 98), and that distant request arrives last, the head might continuously move toward the near end, causing the distant request to never be serviced. This unfairness makes SSTF difficult to use in isolation in actual production environments; it often requires combination with other strategies or limiting its maximum wait time.

SCAN and C-SCAN Algorithms

To overcome starvation issues and improve throughput, scan-based scheduling algorithms (SCAN) and circular-scan (C-SCAN) have become the mainstream choices.

The SCAN algorithm, also known as the Elevator Algorithm, simulates the logic of an elevator going up and down floors. While moving from one end to the other, the head sequentially accesses all requests along the path. Upon reaching an end, it reverses direction immediately without waiting for new requests in the same direction. For example, if the head starts at cylinder 20 and moves toward cylinder 1, it will sequentially access 8, 6, 9 (assuming these are on the path), reach 1, reverse, and then access 15, 17, 24, 30.

The C-SCAN algorithm is more aggressive; it stipulates that the head moves in only one direction. When reaching one end of the disk, instead of immediately returning, it jumps directly to the other end to restart the scan. This forms a loop, ensuring every request can be accessed within a finite time and completely eliminating starvation. Although the total seek time for C-SCAN is typically less than SCAN (due to avoiding redundant coverage of certain areas), its jump-based design may cause frequent large movements between ends, potentially increasing total movement distance under specific load conditions.

Additionally, the LOOK algorithm is an improved version of SCAN. Unlike SCAN, the LOOK algorithm stops accessing before reaching the disk edge and moves toward the nearest request in that direction until no more requests exist in that direction, at which point it reverses. This reduces unnecessary empty travel and improves efficiency.

Practical Application Recommendations

Selecting the appropriate scheduling algorithm is crucial in actual system design. For most modern operating system kernels (such as Linux's cfq or mq-deadline schedulers), they do not simply copy the above classic algorithms entirely but combine multiple strategies, dynamically adjusting based on load types. For instance, in latency-sensitive scenarios like database servers, more aggressive prefetching strategies might be required; whereas in file servers with high random read/write activity, balanced strategies similar to C-SCAN are preferred.

Understanding the core mechanisms of these algorithms helps developers optimize systems better. By monitoring I/O wait times and disk utilization, one can determine if the current scheduler is operating reasonably. If frequent long-distance seeks or a process unable to get I/O service for an extended period are observed, it may be necessary to adjust scheduling parameters or switch to a more suitable algorithm strategy. In summary, disk scheduling algorithms are a key component of operating system performance optimization; reasonable algorithm selection can significantly enhance system throughput and response speed.