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

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

Pehle aap the parent note padh sakein aur har line follow kar sakein, uske liye aapko kuch symbols aur pictures ko apna banana hoga. Yeh page har ek cheez absolutely nothing se build karta hai, ek aisi order mein jahan har idea pehle wale par lean karta hai. Yahan kuch bhi assumed nahi hai — agar parent ne use kiya, toh hum ise yahan define karte hain.

1. Disk ek rings ka set hai — "cylinder" kya hota hai

Ek chamakdar circular platter ki picture karo, jaise ek chhoti si record. Data us par randomly nahi likha hota — yeh concentric rings par rehta hai, ek doosre ke andar, jaise woh rings jo aap ek ped ka tana kaatne par dekhte hain.

Picture yeh hai: figure mein har ring ek cylinder hai. Sabse andar wali ring cylinder $0$ hai; woh bahar ki taraf count karte hain.

Topic ko yeh kyun chahiye: poora game rings ke beech move karna hai. Agar rings nahi hote — agar data ek blob hota — toh schedule karne ke liye kuch bhi nahi hota. Poori anatomy ke liye Hard Disk Drive structure (cylinders, tracks, sectors) dekhein.

2. Rings ko number dena — "cylinder number"

Hum har ring ko ek whole number dete hain taaki positions par arithmetic kar sakein.

Picture yeh hai: rings ko ek seedhi number line mein unroll karo — ek ruler jo left mein $0$ se right mein $199$ tak rakha ho. Har request ab us ruler par sirf ek dot hai. "Rings ko ek line mein flatten karo" wala yeh trick poore topic ka sabse important visual hai.

Topic ko yeh kyun chahiye: jab rings line par numbers ban jaate hain, toh "head kitna move hua?" plain subtraction ban jaata hai. Yehi poore subject ko computable banata hai.

3. Head — moving arm

Picture yeh hai: number-line par, head ek single marker hai jo ek dot par baitha hai. Kisi aur request ko serve karne ke liye, marker ko us dot tak line ke saath walk karna padta hai — yeh teleport nahi kar sakta (C-SCAN ke return jump ko chhodkar, jo abhi bhi ek real physical sweep hai).

Topic ko yeh kyun chahiye: sirf ek hi head hai. Yeh ek saath do jagah nahi ho sakta, isliye requests ko kisi order mein, ek ke baad ek serve karna padta hai. Yahi constraint poori "scheduling" ki existence ki wajah hai.

4. Symbol $h_0,h_1,h_2,\dots$ — service order

Parent note $h_0\to h_1\to \cdots \to h_n$ jaisi cheezein likhta hai. Har piece earn karte hain.

Picture yeh hai: number line par, har stop par ek labelled flag lagao us order mein jis order mein head unhe reach karta hai: start dot par flag $h_0$, phir $h_1$, $h_2$, … Ek alag algorithm simply unhi flags ko alag order mein plant karta hai.

5. Absolute value $|x|$ — "distance, direction ignore karo"

Parent ka core formula vertical bars se bhara hua hai, $|h_i-h_{i-1}|$. Zero se yeh kya maana hai:

Yahan hamen yeh kyun chahiye — is tool ko choose karne ka WHY: head ka cylinder $124$ se neeche $65$ tak move karna $124-65=59$ cylinders cover karta hai. Lekin $65$ se upar $124$ tak move karna $124-65=59$ deta hai — ruko, lekin $65-124=-59$. Physical travel ke liye negative distance meaningless hai; arm dono taraf $59$ cylinders slide karta hai. Absolute value exactly woh tool hai jo kehta hai "mujhe parwah hai kitni door, kisi taraf nahi." Hum ne ise (plain subtraction nahi) choose kiya kyunki direction ko travel total karte waqt discard karna padta hai.

6. Summation $\sum$ — "saare steps jodo"

Picture yeh hai: number line par head ka har step ek colored segment hai. $\sum$ ka matlab bas woh saare segments end-to-end rakho aur total length measure karo.

7. "Direction" aur "boundary" — aakhri do ingredients

Picture yeh hai: number line par, $0$ aur $199$ par do walls mark karo. "Direction" left ya right point karta ek arrow hai; "boundary" ek wall se takrana hai.

Prerequisite map

Ise bottom se top tak ek build ki tarah padho: rings → numbers → ek line → ek moving marker → stops ka ek order, saath mein distance aur sum ke tools, aur direction aur edges — sab milke ek single quantity total head movement mein feed hote hain, jo parent note mein har algorithm shrink karne ki koshish karta hai.

Yeh aage kahan feed karta hai

• Story ka why-it's-slow wala aadha hissa Seek time vs Rotational latency mein hai — yeh page cylinders count karta hai; woh page cylinders ko milliseconds mein convert karta hai.
• "Bahut saari requests waiting, ek order choose karo" wala pattern Process Scheduling — FCFS, SJF, Round Robin aur greedy cousin SSTF (Shortest Seek Time First) ke peeche bhi yehi hai.
• Ek fair order matter kyun karta hai: Starvation and Fairness in OS.
• Yeh requests pehle aate kahan se hain: I/O Subsystem and Device Drivers.

Equipment checklist

Aap parent note ke liye ready hain jab aap inhe zor se bol sakein: