Disk scheduling — FCFS, SCAN, C-SCAN, LOOK: Worked examples

4.2.38 · D3 · Coding › Operating Systems › Disk scheduling — FCFS, SCAN, C-SCAN, LOOK

Shuru karne se pehle, ek reminder uss single rule ka jo matter karta hai (parent mein build kiya gaya):

Scenario matrix

Har disk-scheduling problem kuch independent choices se bani hoti hai. Yeh table har case class list karta hai — woh odd corners jo logon ko trip karte hain — aur woh example jo usse solve karta hai.

#	Case class	Kya khaas baat hai	Example
A	Head beech mein, requests dono taraf	"normal" case, charon algos	Ex 1
B	Head low edge par (0)	neeche koi travel nahi; SCAN reversal trivial hai	Ex 2
C	Head high edge par (max)	pehle se hi wall par start	Ex 3
D	Saare requests head ke upar	direction neeche poora trip waste karta hai	Ex 4
E	Direction = pehle neeche	mirror image; test karta hai ki tumne "upar" hard-code to nahi kiya	Ex 5
F	Degenerate: ek request (aur empty queue)	limiting case, sum mein ek term ya zero	Ex 6
G	Duplicate / tie head par ya requests ke beech	$	h_i-h_{i-1}
H	Word problem in milliseconds (seek-rate given)	cylinders → time convert karo, real units	Ex 8
I	Exam twist: C-LOOK + "charon compare karo"	wrap-jump to last request, ranking	Ex 9
J	Circular scans pehle NEECHE jaate hain	C-SCAN/C-LOOK wrap par upar jaata hai	Ex 10
K	Request bilkul wall par (0 ya 199)	wall tak ka trip "free" hai ya paid?	Ex 11

Hum ek fresh, chhoti queue use karte hain taaki arithmetic haath se check ho sake: Queue = {90, 20, 150, 60, 10}, disk range 0–199, jab tak koi case override na kare. Reference ke liye sorted: 10, 20, 60, 90, 150.

Neeche wali figure exactly yahi setup draw karti hai. Jab tum Case A padho tab isse dekhte raho — amber square head hai, cyan dots pending requests hain, aur do arrows dikhate hain ki head position queue ko up-side aur down-side mein kaise "cut" karta hai. Har algorithm neeche sirf un dono sides ko combine karne ka ek alag rule hai.

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

Figure s01 — cylinder axis (0 se 199) par standard scenario: amber square = head at 70, cyan dots = requests {10, 20, 60, 90, 150}. Amber arrow up-side requests {90, 150} ki taraf point karta hai; cyan arrow down-side requests {60, 20, 10} ki taraf point karta hai.

Case A — head beech mein, requests dono taraf

Worked example (Cell A) Head at 70, charon algorithms, pehle upar.

Queue = {90, 20, 150, 60, 10}, head = 70, range 0–199, direction up.

Forecast: Tumhara kya lagta hai kaun kam travel karta hai — FCFS, SCAN, LOOK, ya C-SCAN? Padhne se pehle guess karo. (Figure s01 dekho — head at 70 ke do requests upar hain aur teen neeche.)

Sorted: 10, 20, 60, 90, 150. Head 70 unhe split karta hai: below = {60, 20, 10}, above = {90, 150}.

Step 1 — FCFS (arrival order 90, 20, 150, 60, 10). Yahan $h_{0} = 70$ start hai. $∣90 - 70∣ + ∣20 - 90∣ + ∣150 - 20∣ + ∣60 - 150∣ + ∣10 - 60∣$ $= 20 + 70 + 130 + 90 + 50 = 360$ Yeh step kyun? FCFS reordering forbid karta hai, toh hum literally queue ko jaise aaya waisa walk karte hain — 20→150→60 zig-zag "fairness with no thinking" ki cost hai.

Step 2 — SCAN up. Upar jaao 90, 150 hit karte hue, phir wall 199 tak, reverse hokar neeche 60, 20, 10 tak. Up part: $199 - 70 = 129$ . Down part: $199 - 10 = 189$ . $Total = 129 + 189 = 318$ Yeh step kyun? SCAN ko physical boundary 199 touch karni chahiye even though wahan koi request nahi hai — yahi definition hai. Up-distance sirf (end − start) hai; down-distance (end − lowest request) hai kyunki yeh 199 se neeche 10 tak sweep karta hai.

