Visual walkthrough — Heap fragmentation

5.1.17 · D2 · Coding › C Programming › Heap fragmentation

---

Step 1 — Heap ko boxes ki ek row ke roop mein draw karo

KYA. Kisi bhi symbol se pehle, ek picture. Heap bas memory ki ek lambi strip hai. Hum ise 100 chhote boxes ke roop mein draw karenge, 0 se 99 tak numbered. Box number = address = "yeh byte strip mein kitni door hai". Ek bhara hua box ■ matlab in use; ek dot · matlab free.

Seedhi line kyun? Kyunki memory addresses ek ke baad ek hote hain, jaise ek hi street par ghar ke numbers. Yeh seedhapan hi poori kahaani hai: memory ka ek chunk neighbouring boxes ki ek run hai, aur "neighbouring" hi sab kuch nikalta hai.

PICTURE. Strip dekho — 100 empty boxes, unke neeche kuch address labels. Abhi kuch use nahi hua. Yeh ek hi empty run ek hole hai: free boxes ka ek maximal stretch.

Notation [0, 100) ka matlab hai "box 0 se shuru, box 100 tak but not including" — toh yeh boxes 0…99 cover karta hai, 100 ki ek run.

---

Step 2 — malloc(n) ek hole ke front se kaata hai

KYA. malloc(30) call karo. Allocator apni holes ki list mein walk karta hai, pehla wala dhundhta hai jo kaafi bada ho (yeh rule first-fit kehlata hai), aur uske front se 30 boxes kaatata hai. Woh boxes block A ban jaate hain.

First-fit kyun? Kyunki scanning pehle hole par rukti hai jo fit hota hai — yeh sabse simple, sabse fast rule hai. Koi bhi fitting rule baad mein same fragmentation dikhayega; first-fit sirf kahaani ko concrete banata hai.

PICTURE. Boxes 0…29 ab filled hain (yeh hai A). Ek hole sikudar kar [30, 100) ho gaya, 70 ki ek run.

$$\underset{\text{ask for 30 boxes}}{\underbrace{\text{malloc}(30)}}⟶\underset{\text{30 used boxes}}{\underbrace{A=[0,30)}},\underset{[30,100)}{\underbrace{\text{hole}=[70\text{ left}]}}$$

• $[0,30)$ — woh boxes jo A ke paas hain; koi aur inhe tab tak nahi chhoo sakta jab tak A free nahi hota.
• $[30,100)$ — jo bacha hai, abhi bhi $70$ size ka ek saaf hole.

---

Step 3 — Teen same-size blocks se bharo

KYA. Do aur malloc(30) calls: block B [30,60) leta hai, block C [60,90) leta hai. A, B, C ke baad teen live blocks packed hain aur ek chhota tail hole [90,100) size 10 ka hai.

Pack kyun kiya? Taaki picture dense aur honest ho — ek busy program aisa hi dikhta hai: bahut se blocks ek saath live hote hain, holes edges par squeeze ho jaate hain.

PICTURE. Teen coloured runs A, B, C boxes 0…89 fill karte hain; sirf [90,100) free rehta hai.

$$A=[0,30),B=[30,60),C=[60,90),\text{hole}=[90,100)$$

Notice karo B, A aur C ke beech wedged hai. Woh word wedged yaad rakho — yeh abhi matter karne wala hai.

---

Step 4 — free(B) MIDDLE mein ek hole kholta hai

KYA. Hum free(B) karte hain. Boxes [30,60) free ho jaate hain. Ab do holes hain: [30,60) (size 30) aur [90,100) (size 10).

Yeh hurt kyun karta hai? Freed hole surrounded hai — left mein A, right mein C. Yeh trapped hai. Yeh doosre hole se haath nahi mila sakta kyunki C unke beech khada hai.

PICTURE. A live, ek 30-box gap, C live, phir ek 10-box gap. Dono dotted regions touch nahi kar rahe.

Abhi total free:

$$\underset{[30,60)}{\underbrace{30}}+\underset{[90,100)}{\underbrace{10}}=\underset{\text{free bytes}}{\underbrace{40}}$$

Chaalees boxes free hain. Yeh number pakde raho.

---

Step 5 — Failure: malloc(40) NULL return karta hai

KYA. malloc(40) maango. Allocator ko 40 boxes ek unbroken run mein chahiye. Woh har hole check karta hai:

• Hole [30,60) → size 30. $30<40$. ✗
• Hole [90,100) → size 10. $10<40$. ✗

Koi ek bhi hole fit nahi hota. malloc ==NULL== return karta hai — bhalay hi 40 free boxes exist karte hain.

Dono holes use kyun nahi kar sakta? Kyunki malloc ek contiguous run ka waada karta hai: woh pointer jo return karta hai tumhe 40 steps forward walk karne deta hai apna block kabhi chhode bina. 40 free boxes 30 + 10 mein bant gaye hain C ke opposite sides par. Tum ek 40-box object adha yahan aur adha wahan store nahi kar sakte.

PICTURE. Requested 40-box bar (upar floating dikhaaya gaya) kisi bhi gap se lambi hai. Yeh simply kisi bhi slot mein fit nahi hoti.

