Disk scheduling — FCFS, SCAN, C-SCAN, LOOK: Visual walkthrough

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

Hum poore walkthrough mein same setup rakhte hain taaki pictures ek doosre ke upar stack ho sakein:

Step 1 — Disk ko ruler ki tarah draw karo

KYA: Kisi bhi algorithm se pehle, hum physical stage lay out karte hain. Hard disk ke cylinders numbered concentric rings hote hain. Hum unhe $0$ se $199$ tak ki straight number line mein flatten karte hain. Read/write head ek waqt ek number par baith ta hai; yahan yeh $53$ par start karta hai.

KYU ek straight line, real circular platter nahi? Kyunki jo cost hum care karte hain — seek time — sirf is baat par depend karti hai ki head cylinders ke across kitna slide karta hai, yaani ki do cylinder numbers ka difference. Physical circle par direction matter nahi karta; sirf ruler-along-ki-distance matter karti hai. Toh ek 1-D ruler woh sab 100% capture karta hai jo humein chahiye aur kuch bhi important nahi chhodta.

PICTURE: Aath requests pink ticks hain; head $53$ par yellow dot hai. Dekho requests kitni scattered hain — kuch $53$ ke neeche, zyaadatar upar. Yahi scatter poora problem hai: humein har pink tick visit karni hai, aur hum shortest walk chahte hain.

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

Step 2 — "Cost" ko ek path ki length ki tarah define karo

KYA: Ab hum precisely kehte hain "better" ka matlab kya hai. Maano algorithm decide karta hai requests ko kisi order mein serve karne ka, toh head positions $h_{0}, h_{1}, h_{2}, \dots, h_{n}$ us sequence mein visit karta hai. $h_{i - 1}$ se $h_{i}$ tak ek single move head ko $∣ h_{i} - h_{i - 1} ∣$ cylinders slide karata hai.

KYU absolute value $∣ \cdot ∣$ ? Distance negative nahi ho sakti. Agar head $124$ se $65$ tak neeche jaata hai, toh number $65 - 124 = - 59$ negative hai, lekin effort $59$ cylinders of sliding hai. Bars $∣ ∣$ ka matlab hai "minus sign phenko — mujhe sirf kitna door, kaunsi direction nahi."

KYU hum moves add karte hain? Kyunki head physically ek segment slide karta hai, phir agla, phir agla. Total wear = segment $1$ + segment $2$ + $\dots$ Travel additive hai, bilkul ek road trip ki legs add karne ki tarah.

PICTURE: Ruler ke upar do example moves arcs ki tarah drawn hain, har ek apni length ke saath labelled. Har arc ke neeche ka number sum mein ek term hai. Ek algorithm bas ek choice hai ki kaun se arcs draw karein aur kis order mein — total wahi picture hai jise ruler se measure kiya.

Step 3 — FCFS: queue ki obey karo, zig-zag ka daam chukao

KYA: First-Come-First-Served koi bhi choice nahi karta — yeh requests ko arrival order mein visit karta hai. Toh path forced hai: $53 \to 98 \to 183 \to 37 \to 122 \to 14 \to 124 \to 65 \to 67.$

KYU pehle yeh dikhayein? Yeh baseline "dumb" walk hai. Kyunki yeh kabhi reorder nahi karta, head bahut upar ( $183$ ) phir bahut neeche ( $37$ ) phir wapas upar lurch karta hai — har reversal wasted travel hai. Yeh hamara yardstick hai: har clever algorithm ko $640$ beat karna chahiye.

PICTURE: Path ko ek time-graph ki tarah draw kiya gaya hai — vertical axis cylinder number hai, horizontal axis hai "order mein kaun si request." Line ko upar neeche ek heartbeat ki tarah stab karte dekho. Har near-vertical plunge (jaise $183 \to 37$ ) sum mein ek giant term hai.

Step 4 — SCAN: wall tak upar sweep karo, phir wapas neeche

KYA: SCAN requests ko sort karta hai aur pehle ek direction mein sweep karta hai. $53$ se upar jaate hue, yeh har request ko increasing order mein serve karta hai jab tak yeh physical end $199$ ("wall") hit nahi karta, chahe $199$ par koi request na ho. Phir yeh turn karta hai aur baaki lower requests ko waapas neeche jaate hue serve karta hai.

Path: $53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 199 \to 37 \to 14$ .

KYU $199$ tak jaao? Yahi SCAN ka defining rule hai — yeh ek building elevator ki tarah behave karta hai jo reverse karne se pehle hamesha top floor tak jaata hai. Yeh agle step mein LOOK ke contrast fuel hai: khali wall tak jaana optional travel hai.

KYU yeh FCFS ko beat karta hai? Koi zig-zag nahi. Saari up-requests ek clean climb mein done, saari down-requests ek clean descent mein. Line mein exactly ek turn hai instead of chhe.

PICTURE: Same time-graph style. $199$ tak ek smooth climb (yellow), $14$ tak ek smooth descent (blue). $183$ se wall $199$ tak aur wapas neeche chota stub highlight kiya gaya hai — wahi stub hai jo LOOK delete karega.

Step 5 — LOOK: khali wall tak mat jao

KYA: LOOK woh SCAN hai jo peek karta hai aage: yeh us direction mein last actual request ( $183$ ) par climbing band kar deta hai wall ( $199$ ) ki jagah, phir reverse karta hai.

Path: $53 \to 65 \to 67 \to 98 \to 122 \to 124 \to 183 \to 37 \to 14$ .

KYU yeh hamesha SCAN se kam se kam utna hi achha hota hai? Kyunki yeh wall tak pointless out-and-back delete kar deta hai. SCAN $199$ tak climb kiya tha phir $183$ se wapas neeche aaya — yeh extra stub $2 \times (199 - 183) = 32$ cylinders karti hai. LOOK simply kabhi yeh pay hi nahi karta.

