4.2.38 · D5 · HinglishOperating Systems
Question bank — Disk scheduling — FCFS, SCAN, C-SCAN, LOOK
4.2.38 · D5· Coding › Operating Systems › Disk scheduling — FCFS, SCAN, C-SCAN, LOOK
Setup aur notation (pehle yeh padho)
True ya false — justify karo
Har claim ya to true hai ya false. Batao kaunsa hai aur kyun ek sentence mein.
FCFS same queue ke liye SCAN se kabhi zyada head move nahi karta.
False — FCFS arrival order follow karta hai aur zig-zag kar sakta hai (jaise 53→183→14), isliye yeh usually SCAN se zyada move karta hai; yeh sirf trivially already-sorted queues mein tie karta hai.
SCAN aur LOOK hamesha requests ko same order mein service karte hain.
True — dono ek direction mein sweep karte hain phir reverse karte hain, isliye request order identical hota hai; yeh sirf is baat mein alag hain ki head empty physical boundary ko bhi visit karta hai ya nahi.
C-SCAN ke paas same queue aur direction ke liye SCAN se hamesha strictly bada total head movement hota hai.
True as an inequality lekin ties possible hain — C-SCAN boundary tak full sweep ke upar empty full-width return jump add karta hai, isliye iska total hamesha SCAN ka ≥ hota hai aur kabhi chota nahi; yeh sirf degenerate cases mein tie kar sakte hain, kabhi C-SCAN favor nahi hota.
Chota total head movement choose karna hamesha better real-world disk deta hai.
False — yeh fairness ko ignore karta hai (SSTF/SCAN ke under ek far-edge request starve ho sakti hai) aur rotational latency ko bhi ignore karta hai, isliye "least travel" poori kahani nahi hai.
C-SCAN mein return jump (jaise 199→0) koi requests service nahi karta.
True — yahi definition hai; C-SCAN sirf ek direction mein serve karta hai aur empty reset karta hai taaki har cylinder ka wait time uniform rahe.
LOOK ek request ko starve kar sakta hai jis tarah FCFS nahi kar sakta.
False — FCFS woh ek algorithm hai jo starvation nahi kar sakta (strict arrival order); LOOK/SCAN ek edge request ko delay kar sakte hain jo baar baar overtake hoti rehti hai, lekin phir bhi woh usse ek sweep pe eventually serve karte hain.
Ek single pending request ke liye, FCFS, SCAN, C-SCAN aur LOOK sabhi head ko same distance move karte hain.
True — ek request ke saath koi reordering nahi hoti aur koi boundary sweep ki zaroorat nahi (LOOK/SCAN us ek request pe ruk jaate hain), isliye har algorithm bas start→request travel karta hai.
Total head movement head ke starting cylinder pe depend karta hai, sirf request set pe nahi.
True — pehla move se measure hota hai, isliye alag start positions wali do identical queues generally alag totals deti hain.
Error dhundo
Har line mein ek flawed statement hai. Batao galat kya hai.
"SCAN total = sorted requests ke beech gaps ka sum."
Galat — woh formula physical boundary (0 ya 199) tak ki trip aur reversal ko bhool jaata hai; SCAN ka total hai (start→end) + (end→farthest-other-side), sirf adjacent request gaps nahi.
"LOOK, SCAN se (end − last request) ke barabar distance bachata hai."
Galat — saving hai: SCAN last request ke past wall tak chalta hai (woh extra hai) aur phir wahi stretch wall se wapas chalta hai (ek aur ), isliye wasted stretch do baar cover hoti hai — jaise last request 183, end 199 deta hai saved, exactly parent ka .
"C-SCAN ka total = SCAN ka total + disk width."
Galat — C-SCAN return pe service nahi karta, isliye iska downward-sweep distance SCAN se alag hota hai; tum sirf SCAN ke number mein ek disk width add nahi kar sakte, tumhe one-directional sweeps plus jump dobara compute karna padega.
"Total head movement queue ko sort karke consecutive differences sum karke compute kar sakte ho."
Galat — yeh tabhi kaam karta hai jab head monotonically ek end se sweep kare aur start position aur direction ko ignore kare; FCFS ke liye bilkul fail hota hai aur SCAN/LOOK ke reversal legs ke liye bhi.
"Head sorted list ki pehli request pe start karta hai."
Galat — head ek diya hua position pe start karta hai (jaise 53) jo koi request bhi na ho; pehla move se us request tak jaata hai jo algorithm pehle pick karta hai.
"C-SCAN ko 'circular' isliye kehte hain kyunki head physically platter edge ke around loop karta hai."
Galat — "circular" scheduling pattern ko refer karta hai (logical cylinder index ko wapas 0 pe wrap karo), kisi physical looping ko nahi; head ek arm hai jo radially andar-bahar move karta hai.
"SSTF bas SCAN hai kyunki dono nearby requests pick karte hain."
Galat — SSTF hamesha globally nearest request pe jump karta hai aur baar baar direction reverse kar sakta hai, isliye yeh zig-zag kar sakta hai; SCAN ek direction mein commit karta hai jab tak reverse karna na pade. Dekho SSTF (Shortest Seek Time First).
Why questions
Sirf fact nahi, reasoning explain karo.
Disk scheduling exist kyun karta hai jab process scheduling already exist karta hai?
Kyunki disk head physically move karta hai aur seek time I/O latency pe dominate karta hai; request queue ko reorder karna head travel kam karta hai, jo Process Scheduling — FCFS, SJF, Round Robin mein CPU time-slicing se alag concern hai.
Total head movement absolute values se kyun measure kiya jaata hai?
Distance negative nahi ho sakti — cylinder 122 se neeche 14 tak move karne ka cost 108 cylinders travel hai regardless of direction, isliye hum har hop ka magnitude lete hain.
FCFS wasteful hone ke bawajood popular kyun rehta hai?
Yeh ek strictly fair, starvation-free scheme hai aur implement karna trivial hai; lightly loaded disks pe reordering ka benefit chota hota hai, isliye simplicity jeet jaati hai.
SCAN edge cylinders ko middle walo se zyada wait kyun karwata hai?
Head boundary pe reverse karta hai, isliye head ke just peeche wali request ko wait karna padta hai jab tak head far end tak na pahunche aur poora wapas na aaye — edges pe worst hota hai.
C-SCAN SCAN se zyada uniform wait times kyun deta hai?
Sirf ek direction mein service karke aur start pe reset karke, har cylinder ko ek one-way loop pe ek point ki tarah treat kiya jaata hai, isliye koi bhi position systematically "always last" nahi hoti jis tarah SCAN ki just-passed edge hoti hai.
Seek time, rotational latency nahi, scheduling decisions kyun drive karta hai?
Seek (cylinders ke across arm movement) sabse bada, sabse zyada reorderable delay hai; rotational latency per-request hoti hai aur queue order se optimize karna mushkil hai — dekho Seek time vs Rotational latency.
Direction (upar vs neeche) SCAN/LOOK/C-SCAN ke liye problem statement ka part kyun hai?
Pehli sweep ki direction decide karti hai ki reversal se pehle kaunsi requests serve hoti hain, jo order aur isliye total change karta hai; iske bina jawab undefined hai.
Hum hamesha sabse chota total wala algorithm kyun nahi run kar sakte?
Fairness aur starvation matter karte hain (dekho Starvation and Fairness in OS); travel minimize karne wala algorithm heavy load ke under ek far-edge request ko indefinitely wait karwa sakta hai.
Edge cases
Boundary aur degenerate inputs — har ek ko reason karo.
Queue empty hai (koi pending requests nahi). Har algorithm kya karta hai?
Kuch nahi — total head movement 0 hai aur head pe hi rehta hai; choose karne ke liye koi order nahi hai.
Sabhi requests head ke ek hi side pe hain (sabhi 53 se upar). Kya SCAN kabhi reverse karta hai?
SCAN phir bhi chosen direction mein boundary tak travel karta hai, lekin uske peeche koi requests nahi hone se, reverse leg kuch service nahi karta; LOOK simply last request pe ruk jaata aur end ho jaata.
Head exactly ek requested cylinder pe start karta hai. Kya pehla move count hota hai?
Us cylinder tak ka move distance 0 hai, isliye total mein kuch add nahi hota; yeh "free mein" serve ho jaata hai head ke kahin move karne se pehle.
Ek request exactly disk boundary pe baith gayi (cylinder 0 ya 199). Kya SCAN aur LOOK tab agree karte hain?
Haan us end pe — LOOK ki "last request" hi boundary hai, isliye woh SCAN ke same distance travel karta hai wahan; yeh sirf tab alag hote hain jab last request edge se short ho.
Sirf ek request exist karti hai, aur woh head ke peeche chosen direction mein hai. Kya hota hai?
SCAN/LOOK boundary tak jaate hain (ya, LOOK ke liye, immediately reverse karte hain), phir wapas aake use serve karte hain; chosen direction extra travel ka cost de sakta hai, jo dikhata hai ki direction kyun matter karta hai ek request ke liye bhi.
Do requests identical cylinders pe hain. Kya unke beech ka order total affect karta hai?
Nahi — doosra 0 distance add karta hai kyunki head already wahan hai; duplicate cylinders total head movement kabhi change nahi karte.
Head exact middle pe start karta hai symmetric requests ke saath. Kya direction choice total ke liye matter karta hai?
LOOK/SCAN ke liye ek symmetric layout mein up-first aur down-first equal totals de sakte hain, lekin C-SCAN phir bhi alag hota hai kyunki iska one-way jump design se asymmetric hai.
Recall Ek-line self-test
Agar koi kahe "C-SCAN best hai kyunki yeh circular aur efficient hai," to tera rebuttal kya hoga? ::: Circular ≠ chota travel; C-SCAN ek full-width empty return jump pay karta hai aur fairness/uniform wait optimize karta hai, total head movement nahi.
Head-movement pictures
Neeche teen figures hain jo parent note ke standard setup ke liye ek full service cycle mein head ka path dikhate hain (head start 53; queue 98, 183, 37, 122, 14, 124, 65, 67; range 0–199; up first). Horizontal axis ko cylinder number aur vertical axis ko neeche flow karte time ke roop mein padho — to ek diagonal line head ka sliding hai, aur iska total length wahi hai jo hum sum karte hain.
SCAN — 199 pe wall tak upar sweep karta hai, phir 14 tak neeche reverse karta hai:
LOOK — identical order, lekin wall ki jagah last request 183 pe reverse karta hai (saved stretch highlighted hai):
C-SCAN — 199 tak upar sweep karta hai, phir seedha 0 pe jump karta hai bina kuch serve kiye (dashed empty jump), aur upar resume karta hai:
Connections
- Parent topic
- SSTF (Shortest Seek Time First)
- Seek time vs Rotational latency
- Hard Disk Drive structure (cylinders, tracks, sectors)
- Starvation and Fairness in OS
- Process Scheduling — FCFS, SJF, Round Robin
- I/O Subsystem and Device Drivers