Section 01
The Story That Explains Disk Scheduling
📖 Real World Analogy
The Elevator in a 200-Floor Skyscraper
Imagine a single elevator serving a 200-storey building. At any moment, dozens of people
across many floors press their call buttons. The elevator can only be on one floor at a
time, so a scheduling algorithm decides which call to answer next.
Strategy A — First Come First Served: answer calls in the exact order they came in. Floor 50 calls first, then floor 183, then floor 12, then floor 190. The elevator zigzags wildly, wearing out the motor and making everyone wait.
Strategy B — Nearest Floor: always answer the closest call. Fast for the people nearby — but a person on floor 190 might wait forever while lower-floor calls keep jumping in.
Now replace "elevator" with disk read/write head, "floor" with cylinder number, and "call button" with I/O request. You have disk scheduling — the OS decides in what order to service pending disk I/O so that head movement is minimised. A saved seek is a saved millisecond, and on a busy server that means everything.
Strategy A — First Come First Served: answer calls in the exact order they came in. Floor 50 calls first, then floor 183, then floor 12, then floor 190. The elevator zigzags wildly, wearing out the motor and making everyone wait.
Strategy B — Nearest Floor: always answer the closest call. Fast for the people nearby — but a person on floor 190 might wait forever while lower-floor calls keep jumping in.
Now replace "elevator" with disk read/write head, "floor" with cylinder number, and "call button" with I/O request. You have disk scheduling — the OS decides in what order to service pending disk I/O so that head movement is minimised. A saved seek is a saved millisecond, and on a busy server that means everything.
Why This Chapter Matters
Disks are 10 000× slower than RAM. On a server handling 50 000 I/O requests per second, the difference between a smart and a dumb scheduling algorithm can translate into milliseconds of latency per request — the difference between "instant" and "sluggish" for the end user.
Section 02
Mass Storage — The Physical Reality
Anatomy of a Hard Disk Drive
HDD physical structure — platters, tracks, sectors, cylinders
Disk Performance — Where Time Goes
Seek Time
move the arm
Time for the disk head to move radially to the target cylinder. Dominant cost
— typically 3–10 ms on modern HDDs. This is what scheduling algorithms optimise.
Rotational Latency
wait for sector
Once the head is on the right track, wait for the target sector to rotate under it.
Average = half a revolution. At 7200 RPM → 4.17 ms average.
Transfer Time
read the bytes
Time to actually stream data from platter through disk buffer. Depends on rotational
speed and sector size. Fast — usually < 1 ms per block. Not the bottleneck.
Total Access Time
Access Time = Seek Time + Rotational Latency + Transfer Time. Since seek time dominates and is the only component the OS can control (via scheduling), disk scheduling algorithms focus on minimising cumulative head movement.
Section 03
Why Disk Scheduling Matters
A multiprogramming OS accumulates pending I/O requests from many processes. At any moment, the disk driver's queue may hold dozens of requests, each targeting a different cylinder. The order in which the driver services them determines total head movement — and therefore latency and throughput.
🌱 Bad Scheduling
| Head zigzags across the disk |
| Extra seek cost adds up to seconds per second of workload |
| Mechanical wear accelerates |
| Users see stuttering and slow response |
🏆 Good Scheduling
| Head moves smoothly across cylinders |
| Total seek distance drops 60–70% |
| Longer disk lifespan |
| Higher throughput, lower latency, happy users |
Section 04
FCFS — First Come, First Served
The simplest scheduling algorithm. Requests are served in the order they arrive in the queue. No prioritisation, no reordering.
Fairness
no starvation
Every request is guaranteed to be served in bounded time. No one waits forever — the
queue is strict FIFO.
Simplicity
zero overhead
Just process the head of the queue. No comparisons, no sorting. Cheapest possible
implementation.
Inefficient
huge seeks
Adjacent requests may target opposite ends of the disk. Head can bounce 190 → 12 → 180
→ 14, covering hundreds of cylinders per request. Wastes seek time.
🎮 Interactive — FCFS Simulation
Setup: Head starts at cylinder 53. Request queue (in arrival order): 98, 183, 37, 122, 14, 124, 65, 67. Disk has 200 cylinders (0–199). Click Next to service each request in FCFS order.
FCFS — service requests in strict arrival order
Request queue (arrival order — highlighted = current)
Step: 0 / 8
Last move: —
Total seek distance: 0 cylinders
Step 0 of 8
START
Head at cylinder 53. Queue holds 8 requests. Click Next to service the first one (98).
Section 05
SSTF — Shortest Seek Time First
Instead of blindly following queue order, always pick the request nearest to the current head position. Minimises each individual seek — a greedy strategy.
Locally Optimal
nearest first
Each individual seek is the smallest possible. Cuts total head movement dramatically
compared to FCFS — often by 60–70% on realistic workloads.
Not Globally Optimal
greedy trap
Sometimes a slightly-farther choice leads to a shorter overall path. SSTF's greediness
can miss this. Similar in spirit to SJF for CPU scheduling.
Starvation Risk
edge requests wait
A request at cylinder 199 can wait forever if new requests keep arriving near the
current head position. Fair-schedulers like SCAN and C-SCAN solve this.
🎮 Interactive — SSTF Simulation
Same setup as FCFS: head at 53, queue 98, 183, 37, 122, 14, 124, 65, 67. Watch SSTF pick the nearest request at each step.
SSTF — service the closest pending request
Requests pending (highlighted = next chosen)
Step: 0 / 8
Last move: —
Total seek distance: 0 cylinders
Step 0 of 8
START
Head at cylinder 53. From here, the nearest pending request is 65 (distance 12). Click Next.
Section 06
🎮 Interactive — FCFS vs SSTF Side by Side
Same input processed by both algorithms simultaneously. Watch the total-distance counters diverge dramatically.
FCFS vs SSTF — same requests, different totals
FCFS
Total: 0 cylinders
SSTF
Total: 0 cylinders
Ready — click Next to run both algorithms in parallel
Step 0 of 8
START
Same head (53) and same queue in both panels. Click Next to service one request per algorithm at a time.
Section 07
Numerical Problem 1 — Worked Example
Head starts at cylinder 50. Request queue: 82, 170, 43, 140, 24, 16, 190. Compute total seek distance for FCFS and SSTF.
Part (a) — FCFS
Service requests in arrival order:
Order: 50 → 82 → 170 → 43 → 140 → 24 → 16 → 190
|50 − 82 | = 32
|82 − 170| = 88
|170 − 43 | = 127
|43 − 140| = 97
|140 − 24 | = 116
|24 − 16 | = 8
|16 − 190| = 174
─────────────────────
Total FCFS = 642 cylindersPart (b) — SSTF
🔭 SSTF Trace
From 50
Distances: 43(7), 24(26), 82(32), 16(34), 140(90), 170(120), 190(140). Nearest = 43 (7).From 43
Remaining: 24(19), 16(27), 82(39), 140(97), 170(127), 190(147). Nearest = 24 (19).From 24
Remaining: 16(8), 82(58), 140(116), 170(146), 190(166). Nearest = 16 (8).From 16
Remaining: 82(66), 140(124), 170(154), 190(174). Nearest = 82 (66).From 82
Remaining: 140(58), 170(88), 190(108). Nearest = 140 (58).From 140
Remaining: 170(30), 190(50). Nearest = 170 (30).From 170
Only 190 left, distance = 20.SSTF
Total = 7 + 19 + 8 + 66 + 58 + 30 + 20 = 208 cylinders.Comparison
FCFS = 642 cylinders. SSTF = 208 cylinders. SSTF is 3.1× better on this workload. On a 5 ms average seek disk, this saves about 2.2 seconds of head-motion time.
Section 08
Numerical Problem 2 — Interactive Walkthrough
Head starts at cylinder 50. Request queue: 176, 79, 34, 60, 92, 11, 41, 114. Click Next to trace SSTF step by step.
Numerical 2 — SSTF trace with fresh input
Requests pending (highlighted = next chosen)
Step: 0 / 8
Last move: —
Total seek: 0 cylinders
Step 0 of 8
START
Head at 50. Nearest pending is 41 (distance 9). Click Next.
Section 09
Comparison — FCFS vs SSTF
| Property | FCFS | SSTF |
|---|---|---|
| Selection rule | Head of queue (arrival order) | Nearest pending request |
| Total seek distance | High — often 2–5× worse | Much lower |
| Implementation cost | O(1) — dequeue | O(n) — scan queue |
| Starvation possible | No — strict FIFO | Yes — edge cylinders may wait |
| Fairness | Perfect | None |
| Predictable latency | Yes — bounded queue wait | No — depends on arrivals |
| Best for | Lightly loaded systems, batch queues | Heavy random-access workloads |
Section 10
Real-World Applications
Linux I/O Schedulers
Linux ships with multiple I/O schedulers:
noop (like FCFS, for SSDs),
deadline and mq-deadline (SSTF variants with deadlines to
prevent starvation), and bfq (fairness-focused). The choice depends on
workload and storage type.
noop · deadline · bfq
Database Storage Engines
InnoDB, PostgreSQL, and Oracle batch and sort I/O requests before dispatching to the OS.
Effectively an application-level SSTF on top of the OS scheduler. Doubles query
throughput on rotational storage.
InnoDB · PostgreSQL
RAID Controllers
Hardware RAID cards implement their own request queues and scheduling. They can reorder
requests across multiple physical disks to minimise cross-disk seeking.
RAID controllers
SSDs Change the Game
Solid-state drives have no seek time — access is uniform across all blocks. Traditional
seek-minimising schedulers become moot. Linux's
noop and none
schedulers exist precisely for SSDs.
NVMe · SSD queues
Game Level Streaming
Open-world games issue thousands of asset-load requests during gameplay. Engines
reorder them by expected proximity on disk to reduce load-stutter — an SSTF-inspired
technique at the application level.
Asset streaming
Cloud Object Stores
Amazon S3 and Google Cloud Storage don't expose seek concepts to users, but internally
they cluster and prefetch objects using proximity heuristics that mirror disk scheduling
principles.
S3 · GCS internals
Section 11
Golden Rules — Disk Scheduling
🔑 Galvin's Non-Negotiable Rules
1
Total disk access time = seek time + rotational latency + transfer time. Seek time dominates and is the only component the OS controls via scheduling.
2
Disk scheduling algorithms are evaluated by total head movement (total seek distance). Fewer cylinders traversed = lower latency and less mechanical wear.
3
FCFS services requests in arrival order. Fair (no starvation) and O(1) per request, but wastes seeks — often 2–5× worse than SSTF.
4
SSTF picks the request nearest to the current head position. Locally optimal, but may cause starvation of requests at disk extremities.
5
SSTF is not globally optimal. There exist request patterns where a slightly-farther choice would give a shorter overall path — analogous to SJF being greedy for CPU.
6
SSTF requires O(n) scan to find the nearest, while FCFS is O(1). Trade-off: scheduling overhead vs seek savings. Almost always worth it.
7
To solve a numerical: (a) list distances |head − request| in arrival order for FCFS, or (b) at each step pick the smallest |current − remaining request| for SSTF. Sum all distances.
8
SSDs eliminate seek time. Modern flash storage makes seek-based scheduling irrelevant — Linux uses
none/noop for NVMe. The algorithms still matter for spinning disks in servers and cloud archives.9
Real production schedulers combine ideas from FCFS, SSTF, SCAN, and C-SCAN — with deadline mechanisms to guarantee no request waits longer than a threshold. Best of both worlds.
10
When in doubt, compute both FCFS and SSTF totals for the given input. FCFS is the baseline; SSTF is the greedy improvement. The gap reveals how much the OS can save through smart scheduling.