Heap fragmentation: Exercises — Hinglish deep dive

5.1.17 · D4 · Coding › C Programming › Heap fragmentation

Yahan sirf do ideas reuse hoti hain parent se, jo yahan dobara state ki gayi hain taaki ye page akela khad rahe:

Level 1 — Recognition

L1.1

Har scenario ko external fragmentation, internal fragmentation, ya neither classify karo:

(a) Tum malloc(20) karte ho aur allocator 16-byte quantum + 8-byte header use karta hai, jisse 32-byte block milta hai.
(b) Total free = 40 bytes, do holes mein: 30 aur 10; malloc(40) NULL return karta hai.
(c) Tum malloc se ek block lete ho aur kabhi free nahi karte.

Recall Solution

(a) Internal. Extra bytes ek in-use block ke andar hain rounding + header ki wajah se — yahi internal fragmentation ki definition hai. (b) External. Free memory total mein kaafi hai (40) lekin non-contiguous holes mein split hai, isliye koi single hole 40 fit nahi kar sakta. Ye external fragmentation hai. (c) Neither — ye ek memory leak hai. Leaked memory kabhi return nahi hoti; fragmented memory free hoti hai par buri tarah arrange hoti hai. Bilkul alag bug hai.

L1.2

True ya false: "Agar malloc(n) fail kare, to heap bilkul full honi chahiye."

Recall Solution

False. Largest-hole rule ke mutabiq, malloc(n) tab fail karta hai jab koi single hole $\geq n$ na ho, chahe bahut saara total space free ho. Aadha-khali heap bhi ek request refuse kar sakta hai.

Level 2 — Application

L2 ke liye $h = 8$ (header) aur $a = 16$ (alignment) lo jab tak problem kuch aur na kahe.

L2.1

$r = 20$ ke liye $B (r)$ aur $W (r)$ compute karo.

Recall Solution

WHAT: Tool 1 mein plug karo. WHY: $r = 20$ plus header 16-boundary par nahi padta, isliye round up karna padega. $r + h = 20 + 8 = 28$ . $⌈ 28/16 ⌉ = ⌈ 1.75 ⌉ = 2$ . $B = 2 \cdot 16 = 32$ . $W = 32 - 20 = 12$ . Block = 32 bytes, wasted = 12 bytes.

L2.2

$r = 24$ ke liye $B (r)$ aur $W (r)$ compute karo.

Recall Solution

$r + h = 24 + 8 = 32$ . $⌈ 32/16 ⌉ = ⌈ 2.0 ⌉ = 2$ . $B = 32$ . $W = 32 - 24 = 8$ . Block = 32 bytes, wasted = 8 bytes. Note karo: zyada maangne par (24 vs 20) kam waste hua — kyunki 24 ek block boundary ke zyada paas hai.

L2.3

Tum 1000 allocations karte ho $r = 20$ bytes each (same $h = 8$ , $a = 16$ ). Total kitne bytes internal waste hain?

Recall Solution

L2.1 se, har aise allocation mein $W = 12$ bytes waste hote hain. WHY multiply: internal waste har allocation mein identically repeat hota hai, doosron se independent. $1000 \times 12 = 12000$ bytes $= 12$ kB wasted, un 20 kB ke upar jo tumne actually maange the.

L2.4

Ek allocator power-of-two size class scheme use karta hai (koi header nahi): $r$ ki request ko smallest power of two $\geq r$ tak round up kiya jaata hai. $r = 65$ ke liye $B$ aur $W$ dhundho.

Recall Solution

WHY ek naya rule: yahan "block size" set hai ${1, 2, 4, 8, 16, 32, 64, 128, \dots}$ , 16 ke multiples nahi. Hum $r$ ko nearest aise value tak round up karte hain. 65 ke aas-paas powers of two: $64 < 65 \leq 128$ . To $B = 128$ , $W = 128 - 65 = 63$ . Block = 128, wasted = 63 bytes — power-of-two classes boundary ke thik upar nearly 50% waste kar sakte hain.

Common mistake L2 trap: galat target par round karna

