Fragmentation — internal vs external, compaction: Visual walkthrough

Before we begin, one word we will lean on constantly:

Step 1 — Lay the ruler down: what "allocation" even means

WHAT. We draw a bare strip of memory and mark off equal blocks, each of length $B$ bytes. Nothing is used yet.

WHY. You cannot talk about wasted space until you can see the two things that get compared: the space a process needs versus the space it is given. The ruler shows both on the same scale.

PICTURE. Look at the figure. The whole strip is memory. The vertical chalk ticks split it into blocks of equal width $B$ . Every tick is a place where the OS is allowed to start a new allocation — and the only such places.

Figure — Fragmentation — internal vs external, compaction

Step 2 — Fill one block: where does internal waste hide?

WHAT. We place a process needing $S$ bytes at the left, where $S$ is smaller than one block ( $S < B$ ). It fills part of the first block and stops.

WHY. The OS cannot hand out part of a block — the smallest unit is the whole block $B$ . So even though the process only wanted $S$ , it is given the whole block $B$ . That gap between "given" and "needed" is the waste we are hunting.

PICTURE. The blue region is the $S$ bytes the process uses. The pink region is the leftover inside the same block — bytes the process now owns but will never touch. That pink strip is internal fragmentation: waste hiding inside an allocated block.

given (whole block) B - needed S = wasted tail (pink) B - S

$B$ — the whole block handed over, because a block is indivisible.
$S$ — the bytes actually used (blue).
$B - S$ — the pink tail; owned but idle. This is internal waste for the case $S < B$ .

Step 3 — A big process: many blocks and the ceiling

WHAT. Now the process is large: $S > B$ . It needs several blocks. We count how many.

WHY. We must round up, never down — if even a single byte spills past the last full block, we are forced to grab one more whole block for it. The math tool that means "round up to the next whole number" is the ceiling function, written $⌈ ⌉$ . We use ceiling (not ordinary rounding, not floor) precisely because a fraction of a block is impossible.

PICTURE. The process (blue) needs $S$ bytes. It fills two whole blocks and then spills a little into a third. That spill forces the whole third block to be reserved. The pink tail in the third block is again internal waste.

N = ⌈ \frac{S}{B} ⌉

$\frac{S}{B}$ — how many blocks the need is worth, as a possibly-fractional number (here $S / B \approx 2.4$ ).
$⌈ ⌉$ — the ceiling; it bumps $2.4$ up to $3$ , because that leftover $0.4$ of a block still costs a whole block.
$N$ — the resulting whole number of blocks reserved.

Step 4 — The internal fragmentation formula, fully assembled

WHAT. We combine Steps 2 and 3 into one formula that works for any size $S$ and any block $B$ .

WHY. We want a single expression: total space given minus total space needed. "Given" is $N$ blocks each of length $B$ , i.e. $N \cdot B$ . "Needed" is $S$ . Subtract.

PICTURE. The bracket over the reserved region is $N \cdot B$ (all three blocks). The blue bracket underneath is $S$ . The pink sliver that pokes out past $S$ but stays under $N \cdot B$ is the answer.

Internal = N \cdot B - S = ⌈ \frac{S}{B} ⌉ B - S

$N \cdot B$ — total bytes reserved (blocks $\times$ block-length).
$S$ — bytes actually used.
The difference — the pink tail in the last block; the earlier full blocks waste nothing.

Step 5 — Take pieces back: where external waste is born

WHAT. Switch worlds. Now allocation is variable-size (as in Segmentation and Dynamic Memory Allocation): each process gets exactly what it asks for. We allocate three processes A, B, C tightly, then free B — leaving a gap.

WHY. Variable sizing kills internal waste (you get exactly $S$ ). But when processes leave, they punch holes of awkward sizes into the middle. Holes between allocations are a new kind of waste: external fragmentation.

PICTURE. Top strip: A, B, C packed tight — no waste. Bottom strip: B has left, leaving a yellow hole between A and C. The hole is free, but it is stranded between two used blocks.

Step 6 — Enough free space, yet the request fails

WHAT. After many allocate/free cycles the strip becomes Swiss cheese: holes of 40K, 30K, 50K. A new request for 100K arrives — and fails.

WHY. The OS in a contiguous scheme must place a request in one hole. $40 + 30 + 50 = 120$ K is free in total, but the biggest single hole is only 50K. 100K fits in no single hole, so the allocation is refused despite plenty of total free space. This is the pure, maddening face of external fragmentation.

PICTURE. Three yellow holes with their sizes. A pink 100K request-bar floats above, wider than every hole — it cannot land anywhere.

External fragmentation ratio = 1 - \frac{largest free block}{total free memory}

$largest free block$ — the biggest single hole ( $50$ K), the best you could actually use at once.
$total free memory$ — all holes summed ( $120$ K).
$1 - \frac{50}{120} = 1 - 0.4167 = 0.583$ — over half the free memory is unusable for anything bigger than 50K.

Step 7 — Compaction: sweep the holes together

WHAT. We slide every used block toward one end. As they close ranks, all the little holes pool into a single large free block at the far end.

WHY. The bytes were always enough (120K); the only problem was that they were scattered. Compaction fixes the geometry, not the amount: it re-arranges used blocks so free space becomes contiguous (one unbroken run). Now the 100K request finds room.

PICTURE. Before: A, B, C with holes between them. Arrows push each used block left. After: A, B, C flush at the left, and one merged yellow free block of $40 + 30 + 50 = 120$ K at the right — wide enough for the pink 100K request, which now lands.

Step 8 — The two escape hatches, side by side

WHAT. We contrast the two ways out: compaction (rearrange to merge holes) versus paging (make blocks fixed-size so holes never form).

WHY. Compaction is a cure — expensive, because it copies bytes and pauses ("stops the world"); cost grows with bytes moved. Paging is a prevention: with all frames identical, any free frame satisfies any request, so external holes cannot exist. Paging pays instead with a little internal waste (the last partial page) — the very trade-off from Step 4.

PICTURE. Left panel: variable blocks + compaction arrow (a running cost). Right panel: uniform paged frames — a process spread across non-adjacent frames, yet zero external waste because frames are interchangeable, plus one small pink tail of internal waste.

The one-picture summary

This final figure compresses all eight steps: the fixed-block world (internal waste, pink) on the left, the variable-block world (external holes, yellow) on the right, and the two cures — compaction merging holes, paging preventing them — as arrows out the bottom.

Recall Feynman retelling — the whole walkthrough in plain words

Picture memory as a ruler. First we only allow cuts at fixed tick marks (blocks). A small toy sits in a big bag: the empty room in the bag is wasted — that's internal waste, and it's exactly "the whole bag minus the toy," rounded so any spilled bit forces one more whole bag ( $⌈ S / B ⌉ B - S$ ). On average a bag is half-empty, so waste is about half a bag each. Next we allow bags of any size, so no room is wasted inside — but when toys leave, they punch gaps between the others. Add up the gaps and there's plenty of room, yet no single gap is wide enough for a big toy: that's external waste, measured by "how much of the free space is not in the biggest single gap." Two ways out: compaction slides all toys to one side so the gaps merge into one big free space (needs toys that aren't nailed down — run-time addressing), and it only ever fixes the between gaps, never the inside-the-bag waste. Or use paging: cut every bag to the same size so any empty bag fits any need — external gaps simply can't form, at the price of a tiny leftover in each last bag. Prevention beats the expensive copy-everything cure.

Prefer this in Hinglish? → यह note Hinglish में.