Step 3 — LOOK up. Last request 150 tak upar (199 tak nahi), phir 10 tak neeche. Up: $150 - 70 = 80$ . Down: $150 - 10 = 140$ . $Total = 80 + 140 = 220$ Yeh step kyun? LOOK peek karta hai — yeh 150 par reverse karta hai, jo sabse door wali real request hai, aur woh bekar $2 \times (199 - 150) = 98$ bachata hai jo SCAN spend karta hai. Check: $318 - 220 = 98$ . ✔

Step 4 — C-SCAN up. 150 tak phir wall 199 tak upar, jump 199→0, phir upar 0→10→20→60. Up to end: $199 - 70 = 129$ . Jump: $199 - 0 = 199$ . Then to last-served: $60 - 0 = 60$ . $Total = 129 + 199 + 60 = 388$ Yeh step kyun? C-SCAN waapsi par serve nahi karta; yeh uniform waiting ke liye 0 par reset karta hai. 199 jump fairness ki keemat hai (aur, convention box ke mutabik, hum isse count karte hain).

Verify: Ranking LOOK (220) < SCAN (318) < FCFS (360) < C-SCAN (388). Units poore mein cylinders hain. Sanity: LOOK ≤ SCAN hamesha (yeh kabhi boundary trips nahi add karta) ✔; C-SCAN yahan sabse bada kyunki wrap jump hai ✔.

SCAN reversal "double" kyun karta hai bekar distance

Edge cases se pehle, ek fact nail karte hain jo hum baar-baar use karenge. Pehle, do naam jo hum use karte rahenge:

$E$ = "end", yaani physical wall jis taraf SCAN ja raha hai (high wall $E = 199$ hai, low wall $E = 0$ hai).
$L$ = "last real request", yaani us direction mein sabse door wala cylinder jahan koi actual request hai.

Maan lo SCAN upar sweep kar raha hai, toh last real request cylinder $L$ par hai, lekin SCAN wall $E$ tak chadhne par insist karta hai. Yeh extra $E - L$ upar travel karta hai wall reach karne ke liye, aur phir — kyunki yeh reverse karta hai aur usi stretch se waapas aata hai — yeh $E - L$ neeche bhi travel karta hai kisi request se milne se pehle. Toh ek unneeded wall ko touch karne ki bekar distance hai: $waste = 2 (E - L)$ Woh 2 ka factor up-then-back-down round trip hai. LOOK isse $L$ par reverse karke poori tarah bachata hai. Yeh exactly Case A mein 98 hai ( $2 \times (199 - 150)$ , toh $E = 199$ , $L = 150$ ). Is "×2" ko dhyan mein rakho — yeh sirf tab aata hai jab head wall tak bhi jaata hai aur us hi gap se waapas bhi aata hai. Jab head wall par start karta hai, toh us gap se waapas aane ki zaroorat nahi, isliye ×2 apply nahi hota (Case B dekho).

Case B — head low edge par (cylinder 0)

Worked example (Cell B) Head at 0, SCAN aur LOOK, pehle upar.

Queue = {90, 20, 150, 60, 10}, head = 0, range 0–199.

Forecast: Agar head pehle se 0 par hai, toh kya "reverse aur neeche jao" kuch cost karta hai?

Step 1 — SCAN up from 0. 0 se neeche kuch nahi hai, toh down-sweep empty hai. Head 0→10→20→60→90→150→199 jaata hai. $Total = 199 - 0 = 199$ Yeh step kyun? Jab head boundary par baith jaata hai, SCAN ke do sweeps mein se ek ke zero requests hoti hain. Reversal distance zero ho jaati hai — tum sirf 199 tak up trip pay karte ho.

