Disk Scheduling Algorithms
Scenario
Imagine an elevator taking requests from floors 2, 8, 3, and 9. If it just goes in the exact order requested, bouncing up and down, it wastes a massive amount of time and energy. Hard drives face the exact same problem with data requests scattered across a spinning disk.
Mental model
Optimizing an elevator's route to pick up passengers.
Instead of serving data requests exactly in the order they arrive (which causes the disk read head to thrash wildly back and forth), disk scheduling algorithms organize the queue. They figure out the most efficient path for the read/write head to sweep across the disk tracks to minimize mechanical travel time.
Explanation
To understand disk scheduling, you first have to visualize a traditional Hard Disk Drive (HDD). Inside an HDD, data is stored on circular tracks, and a mechanical arm moves a read/write head back and forth across these tracks to access the data. The time it takes for this arm to move from its current track to the requested track is called 'seek time'. Because the arm is a physical moving part, seek time is the absolute slowest operation in computing. The overarching goal of disk scheduling algorithms is to reorganize the queue of I/O requests to minimize total head movement.
The simplest approach is First-Come, First-Served (FCFS). Exactly as the name implies, the disk serves requests in the exact order they arrive in the queue. While perfectly fair, it is wildly inefficient. If requests constantly bounce between the inner tracks and the outer tracks, the disk head spends the majority of its time just traveling back and forth, dragging down the performance of the entire system.
To improve this, operating systems use Shortest Seek Time First (SSTF). In SSTF, the disk head always moves to the closest unfulfilled request next, regardless of when that request arrived. While this drastically reduces the average travel time and increases throughput, it introduces a critical flaw: starvation. If new requests continuously arrive for nearby tracks, requests located at the far edges of the disk might be ignored indefinitely.
To solve the starvation problem while maintaining efficiency, the SCAN algorithm (also known as the Elevator algorithm) is used. The disk head moves continuously in one direction—say, from track 0 towards track 199—fulfilling all requests along its path. When it hits the very edge of the disk, it reverses direction and fulfills requests on the way back down. Like a real elevator, it sweeps back and forth, guaranteeing that every request is eventually served without forcing the head to make erratic jumps.
A popular variation of this is C-SCAN (Circular SCAN). C-SCAN operates similarly by sweeping in one direction and fulfilling requests. However, when it reaches the edge, it does not read on the return trip. Instead, it quickly snaps back to the starting edge without servicing any requests, and begins another sweep in the original direction. This provides a much more uniform wait time, because regular SCAN naturally favors tracks in the middle of the disk (which get crossed twice as often) compared to tracks on the edges.
Key points
- FCFS (First-Come, First-Served): Serves requests in arrival order. Fair, but suffers from massive seek times if requests are scattered.
- SSTF (Shortest Seek Time First): Serves the closest request next. Excellent throughput, but edge requests can suffer from starvation.
- SCAN (Elevator Algorithm): Head sweeps back and forth across the disk, fulfilling requests in its path. Prevents starvation.
- C-SCAN (Circular SCAN): Head sweeps in one direction, snaps back to the start, and sweeps again. Provides uniform wait times.
- LOOK and C-LOOK: Smarter versions of SCAN and C-SCAN that reverse direction immediately after the last request, instead of traveling all the way to the absolute edge of the disk.
Common mistakes
- Confusing SCAN and C-SCAN: SCAN reads data in both directions as it sweeps back and forth. C-SCAN only reads in one direction, snapping back to the start like a typewriter carriage, ensuring edge tracks don't have to wait longer than middle tracks.
- Assuming SSTF is the best choice: Because it minimizes immediate head movement, SSTF looks optimal on paper. However, the risk of starvation makes it unsuitable for heavily loaded systems where unfairness cannot be tolerated.
Glossary
- Hard Disk Drive
- A traditional storage device that saves data magnetically on spinning metal platters, read by a tiny mechanical arm that moves back and forth.
- seek time
- The frustratingly slow fraction of a second it takes for the mechanical arm in a hard drive to physically move to the exact spot where your data is stored.
- circular tracks
- The microscopic concentric rings on a hard drive's surface where the actual data bits are written and organized.
Recall questions
- What is the primary physical constraint that disk scheduling algorithms attempt to minimize?
- Why is SSTF (Shortest Seek Time First) generally not used in practice despite minimizing average seek time?
- How does C-SCAN improve upon the traditional SCAN algorithm?
Questions & answers
Given a sequence of disk requests, calculate the total head movement required for FCFS versus SSTF.
Map the starting head position. For FCFS, sum the absolute differences between consecutive requests. For SSTF, repeatedly find and sum the absolute difference to the closest remaining request.
Approach: This requires walking through the queue manually. Remember that SSTF mutates the remaining list of requests as you jump to the nearest one.
Identify which disk scheduling algorithm was used given a starting position and an ordered list of serviced tracks.
Check the pattern. If it jumps randomly, it's FCFS. If it goes monotonically up to the edge and down, it's SCAN. If it goes up, drops sharply to 0, and goes up again, it's C-SCAN.
Approach: Look for the turnaround points. If the head turns around before the physical edge of the disk, it's LOOK or C-LOOK.