4.2.23 · D5 · HinglishOperating Systems
Question bank — Memory allocation — contiguous (first-fit, best-fit, worst-fit)
4.2.23 · D5· Coding › Operating Systems › Memory allocation — contiguous (first-fit, best-fit, worst-f
Pehle, in do symbols ko pakad lo jo yeh page baar baar use karta hai
Kisi bhi trap se pehle, hum un do letters ko pin down karte hain jo baar baar appear hote hain, taaki neeche koi line tumhe guess karwane na de.
Upar strip dekho: blue segment hole hai (), yellow part woh request hai jo uske andar land karti hai (), aur green tail leftover () hai jo ek naye, chhote hole ke roop mein bacha rehta hai.
Do fragmentations — ek picture jo inhe alag karti hai
Yeh do words cousins hain jinhe log constantly swap karte hain. Neeche ki figure dono ko ek hi strip par dikhati hai taaki tum inhe kabhi confuse na karo.
Top strip mein (external), processes ke beech red gaps milke kaafi free space banaate hain, phir bhi akela koi itna bada nahi. Bottom strip mein (internal), red slice block ke andar rehta hai, rounding se lock ho jaata hai.
Har scan ki cost kitni hai? (complexity picture)
Teen rules sirf kaunsa hole choose karte hain isme nahi, balki kitni der dekhte hain isme bhi differ karte hain. free holes ke saath:
Bars relative work dikhate hain: first-fit ka bar chhota aur variable hai (yeh kahin bhi ruk sakta hai), jabki best-fit aur worst-fit dono har baar poori list sweep karte hain.
"50% rule" kahan se aati hai (ek sketch)
Parent note 50% rule invoke karta hai first-fit ke liye. Yahan ek saanson mein kyun hai, taaki number magic na lage.
Figure allocated blocks (blue) aur chhote residual holes (red) jo unse paida hote hain, ko alternate karta hai — inhe gino aur dekho roughly do blocks par ek hole hai.
Compaction aur paging — fixes actually kya karte hain
Neeche ke links decoration nahi hain; har ek fragmentation se ek alag escape hai, aur figure mechanism dikhati hai.
Top row (compaction): fragmented strip → blocks left shift hote hain → ek merged free tail. Bottom row (paging): wohi process pages mein split ho jaati hai jo non-adjacent frames occupy karte hain, isliye kisi bhi contiguous hole ki zarurat nahi padti.
Sahi hai ya galat — justify karo
Sahi hai ya galat: best-fit hamesha lambe run mein first-fit se kam total wasted memory chhod ta hai.
Galat. Best-fit har allocation par leftover minimize karta hai, jo tiny unusable slivers shave karta hai jo pile up hote hain; empirically long-run fragmentation mein first-fit ≈ best-fit.
Sahi hai ya galat: agar total free memory request size se kam se kam barabar ho, toh contiguous allocation succeed karegi.
Galat. Free space kai holes mein split ho sakti hai; contiguity demand karti hai ek single hole , isliye 30+30 free milke 50 ki request serve nahi kar sakta.
Sahi hai ya galat: first-fit choose karne se pehle har free hole ka size compare karta hai.
Galat. First-fit address order mein scan karta hai aur pehle hole par ruk jaata hai — yeh kabhi candidate sizes compare nahi karta, isliye yeh fast hai.
Sahi hai ya galat: worst-fit har allocation mein sabse bada single leftover produce karta hai.
Sahi. Hamesha sabse bade hole se cut karke, us step ke liye leftover maximize ho jaata hai — lekin yeh per-step property hai, achhi utilization ki guarantee nahi.
Sahi hai ya galat: exact-size splitting ke saath, pure contiguous allocation internal fragmentation produce karta hai.
Galat. Jab har hole exactly requested size tak split ho, toh koi space block ke andar trapped nahi hota, isliye sirf external fragmentation hoti hai; internal fragmentation ke liye fixed-unit rounding chahiye.
Sahi hai ya galat: worst-fit sabse safe choice hai jab baad mein bade requests expected hain.
Galat. Worst-fit bade holes ko greedily burn karta hai, isliye ek bada future request sabse zyada starve hone ka chance hota hai — yeh usually utilization ke liye sabse bura hai.
Sahi hai ya galat: same request ke liye alag hole choose karna future mein kaunsi requests serve ho sakti hain, yeh badal deta hai.
Sahi. Chosen hole remaining holes ki shape aur sizes decide karta hai, isliye placement policy directly future success affect karti hai.
Sahi hai ya galat: agar har request kisi na kisi hole size ke exactly barabar ho, toh teeno algorithms identically behave karte hain.
Generally galat. Sab exact fit dhundh sakte hain (leftover 0), lekin jab multiple exact matches hote hain, toh tie-breaking (address order vs size) baad ke choices — aur baad ki successes — ko diverge kar sakta hai.
Error dhundho
Error dhundho: "First-fit woh sabse chhota hole pick karta hai jo kaafi bada ho, jaldi ruk jaata hai."
"Sabse chhota hole" waali baat galat hai — yeh best-fit describe karta hai. First-fit address order mein pehla fitting hole leta hai chahe size kuch bhi ho.
Error dhundho: "Best-fit poori free list scan nahi karta kyunki yeh ek achhe-enough hole par ruk jaata hai."
Galat — best-fit ko sure hone ke liye ki usne tightest fit dhundh liya, poori list scan karni padti hai (); sirf first-fit jaldi ruk sakta hai.
Error dhundho: "External fragmentation ka matlab hai allocated block ke andar unused bytes."
Yeh internal fragmentation hai. External fragmentation free memory hai jo allocated blocks ke beech bahut-chhote holes mein scattered hoti hai.
Error dhundho: "50% rule prove karta hai ki best-fit apne aadhe blocks fragmentation mein kho deta hai."
50% rule first-fit ka analysis hai: allocated blocks ke liye lagbhag additional fragmentation mein kho jaate hain — yeh best-fit ke baare mein koi statement nahi hai.
Error dhundho: "Compaction unnecessary hai kyunki worst-fit already holes ko bada rakhta hai."
Worst-fit ke bade leftovers bhi time ke saath fragment ho jaate hain; Compaction physically blocks relocate karta hai scattered free space merge karne ke liye, ek aisi problem solve karta hai jo koi bhi placement rule poori tarah prevent nahi kar sakta.
Error dhundho: "Kyunki best-fit leftover minimize karta hai, uske leftover holes sabse reusable hote hain."
Ulta — leftover minimize karne se sabse chhote holes bante hain, jo future requests ke liye reusable hone ki sabse kam sambhavna rakhte hain.
Kyun wale questions
Kyun external fragmentation exist karta hai agar hum total free memory sahi track kar rahe hain?
Kyunki processes ko ek single contiguous block chahiye; free memory plentiful ho sakti hai phir bhi pieces mein kati ho sakti hai jo har ek request se chhoti ho.
Kyun first-fit practical favorite hai jabki best-fit kabhi kabhi better pack karta hai?
Yeh average par best-fit jaisa achha hai phir bhi kaafi faster hai — iska scan jaldi ruk sakta hai ( best case) jabki best-fit hamesha hai.
Kyun best-fit bahut saare tiny "dead" slivers create karta hai?
Baar baar tightest hole choose karne se size ke leftovers shave hote hain jo sirf kuch units ke hote hain — kisi bhi cheez ke liye bahut chhote, isliye fragmentation ke roop mein accumulate hote hain.
Kyun worst-fit large future requests fail karta hai specifically?
Yeh pehle sabse bade holes consume karta hai, isliye koi bada hole ek subsequent bade request ke liye bach nahi paata chahe kaafi chhote holes bache hों.
Kyun placement rule badalna ek failing workload ko succeeding mein badal sakta hai?
Alag rules alag-sized residual holes chhod te hain; ek rule jo baad ke request ke liye ek hole preserve karta hai us request ko succeed karne deta hai jahan doosre rule ne us space ko fragment kar diya.
Kyun Paging external fragmentation bilkul khatam kar deta hai?
Yeh fixed-size pages ko kisi bhi free frames mein map karke contiguity requirement drop kar deta hai, isliye scattered free frames fully usable ho jaate hain.
Edge cases
Edge case: ek request jiska size exactly ek hole ke barabar ho — leftover kya hai aur hole ka kya hota hai?
Leftover , isliye hole free list se poori tarah gayab ho jaata hai.
Edge case: size 0 ki request aati hai — allocation ise kaise treat kare?
Koi bhi hole (conceptually size 0 bhi) "fit" hota hai kyunki ; practically 0-size request kuch allocate nahi karta aur free list unchanged rehti hai.
Edge case: free list empty hai lekin request chhoti hai — teeno rules kya karte hain?
Sab identically fail karte hain; bina kisi hole ke, koi rule nahi dhundh sakta, speed ya strategy se farq nahi padta.
Edge case: do holes best-fit mein "tightest" ke liye tie karte hain — kaunsa choose hota hai?
Tie convention se break hoti hai (usually address order mein pehla wala); chosen wala baad ke hole layout affect karta hai, isliye implementations mein yeh explicitly define hona chahiye.
Edge case: ek single hole poori free memory span karta hai aur request tiny hai — kya first-fit, best-fit, worst-fit differ karte hain?
Nahi. Exactly ek hole ke saath, teeno use pick karte hain; yeh sirf tabhi diverge karte hain jab multiple candidate holes exist karte hain.
Edge case: kaafi allocations aur frees ke baad, do adjacent free holes exist karte hain — kya contiguous allocation inhe merge karta hai?
Sirf agar Free List Management free hone par adjacent holes coalesce kare; coalescing ke bina yeh alag rahte hain aur milkar bade request serve nahi kar sakte.