Step 2 — LOOK up from 0. Last request 150 par rukta hai. $Total = 150 - 0 = 150$ Yeh step kyun? Upar wale box se "×2" rule yaad karo ( $E = 199$ , $L = 150$ ke saath): SCAN ki waste normally $2 (E - L)$ hoti hai kyunki yeh wall tak chadhta hai aur $150 \to 199$ gap se waapas neeche bhi aata hai. Lekin yahan head low wall par start karta hai aur sirf upar sweep karta hai — yeh $150 \to 199$ gap se kabhi waapas nahi aata. Toh SCAN us gap ko sirf ek baar traverse karta hai, aur LOOK ki saving isliye single $199 - 150 = 49$ hai, $2 \times 49$ nahi. Doubling ke liye return trip chahiye jo edge par shuru karne par hota hi nahi.

Verify: $199 - 150 = 49$ , SCAN−LOOK gap se match karta hai. Dono totals sirf "top tak distance" hain, kyunki edge par start karna ek poori direction hata deta hai. ✔

Case C — head high edge par (cylinder max)

Case D — saare requests head ke upar

Worked example (Cell D) Head at 5, saare requests upar, SCAN down-first vs up-first.

Queue = {90, 20, 150, 60, 10}, head = 5.

Forecast: Agar tum galti se SCAN ko neeche start karo, kitna waste hoga?

Step 1 — SCAN up first (sahi instinct). 5 se neeche kuch nahi, toh upar: 5→10→20→60→90→150→199, koi return nahi. $Total = 199 - 5 = 194$ Yeh step kyun? Saare requests upar hain, toh "up first" ko koi return sweep nahi chahiye — down side empty hai.

Step 2 — SCAN down first (trap). Head pehle 5→0 (low wall) jaata hai, phir reverse hokar puri tarah 199 tak upar jaata hai. Down: $5 - 0 = 5$ . Up: $199 - 0 = 199$ . $Total = 5 + 199 = 204$ Yeh step kyun? Empty direction pehle choose karna near wall tak ek bekar round trip force karta hai. Galat choice ki cost: $204 - 194 = 10 = 2 \times 5$ (near wall tak distance ka do guna — wohi "×2" round-trip rule).

Verify: Bekar amount exactly $2 \times (head - 0) = 2 \times 5 = 10$ hai. Direction choice matter karti hai — isliye exams hamesha isse state karte hain. ✔

Case E — direction = pehle neeche (mirror image)

Worked example (Cell E) Head at 70, SCAN aur LOOK, direction

down pehle. Queue = {90, 20, 150, 60, 10}, head = 70, range 0–199.

Forecast: Same queue Case A jaisi but pehle neeche jaana — kya LOOK ka total badlega?

Step 1 — LOOK down. Pehle neeche serve karo: 70→60→20→10, phir reverse upar: →90→150. Down: $70 - 10 = 60$ . Up: $150 - 10 = 140$ . $Total = 60 + 140 = 200$ Yeh step kyun? Ab down-side pehle serve hoti hai. Hum lowest request 10 tak jaate hain, phir highest 150 tak upar sweep karte hain. Direction ne order badla, isliye number bhi badla (up-first mein 220 tha).

Step 2 — SCAN down. 70→0 (low wall), reverse upar 199 tak. Down: $70 - 0 = 70$ . Up: $199 - 0 = 199$ . $Total = 70 + 199 = 269$ Yeh step kyun? SCAN is baar low wall 0 touch karta hai. LOOK se compare karo: SCAN $2 \times (10 - 0) = 20$ low side par aur $199 - 150 = 49$ high side par waste karta hai; $200 + 20 + 49 = 269$ . ✔

Verify: LOOK down (200) < LOOK up (220) yahan — direction genuinely answer affect karti hai, toh "kaunsi direction" kabhi optional nahi. ✔

Case F — degenerate inputs (ek request, empty queue)

Worked example (Cell F) Limiting cases.

F1 — ek request. Head 53, queue = {110}. F2 — empty queue. Head 53, queue = {}.

Forecast: Sum $\sum ∣ h_{i} - h_{i - 1} ∣$ kya deta hai jab sirf ek term ho? Jab zero terms hon?

Step 1 — ek request (F1). Order sirf $53 \to 110$ hai. Sum mein ek hi term hai: $Total = ∣110 - 53∣ = 57$ Yeh step kyun? Ek request ke saath har algorithm agree karta hai — choose karne ke liye koi ordering nahi hai. FCFS = SCAN = LOOK = C-SCAN = 57 (boundary/wrap ignore karke, jo koi textbook tab count nahi karta jab kuch aage nahi ho).

