Heap fragmentation: Exercises — Coding deep dive

Everything here reuses only two ideas from the parent, restated so this page stands alone:

Level 1 — Recognition

L1.1

Classify each scenario as external fragmentation, internal fragmentation, or neither:

(a) You malloc(20) and the allocator uses a 16-byte quantum + 8-byte header, giving a 32-byte block.
(b) Total free = 40 bytes as two holes of 30 and 10; malloc(40) returns NULL.
(c) You malloc a block and never free it.

Recall Solution

(a) Internal. The extra bytes live inside one in-use block due to rounding + header — that is the definition of internal fragmentation. (b) External. Free memory is enough in total (40) but split into non-contiguous holes, so no single hole fits 40. That is external fragmentation. (c) Neither — it is a memory leak. Leaked memory is never returned; fragmented memory is free but badly arranged. Different bug entirely.

L1.2

True or false: "If malloc(n) fails, the heap must be completely full."

Recall Solution

False. By the largest-hole rule, malloc(n) fails whenever no single hole is $\geq n$ , even if plenty of total space is free. A half-empty heap can still refuse a request.

Level 2 — Application

For L2 use $h = 8$ (header) and $a = 16$ (alignment) unless a problem says otherwise.

L2.1

Compute $B (r)$ and $W (r)$ for $r = 20$ .

Recall Solution

WHAT: plug into Tool 1. WHY: $r = 20$ plus header does not land on a 16-boundary, so we round up. $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

Compute $B (r)$ and $W (r)$ for $r = 24$ .

Recall Solution

$r + h = 24 + 8 = 32$ . $⌈ 32/16 ⌉ = ⌈ 2.0 ⌉ = 2$ . $B = 32$ . $W = 32 - 24 = 8$ . Block = 32 bytes, wasted = 8 bytes. Notice: asking for more (24 vs 20) wasted less — because 24 sits closer to a block boundary.

L2.3

You make 1000 allocations of $r = 20$ bytes each (same $h = 8$ , $a = 16$ ). How many total bytes are internal waste?

Recall Solution

From L2.1, each such allocation wastes $W = 12$ bytes. WHY multiply: internal waste repeats identically per allocation, independent of the others. $1000 \times 12 = 12000$ bytes $= 12$ kB wasted, on top of the 20 kB you actually asked for.

L2.4

An allocator uses a power-of-two size class scheme (no header): a request of $r$ is rounded up to the smallest power of two $\geq r$ . Find $B$ and $W$ for $r = 65$ .

Recall Solution

WHY a new rule: here the "block size" set is ${1, 2, 4, 8, 16, 32, 64, 128, \dots}$ , not multiples of 16. We round $r$ up to the nearest such value. Powers of two around 65: $64 < 65 \leq 128$ . So $B = 128$ , $W = 128 - 65 = 63$ . Block = 128, wasted = 63 bytes — power-of-two classes can waste up to nearly 50% just above a boundary.

Level 3 — Analysis

We now track a live heap. The heap is 100 bytes, addresses [0,100). Allocator is first-fit (scans left, takes the first hole big enough), and coalesces a freed block with any physically adjacent free neighbour. Ignore headers/alignment for L3 (each malloc(n) takes exactly $n$ bytes). Every region is written [start, size) as defined at the top.

The figure below shows the run of L3.1 so you can see the holes forming.

L3.1

Execute in order: A=malloc(30), B=malloc(30), C=malloc(30), free(B). Then attempt malloc(40). What is the free-list, and does malloc(40) succeed?

Recall Solution

Trace the layout (■ used, · free), all regions as [start, size):

A=malloc(30) → A takes [0,30). Free: [30,70).
B=malloc(30) → first-fit takes [30,30). Free: [60,40).
C=malloc(30) → takes [60,30). Free: [90,10).
free(B) → B's region [30,30) returns. Left neighbour A is used, right neighbour C is used → no coalescing. Free-list becomes [30,30) and [90,10).

Total free $= 30 + 10 = 40$ . But malloc(40) scans: hole [30,30) has size 30 (✗), hole [90,10) has size 10 (✗). No single hole $\geq 40$ ⇒ malloc(40) returns NULL. Classic external fragmentation — the live block C fences the two holes apart.

