skip to content

Internal and External Fragmentation

16 roadmaps5 questions

Two different wastes: bytes lost rounding a request up to a block, and free space broken into pieces too small to use. Interviewers ask which one you have and what fixes it.

part ofComputer science fundamentalsoverview, primer and where to startread it →
on this pageshow

explore

questions

5

Which fragmentation does an allocator harness measure when it reports 100 MB requested but 128 MB occupied, and which does it miss?

level: middleimportance: must knowfreq 62%

answer

  1. two wastes, two different places
  2. inside a block versus between blocks
  3. occupied minus requested
  4. rounding up to a size class
  5. gaps need contiguity, not total bytes

basics

~10 s

That 28 MB gap is internal fragmentation: bytes lost rounding each request up to a whole block. It cannot see external fragmentation, the free-but-scattered space between blocks, because nobody occupies those bytes.

solid answer

~40 s

Internal fragmentation lives **inside** a block that was handed out: ask for 24 bytes, receive a 32-byte block, and 8 bytes are held for you and never used. Summed over a trace it is exactly `occupied - requested`, so 100 MB against 128 MB means 28 MB of rounding waste, about 22% of what the allocator holds. External fragmentation lives **between** blocks: free bytes that no request can use because they are not contiguous. A requested-versus-occupied table is structurally blind to it, since those bytes appear in neither column — no block covers them and nobody asked for them. To see external waste you need a second pair of numbers, total free against the largest contiguous free run.

code

pseudocode · 10 lines
pseudocode
requested = 0
occupied = 0

for each request r in trace:
    class_size = smallest size class >= r.size
    requested = requested + r.size
    occupied  = occupied + class_size

internal_waste = occupied - requested
waste_share    = internal_waste / occupied

go deeper

for a junior

Learn the two definitions with their locations attached: waste inside a block you were given, and free space between blocks that is too broken up to use. Say which one you mean every time.

for a middle

Be able to compute both: occupied minus requested for the rounding waste, and total free against the largest contiguous run for the gaps. Explain why a requested-versus-occupied table cannot see the second one.

for a senior

Show that you would instrument before acting. Name the counters you would export, say which waste each one can and cannot reveal, and pair each waste with the mitigation that could plausibly address it.

for a principal

Frame it as a budget: bounded rounding waste is a predictable tax you can size for, while gap waste depends on request history and is far harder to promise a number for. That asymmetry drives the design.