Yeh parent ka central result hai, ab box one se derive kiya gaya: free memory exist kar sakti hai aur phir bhi unusable ho sakti hai, kyunki woh non-adjacent pieces mein tooti hui hai.

---

Step 6 — Woh cure jo kaam nahi karta vs. jo karta hai: coalescing

KYA. Coalescing = jab tum ek block free karte ho, allocator immediately left aur immediately right wale box ki taraf dekhta hai; agar koi bhi already ek hole hai, toh woh unhe fuse karke ek bada hole banata hai.

Yeh kabhi kabhi kaise save kar sakta hai. Coalescing sirf neighbours merge karta hai. Toh order jisme tum free karte ho woh sab kuch decide karta hai.

PICTURE — do timelines side by side:

• Bad order (top): pehle B free kiya (trapped, koi neighbour free nahi) → 30 + 10 par stuck.
• Good order (bottom): allocation ka reverse — C free karo, phir B, phir A. Har free badhte right-hand hole ko touch karta hai aur fuse ho jaata hai. Heap wapas ek clean [0,100) mein heal ho jaata hai.

Good order box-by-box dekho:

$$\begin{array}{l}\text{free }C:[60,100)\text{(C’s 30 + tail 10 fuse)}\\ \text{free }B:[30,100)\text{(B joins the run on its right)}\\ \text{free }A:[0,100)\text{(A joins — one whole hole again)}\end{array}$$

Har line padhte hue: freed block ka right neighbour already free tha, toh dono ek edge share karte hain aur merge ho jaate hain. Woh freeing-newest-first pattern LIFO / stack order hai — wahi discipline jo stack automatically use karta hai, isliye stack kabhi fragment nahi hota.

---

Step 7 — Doosra flavour: internal fragmentation (waste andar chhupa hua)

KYA. Ek akela bhi malloc memory waste karta hai. Real allocators odd sizes refuse karte hain: woh har request ko ek fixed step tak round up karte hain (alignment ke liye aur ek bookkeeping header store karne ke liye). Toh tum r boxes maangte ho, woh ek bada block set aside karte hain, aur extra tail tumhare block ke andar dead space hai.

Round up kyun? Hardware aligned addresses (multiples of a) par memory sabse fast padhta hai, aur allocator ko h header boxes chahiye block ki size yaad rakhne ke liye. Dono sizes ko ek grid par force karte hain.

PICTURE. Request $r=20$. Header $h=8$ add karo → $28$ chahiye. Grid step $a=16$ hai. Aathais ek 16-box unit mein fit nahi hoti, toh hume do units = $32$ lene padte hain. Tumhare $20$ andar baithe hain; $32-20=12$ boxes waste hain aur ek live block ke andar locked hain — koi coalescing unhe kabhi nahi pahunch sakta.

---

Ek-picture summary

Ek board, poori kahaani: ek full strip, mid-strip free, fatal malloc(40), LIFO cure, aur internal-waste inset — external fragmentation (blocks ke beech gaps) aur internal fragmentation (ek block ke andar waste) side by side.

Recall Feynman retelling — ek 12-saal ke bachche ko batao

Socho ek shelf hai jisme 100 slots hain. Tum teeno toy boxes A, B, C ek ke baad ek, packed tight rakhte ho. Ab middle wala box B nikalte ho. Wahan ek hole hai jahan B tha, aur ek chhota hole bilkul end mein — total 40 empty slots. Lekin tumhara naya toy 40 slots ek row mein chahiye, aur box C tumhare empty slots ke bilkul beech mein khada hai. Toh bhalay hi 40 slots empty hain, toy andar nahi jayega. Yahi hai external fragmentation. Ab ek trick: agar tum toys newest-first nikalte (C, phir B, phir A), toh har empty slot pichhle wale se touch karta hai aur sab ek bade empty space mein merge ho jaate hain — koi fragmentation nahi. Alag se, shelf sirf toys ko slots ke pairs plus ek naam-tag slot mein accept karta hai, toh ek toy jo 20 slots chahiye woh actually 32 le leta hai aur 12 forever waste karta hai apni jagah ke andar — yahi hai internal fragmentation, aur kitna bhi tidying karne se woh 12 free nahi honge jab tak poora toy nahi nikalo.

Recall

Total free = 40, holes 30 aur 10 hain block C ke aas-paas. Kya malloc(40) succeed karta hai? ::: Nahi — koi ek bhi contiguous hole $\ge 40$ nahi hai, toh yeh NULL return karta hai. Kaun sa free order heap ko ek hole mein heal karta hai? ::: LIFO / stack order (C free karo, phir B, phir A). $r=20$, $h=8$, $a=16$ ke liye, block size aur waste kya hai? ::: $B=32$, $W=12$ boxes.

---

Connections

• malloc and free — allocator jo holes draw kiye unhe carve aur fuse karta hai
• Stack vs Heap — kyun stack (strict LIFO) kabhi Step 5 nahi hit karta
• Memory alignment — grid step a Step 7 ke internal waste ke peeche
• Memory leaks — leaked = kabhi freed nahi; fragmented = freed but scattered
• Pool allocator / Arena allocator — same-size ya bulk strategies jo Step 5 se bachti hain
• Garbage collection — compacting collectors physically blocks move karte hain taaki gaps mita sake