L3.2

Take the state at the end of L3.1 (holes [30,30) and [90,10), with A and C live). Now free(C). What happens to the free-list, and does malloc(40) now succeed?

Recall Solution

WHAT: C occupies the region starting at address 60 with size 30, i.e. [60,30) (addresses 60 up to 90). WHY it matters: check both neighbours by address. C's left neighbour is the hole [30,30) (addresses 30 up to 60) — free. C's right neighbour is the hole [90,10) (addresses 90 up to 100) — free. Coalescing merges all three adjacent regions — addresses 30 up to 60, 60 up to 90, and 90 up to 100 — into one region covering addresses 30 up to 100, i.e. [30,70) (size 70). Free-list: [30,70). Now malloc(40) finds a 70-byte hole → succeeds. Freeing the fence let the holes fuse.

L3.3

Define fragmentation ratio $F = 1 - \frac{largest free hole}{total free bytes}$ (so $F = 0$ means all free space is in one hole; $F$ near 1 means badly scattered). Compute $F$ for the end-state of L3.1.

Recall Solution

End of L3.1: total free $= 40$ , largest hole $= 30$ . $F = 1 - \frac{30}{40} = 1 - 0.75 = 0.25.$ $F = 0.25$ . A quarter of the free space is "stranded" beyond the biggest usable hole. (After L3.2's coalesce, largest hole = total = 70, so $F = 0$ .)

Level 4 — Synthesis

L4.1

You must allocate 5 blocks of 30 bytes each in a 150-byte heap, then free all 5, repeatedly, in a loop. You may choose the free order. Which order guarantees the heap returns to one 150-byte hole every cycle, and why? Contrast with a bad order.

Recall Solution

Good order: LIFO / stack order — free the most recently allocated first. Allocations lay blocks left-to-right: $A [0, 30), B [30, 30), C [60, 30), D [90, 30), E [120, 30)$ (all [start, size)). Freeing E first: its right side is heap-end (free), left side D is live → E becomes hole [120,30). Free D: right neighbour [120,30) is now free → coalesce to [90,60). Continue C, B, A — each free coalesces with the growing right-hand hole. End: one [0,150) hole. $F = 0$ . Bad order: free the middle first (say C, then A, then E, then B, then D). Freeing C leaves an isolated [60,30) hole fenced by live B and D — no coalesce until its neighbours also go. Interior frees temporarily create scattered holes and raise the peak fragmentation ratio mid-cycle even though the end state may still merge. Rule learned: free in reverse order of allocation (like the stack does automatically) so every free touches the adjacent growing hole.

L4.2

You allocate many objects of the same size $r = 20$ ( $h = 8$ , $a = 16$ ). Explain why a pool allocator eliminates external fragmentation but does not remove the internal waste of 12 bytes each.

Recall Solution

External gone: a pool carves the heap into a grid of identical 32-byte slots. Every free slot is interchangeable and exactly the size of a request, so a free slot can always serve the next request — there is never a "hole too small," hence no external fragmentation. Internal stays: the slot size is still $B (20) = 32$ (from L2.1), so each in-use slot still wastes $W = 12$ bytes inside itself. The pool fixes where free space sits, not how much waste rounding creates. To kill the 12 bytes you'd have to change the requested/slot size to match the boundary (Tool-1 thinking).

L4.3

A compacting garbage collector can serve malloc(40) in the fragmented end-state of L3.1 without freeing C. How, and what does that cost that plain malloc/free never pays?

Recall Solution

A compacting GC physically moves live objects so that all free space slides into one contiguous region: it could shift C from [60,30) down to [30,30), merging the two holes into [60,40) (addresses 60 up to 100, size 40) — now malloc(40) fits, while C is still alive. The cost: moving an object changes its address, so every pointer to it must be updated (the GC must find and rewrite all references). Plain C malloc/free can never move a live block, because it doesn't know who points to it — that's exactly why manual heaps stay fragmented.

Level 5 — Mastery

L5.1

An allocator has $h = 16$ , $a = 64$ . A program does $N = 2000$ allocations of $r = 100$ bytes. (a) Find $B$ and $W$ per allocation. (b) Total internal waste. (c) What is the overhead ratio = total block bytes ÷ total requested bytes, as a percentage rounded to 1 decimal?

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%.$ You physically consume 28% more heap than you asked for (ratio 128.0% of requests).

L5.2

Heap of 200 bytes, first-fit, coalescing, no header/alignment. All regions written [start, size). Run: A=malloc(50), B=malloc(60), C=malloc(40), free(A), D=malloc(30), free(C), E=malloc(45). Give the final free-list and state whether E succeeded.

Recall Solution

Track each region as [start, size) across the 200-byte heap:

A=malloc(50) → A [0,50) (addresses 0 up to 50). Free: [50,150).
B=malloc(60) → B [50,60) (addresses 50 up to 110). Free: [110,90).
C=malloc(40) → C [110,40) (addresses 110 up to 150). Free: [150,50).
free(A) → A's region [0,50) freed; left = heap start, right neighbour B is live → no coalesce. Free: [0,50), [150,50).
D=malloc(30) → first-fit scans left, hole [0,50) fits 30 → D [0,30). Free: [30,20), [150,50).
free(C) → C's region [110,40) freed; left neighbour B [50,60) (ends at 110) is live, right neighbour [150,50) is free and starts exactly at 150 = C's end → coalesce → [110,90). Free: [30,20), [110,90).
E=malloc(45) → scan: [30,20) has size 20 (✗), [110,90) has size 90 (✓) → E takes [110,45) (addresses 110 up to 155). Free: [30,20), [155,45).

E succeeded (placed at [110,45)). Final free-list: [30,20) and [155,45), total free $= 65$ .

L5.3

Continuing from the end-state of L5.2 (free holes [30,20) and [155,45), total free 65), a request malloc(60) arrives. (a) Does it succeed? (b) Compute the fragmentation ratio $F = 1 - \frac{largest hole}{total free}$ . (c) One free would make malloc(60) succeed — which live block, and why?

Recall Solution

(a) Largest hole $= 45 < 60$ ⇒ malloc(60) fails (NULL), despite 65 total free bytes — largest-hole rule. (b) $F = 1 - \frac{45}{65} = 1 - 0.6923 \dots = 0.3077 \approx 0.308$ . Roughly 31% of free space is stranded outside the biggest hole. (c) Free the block E [110,45). Why E and not another: E's region is addresses 110 up to 155, so its right neighbour is the free hole [155,45) (starts exactly at 155 = E's end). Freeing E therefore coalesces with [155,45) into one hole [110,90) of size 90 $\geq 60$ — so free(E) followed by malloc(60) succeeds. Why the alternatives fail: freeing D [0,30) only merges with its right neighbour [30,20) into a 50-byte hole ( $50 < 60$ , still too small). Freeing B [50,60) (addresses 50 up to 110) merges with its right neighbour... which after freeing E would be free, but on its own B's left neighbour is live D-region and right neighbour is live E — so freeing B alone gives just a 60-byte hole [50,60) that happens to equal 60, but B is a live block you may still need, and the question asks for the single free that unlocks the request cleanly. E is the correct answer because it fuses two existing regions into a 90-byte hole with no ambiguity.

Connections

Heap fragmentation — the parent theory these exercises drill.
malloc and free — the first-fit + coalescing behaviour every L3–L5 trace models.
Stack vs Heap — why the LIFO free order in L4.1 defragments (the stack does it for free).
Memory alignment — the source of the ceiling term in every L2/L5 waste calc.
Pool allocator / Arena allocator — the L4.2 fix for external fragmentation.
Garbage collection — the L4.3 compaction that plain C cannot do.
Memory leaks — contrasted in L1.1(c): free-but-scattered vs never-freed.

Recall Master check (cloze)

malloc(n) succeeds iff the largest single free hole is at least n bytes (not the total). Coalescing merges a freed block only with a neighbour that is physically adjacent and also free. Block size formula ::: $B (r) = ⌈(r + h) / a ⌉ \cdot a$ , waste $W = B - r$ . For $r = 100, h = 16, a = 64$ the waste per block is ::: 28 bytes. Fragmentation ratio $F = 1 - \frac{largest hole}{total free}$ ; $F = 0$ means ::: all free space is one contiguous hole.