Step 2 — empty queue (F2). Service order sirf $h_{0}$ hai jiske baad koi stop nahi. Sum empty hai. $Total = \sum_{i = 1}^{0} ∣ h_{i} - h_{i - 1} ∣ = 0$ Yeh step kyun? Ek empty sum definition se 0 hai — head kabhi move nahi karta kyunki serve karne ke liye kuch nahi. Yeh sabse chhota possible answer hai aur ek accha "kya mera code crash karta hai?" test hai.

Verify: F1 = 57 har algorithm ke liye; F2 = 0. Yeh boundary values hain jo kisi bhi implementation ko stress-test karte hain. ✔

Case G — duplicates aur ties

Worked example (Cell G) Head at 60, head par ek request aur ek tie.

Queue = {60, 60, 120, 20}, head = 60, LOOK up first.

Forecast: Current position ke equal ek request — kya yeh travel add karta hai?

Step 1 — head par requests serve karo. Do requests 60 par hain, exactly wahan jahan head hai. $∣60 - 60∣ + ∣60 - 60∣ = 0 + 0 = 0$ Yeh step kyun? $∣ h_{i} - h_{i - 1} ∣ = 0$ jab consecutive positions equal hon — ek duplicate ya current cylinder par ek request free travel hai. Inhe immediately serve karo, cost zero.

Step 2 — LOOK up phir down continue karo. Remaining sorted: below = {20}, above = {120}. Up first: 60→120, phir down 120→20. Up: $120 - 60 = 60$ . Down: $120 - 20 = 100$ . $Total = 0 + 60 + 100 = 160$ Yeh step kyun? Ties distance total ko kabhi nahi badlte (woh zeros add karte hain); woh sirf I/O operations ki count affect karte hain, head travel nahi. Equal cylinders ke beech order arbitrary hai.

Verify: Total = 160; do duplicate 60's exactly 0 contribute karte hain, toh ek hatane se same head movement milti. ✔

Case H — word problem: cylinders ko milliseconds mein convert karo

Worked example (Cell H) Real units. Seek rate given.

Head at 100, queue = {40, 180, 90}, range 0–199. Har cylinder cross karne ki cost 0.2 ms seek time hai; har request ke liye ek flat 1 ms rotation+transfer ke liye hai. LOOK, up first use karo. Total kitna time?

Forecast: Kya dominate karta hai — seek time ya fixed per-request time?

Step 1 — head movement (cylinders) nikalo. Sorted: 40, 90, 180. Above 100 = {180}, below = {40, 90}. LOOK up: 100→180, phir down: 180→90→40. Up: $180 - 100 = 80$ . Down: $180 - 40 = 140$ . $Movement = 80 + 140 = 220 cylinders$ Yeh step kyun? Time travel se aata hai, toh pehle cylinder count lena zaroori hai — algorithm ka poora kaam yehi hai.

Step 2 — cylinders ko seek time mein convert karo. $220 \times 0.2 ms = 44 ms$ Yeh step kyun? "0.2 ms per cylinder" ek rate hai (ms/cylinder). Rate × cylinders multiply karne se cylinders cancel hote hain aur ms milta hai — ek units check ki humne sahi kiya. Dekho Seek time vs Rotational latency.

Step 3 — fixed per-request cost add karo. 3 requests hain, har ek 1 ms. $3 \times 1 ms = 3 ms$ $Total = 44 ms + 3 ms = 47 ms$ Yeh step kyun? Seek disk access ka sirf ek hissa hai; rotation aur transfer yahan alag flat costs hain. Total access = seek + fixed.

Verify: $220 \times 0.2 = 44$ , $+ 3 = 47$ ms. Units: $(cyl) (ms/cyl) + (req) (ms/req) = ms$ . ✔ Seek (44) fixed (3) par dominate karta hai, aur yahi poora reason hai ki hum cylinders cut karne ke liye schedule karte hain.

Case I — exam twist: C-LOOK aur charon rank karo

Worked example (Cell I) Head at 50, C-LOOK, phir charon rank karo.

