💿

Disk Scheduling — FCFS & SSTF With Head-Movement Traces

A hard disk's arm is slow, so the order it serves requests decides throughput. Watch FCFS and SSTF sweep the same request queue cylinder-by-cylinder, count the head movement each costs, and see why "nearest first" is fast but can starve the edges — with fully animated head-movement traces and two worked numericals.

FCFS SSTF Head-Movement Traces 2 Numericals

Press Next → or use ← → arrow keys

SECTION 01

The Problem — An Elevator's Dilemma

🛗 REAL-WORLD ANALOGY · THE ELEVATOR

Serve the Buttons in the Best Order

An elevator with requests for floors 2, 15, 4 and 12 could answer them in the order pressed — but zig-zagging up and down wastes time and wears the motor. A smarter elevator serves floors along the way. A disk arm faces the same choice: pending reads sit at scattered cylinders, and the order the head visits them decides how far it travels — and how long everyone waits.

🧠

Why Order Matters

The single slowest step in a disk read is seek time — physically moving the arm to the right cylinder. It's the only part the OS can control, and it does so by choosing which pending request to serve next. That choice is disk scheduling.

SECTION 02 · DIAGRAM

Inside a Hard Disk

💿

Tracks, Sectors, Cylinders

A spinning platter is divided into concentric tracks, each split into sectors (512 B or 4 KB — the smallest unit). The same track across all stacked platters forms a cylinder. The head moves radially to a cylinder while the spindle spins the platters at 5400 or 7200 RPM.

SECTION 02 · DIAGRAM

Access Time — Three Costs

⏱️

Only One Part Is the OS's to Optimise

Rotational latency is fixed by RPM and transfer by the interface — the OS can't change them. But seek time depends on how far the arm travels, and that's set entirely by the order requests are served. Minimising total head movement is the whole job of disk scheduling.

SECTION 04 · DIAGRAM

FCFS — Serve in Arrival Order

📋

Head 53 · Queue 98 183 37 122 14 124 65 67

FCFS serves strictly in arrival order, so the arm lurches from 98 out to 183, all the way back to 37, out again to 122… Those wild swings add up to 640 cylinders of travel. Simple and perfectly fair — but the head crosses the disk again and again.

SECTION 04

FCFS — Fair but Wasteful

✅

Advantages

Perfectly fair — strict FIFO means no request ever starves; every one is served in bounded time. Trivial to implement — O(1), just dequeue the head. Latency is predictable.

⚠️

Disadvantage

Huge seeks — consecutive requests may sit at opposite ends of the disk, so the arm sweeps back and forth. Total travel is often 2–5× worse than SSTF.

🎯

When FCFS Is the Right Call

On a lightly loaded system or a batch queue, few requests are pending at once, so there's little to reorder — and FCFS's fairness and zero overhead win. Its weakness only shows under heavy, scattered load.

SECTION 05 · DIAGRAM

SSTF — Always the Nearest Request

🎯

Same Queue, Far Less Travel

At each step SSTF picks the closest pending cylinder: from 53 it takes 65, then 67, sweeps down through 37 and 14, then climbs steadily to 98, 122, 124, 183. The path barely doubles back — 236 cylinders versus FCFS's 640, a 63% reduction.

SECTION 05

SSTF — Fast, but It Can Starve

⚡

Locally Optimal

Each individual seek is the smallest possible from where the head currently sits — so total travel drops sharply, typically a 60–70% reduction on heavy random workloads.

🚫

Starvation Risk

A request at an edge cylinder (say 199) can wait forever if new nearby requests keep arriving — the head never travels out to it. No fairness guarantee.

🪤

The Greedy Trap

SSTF is not globally optimal: always grabbing the nearest request can miss a shorter overall path — the same greedy pitfall as SJF in CPU scheduling. It also costs O(n) per step to scan the queue. Production systems bolt on deadlines to stop the edges from starving.

SECTION 06 · DIAGRAM

Same Queue, Two Totals

🏁

640 → 236 Cylinders

On the identical queue, SSTF moves the arm less than 40% as far as FCFS. On a disk averaging 5 ms per seek, that gap is real wall-clock time saved — and less mechanical wear on the arm. The cost is fairness, which SSTF gives up.

NUMERICAL 1

Worked Example — Head at 50

Head starts at 50; queue 82, 170, 43, 140, 24, 16, 190. Disk 0–199.

FCFS path	Move	SSTF path	Move
50 → 82	32	50 → 43	7
82 → 170	88	43 → 24	19
170 → 43	127	24 → 16	8
43 → 140	97	16 → 82	66
140 → 24	116	82 → 140	58
24 → 16	8	140 → 170	30
16 → 190	174	170 → 190	20
Total	642	Total	208