PICTURE: SCAN path background mein faint draw kiya gaya hai; LOOK upar bold draw kiya gaya hai. Sirf ek visible difference hai upar missing triangle (deleted $183 \to 199 \to 183$ stub), pink shaded aur " $32$ saved" labelled.

Step 6 — C-SCAN: one-way service, ghar jump karo, phir se sweep karo

KYA: C-SCAN (Circular SCAN) sirf upar jaate waqt serve karta hai. Yeh wall $199$ tak climb karta hai, phir bina kuch serve kiye seedha $0$ tak jump karta hai, aur un requests ko pick karne ke liye ek fresh upward sweep start karta hai jo skip ho gayi theen ( $14$ , phir $37$ ).

Path: $53 \to \dots \to 183 \to 199 \to jump, no service 0 \to 14 \to 37$ .

KYU return trip phenko? Fairness. SCAN mein, ek request jo upward sweep barely miss kar gayi woh poore down-and-up cycle ka wait karti hai — edges sabse zyaada wait karti hain. C-SCAN har request ko same style ki trip wait karaata hai (hamesha upar jaate serve hona), toh koi bhi cylinder far edge par starve nahi karta. Iski keemat hai bada khali jump.

PICTURE: $199$ tak climb (yellow), phir $0$ tak seedha dashed vertical drop "wrap jump — no service" mark kiya, phir $37$ tak short climb (blue). Dashed segment visually chillata hai "yahi fairness ki keemat hai."

Step 7 — Edge & degenerate cases (kabhi surprise mat ho)

KYA: Rules tab bhi work karne chahiye jab inputs weird hon. Chaar scenarios, sab tiny rulers par drawn:

Saari requests start ke upar — tab "pehle neeche" kuch bhi serve nahi karta neeche jaate waqt; head seedha upar jaata hai. SCAN/LOOK effectively ek direction mein hain.
Saari requests start ke neeche — mirror image; pehle upar jaana ek trip waste karta hai.
Head exactly ek request par start karta hai — pehli move distance $0$ hai; woh request free serve ho jaati hai, double counting nahi.
Empty queue — total head movement $0$ hai; kuch karna hi nahi.

KYU care karein? Parent note warn karta hai ki tumhe ek start aur ek direction choose karni hai. Yeh cases dikhate hain ki direction choice total dramatically change kar sakti hai, aur formula tab bhi hold karta hai (sirf kam, ya zero, terms add karta hai).

PICTURE: Chaar mini-rulers side by side, har ek apne head dot aur requests ke saath, aur resulting one-turn path. Case 4 sirf ek lone dot hai: "path length $0$ ."

Ek-picture summary

KYA: Saare chaar paths ek ruler-vs-time chart par, taaki tum literally dekh sako kaun si line shortest hai. FCFS zig-zag karta hai (sabse lamba, $640$ ). SCAN aur LOOK mein se har ek ek clean turn karta hai (LOOK deleted wall-stub se chota). C-SCAN tall dashed wrap jump add karta hai.

KYU yeh payoff hai: total head movement = drawn line ki length. Choti line = kam seek time. Lekin C-SCAN ki lambi line fairness khareedti hai — proof ki "sabse chota total" automatically "sabse achha" nahi hai.

Algo	Path shape	Total (is setup mein)	Tumhe milta hai
FCFS	zig-zag	$640$	simplicity, order ki fairness
SCAN	up→wall→down	$331$	elevator smoothness
LOOK	up→last→down	$299$	yahan least travel
C-SCAN	up→wall→jump→up	$382$	uniform waiting

Recall Feynman: saara walkthrough plain words mein

Socho ek hallway $0$ se $199$ numbered hai aur ek cleaning robot door $53$ par khada hai. Uske paas doors ki ek list hai visit karne ki. Dumb robot (FCFS) uss door par jaata hai jo pehle request hua tha, toh yeh hallway mein upar sprint karta hai, wapas neeche, phir upar — exhausting ( $640$ steps). Elevator robot (SCAN) zyaada smart hai: yeh hallway mein upar walk karta hai har door kholte hue, $199$ par far wall tak march karta hai (chahe last door $183$ tha), phir turn karta hai aur baaki kholte hue wapas walk karta hai ( $331$ ). Peeking robot (LOOK) same hai lekin kehta hai "wall kyun touch karein? mera last door yahan $183$ hai, main wahan turn kar lunga" — woh $32$ wasted steps bachata hai ( $299$ ). One-way robot (C-SCAN) sirf upar jaate waqt doors kholta hai; wall pahunche ke baad woh seedha door $0$ par zoom karta hai bina kuch khole, phir fresh sweep upar — toh door $1$ waala kabhi forever wait nahi karta, lekin khali sprint wapas bahut cost karta hai ( $382$ ). Har robot ke footprints measure karo: uske path ki length hi seek cost hai. Sabse chote footprints speed mein win karte hain — lekin one-way robot fair hone mein win karta hai.

Connections

4.2.38 Disk scheduling — FCFS, SCAN, C-SCAN, LOOK (Hinglish) — parent, Hinglish version
Seek time vs Rotational latency — path length actually time mein kya cost karti hai
Hard Disk Drive structure (cylinders, tracks, sectors) — kyun cylinders hamaara ruler banaate hain
SSTF (Shortest Seek Time First) — in algorithms ka greedy cousin
Starvation and Fairness in OS — kyun C-SCAN fairness ke liye pay karta hai
Process Scheduling — FCFS, SJF, Round Robin — CPU ke liye wahi ordering trade-offs
I/O Subsystem and Device Drivers — jahan request queue rehti hai