Ye sahi kyun lagta hai: tum request $r$ dekhte ho aur immediately use nearest block size tak round up karte ho, ye bhool jaate ho ki allocator ki apni bookkeeping bhi fit honi chahiye. Ye galat kyun hai: target jo tum round karte ho usse do alag cheezein determine karti hain. (1) Jab header present ho (jaise L2.1–L2.3 mein $h = 8$ ke saath), tumhe $r + h$ round karna chahiye, na ki $r$ — warna header usable bytes chura leta hai aur $B$ bahut chota aata hai. (2) Jab koi header nahi (jaise L2.4), tum $r$ khud round karte ho, par sahi size-class set par — yahan powers of two, 16 ke multiples nahi. Fix: pehle is allocator ka block-size rule padho ( $a$ ke multiples? powers of two?) aur check karo ki header $h$ hai ya nahi; sirf tab $r + h$ round karo jab header actually specified ho, phir sahi set par round karo.

Level 3 — Analysis

Ab hum ek live heap track karte hain. Heap 100 bytes ka hai, addresses [0,100). Allocator first-fit hai (left se scan karta hai, pehla kaafi bada hole leta hai), aur kisi freed block ko uske physically adjacent free neighbour ke saath coalesce karta hai. L3 ke liye headers/alignment ignore karo (har malloc(n) exactly $n$ bytes leta hai). Har region [start, size) likh ke dikhaya gaya hai jaisa upar define kiya gaya.

Neeche ki figure L3.1 ka run dikhati hai taaki tum holes bante dekh sako.

L3.1

Order mein execute karo: A=malloc(30), B=malloc(30), C=malloc(30), free(B). Phir malloc(40) try karo. Free-list kya hai, aur kya malloc(40) succeed karta hai?

Recall Solution

Layout trace karo (■ used, · free), saare regions [start, size) mein:

A=malloc(30) → A leta hai [0,30). Free: [30,70).
B=malloc(30) → first-fit [30,30) leta hai. Free: [60,40).
C=malloc(30) → leta hai [60,30). Free: [90,10).
free(B) → B ka region [30,30) return hota hai. Left neighbour A used hai, right neighbour C used hai → koi coalescing nahi. Free-list ban jaata hai [30,30) aur [90,10).

Total free $= 30 + 10 = 40$ . Par malloc(40) scan karta hai: hole [30,30) ka size 30 hai (✗), hole [90,10) ka size 10 hai (✗). Koi single hole $\geq 40$ nahi ⇒ malloc(40) NULL return karta hai. Classic external fragmentation — live block C dono holes ko alag kar ke rokta hai.

L3.2

L3.1 ke end state se shuru karo (holes [30,30) aur [90,10), A aur C live hain). Ab free(C) karo. Free-list ka kya hoga, aur kya malloc(40) ab succeed karta hai?

Recall Solution

WHAT: C address 60 se start hone wale region mein hai, size 30 ke saath, yaani [60,30) (addresses 60 se 90 tak). WHY it matters: address se dono neighbours check karo. C ka left neighbour hole [30,30) hai (addresses 30 se 60 tak) — free. C ka right neighbour hole [90,10) hai (addresses 90 se 100 tak) — free. Coalescing teeno adjacent regions ko merge karta hai — addresses 30 se 60, 60 se 90, aur 90 se 100 — ek region mein jo addresses 30 se 100 tak cover karta hai, yaani [30,70) (size 70). Free-list: [30,70). Ab malloc(40) ek 70-byte hole paata hai → succeed karta hai. "Fence" free karne se holes fuse ho gayi.

L3.3

Fragmentation ratio define karo $F = 1 - \frac{largest free hole}{total free bytes}$ (to $F = 0$ ka matlab hai saara free space ek hole mein hai; $F$ near 1 ka matlab hai buri tarah scattered). L3.1 ke end-state ke liye $F$ compute karo.

Recall Solution

L3.1 ka end: total free $= 40$ , largest hole $= 30$ . $F = 1 - \frac{30}{40} = 1 - 0.75 = 0.25.$ $F = 0.25$ . Free space ka ek-chauthai hissa biggest usable hole se aage "stranded" hai. (L3.2 ke coalesce ke baad, largest hole = total = 70, to $F = 0$ .)

Level 4 — Synthesis

L4.1

Tumhe ek 150-byte heap mein 5 blocks of 30 bytes each allocate karne hain, phir saare 5 free karne hain, baar baar ek loop mein. Tum free order choose kar sakte ho. Kaun sa order guarantee karta hai ki heap har cycle mein ek 150-byte hole mein return ho, aur kyun? Ek bure order se contrast karo.

Recall Solution