🧮

642 vs 208 — a 3.1× Improvement

FCFS crosses 642 cylinders; SSTF, always taking the nearest, needs just 208 — about 3.1× less. On a 5 ms/seek disk that's roughly 2.2 seconds saved on this one batch of requests.

NUMERICAL 2

Practice — Head at 50, New Queue

Head starts at 50; queue 176, 79, 34, 60, 92, 11, 41, 114. Disk 0–199.

FCFS order	Total		SSTF order (nearest each step)	Total
50 → 176 → 79 → 34 → 60 → 92 → 11 → 41 → 114	510		50 → 41 → 34 → 11 → 60 → 79 → 92 → 114 → 176	204

# SSTF, step by step — pick the nearest remaining cylinder
50 →41 (9)  →34 (7)  →11 (23)  →60 (49)  →79 (19)  →92 (13)  →114 (22)  →176 (62)
Total = 9 + 7 + 23 + 49 + 19 + 13 + 22 + 62 = 204 cylinders

🧮

The Recipe Every Time

For FCFS, sum the gaps in arrival order (510). For SSTF, at each step pick the smallest distance from the current head and add it up (204). The first nearest request from 50 is 41 (distance 9) — and SSTF again more than halves the travel.

SECTION 09

FCFS vs SSTF at a Glance

Property	FCFS	SSTF
Selection rule	Head of queue (arrival)	Nearest pending request
Total seek distance	High — 2–5× worse	Much lower
Implementation cost	O(1) — dequeue	O(n) — scan queue
Starvation possible	No — strict FIFO	Yes — edge cylinders
Fairness	Perfect	None
Predictable latency	Yes — bounded wait	No — depends on arrivals
Best for	Light load, batch queues	Heavy random-access

⚖️

Speed vs Fairness

FCFS trades speed for guaranteed fairness; SSTF trades fairness for speed. Neither is globally optimal, which is why real schedulers add directional sweeps (SCAN, C-SCAN) and deadlines to get most of SSTF's speed without the starvation.

SECTION 10

Disk Scheduling in the Real World

🐧

Linux I/O Schedulers

deadline · bfq · mq-deadline

Real kernels blend SSTF-style reordering with deadlines so throughput improves without starving any request; bfq targets fairness.

⚡

SSDs Change Everything

noop / none

Flash has no seek time, so seek-minimising is moot. NVMe drives use the none/noop scheduler — just pass requests straight through.

🗄️

Database Engines

InnoDB · PostgreSQL

Databases batch and reorder their own I/O before dispatch to keep the disk arm moving efficiently across a page-heavy workload.

🧱

RAID Controllers

multi-disk

Controllers reorder requests across several disks at once, minimising cross-disk seeking for the whole array.

🎮

Game Level Streaming

asset loading

Engines order asset-load requests by expected disk proximity so a level streams in smoothly as the player moves.

☁️

Cloud Object Stores

S3 · GCS

Large stores cluster objects by proximity heuristics, applying the same "serve what's near" idea at data-centre scale.

SECTION 11

Eight Rules for Disk Scheduling

💿 DISK SCHEDULING · CHECKLIST

1

Access time = seek + rotational latency + transfer; only seek is OS-controllable, and it dominates.

2

The metric is total head movement (cylinders traversed) — fewer means lower latency and less wear.

3

FCFS serves in arrival order: fair, no starvation, O(1) — but 2–5× more seeking.

4

SSTF picks the nearest request: locally optimal and much faster, but O(n) and can starve the edges.

5

SSTF is not globally optimal — greedy nearest-first can miss a shorter overall path (like SJF).

6

Method: for FCFS sum gaps in order; for SSTF pick the smallest remaining distance each step, then total.

7

SSDs have no seek time, so scheduling is moot — Linux uses none/noop for NVMe.

8

Production schedulers combine FCFS, SSTF, SCAN and C-SCAN with deadlines to stop starvation.

FINAL

Choosing What the Head Does Next

FCFS 640Arrival order

SSTF 236Nearest first

63%Less head travel

O(1) vs O(n)Cost trade-off

edges starveSSTF's price

🎯

You Now Understand FCFS & SSTF

From disk anatomy and the access-time breakdown to tracing FCFS and SSTF cylinder-by-cylinder and totalling their head movement — you can work either algorithm by hand and explain the fairness-versus-speed trade at the heart of disk scheduling.

📚

Where To Go Next

SSTF's starvation is exactly what the directional algorithms fix. Next come SCAN, C-SCAN, LOOK and C-LOOK — the "elevator" schedulers that sweep the disk in one direction — completing the disk-scheduling family.

💿 End of tutorial · Press ← to review, or click Restart