Heap fragmentation — Hinglish notes

5.1.17 · Coding › C Programming

WHAT hai heap fragmentation?

YEH KYUN HOTA HAI (root cause): malloc ko ek single contiguous range of addresses return karni hoti hai. Heap ko free "holes" ki list ke roop mein manage kiya jaata hai. Jab tum mixed order mein alag-alag sizes ke malloc/free blocks karte ho, toh free holes live blocks ke saath interleave ho jaate hain. Tum do free holes ko tab tak merge nahi kar sakte jab tak woh memory mein physically adjacent na hon.

HOW yeh arise karta hai — scratch se derive karo

Heap ko ek linear array of bytes maano. Allocation ko (start, size) holes ki free-list se model karo. Ek bade hole [0, 100) se shuru karo.

Hum simulate karte hain malloc(n) = kisi hole se n bytes lo (first-fit), free(p) = ek hole return karo, adjacent neighbours ke saath coalescing karte hue agar adjacent hon.

Step                Heap layout (■=used, ·=free), 100 bytes
malloc A=30         ■■■A■■■············································  free: [30,70)
malloc B=30         ■■■A■■■■■■B■■■······································  free: [60,40)
malloc C=30         ■■■A■■■■■■B■■■■■■C■■■·······························  free: [90,10)
free B              ■■■A■■■······■■■C■■■·······························  free: [30,30)+[90,10)

Ab total free = 30 + 10 = 40 bytes. malloc(40) maango:

Coalescing — the defence

Agar hum stack order mein free karte (free C, phir B, phir A), toh har free growing right-hand hole ke saath coalesce ho jaata aur heap ek bade [0,100) hole mein return ho jaata — zero fragmentation.

Internal fragmentation — waste derive karo

Real allocators har request ko ek block size tak round up karte hain (alignment + bookkeeping ke liye). Maano blocks 16 bytes ke multiples mein aate hain, plus ek 8-byte header.

Flashcards

External fragmentation kya hai?

Enough total free memory exist karti hai, lekin woh non-contiguous holes mein split hai, isliye koi single hole request ke liye itna bada nahi hota.

Internal fragmentation kya hai?

Allocator requested se bada block deta hai (rounding/alignment/header ki wajah se); block ke andar ka unused tail waste hota hai.

malloc do free holes ko badi request satisfy karne ke liye kyun combine nahi kar sakta?

malloc ko ek contiguous address range return karni hoti hai; non-adjacent holes ko live block ke across merge nahi kiya ja sakta.

Coalescing kya hai?

Ek naye freed block ko uske physically adjacent free neighbour ke saath merge karke ek bada hole banana.

Coalescing sirf un blocks ke beech kaam karti hai jo...?

Memory mein physically adjacent hain.

Request r, header h, alignment a diye hue allocated block size ka formula?

B = ceil((r+h)/a) * a

r=20, h=8, a=16 ke liye, internal waste hai?

32 - 20 = 12 bytes.

Nested allocations ke liye fragmentation avoid karne wala free order kaun sa hai?

LIFO / stack order (sabse recently allocated pehle free karo), taaki har free adjacent hole ke saath coalesce ho.

Kya fragmentation matlab memory leak hai?

Nahi — leaked memory kabhi free nahi hoti; fragmented memory IS free hoti hai lekin unusably arranged hoti hai.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Tumhare toy box mein 100 blocks ki jagah hai. Tum toys nikalte aur rakhte rehte ho. Khelne ke baad tumhare paas yahan-wahan empty gaps ho jaate hain — kul khali jagah itni kaafi hai ki ek bada robot toy aa sake total mein — lekin gaps chhote hain aur doosre toys ke beech bikhar gaye hain. Robot ko ek badi khali jagah chahiye, aur woh nahi hai, chahe box "kaafi khali" ho. Yahi atka-hua feeling fragmentation hai. Agar tum hamesha last nikala hua toy pehle wapas rakho, toh khali jagah ek neat corner mein rehti hai aur robot fit ho jaata hai!

Connections

malloc and free — woh allocator jiska free-list holes create/coalesce karta hai
Memory leaks — alag bug: memory kabhi return nahi hoti vs. return hoti hai lekin scattered
Stack vs Heap — stack kabhi fragment nahi hota (strict LIFO); heap ho sakta hai
Memory alignment — internal fragmentation ka root cause
Pool allocator / Arena allocator — fixed-size pools jo external fragmentation eliminate karte hain
Garbage collection — compacting GCs physically objects ko move karte hain defragment karne ke liye