Heap fragmentation: Foundations — Hinglish deep dive

5.1.17 · D1 · Coding › C Programming › Heap fragmentation

Parent note Heap fragmentation follow karne se pehle, tumhe usmein use hone wala har word aur symbol apna banana hoga. Hum har ek ko zero se build karte hain, ek aisi order mein jahan har cheez pichli cheez par tikti hai.

1. Ek byte, aur memory as a ruler of numbered boxes

Figure dekho: boxes ko ek single row mein draw kiya gaya hai kyunki yahi sach hai — memory one-dimensional hoti hai. Box 0, phir box 1, phir box 2, numbering mein koi gap nahi. Jab parent note ek "100 bytes ka" heap likhta hai, iska matlab hai boxes 0 se 99 tak.

Yeh topic kyun zaroori hai: fragmentation ka poora idea is ruler par positions ke baare mein hai. "Adjacent", "contiguous", "a gap" — ye sab statements hain box numbers ke ek doosre ke paas hone ke baare mein. Ruler picture ke bina, baad ke words ka koi matlab nahi.

2. Contiguous — woh word jo fragmentation possible banata hai

Yeh topic kyun zaroori hai: parent note ka key sentence — "malloc must return a single contiguous range" — yahi wajah hai ki fragmentation hoti hi hai. Agar memory scattered pieces mein di ja sakti, toh fragmentation ki koi problem hi nahi hoti.

3. Heap — woh box-region jise tum rent karte ho

Kisi bhi order mein free karne ki freedom hi woh cheez hai jo holes ko awkward jagahon par aane deti hai. In do functions ki mechanics ke liye malloc and free dekho.

Yeh topic kyun zaroori hai: fragmentation ek heap phenomenon hai. Stack, strict order mein free karte hue, kabhi fragment nahi hota — ek fact jo parent note batata hai aur hum section 7 mein samajhte hain.

4. Ek "block", ek "hole", aur free-list

Pair notation $(start, size)$ ka matlab hai: "ek hole box start par shuru hota hai aur size boxes lamba hai." Toh $(30, 30)$ ka matlab hai boxes 30, 31, ..., 59 free hain — woh hai start = 30 aur size = 30, jo last free box ko $30 + 30 - 1 = 59$ deta hai.

Half-open bracket $[a, b)$ jo parent use karta hai wahi run batata hai: boxes a se lekin b include nahi tak. Toh $[30, 60)$ = boxes 30 se 59. Square bracket [ a ko include karta hai; round bracket ) b ko exclude karta hai. Hum iska use karte hain kyunki phir length simply $b - a$ hoti hai bina koi "+1" yaad rakhe.

Recall Check:

$[90, 100)$ kaun se boxes cover karta hai, aur kitne? Boxes 90, 91, ..., 99 — woh hai $100 - 90 = 10$ boxes.

Yeh topic kyun zaroori hai: parent note ka simulation table har operation ke baad free-list track karta hai. Tumhe $(30, 30) + [90, 10)$ ko padhna aana chahiye as "do alag holes: ek 30 boxes ka position 30 par, ek 10 boxes ka position 90 par."

5. Adjacent — merging ke liye condition

Yeh topic kyun zaroori hai: "adjacent" woh exact word hai jo decide karta hai ki do holes ek ban sakte hain ya nahi. Yeh ek distinction hi ek aisa heap alag karta hai jo khud ko heal karta hai us se jo toot kar reh jaata hai.

6. Coalescing — neighbour holes ko merge karna

Figure ko top se bottom tak follow karo. Top strip mein, middle block ko free karne par ek hole banta hai jo existing right-hand hole ko touch karta hai; kyunki wo adjacent hain, allocator boundary mita deta hai aur ek lamba hole likhta hai (bottom strip). Yahi wajah hai ki tumhare free calls ki ordering itni zyada matter karti hai: sirf neighbours hi merge hote hain.

Yeh topic kyun zaroori hai: coalescing heap ki fragmentation ke against ek maat built-in defence hai. Yeh samajhna ki yeh sirf neighbours par kaam karta hai, parent note ke har result ko explain karta hai.

7. Allocation orders — LIFO clean kyun rehta hai

Jab tum LIFO order mein free karte ho, har freed block hamesha woh hota hai jo apni right par growing free region ko touch karta hai, toh har free turant coalesce ho jaata hai — heap ek bade hole mein wapas collapse ho jaata hai. Mixed order mein free karo aur tum holes ko still-live blocks ke beech phansa dete ho. Yahi difference hai jo parent note "middle mein B free karo" (fragmenting) aur "C, B, A free karo" (clean) ke beech demonstrate karta hai.

