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

4.2.23 · D3 · Coding › Operating Systems › Memory allocation — contiguous (first-fit, best-fit, worst-f

Shuru karne se pehle, ek symbol jo hum baar baar use karte hain:

Scenario matrix

Har case jo ek contiguous-allocation problem tumhare saath kar sakti hai, in cells mein se ek hai. Neeche har worked example ko us cell ke saath tag kiya gaya hai jo wo cover karta hai.

Cell	Case class	Kya unusual hai	Covered by
C1	Exact fit ( $H = s$ , leftover $= 0$ )	hole poori tarah khatam ho jaata hai	Ex 1
C2	Tie — do holes equally "best" ya "worst"	tie-break rule (lowest address)	Ex 2
C3	Request fail: koi hole itna bada nahi	allocation failure return karta hai	Ex 3
C4	Fail hota hai jabki total free ≥ request	fragmentation, kami nahi	Ex 3
C5	Zero / degenerate input ( $s = 0$ , empty free list)	boundary behaviour	Ex 4
C6	Sliver accumulation (best-fit worst case)	chote dead leftovers pile up ho jaate hain	Ex 5
C7	Big-hole starvation (worst-fit weakness)	badi future request starve ho jaati hai	Ex 6
C8	Same workload, teeno rules alag result	rule choice success change kar deta hai	Ex 7
C9	Real-world word problem (parking lot / disk)	story → holes mein translate karo	Ex 8
C10	Exam twist: 50% rule / free hone ke baad holes merge hote hain	analysis + coalescing	Ex 9, Ex 10

Hum holes-ki-shelf idea ek baar visualise karte hain taaki baad ke har example isko lean kar sake:

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

Step 1. Holes list karo jo $∣ h ∣ \geq 250$ satisfy karte hain: B=250, C=400. Ye step kyun? Best-fit sirf unhi holes mein se choose karta hai jo actually fit hote hain. A=100 turant disqualify ho jaata hai ( $100 < 250$ ).

Step 2. Sabse chhota qualifying hole pick karo. 250 aur 400 mein sabse chhota B=250 hai. Ye step kyun? "Best-fit = tightest fit" matlab minimum $∣ h ∣ - s$ ; yahan $250 - 250 = 0$ , possible tightest.

Step 3. Leftover compute karo: $H - s = 250 - 250 = 0$ . Ye step kyun? Leftover formula shard size batata hai. Zero leftover matlab hole poori tarah consume ho gaya aur free list se remove ho gaya — 0-size hole ki tarah nahi raha.

Result: B poori tarah disappear ho gaya. Free list ban gayi A=100, C=400.

Verify: leftover $= 250 - 250 = 0$ ; remaining free total $= 100 + 400 = 500$ ; original free tha $100 + 250 + 400 = 750$ ; humne 250 allocate kiya, toh $750 - 250 = 500$ . ✓

Ex 2 — Tie-break (Cell C2)

Step 1. Qualifying holes ( $\geq 180$ ): A=300, B=200, C=300. Sabse chhota B=200 hai. Ye step kyun? Ruko — B=200 dono 300 se chhota hai aur phir bhi $\geq 180$ hai. Toh best-fit ke liye yahan koi tie nahi hai; B outright jeet jaata hai.

Step 2. Lekin maan lo request P=250 hoti. Ab qualifying holes hain A=300, C=300 (B=200 fail). Dono size 300 hain — asli tie. Ye step kyun? Humne actual tie engineer ki taaki tum rule dekh sako.

Step 3. Tie-break: lowest address (list mein pehle) waala hole choose karo. Toh A, C nahi. Ye step kyun? Jab sizes equal hoon, standard convention address order hai — ye algorithm ko deterministic banata hai aur free list traverse hone ke tarike se match karta hai.

Result: P=250 ke liye, best-fit A pick karta hai, leftover $= 300 - 250 = 50$ ; C 300 hi rehta hai.

Verify: leftover $= 300 - 250 = 50$ ; free list ban jaati hai A=50, B=200, C=300, total $= 550$ ; original $= 800$ ; $800 - 250 = 550$ . ✓

Ex 3 — Kaafi free memory hone ke bawajood failure (Cells C3, C4)

Step 1. Total free $= 30 + 30 + 30 + 30 = 120 \geq 50$ . Tempting hai "haan" bolne ka. Ye step kyun? Trap expose karne ke liye: free memory add karna galat test hai.

Step 2. Contiguity requirement apply karo: ek request ko ek single hole $\geq s$ chahiye. Har hole scan karo: sabke liye $30 < 50$ . Ye step kyun? Contiguous allocation do holes ko stitch nahi kar sakta. Chahe koi bhi rule ho (first/best/worst), qualifying holes ka set empty hai.

Step 3. Kyunki koi hole qualify nahi karta, allocation fail ho jaata hai — teeno rules ke liye identical.

Result: P=50 FAIL ho jaata hai chahe 120 KB free ho. Ye pure external fragmentation hai.

Verify: $max (30, 30, 30, 30) = 30 < 50$ toh koi single hole fit nahi hota; total $= 120 \geq 50$ lekin contiguous allocator ke liye ye irrelevant hai. ✓

Ex 4 — Degenerate inputs (Cell C5)

Step 1 — (a) $s = 0$ . Koi bhi hole (ya koi nahi) $∣ h ∣ \geq 0$ satisfy karta hai. Ek well-behaved allocator 0-size request ko no-op treat karta hai: kuch allocate nahi karta, free list untouched rehti hai. Ye step kyun? Condition $∣ h ∣ \geq s$ trivially true hai, toh first-fit pehla hole "pick" kar leta aur leftover $H - 0 = H$ ke saath split karta — yaani koi change nahi. Reject/ignore karna sabse clean hai.

Step 2 — (b) empty free list. Scan karne ke liye zero holes hain. Har rule failure immediately return karta hai. Ye step kyun? Teeno rules free list scan karke shuru hote hain; empty list se empty candidate set milta hai → fail. Koi special case nahi chahiye.

Step 3 — (c) exact whole-hole request. Ek hole bacha hai, maano H=400, request P=400. Leftover $= 400 - 400 = 0$ , hole remove, free list empty ho jaati hai. Ye step kyun? Ex 1 jaisi hi mechanic lekin memory khaali kar deta hai. Confirm karta hai exact fit boundary par bhi kaam karta hai.

Result: (a) no-op, (b) fail, (c) free list khaali hoke succeed.

Verify: (a) leftover $= H - 0 = H$ ⇒ free unchanged. (b) candidate count $= 0$ ⇒ fail. (c) $400 - 400 = 0$ ⇒ list empty. ✓

Ex 5 — Best-fit memory ko sliver kar deta hai (Cell C6)

Step 1. P1=12. Qualifying ( $\geq 12$ ): 20, 15, 13. Tightest = 13, leftover $= 13 - 12 = 1$ . Ye step kyun? Best-fit closest match leta hai, 1 KB sliver shave off karta hai — itna chhota ki kabhi reuse nahi hoga.

Step 2. P2=12. Remaining holes: 20, 15, (1). Qualifying: 20, 15. Tightest = 15, leftover $= 15 - 12 = 3$ . Ye step kyun? Phir ek chhota 3 KB dead shard paida ho gaya.

Step 3. P3=12. Remaining: 20, (3), (1). Qualifying: sirf 20. Leftover $= 20 - 12 = 8$ . Ye step kyun? Ab bada hole bhi 8 KB shard yield kar raha hai.

Result: leftovers 1, 3, 8 — total $12$ KB free lekin koi single hole ≥ 12 nahi. Ek fourth P4=12 FAIL ho jaata.

Verify: leftovers $13 - 12 = 1$ , $15 - 12 = 3$ , $20 - 12 = 8$ ; $max (1, 3, 8) = 8 < 12$ toh 4th request of 12 fail; sum $= 12$ . ✓

Ex 6 — Worst-fit ek badi request ko starve kar deta hai (Cell C7)

Step 1. P1=200. Sabse bada hole = 600, leftover $= 600 - 200 = 400$ . Ye step kyun? Worst-fit hamesha sabse bade hole ko kaatta hai, umeed mein ki baaki hissa useful rahega.

Step 2. P2=200. Holes ab 400, 500, 300 hain. Sabse bada = 500, leftover $= 500 - 200 = 300$ . Ye step kyun? Humne abhi dusre-sabse-bade hole ko bhi kha liya.

Step 3. P3=450. Holes ab 400, 300, 300 hain. Sabse bada = 400 $< 450$ — aur koi bhi hole $\geq 450$ nahi. FAILS. Ye step kyun? Sabse bade holes pe requests spread karke, worst-fit ne dono bade holes barbaad kar diye; 450 ke liye jagah nahi bachi.

Result: 450 FAIL ho jaata hai — bilkul wahi starvation jiski parent ne warning di thi.

Verify: do placements ke baad holes hain ${600 - 200, 500 - 200, 300} = {400, 300, 300}$ ; $max = 400 < 450$ ⇒ fail. ✓

Ex 7 — Same workload, teeno rules alag raaste (Cell C8)

Step 1 — First-fit. P1→B(500), lo 288. P2→E(600), lo 183. P3→B(288)→176. P4: holes {100,176,200,300,183}, max=300<426 → FAIL. Ye step kyun? First-fit har baar pehli fit pe ruk jaata hai — koi size comparison nahi — toh P4 ke liye koi bada enough hole nahi bachा.

Step 2 — Best-fit. P1→D(300)lo88. P2→B(500)lo83. P3→C(200)lo88. P4→E(600)lo174. SARE SUCCEED. Ye step kyun? Tightest fits ne E=600 ko tab tak untouched rakha jab tak P4 ko zaroorat nahi padi.

Step 3 — Worst-fit. P1→E(600)lo388. P2→B(500)lo83. P3→E(388)lo276. P4: max hole 300<426 → FAIL. Ye step kyun? Worst-fit ne bade holes pehle kha liye; 426 starve ho gaya.

Result: Best-fit charon place karta hai; first-fit aur worst-fit P4 ko strand karte hain.

Verify (best-fit leftovers): $300 - 212 = 88$ , $500 - 417 = 83$ , $200 - 112 = 88$ , $600 - 426 = 174$ , sab $\geq 0$ ⇒ sab succeed. ✓

Ex 8 — Word problem: parking lot (Cell C9)

Step 1. Car 4 m, first-fit: scan 5≥4 → gap-1 mein park. Leftover $5 - 4 = 1$ . Ye step kyun? First-fit pehla gap leta hai jo fit ho, street ke saath position order mein.

Step 2. Van 7 m: scan 1(no), 8≥7 → gap-2. Leftover $8 - 7 = 1$ . Ye step kyun? 1 m bahut chhota hai; 8 m pehla fit hai.

Step 3. Bus 11 m: scan 1,1,3,12≥11 → gap-4. Leftover $12 - 11 = 1$ . Ye step kyun? First-fit 12 m gap tak pahuncha aur park kar liya. Bus succeed karti hai.

Result: teeno park ho jaate hain; leftovers teen useless 1 m slivers hain.

Verify: leftovers $5 - 4 = 1$ , $8 - 7 = 1$ , $12 - 11 = 1$ ; bus ka chosen gap $12 \geq 11$ ⇒ parks. ✓

Ex 9 — Exam twist: 50% rule (Cell C10)

Step 1. 50% rule (first-fit ka ek classic analysis) kehta hai: $N$ allocated blocks ke liye, roughly $0.5 N$ blocks ka memory fragmentation mein kho jaata hai. Ye step kyun? Ye ek empirical/analytical result hai jo parent ki mistakes section mein quoted hai — exam number $N /2$ expect karta hai.

Step 2. Lost $= 0.5 \times 1000 = 500$ block-equivalents compute karo. Ye step kyun? Direct substitution.

Step 3. Free memory ka fraction jo unusable hai: free $= 0.4 N = 400$ blocks; lekin rule fragmentation ko allocated ke relative count karta hai. Ek common exam form: agar memory $=$ allocated $+$ free $= 1000 + 400 = 1400$ blocks aur $\approx 500$ fragmentation-bound hain free/hole structure mein, wasted fraction $\approx \frac{500}{1400} \approx 0.357 = 35.7%$ . Ye step kyun? Dikhata hai count ko percentage mein kaise convert karein jo exam chahta hai.

Result: $\approx 500$ blocks lost; $\approx 35.7%$ total memory affected.

Verify: $0.5 \times 1000 = 500$ ; $500/1400 = 0.357 \dots$ ✓

Ex 10 — Exam twist: free() holes coalesce karta hai (Cell C10)

Step 1. 60 block ko free karne se wo hole ban jaata hai. Ab address order hai: [hole 40][hole 60][hole 30][used 50][hole 20]. Ye step kyun? free() ek allocated block ko wapas hole mein convert karta hai — lekin adjacency agle step mein matter karti hai.

Step 2. Coalescing: adjacent holes merge ho jaate hain. 40 aur newly-freed 60 neighbours hain ⇒ 100 mein merge. 30 unke baad hai lekin 100 se alag hai? Adjacency check karo: order hai 40,60,30 sab address mein contiguous hain (pehle teen ke beech koi used block nahi) ⇒ ye $40 + 60 + 30 = 130$ mein merge ho jaate hain. Ye step kyun? Compaction aur Free List Management neighbours merge karne par rely karte hain taaki holes artificially fragmented na rahein. Sirf address-adjacent holes merge hote hain.

Step 3. Nayi free list: [hole 130][used 50][hole 20]. Request 120: koi hole $\geq 120$ hai? Haan, 130. SUCCEED karta hai, leftover $130 - 120 = 10$ . Ye step kyun? Coalescing ne teen chhote holes ko ek itne bade hole mein convert kar diya jo fit ho gaya — wo request jo pehle fail hoti ab fit ho gayi.

Result: coalescing ke baad free list = 130, 20; 120 request leftover 10 ke saath succeed karti hai.

Verify: merged hole $= 40 + 60 + 30 = 130 \geq 120$ ; leftover $= 130 - 120 = 10$ ; un-merged max $= 60 < 120$ toh coalescing zaroori tha. ✓

Active Recall

Kya hota hai jab request chosen hole size ke exactly barabar ho?

Leftover 0 hota hai, hole free list se remove ho jaata hai — zero fragmentation.

Best-fit tie-break rule jab do holes equally tight hoon?

Lowest address (list mein pehle) waala hole choose karo.

Kya 50 KB request fail ho sakti hai jab char 30 KB holes (120 KB total) free hoon?

Haan — koi single contiguous hole ≥ 50 nahi; total free irrelevant hai.

First-fit allocator size-0 request ke saath kya karta hai?

Kuch nahi — ye no-op hai; free list unchanged rehti hai.

Worst-fit badi future requests ko kyun starve karta hai?

Ye pehle sabse bade holes consume karta hai, baad ki badi request ke liye koi large hole nahi bachta.

Jab koi block free ho, address-adjacent holes ke saath kya hona chahiye?

Ye coalesce (merge) ho jaate hain ek bade hole mein.

50% rule N allocated blocks ke liye kitna loss predict karta hai?

Roughly N/2 blocks ka fragmentation mein loss.

Connections

Paging — contiguity hatata hai toh Ex 3 ki failure kabhi nahi hoti.
Compaction — blocks slide karta hai scattered holes merge karne ke liye (Ex 3, Ex 5 fix karta hai).
Free List Management — Ex 10 ka coalescing yahan hota hai.
Fragmentation — Ex 5 ka sliver accumulation quantified.
Buddy System — ek alternative allocator power-of-two rounding ke saath.
Segmentation · Virtual Memory — in placement ideas par build karte hain.

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