Queue = {82, 170, 43, 140, 24, 16, 190}, head = 50, range 0–199, up first.

Forecast: C-LOOK, C-SCAN ka thrifty cousin hai. Yeh kahaan jump karta hai — 0 par ya lowest request par?

Sorted: 16, 24, 43, 82, 140, 170, 190. Above 50 = {82,140,170,190}; below = {43,24,16}.

Step 1 — C-LOOK sweep up. 50→82→140→170→190 (last request, 199 nahi). Up: $190 - 50 = 140$ . Yeh step kyun? LOOK ki tarah, C-LOOK last real request (190) par rukta hai, physical wall par kabhi nahi.

Step 2 — lowest request par jump karo (0 par nahi). Jump 190→16. Jump: $190 - 16 = 174$ . Yeh step kyun? C-LOOK lowest pending request (16) par reset karta hai, cylinder 0 par nahi — yahi "LOOK" saving wrap par apply hoti hai. (C-SCAN 0 par jump karta.) Convention box ke mutabik, hum is jump ko count karte hain.

Step 3 — upward sweep finish karo. 16→24→43. $16 \to 24 \to 43 : 43 - 16 = 27$ $Total = 140 + 174 + 27 = 341$ Yeh step kyun? Wrap ke baad hum remaining low requests ke through upar continue karte hain, unme se sabse upar wale (43) par khatam karte hain.

Step 4 — ranking ke liye baaki teen.

LOOK up: up 50→190 = 140; down 190→16 = 174. Total $= 140 + 174 = 314$ .
SCAN up: up 50→199 = 149; down 199→16 = 183. Total $= 149 + 183 = 332$ .
C-SCAN up: up 50→199 = 149; jump 199→0 = 199; up 0→43 = 43. Total $= 149 + 199 + 43 = 391$ . Yeh step kyun? Exams ko "charon compute karo aur rank karo" bahut pasand hai. Pattern: LOOK ≤ SCAN, aur C-LOOK ≤ C-SCAN, circular pair usually larger hoti hai jump ki wajah se.

Verify: Ranking LOOK (314) < SCAN (332) < C-LOOK (341) < C-SCAN (391). Checks: LOOK ≤ SCAN (314≤332) ✔; C-LOOK ≤ C-SCAN (341≤391) ✔; SCAN−LOOK $= 332 - 314 = 18 = 2 (199 - 190)$ ✔.

Case J — circular scans pehle NEECHE jaate hain

Ab tak C-SCAN aur C-LOOK upar sweep karte the aur neeche wrap karte the (0 par ya lowest request par). Mirror case pehle neeche sweep karta hai aur isliye upar wrap karta hai — tumhe har "0/lowest" ko "199/highest" se flip karna hoga. Yeh woh case hai jo textbooks miss karte hain aur exams exploit karte hain.

Worked example (Cell J) Head at 100, C-SCAN aur C-LOOK, direction

down pehle. Queue = {90, 20, 150, 60, 10}, head = 100, range 0–199.

Forecast: Pehle neeche jaate hue, wrap jump 0 par jaata hai ya 199 par?

Sorted: 10, 20, 60, 90, 150. Below 100 = {90, 60, 20, 10}; above = {150}.

Step 1 — C-SCAN down. Neeche sweep karo 100→90→60→20→10→0 (low wall), phir upar jump karo 0→199, phir neeche continue 199→150. Down to wall: $100 - 0 = 100$ . Jump up: $199 - 0 = 199$ . Then to last-served: $199 - 150 = 49$ . $Total = 100 + 199 + 49 = 348$ Yeh step kyun? C-SCAN neeche jaate hue sirf neeche service karta hai, low wall 0 tak drive karta hai, phir high wall 199 par reset karta hai aur neeche service karta rehta hai. Wrap ek full-disk $199 - 0$ jump hai (counted, convention box ke mutabik), up-first version ka mirror.