Yeh topic kyun zaroori hai: parent jo fix recommend karta hai — "reverse order mein free karo" — tabhi sense karta hai jab tum dekh lo ki reverse order har step par adjacency guarantee karta hai.

8. Math symbols: ceiling $⌈ \cdot ⌉$ , $r$ , $h$ , $a$

Internal-fragmentation formula char symbols use karta hai. Unhe ek ek karke lo.

Figure ko $r = 20, h = 8, a = 16$ ke liye trace karo: tumhe $20 + 8 = 28$ boxes chahiye. Woh ek 16-box quantum se zyada hai lekin do se kam, toh $⌈ 28/16 ⌉ = 2$ , jo $B = 2 \times 16 = 32$ deta hai. Bar dikhata hai 20 usable (green) + 8 header (yellow) + 4 dead (red) $= 32$ ; tumhare liye wasted portion hai $W = 32 - 20 = 12$ (8 header plus 4 dead tail).

Recall Ceiling check karo:

$r = 40, h = 8, a = 16$ — $B$ kya hai? $r + h = 48$ ; $48/16 = 3$ exactly; $⌈ 3 ⌉ = 3$ ; $B = 3 \times 16 = 48$ . Waste $W = 48 - 40 = 8$ .

Yeh topic kyun zaroori hai: internal fragmentation is formula se define hoti hai. Isme har symbol crisp hona chahiye warna "12 bytes wasted" result sirf magic lagega.

9. NULL — "no room" ka jawab

Yeh topic kyun zaroori hai: external fragmentation ka punchline — "malloc(40) NULL return karta hai chahe 40 bytes free hon" — isi baat par hinge karta hai ki NULL ka matlab failure hai, koi address nahi.

Prerequisite map

Equipment checklist

Mujhe pata hai ek byte aur ek address kya hote hain

Ek byte ek numbered box hai jo ek number rakhta hai; uska address uski position hai, memory ki ek seedhi ruler par 0 se count karte hue.

Mujhe contiguous define karna aata hai

Woh boxes jinke addresses bina kisi interruption ke consecutive hain — ek unbroken run.

Mujhe pata hai malloc ko contiguous memory kyun chahiye

N bytes ka ek object N boxes mein ek row mein rehna chahiye; woh kisi used region ko straddle nahi kar sakta, isliye scattered free boxes ek request serve nahi kar sakte.

Mujhe pair notation (start, size) aur bracket [a, b) padhna aata hai

(start, size) ek hole hai jo box start par start hota hai, size boxes lamba; [a, b) boxes a se lekin b include na karte hue cover karta hai, length b - a.

Mujhe adjacent holes aur non-adjacent holes mein fark pata hai

Adjacent = ek theek wahin khatam hota hai jahan doosra shuru hota hai, beech mein koi box nahi; non-adjacent = beech mein ek live block baitha hai.

Mujhe pata hai coalescing kya karta hai aur uski ek condition kya hai

Yeh do holes ko fuse karke ek bada hole banata hai; yeh tabhi kaam karta hai jab holes physically adjacent hon.

Mujhe pata hai LIFO free order fragmentation kyun avoid karta hai

Har freed block hamesha growing free region ko touch karta hai, isliye har free turant coalesce ho jaata hai aur heap ek bade hole mein wapas aa jaata hai.

Mujhe kisi number ka ceiling compute karna aata hai

Use next whole number tak upar round karo; jo number already whole hai woh wahi rehta hai.

Mujhe B = ceil((r+h)/a)*a aur W = B - r evaluate karna aata hai

r=20,h=8,a=16 ke liye: r+h=28, ceil(28/16)=2, B=32, W=12.

Mujhe pata hai NULL kya signal karta hai

malloc ka NULL return karna matlab hai use koi bhi itna bada contiguous hole nahi mila — request denied.

Connections

Heap fragmentation — woh parent topic jise ye foundations unlock karte hain
malloc and free — woh rent/return functions jo holes build aur coalesce karte hain
Stack vs Heap — kyun strict-order stack kabhi fragment nahi hota
Memory alignment — waste formula mein $a$ quantum ka source
Memory leaks — ek alag bug: kabhi return nahi hua, vs. return hua lekin scattered