Disk Scheduling Algorithms Overview
While Solid State Drives (SSDs) and RAM operate entirely using electricity, traditional Hard Disk Drives (HDDs) are mechanical beasts. They rely on spinning magnetic platters and moving robotic arms.
Because moving physical parts is millions of times slower than moving electrons, the Operating System must carefully optimize how it interacts with the disk. This optimization is called Disk Scheduling.
Anatomy of a Hard Disk
To understand why disk scheduling is necessary, you have to understand the physical hardware:
- Platter: The circular magnetic disk where data is actually stored. A drive usually has multiple platters stacked together.
- Track: Concentric circles drawn on the platter (like rings on a tree).
- Sector: A track is sliced into small arcs called sectors. This is the smallest physical storage unit, typically holding 512 bytes.
- Read/Write Head: The tiny sensor mounted on an arm that hovers microscopically close to the platter to read or write the magnetic data.
Understanding Disk Delays
When an application requests a file, the hard drive cannot fetch it instantly. The total time required to service the request is the sum of three mechanical delays:
- 1. Seek Time: The time it takes for the mechanical arm to move the read/write head to the correct track.
- 2. Rotational Latency: The time spent waiting for the spinning platter to rotate the correct sector under the head.
- 3. Transfer Time: The time it takes to actually read the bits and send them across the cable to the motherboard.
The Scheduling Problem
Imagine the OS receives a queue of requests to read data from the following tracks: [98, 183, 37, 122, 14, 124, 65, 67].
If the Read/Write head is currently resting at track 53, in what order should the OS process these requests? If it processes them randomly, the mechanical arm will thrash wildly back and forth across the disk, destroying performance and wearing out the hardware. We need a strategy.
The Core Algorithms
Computer scientists have developed several algorithms to solve this problem, each balancing raw efficiency against fairness.
| Algorithm | How It Works | Real-World Analogy |
|---|---|---|
| FCFS (First Come First Serve) | Processes requests in the exact order they arrive. | A delivery driver going back and forth across town randomly based on order timestamps. |
| SSTF (Shortest Seek Time First) | Always picks the request closest to the current head position. | A delivery driver hitting all houses in the immediate neighborhood before driving across town. |
| SCAN (Elevator Algorithm) | Head sweeps continuously from one end of the disk to the other. | An elevator picking up everyone on the way up to the top floor, then picking everyone up on the way down. |
| C-SCAN (Circular SCAN) | Sweeps in only one direction, then instantly resets to the start. | An elevator that only takes passengers on the way up. Once at the top, it drops to the bottom empty. |
| LOOK / C-LOOK | Like SCAN, but the head reverses as soon as it hits the last actual request, instead of going to the absolute edge. | An elevator that stops going up once the highest requested floor is reached, rather than always visiting the roof. |
Summary
Choosing the right algorithm is about balancing total throughput against fairness. SSTF minimizes arm movement but can "starve" distant requests if a flood of nearby requests keep arriving. SCAN and LOOK algorithms provide a much better balance of efficiency and fairness, preventing starvation.
In the next few lessons, we will dive deep into each of these algorithms, calculating exact head movements step-by-step.