Good order: LIFO / stack order — sabse recently allocated pehle free karo. Allocations left-to-right blocks rakhti hain: $A [0, 30), B [30, 30), C [60, 30), D [90, 30), E [120, 30)$ (saare [start, size) mein). E pehle free karo: uski right side heap-end hai (free), left side D live hai → E ban jaata hai hole [120,30). D free karo: right neighbour [120,30) ab free hai → coalesce ho ke [90,60) ban jaata hai. C, B, A continue karo — har free growing right-hand hole ke saath coalesce karta hai. End: ek [0,150) hole. $F = 0$ . Bad order: pehle middle free karo (jaise C, phir A, phir E, phir B, phir D). C free karne se ek isolated [60,30) hole banta hai jo live B aur D se fenced hai — koi coalesce tab tak nahi hoga jab tak uske neighbours bhi nahi jaate. Interior frees temporarily scattered holes banate hain aur mid-cycle peak fragmentation ratio badhate hain, chahe end state eventually merge ho jaye. Rule learned: reverse order of allocation mein free karo (jaisa stack automatically karta hai) taaki har free adjacent growing hole ko touch kare.

L4.2

Tum bahut saare objects allocate karte ho same size $r = 20$ ( $h = 8$ , $a = 16$ ). Explain karo ki kyun ek pool allocator external fragmentation khatam kar deta hai lekin har ek ke 12 bytes ka internal waste nahi hatata.

Recall Solution

External gone: ek pool heap ko identical 32-byte slots ki grid mein carve karta hai. Har free slot interchangeable hai aur exactly ek request ke size ka hai, isliye ek free slot hamesha next request serve kar sakta hai — kabhi "hole too small" nahi hogi, isliye koi external fragmentation nahi. Internal stays: slot size abhi bhi $B (20) = 32$ hai (L2.1 se), isliye har in-use slot abhi bhi $W = 12$ bytes andar waste karta hai. Pool fix karta hai kahan free space hai, na kitna waste rounding create karta hai. 12 bytes khatam karne ke liye tumhe requested/slot size change karni padegi taaki wo boundary se match kare (Tool-1 thinking).

L4.3

Ek compacting garbage collector L3.1 ke fragmented end-state mein malloc(40) serve kar sakta hai bina C free kiye. Kaise, aur uski kya cost hai jo plain malloc/free kabhi nahi deta?

Recall Solution

Ek compacting GC live objects ko physically move karta hai taaki saara free space ek contiguous region mein aa jaye: wo C ko [60,30) se shift karke [30,30) par le ja sakta hai, do holes ko merge karke [60,40) bana sakta hai (addresses 60 se 100 tak, size 40) — ab malloc(40) fit ho jaata hai, jabki C abhi bhi alive hai. The cost: ek object ko move karne se uska address badal jaata hai, isliye uski taraf point karne wale har pointer ko update karna padega (GC ko saare references dhundhne aur rewrite karne hote hain). Plain C malloc/free kabhi ek live block move nahi kar sakta, kyunki usse nahi pata kaun uski taraf point kar raha hai — yehi wajah hai ki manual heaps fragmented rehte hain.

Level 5 — Mastery

L5.1

Ek allocator mein $h = 16$ , $a = 64$ hai. Ek program $N = 2000$ allocations karta hai $r = 100$ bytes each. (a) $B$ aur $W$ per allocation find karo. (b) Total internal waste. (c) Overhead ratio kya hai = total block bytes ÷ total requested bytes, percentage mein 1 decimal tak rounded?

Recall Solution

(a) $r + h = 100 + 16 = 116$ . $⌈ 116/64 ⌉ = ⌈ 1.8125 ⌉ = 2$ . $B = 2 \cdot 64 = 128$ . $W = 128 - 100 = 28$ . (b) Total waste $= 2000 \times 28 = 56000$ bytes $= 56$ kB. (c) Total block bytes $= 2000 \times 128 = 256000$ . Total requested $= 2000 \times 100 = 200000$ . $overhead = \frac{256000}{200000} \times 100% = 128.0%.$ Tum physically 28% zyada heap consume karte ho jo tumne maanga tha (ratio 128.0% of requests).

L5.2

200 bytes ka heap, first-fit, coalescing, koi header/alignment nahi. Saare regions [start, size) mein likhe gaye hain. Run karo: A=malloc(50), B=malloc(60), C=malloc(40), free(A), D=malloc(30), free(C), E=malloc(45). Final free-list do aur batao ki E succeed hua ya nahi.

Recall Solution

Har region ko 200-byte heap mein [start, size) mein track karo:

