5.1.17 · D3Heap fragmentation
Yeh Heap fragmentation ka "sleeves roll up karo" wala child note hai. Parent ne tumhe ideas diye the — external vs internal fragmentation, coalescing, block-size formula. Yahan hum un saari ideas ko concrete numbers ke through drive karte hain, aur deliberately har corner case ko hit karte hain jo yeh topic throw kar sakta hai: block formula ke har sign, zero-size aur degenerate inputs, jab requests bahut badi ho jaati hain toh limiting behaviour, ek real-world word problem, aur ek exam-style trick.
Kisi bhi example se pehle, chalte hain un do tools ko apne words mein dobara earn karte hain jinpar hum lean karte hain.
Definition Do symbols jo hum har jagah reuse karte hain
Ek hole likha jaata hai [ s , s + n ) s n s s + n included nahi hai" (yeh next cheez ka pehla byte hai). Toh [ 30 , 60 )
Contiguous ka matlab hai bytes physically ek doosre ke saath hain, bich mein koi live block nahi. [ 30 , 60 ) [ 30 , 60 ) plus [ 90 , 100 ) nahi hai — 60–90 par ek wall hai.
Definition Block-size tool (parent se)Jab tum r h header store karta hai (uski bookkeeping) aur total ko alignment a upar round karta hai:
B ( r ) = ⌈ a r + h ⌉ ⋅ a , W ( r ) = B ( r ) − r . ⌈ x ⌉ x ≥ x kam se kam itna bada hona chahiye; tum user ko next multiple se kam bytes kabhi nahi de sakte jo sab kuch fit kare. W
Neeche har worked example matrix cell ke saath tagged hai jise woh cover karta hai, taaki tum dekh sako ki poora space fill hai.
Cell
Kya vary karta hai
Extreme jo probe karta hai
Example
A External-failfree total ≥ request, holes non-adjacent
classic NULL-despite-free
Ex 1
B Coalesce-saveadjacent order mein free
holes merge hokar ek ho jaate hain
Ex 2
C LIFO vs randomsame allocs, do free orders
order fate decide karta hai
Ex 3
D Internal W > 0 r + h worst-case waste
Ex 4
E Internal W = 0 r + h zero-waste degenerate
Ex 5
F Zero / tiny inputr = 0 header-only block
Ex 6
G Limiting behaviourr → waste fraction → 0
Ex 7
H Word problemgame-server churn
real-world external frag
Ex 8
I Exam twist"total free = request ⇒ success?"
counter-layout se disprove karo
Ex 9
Hum W
Worked example Classic failure100 bytes ka heap, ek hole [ 0 , 100 ) A=malloc(30); B=malloc(30); C=malloc(30); free(B);
Phir malloc(40). Kya yeh succeed karega?
Forecast: free(B) ke baad total free 30 + 10 = 40
A=malloc(30) [ 0 , 30 ) [ 30 , 100 ) Yeh step kyun? First-fit pehle hole ke front se bytes leta hai jo kaafi bada ho.B=malloc(30) [ 30 , 60 ) [ 60 , 100 ) C=malloc(30) [ 60 , 90 ) [ 90 , 100 ) free(B) [ 30 , 60 ) A C free nahi hain, toh kuch coalesce nahi hota. Free list = [ 30 , 60 ) aur [ 90 , 100 ) Yeh step kyun? Coalescing ke liye ek free physical neighbour chahiye; B ke dono neighbours use mein hain.malloc(40): holes scan karo. [ 30 , 60 ) = 30 [ 90 , 100 ) = 10 NULL .
Yeh step kyun? malloc ek contiguous range return karta hai; yeh [ 60 , 90 ) C
Verify: largest single hole = max ( 30 , 10 ) = 30 < 40 = 30 + 10 = 40 ≥ 40 Max par inequality hi success decide karti hai — aur yeh fail hoti hai. Yahi external fragmentation hai.
Worked example Middle-right neighbour ko free karoEx 1 ka same start step 3 tak (holes: sirf [ 90 , 100 ) A [ 0 , 30 ) , B [ 30 , 60 ) , C [ 60 , 90 ) free(C); free(B); karo phir malloc(40).
Forecast: kya 40-byte request ab succeed karega?
free(C) [ 60 , 90 ) [ 90 , 100 ) adjacent! Coalesce: [ 60 , 90 ) ∪ [ 90 , 100 ) = [ 60 , 100 ) Yeh step kyun? C free(B) [ 30 , 60 ) [ 60 , 100 ) [ 30 , 100 ) malloc(40): hole [ 30 , 100 ) success , [ 30 , 70 )
Verify: largest hole = 70 ≥ 40 same total free bytes ke saath. Sirf free order badla.
Worked example Order sab decide karta hai100 mein A , B , C Random order (free(A); free(C);) vs LIFO/stack order (free(C); free(B); free(A);) compare karo. Har ek ke baad largest free hole report karo.
Forecast: kaun sa order ek bada clean hole chhodta hai?
Random: free(A) → hole [ 0 , 30 ) B free(C) → hole [ 60 , 90 ) [ 90 , 100 ) [ 60 , 100 ) B [ 30 , 60 ) [ 0 , 30 ) [ 60 , 100 ) = 40 Yeh step kyun? A C B LIFO: free(C) → [ 60 , 100 ) free(B) → [ 30 , 60 ) [ 30 , 100 ) free(A) → [ 0 , 30 ) [ 0 , 100 ) = 100 Yeh step kyun? Har freed block hamesha badhte hue right-hand hole ko touch karta hai, toh har free coalesce hota hai. Yahi exactly reason hai ki stack kabhi fragment nahi hoti — yeh strict LIFO hai.
Verify: LIFO largest hole = 100 = 40 Pool allocator / Arena allocator dekho.
Worked example Boundary overshoot karnar = 20 h = 8 a = 16 B W
Forecast: tumne 20 maange — kitne bytes actually consume honge?
Header add karo: r + h = 20 + 8 = 28 Yeh step kyun? Allocator ko apni 8-byte bookkeeping block ke andar store karni hai.
16 ke multiple tak round up karo: ⌈ 28/16 ⌉ = ⌈ 1.75 ⌉ = 2 B = 2 ⋅ 16 = 32 Ceiling kyun, round kyun nahi? 28 ek 16-unit mein fit nahi hota; tumhe do lene hi padenge, chahe doosra barely use ho. 1.75 ka regular rounding bhi 2 deta hai yahan, lekin ⌈ ⋅ ⌉ sahi rule hai (e.g. 1.1 → 2, nahi 1).
Waste W = B − r = 32 − 20 = 12
Verify: B = 32 a = 16 B ≥ r + h = 28 16 < 28 = 12/32 = 37.5% Memory alignment dekho.
Worked example Exactly ek multiple par land karnar = 24 h = 8 a = 16 B W
Forecast: kya waste header ke saath bhi kabhi zero ho sakta hai?
r + h = 24 + 8 = 32 ⌈ 32/16 ⌉ = ⌈ 2.0 ⌉ = 2 B = 32 Yeh step kyun? 32 already 16 ka multiple hai, toh ceiling ise upar nahi push karta — koi rounding waste nahi.W = 32 − 24 = 8 B − h − r = 32 − 8 − 24 = 0
Verify: B = 32 r + h = 32 zero rounding waste — sirf unavoidable 8-byte header ka overhead hai. Yeh internal fragmentation ka degenerate best case hai.
Worked example Tiny/degenerate inputr = 0 h = 8 a = 16
Forecast: tumne kuch nahi maanga — kya 0 bytes use honge?
r + h = 0 + 8 = 8 ⌈ 8/16 ⌉ = ⌈ 0.5 ⌉ = 1 B = 1 ⋅ 16 = 16 Zero kyun nahi? Zero-byte request ko bhi 8-byte header kahin store karna hai, aur block phir bhi ek full alignment unit hona chahiye. (Real C mein, malloc(0) NULL ya ek unique non-NULL pointer return kar sakta hai — lekin agar woh real block return kare, toh bhi ek whole unit cost karega.)Waste W = 16 − 0 = 16 poora block overhead hai.
Verify: B = 16 ≥ r + h = 8 malloc(0) avoid karne ka ek reason (yeh Memory leaks pressure ka subtle cousin hai).
r h = 8 a = 16 r = 1024 W / B r → ∞
Forecast: kya bade-object allocation proportionally zyada ya thoda waste karta hai?
r + h = 1024 + 8 = 1032 ⌈ 1032/16 ⌉ = ⌈ 64.5 ⌉ = 65 B = 65 ⋅ 16 = 1040 W = 1040 − 1024 = 16 W / B = 16/1040 ≈ 0.01538 = 1.538% Yeh step kyun? Overhead (h r Limit: overhead ≤ h + a W / B ≤ ( h + a ) / ( r ) → 0 r → ∞ Yeh tool (limit) kyun? Hum trend chahte hain, ek value nahi — limit jawab deta hai "fraction kya approach karta hai jab requests arbitrarily badi ho jaati hain?"
Verify: 1.538% ≪ 37.5% chhote objects ko hurt karta hai , bade ones ke liye negligible ho jaata hai — bahut saare same-size chhote objects ke liye raw malloc ki bajay pools motivate karta hai.
Worked example Game-server projectile churn240 bytes ka ek server pool bullet objects hold karta hai. Bullets first-fit allocate hoti hain. Sequence: bullets b 1 , b 2 , b 3 , b 4 b 2 , b 4 free). Ek naya bada effect object 120 contiguous bytes chahta hai. Fit hoga?
Forecast: do freed 60-byte bullets = 120 free — effect zaroor fit hoga?
4 spawns ke baad layout: b 1 [ 0 , 60 ) , b 2 [ 60 , 120 ) , b 3 [ 120 , 180 ) , b 4 [ 180 , 240 )
free(b_2) → hole [ 60 , 120 ) b 1 , b 3 free(b_4) → hole [ 180 , 240 ) b 3 Yeh step kyun? Alternating live/free pattern classic fragmentation generator hai.Holes: [ 60 , 120 ) = 60 [ 180 , 240 ) = 60 b 3 = 60 < 120 NULL , effect spawn nahi ho sakta.
Verify: total free = 60 + 60 = 120 = = 60 < 120 Pool allocator saari 60-byte bullets store karta aur us pool mein 120-byte object mix karne se refuse karta — problem ko sidestep karta. Compacting Garbage collection iske bajay b 3 move karta holes fuse karne ke liye.
Worked example "Agar total free ≥ request hai, toh malloc succeed karta hai." True ya false?Sabse chota counterexample banao.
Forecast: kya total-free-bytes ek sufficient condition hai?
Success ke liye kya chahiye restate karo: ek single hole size ≥ request, sirf total free ≥ request nahi.
Yeh step kyun? malloc ek contiguous range return karta hai.
Counterexample: 2 holes [ 0 , 1 ) [ 2 , 3 ) [ 1 , 2 ) = 2 malloc(2).
Largest hole = 1 < 2 = 2 ≥ 2 false hai.
Verify: total free 2 ≥ 2 max ( 1 , 1 ) = 1 < 2 max i ( hole i ) ≥ r
Recall Quick self-testmalloc(n) ki success kaunsi quantity par depend karti hai? ::: Largest single contiguous hole ki size, total free bytes par nahi.
r=20, h=8, a=16 ke liye, wasted bytes kitne hain? ::: 12
r=24, h=8, a=16 ke liye, rounding waste kitna hai? ::: 0 (sirf 8-byte header overhead hai)
malloc(0) with h=8, a=16 kitne size ka block carve karta hai? ::: 16 bytes (sab overhead)
r badhne par W/B kya ho jaata hai? ::: 0
Heap fragmentation — parent topic jin examples ko yeh drill karta haimalloc and free — first-fit allocator jo har example simulate karta haiStack vs Heap — kyun LIFO (Ex 3) kabhi fragment nahi hotiMemory alignment — block formula mein a Pool allocator / Arena allocator — Ex 8 ke fixesGarbage collection — compaction jo Ex 8 ko rescue kartaMemory leaks — contrast: leaked ≠ fragmented 
