Noesis
4.2.38Operating Systems

Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

1,981 words9 min readdifficulty · medium4 backlinks
🇮🇳 Yeh note Hinglish mein padho →

WHY does disk scheduling exist?

WHY it matters: The CPU is fast; the disk is slow. If the head zig-zags wildly (e.g., serving 50 → 180 → 10 → 170), it wastes huge travel. Reordering can cut travel by half or more — directly speeding up the system.

WHAT we measure: Total head movement =∑∣current−next∣= \sum |\text{current} - \text{next}| over the whole service sequence, in cylinders. Lower = better.

The four algorithms (HOW each picks the next request)

(C-LOOK = C-SCAN that only goes to the last request, then jumps back to the lowest request.)

Figure — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

Derivation from first principles

There is no magic formula — total head movement is defined as the sum of step distances. Let the head start at h0h_0 and the service order be h0,h1,h2,…,hnh_0, h_1, h_2, \dots, h_n.

For SCAN/C-SCAN, the order includes the boundary (0 or max) as an extra stop; for LOOK it does not. That single difference explains all the numbers.

Worked examples

Use this standard setup throughout: Queue (arrival order): 98, 183, 37, 122, 14, 124, 65, 67 Head start: 53. Disk range: 0–199. Direction: toward larger cylinders (up).

Sorted requests for reference: 14, 37, 65, 67, 98, 122, 124, 183.

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine an elevator in a tall building and people waiting on many floors. The dumb way (FCFS) is to go to whoever pressed first, even if they're at the top, then bottom, then top again — lots of wasted riding. The smart elevator (SCAN/LOOK) keeps going up, picking up everyone on the way, reaches the top, then comes down picking up the rest. C-SCAN is a one-way escalator: it only picks people up going up, zooms back to the ground floor empty, and starts again — so the person on floor 1 never waits forever. The disk head is the elevator; the cylinders are floors; we want the least riding.

Quick comparison

Algo Goes to end? Services on return? Trait
FCFS n/a n/a fair, but wasteful zig-zag
SCAN yes yes elevator, edges wait longer
C-SCAN yes + wrap jump no uniform wait time
LOOK no (stops at last) yes least travel of the elevators
What quantity do disk scheduling algorithms try to minimize?
Total head movement (sum of |seek distances|), i.e. seek time.
Formula for total head movement given service order h0,h1,...,hn?
∑i=1n∣hi−hi−1∣\sum_{i=1}^{n}|h_i - h_{i-1}|.
How does FCFS choose the next request?
It serves requests in exact arrival order — no reordering.
How does SCAN differ from LOOK?
SCAN travels to the physical disk end (0 or max) before reversing; LOOK reverses at the last actual request.
What is the key advantage of C-SCAN over SCAN?
More uniform waiting time (no request starves at the far edge), because it services in only one direction.
In C-SCAN, what happens at the end of a sweep?
The head jumps straight to the other extreme without servicing, then starts a fresh sweep in the same direction.
For requests with head at 53, SCAN up first to end 199 then down to 14, total?
(199−53)+(199−14)=146+185=331 cylinders.
Why is LOOK's total ≤ SCAN's total (same direction)?
LOOK saves 2×(end − last request) by not visiting the unnecessary physical boundary.
Does smaller total head movement always mean a better algorithm?
No — C-SCAN may have larger total but gives fairness/uniform wait; trade-offs matter.

Connections

  • Seek time vs Rotational latency
  • Hard Disk Drive structure (cylinders, tracks, sectors)
  • Process Scheduling — FCFS, SJF, Round Robin (analogous ordering trade-offs)
  • Starvation and Fairness in OS
  • I/O Subsystem and Device Drivers
  • SSTF (Shortest Seek Time First)

Concept Map

motivates

achieved by

measured by

strategy

strategy

variant, uniform wait

variant, no boundary trip

variant

no reordering, may zig-zag

Seek time dominates disk latency

Minimize total head movement

Total = sum of |hi - hi-1|

OS chooses service order

FCFS - arrival order

SCAN - sweep to disk end then reverse

C-SCAN - jump back to other extreme

LOOK - stop at last request

C-LOOK - jump back to lowest request

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dekho, disk ka head ek physical arm hai jo tracks (cylinders) ke upar move karta hai, aur ye movement slow hota hai — isi ko seek time bolte hain. Jab bahut saare I/O requests queue mein hote hain, toh OS decide kar sakta hai ki kaunsa request pehle serve karna hai. Goal simple hai: total head movement (cylinders mein) minimum karo, taaki disk fast lage.

FCFS matlab jo pehle aaya wahi pehle — fair hai par head idhar-udhar zig-zag karta hai, bahut waste. SCAN ek elevator jaisa hai: head ek direction (maan lo up) mein jaata hai, raaste ke saare requests serve karta hai, disk ke end (199) tak jaata hai, phir reverse hoke neeche ke serve karta hai. LOOK bhi same hai par end tak nahi jaata — sirf last actual request tak jaake reverse ho jaata hai, isliye thoda travel bachta hai. C-SCAN ek one-way escalator hai: sirf up direction mein serve karta hai, end pe pahunch ke seedha 0 pe jump kar jaata hai (beech mein serve nahi karta), phir fresh upward sweep — isse har request ka waiting time uniform rehta hai, koi bhukha (starve) nahi marta.

Formula yaad rakhna easy hai kyunki koi rata-rataya formula nahi: bas service order likho aur consecutive positions ke beech ka absolute difference add karte jao. Jaise start 53 se SCAN up: 199−53=146199-53=146 upar, phir 199−14=185199-14=185 neeche, total 331331. Har algorithm ka sirf order alag hota hai, sum karne ka tareeka same.

Ek important baat: chhota total hamesha best nahi hota. C-SCAN ka total zyada ho sakta hai (kyunki wo poora disk wapas jump karta hai), par wo fairness deta hai. Exam mein hamesha start position aur direction clearly note karo, aur SCAN vs LOOK ka difference (end touch karta hai ya nahi) confuse mat karna — wahi sabse common galti hai.

Go deeper — visual, from zero

D1FoundationsEvery symbol from zero · 1,911 wordsD2Visual walkthroughThe derivation in pictures · 2,215 wordsD3Worked examplesEvery scenario covered · 4,376 wordsD4ExercisesGraded, full solutions · 2,498 wordsD5Question bankConcept traps, quick reveals · 2,198 words

Test yourself — Operating Systems

L1 RecognitionL2 RecallL3 ProductionL4 ApplicationL5 Mastery

Connections

File allocation — contiguous, linked, indexed (inode)Coding · 4.2.34ext4 structure — superblock, block groups, inodesCoding · 4.2.35I - O management — polling, interrupt-driven, DMACoding · 4.2.37RAID — levels 0, 1, 5, 6, 10 — trade-offsCoding · 4.2.39