A=malloc(50) → A [0,50) (addresses 0 se 50 tak). Free: [50,150).
B=malloc(60) → B [50,60) (addresses 50 se 110 tak). Free: [110,90).
C=malloc(40) → C [110,40) (addresses 110 se 150 tak). Free: [150,50).
free(A) → A ka region [0,50) free hua; left = heap start, right neighbour B live hai → koi coalesce nahi. Free: [0,50), [150,50).
D=malloc(30) → first-fit left se scan karta hai, hole [0,50) 30 fit karta hai → D [0,30). Free: [30,20), [150,50).
free(C) → C ka region [110,40) free hua; left neighbour B [50,60) (110 par khatam hota hai) live hai, right neighbour [150,50) free hai aur exactly 150 par start hota hai = C ka end → coalesce → [110,90). Free: [30,20), [110,90).
E=malloc(45) → scan: [30,20) ka size 20 hai (✗), [110,90) ka size 90 hai (✓) → E leta hai [110,45) (addresses 110 se 155 tak). Free: [30,20), [155,45).

E succeed hua ([110,45) par placed). Final free-list: [30,20) aur [155,45), total free $= 65$ .

L5.3

L5.2 ke end-state se continue karo (free holes [30,20) aur [155,45), total free 65), ek request malloc(60) aati hai. (a) Kya ye succeed karta hai? (b) Fragmentation ratio $F = 1 - \frac{largest hole}{total free}$ compute karo. (c) Ek free malloc(60) ko succeed kara sakta hai — kaun sa live block, aur kyun?

Recall Solution

(a) Largest hole $= 45 < 60$ ⇒ malloc(60) fail karta hai (NULL), 65 total free bytes hone ke bawajood — largest-hole rule. (b) $F = 1 - \frac{45}{65} = 1 - 0.6923 \dots = 0.3077 \approx 0.308$ . Roughly 31% free space biggest hole se bahar stranded hai. (c) Block E [110,45) free karo. Kyun E aur koi nahi: E ka region addresses 110 se 155 tak hai, isliye uska right neighbour free hole [155,45) hai (exactly 155 par start hota hai = E ka end). E free karne se [155,45) ke saath coalesce ho ke ek hole [110,90) ban jaata hai size 90 ke saath $\geq 60$ — isliye free(E) ke baad malloc(60) succeed karta hai. Kyun alternatives fail karte hain: D [0,30) free karne se sirf uske right neighbour [30,20) ke saath merge ho ke 50-byte hole banta hai ( $50 < 60$ , abhi bhi bahut chota). B [50,60) (addresses 50 se 110 tak) free karne se uske right neighbour ke saath merge hoga... jo E free karne ke baad free hoga, lekin akele B ka left neighbour live D-region hai aur right neighbour live E hai — isliye sirf B free karne se ek 60-byte hole [50,60) ban jaata hai jo exactly 60 ke barabar hai, lekin B ek live block hai jo tumhe abhi bhi chahiye ho sakta hai, aur question pucha hai ki kaun sa single free request ko cleanly unlock karta hai. E sahi answer hai kyunki wo do existing regions ko fuse karke ek 90-byte hole banata hai bina kisi ambiguity ke.

Connections

Heap fragmentation — parent theory jinhe ye exercises drill karte hain.
malloc and free — first-fit + coalescing behaviour jo har L3–L5 trace model karta hai.
Stack vs Heap — kyun L4.1 mein LIFO free order defragment karta hai (stack ye apne aap karta hai).
Memory alignment — ceiling term ka source jo har L2/L5 waste calc mein hai.
Pool allocator / Arena allocator — L4.2 fix external fragmentation ke liye.
Garbage collection — L4.3 compaction jo plain C nahi kar sakta.
Memory leaks — L1.1(c) mein contrast kiya gaya: free-but-scattered vs never-freed.

Recall Master check (cloze)

malloc(n) succeed karta hai tabhi jab the largest single free hole is at least n bytes ho (total nahi). Coalescing ek freed block ko sirf us neighbour ke saath merge karta hai jo physically adjacent and also free ho. Block size formula ::: $B (r) = ⌈(r + h) / a ⌉ \cdot a$ , waste $W = B - r$ . $r = 100, h = 16, a = 64$ ke liye waste per block hai ::: 28 bytes. Fragmentation ratio $F = 1 - \frac{largest hole}{total free}$ ; $F = 0$ ka matlab hai ::: all free space is one contiguous hole.