## Two wastes that share one word Fragmentation is not one phenomenon, and an answer that never says which kind is being discussed tells an interviewer nothing. **Internal fragmentation** is space lost *inside* a block that has already been handed out. The program asked for 24 bytes; the allocator returned a 32-byte block because 32 is the smallest size it is willing to hand out at that scale; the trailing 8 bytes belong to that allocation and will never be written. The bytes are accounted for, owned, and idle. **External fragmentation** is space lost *between* blocks. These bytes are free. Nobody owns them. They cannot satisfy a request because a request needs one **contiguous** run, and the free bytes are broken into pieces that are individually too small. The distinction matters because the two are measured differently, arise differently, and are removed by different design moves. ## Reading a requested-versus-occupied table Picture a measurement harness replaying a synthetic mix: many 24-byte requests and many 3 KB requests, against an allocator with power-of-two size classes. - A 24-byte request occupies a 32-byte block. Waste: **8 bytes** — a quarter of the block, and 33% on top of what was asked for. - A 3 KB request (3,072 bytes) occupies a 4 KB block (4,096 bytes). Waste: **1,024 bytes** — again a quarter of the block. - Summed over the whole trace: **100 MB requested, 128 MB occupied, 28 MB lost**. That is 21.9% of the bytes the allocator holds on the program's behalf, and 28% on top of what the program asked for. That single subtraction is a *complete* measure of internal fragmentation and a *blind* one for external fragmentation. The reason is mechanical: externally fragmented bytes never enter either column. They are not in the occupied column, because no block covers them; they are not in the requested column, because nobody asked for them. A harness can honestly report zero rounding waste over a heap whose free space is shattered into unusable slivers. ## What the second pair of numbers adds External fragmentation is visible only in the *shape* of free space, not its size. Two numbers capture it: **total free bytes** and the **largest contiguous free run**, measured after adjacent free blocks have been merged. When the two are close, free space is essentially one usable region. When total free is large and the largest run is small, the heap holds plenty of memory that no large request can use. ## Side by side | Question | Internal fragmentation | External fragmentation | |---|---|---| | Where are the wasted bytes? | Inside a block that was handed out | In free gaps between live blocks | | Who owns them? | The requester, who never uses them | Nobody — free but not usable | | How is it measured? | Bytes occupied minus bytes requested | Total free minus the largest free run | | When does it go away? | The moment that block is freed | Only if neighbours merge or blocks move | | What causes it? | Rounding up to a size class or alignment | Mixed sizes freed in a different order | | Bounded? | Yes — by the class spacing, per block | No — it depends on allocation history | ## Which fix attacks which 1. **Finer size classes or tighter alignment** cut internal waste. They do not touch external waste, and each extra class carries its own idle reserve. 2. **Merging adjacent free neighbours** attacks external waste by rebuilding large runs. It does nothing to the rounding waste inside live blocks. 3. **Relocating live blocks** attacks external waste directly, since it no longer depends on which neighbours happen to be free. It cannot shrink a block, so internal waste survives it unchanged. 4. **Resetting a whole region at a phase boundary** returns both wastes at once, because the entire region becomes free in one step — at the price of reclaiming nothing before that boundary. 5. **A larger heap** dilutes both as a percentage and removes neither. Growth buys time, not a fix. ## What an interviewer is listening for Three things: that you name which fragmentation you mean; that you can say how you would *measure* it, which is where most candidates stop; and that you pair the waste with the mitigation that can actually address it. Claiming that compaction fixes rounding waste, or that a total-free figure proves the heap is healthy, is the standard stumble. Note also that internal waste is fully recovered when the block is freed — it is idle space, not a leak, and a steady-state process pays it in proportion to its live blocks rather than accumulating it forever.

  • If every request in a workload were exactly the same size, which of the two wastes could still occur?
    Internal waste can remain, if that one size is not exactly a block size and every request is rounded up. External waste essentially disappears: every freed block is the same shape as every future request, so any free block satisfies any request and gaps of the wrong size cannot accumulate.
  • Why does doubling the number of size classes not simply halve total waste?
    Finer classes cut the rounding gap per block, but each class keeps its own pool of free blocks. Bytes idle in one class cannot serve a request in another, so some waste moves from inside blocks into per-class reserve. The measured total falls, usually by less than the rounding arithmetic alone predicts.
  • Is internal fragmentation a leak?
    No. The idle bytes are recovered in full the moment the block is freed, so a steady-state program pays a bounded amount proportional to its live blocks. A leak keeps growing because blocks are never freed at all; rounding waste stops growing when the live set does.

Shirts stored in fixed-size boxes: the slack left inside each box is internal waste, while the awkward gaps between boxes on the shelf are free space that fits nothing bigger.

saying these in an interview costs you the question

  • Calls every wasted byte internal fragmentation, with no second category
  • Believes a large total-free figure proves there is no external fragmentation
  • Says rounding waste is lost forever rather than returned when the block is freed
  • Claims relocating blocks removes the waste inside each block
  • Assumes growing the heap removes external fragmentation instead of delaying it
  • Confuses free-but-unusable space with a memory leak
open as a page

A size-class allocator rounds every 3 KB request up to a 4 KB block; which fragmentation does that trade away, and what does it buy?

level: middleimportance: should knowfreq 48%

basics

~20 s

It trades unbounded gap waste for bounded rounding waste. Within one class every free block fits every request of that class, so unusable gaps cannot form there; the price is 1,024 idle bytes per 3 KB request, a quarter of each block.

open as a page

Why can an allocator's total free bytes overstate what it can actually hand out, and which second number corrects it?

level: seniorimportance: should knowfreq 45%

basics

~20 s

A request needs one contiguous run, but total free bytes sums runs that may be scattered. The largest contiguous free run is the corrective number: it, not the total, bounds the biggest single request that can be placed.

open as a page

How do you choose among size classes, neighbour coalescing, relocation and per-phase region reset when designing for a mixed-size, long-running workload?

level: principalimportance: should knowfreq 36%

basics

~20 s

Match each mitigation to the waste it can actually address, then pick by price. Size classes bound rounding waste, coalescing rebuilds runs from adjacent neighbours, relocation restores contiguity but must update references, and a region reset returns everything at a phase boundary.

open as a page

Why can no allocator that never relocates a block promise to keep total memory within a constant factor of its live set?

level: seniorimportance: nice to knowfreq 22%

basics

~10 s

Because placement alone cannot defeat an adversarial request order. A classical worst-case result shows required memory grows with the live set times the logarithm of the largest-to-smallest request size ratio, for every fixed-placement policy.

open as a page