Step 2 — C-LOOK down. Neeche sweep karo 100→90→60→20→10 (last request, 0 nahi), phir upar jump karo 10→150 (highest pending request, 199 nahi), done. Down to last: $100 - 10 = 90$ . Jump up: $150 - 10 = 140$ . $Total = 90 + 140 = 230$ Yeh step kyun? C-LOOK dono ends trim karta hai: yeh lowest request 10 par reverse karta hai (wall 0 nahi) aur highest request 150 par wrap karta hai (wall 199 nahi). Down-first Case I ke compare mein "lowest" aur "highest" ke roles flip kar deta hai.

Verify: C-LOOK (230) < C-SCAN (348), same ordering up-first pair jaisi. C-SCAN wrap full width $199 - 0 = 199$ hai; C-LOOK wrap $150 - 10 = 140$ hai. Dono trips sirf downward-servicing hain, uniform-wait property preserve karte hain. ✔

Case K — ek request bilkul physical wall par

Worked example (Cell K) Head at 80, ek request cylinder 0 par aur ek 199 par.

Queue = {199, 30, 0, 120}, head = 80, range 0–199, SCAN aur LOOK, up first.

Forecast: SCAN aur LOOK normally $2 (E - L)$ se differ karte hain. Agar wall par koi real request hai, toh kya woh gap vanish ho jaata hai?

Sorted: 0, 30, 120, 199. Above 80 = {120, 199}; below = {30, 0}.

Step 1 — LOOK up. Last up-request 199 hai (jo wall par hi hota hai). Up 80→120→199, phir down 199→30→0. Up: $199 - 80 = 119$ . Down: $199 - 0 = 199$ . $Total = 119 + 199 = 318$ Yeh step kyun? LOOK last real request par reverse karta hai. Yahan woh request 199 hai, toh LOOK vaise bhi top tak jaane par majboor hai — wall tak ka trip ab "bekar" nahi, yeh ek real request ki wajah se paid hai.

Step 2 — SCAN up. SCAN bhi 199 (wall) par rukta hai, phir 0 tak reverse karta hai. Up: $199 - 80 = 119$ . Down: $199 - 0 = 199$ . $Total = 119 + 199 = 318$ Yeh step kyun? Kyunki exactly 199 par ek request hai, "last request" $L$ equals "end" $E$ , toh $E - L = 0$ aur ×2 waste $2 \times 0 = 0$ hai. SCAN aur LOOK exactly coincide karte hain. Same low wall par bhi hota hai: 0 par request ka matlab hai dono algorithms 0 par bottom out karte hain bina kisi bekar stretch ke.

Verify: SCAN total $=$ LOOK total $= 318$ ; usual $2 (E - L)$ gap $2 (199 - 199) = 0$ hai, toh equal hain. Wall par ek request wall-trip ko mandatory banata hai, free nahi — head genuinely wahan ruk ke serve karta hai. ✔

Recall Self-test — ek line each

Empty queue mein total head movement? ::: 0 (empty sum, head kabhi nahi hilta). C-LOOK kis cylinder par wrap karta hai wapas (up-first)? ::: Lowest pending request par, physical 0 par nahi. C-SCAN down-first jaate hue kis wall par jump karta hai? ::: High wall 199 par (phir neeche service karta rehta hai). Agar wall par exactly koi real request ho, toh SCAN aur LOOK kaise compare karte hain? ::: Woh coincide karte hain, kyunki $E - L = 0$ ×2 waste zero kar deta hai. SCAN mein empty direction pehle choose karne ki cost? ::: Near wall tak distance ka $2 \times$ (bekar round trip). Current head position ke equal ek request kitna travel add karta hai? ::: 0 cylinders (yeh free hai). Cylinders ko milliseconds mein convert karne ke liye tum kya multiply karte ho? ::: Seek rate (ms per cylinder).

Connections

4.2.38 Disk scheduling — FCFS, SCAN, C-SCAN, LOOK (Hinglish) — parent (Hinglish)
Seek time vs Rotational latency — Case H mein ms conversion
Hard Disk Drive structure (cylinders, tracks, sectors) — cylinders unit kyun hain
SSTF (Shortest Seek Time First) — greedy cousin jo starve kar sakta hai
Starvation and Fairness in OS — C-SCAN/C-LOOK kyun exist karte hain
Process Scheduling — FCFS, SJF, Round Robin — same ordering trade-offs
I/O Subsystem and Device Drivers