Memory allocation — contiguous (first-fit, best-fit, worst-fit)

4.2.23 · Coding › Operating Systems

Contiguous allocation HAI kya?

Placement policy ki ZAROORAT kyun hai?

Memory finite hai aur requests unpredictable order mein aati hain. Kai allocations/frees ke baad free list Swiss cheese jaisi dikhne lagti hai. Aap kaun sa hole chunte hain, isse baaki hue holes ki shape change ho jaati hai, aur isliye future requests succeed hongi ya nahi. Koi ek best rule nahi hai — har ek speed, fragmentation, aur leftover usefulness ke beech trade-off karta hai.

HOW — har algorithm kaise choose karta hai

Figure — Memory allocation — contiguous (first-fit, best-fit, worst-fit)

Worked Example 1 — same requests, teen rules

Holes (address order mein): A=100, B=500, C=200, D=300, E=600 (KB). Process requests: P1=212, P2=417, P3=112, P4=426 (KB).

First-fit

P1=212 → pehla hole $\geq 212$ : B(500). Leftover B=288. (Kyun? A=100<212, B=500≥212, ruko.)
P2=417 → scan A=100, B=288, C=200, D=300, E(600) ≥417. Leftover E=183.
P3=112 → A(100)? nahi, 100<112. B=288≥112 → B. Leftover B=176.
P4=426 → A=100, B=176, C=200, D=300, E=183 — koi bhi ≥426 nahi. P4 FAIL.

Best-fit

P1=212 → candidates ≥212: B=500, D=300, E=600. Sabse chhhota = D(300). Leftover D=88.
P2=417 → candidates ≥417: B=500, E=600. Sabse chhhota = B(500). Leftover B=83.
P3=112 → candidates ≥112: A? 100 nahi. C=200, D=88? nahi, E=600, B=83 nahi. {C=200, E=600} mein sabse chhhota = C(200). Leftover C=88.
P4=426 → candidates ≥426: E(600). Leftover E=174. Chaaro succeed!

Worst-fit

P1=212 → sabse bada hole = E(600). Leftover E=388.
P2=417 → sabse bada = B(500). Leftover B=83.
P3=112 → sabse bada = E=388 → E. Leftover E=276.
P4=426 → abhi sabse bada = E=276 <426, B=83, A=100, C=200, D=300 — koi ≥426 nahi. P4 FAIL.

Worked Example 2 — kyun best-fit slivers create kar sakta hai

Holes: 20, 15, 13. Requests: 12, 12, 12.

Best-fit P1=12 → tightest ≥12 = 13 → leftover 1 (dead sliver).
Best-fit P2=12 → tightest = 15 → leftover 3 (dead).
Best-fit P3=12 → sirf 20 bacha → leftover 8. Ab teen useless slivers (1,3,8) total 12 KB lekin koi bhi single hole future 12-request ke kaam ka nahi.

Common Mistakes

Recall Feynman: 12-saal ke bachche ko samjhaao

Ek parking lot socho. Cars programs hain, cars ke beech ki parking spaces "holes" hain. Ek bus ko kaafi empty spots ek saath chahiye — woh khud ko lot mein alag-alag nahi kar sakti. First-fit: bus pehli itni badi jagah park kar leti hai — jaldi, par shayad wasteful. Best-fit: sabse tight jagah dhundhte hain taaki almost koi space waste na ho — lekin aap bahut saari tiny slots chhodh dete ho jo koi car nahi chahti. Worst-fit: hamesha sabse badi jagah park karo taaki leftover phir bhi bada aur useful rahe — lekin phir badi buses ko baad mein kahin jaane ki jagah nahi milti. Koi perfect rule nahi hai; yeh depend karta hai ki aage kaun aata hai.

Active Recall

"Contiguous" memory allocation ek process ke liye kya require karta hai?

Physical memory ka ek single unbroken block jiska size ≥ request ho.

First-fit selection rule?

Pehla hole (address order mein) choose karo jo itna bada ho; scanning band karo.

Best-fit selection rule?

Sabse chhhota hole choose karo jo phir bhi ≥ request ho (tightest fit).

Worst-fit selection rule?

Sabse bada available hole choose karo.

Size s ko hole H mein place karne ke baad leftover?

H − s; agar 0 toh hole gayab, warna ek chhhota hole bachta hai.

External vs internal fragmentation?

External = total free memory kaafi hai lekin bahut-chhhote holes mein batti hui. Internal = allocated block ke andar unused space.

Best-fit "smallest leftover" ke bawajood long-run fragmentation kyun zyada create kar sakta hai?

Tiny leftovers jama hokar bahut saari unusable slivers ban jaati hain.

Kaun se do algorithms poori free list scan karte hain?

Best-fit aur worst-fit (first-fit jaldi ruk jaata hai).

Kaun sa algorithm generally sabse fast aur near-optimal in practice hai?

First-fit.

First-fit ka 50% rule kya kehta hai?

N allocated blocks ke liye, lagbhag N/2 fragmentation mein kho jaate hain.

Kya request fail ho sakti hai jab total free memory ≥ request ho?

Haan — kyunki free space contiguous nahi ho sakti.

Worst-fit ka intended advantage aur uski real weakness?

Ek bada reusable leftover chodta hai; lekin bade holes jaldi khatam kar deta hai isliye badi future requests bhookhi reh jaati hain.

Connections

Paging — contiguity requirement hatakar external fragmentation khatam karta hai.
Segmentation — har logical segment ke liye variable-size contiguous chunks.
Virtual Memory — in placement ideas ko page granularity par build karta hai.
Compaction — holes merge karne ke liye blocks relocate karta hai; external fragmentation ka ilaaj.
Buddy System — power-of-two blocks wala alternative allocator.
Free List Management — woh data structure jise yeh policies scan karti hain.
Fragmentation — internal vs external, core cost metric.