Fragmentation — internal vs external, compaction: Worked examples

This page is a drill. We take the two formulas from the parent topic and beat them against every kind of input they can face — clean numbers, exact fits, tiny processes, huge processes, the degenerate "one hole" case, a word problem, and an exam trap.

Before we start, three symbols carry the whole page. We define them from zero:

The $⌈ ⌉$ marks are the ceiling — "round up to the next whole number". We read $⌈ 2.44 ⌉ = 3$ as: "2.44 blocks doesn't exist, so you need 3 whole blocks." Why up and never down? Because rounding down would leave some of the process's bytes with no home — illegal. Every leftover byte forces a fresh block.

The scenario matrix

Here is every distinct case class fragmentation can throw at you. The examples below each name the cell they cover.

Cell	Case class	What's special about it
A	Internal, non-exact fit	$S$ not a multiple of $B$ → some waste
B	Internal, exact fit (degenerate)	$S$ is a multiple of $B$ → waste is zero
C	Internal, tiny process ( $S < B$ )	needs 1 block, wastes almost all of it
D	Internal, many processes (system total)	sum many tails; average $\approx B /2$ each
E	External, scattered holes	ratio between 0 and 1
F	External, one single hole (degenerate)	ratio $= 0$ , perfectly healthy
G	External, request fails but total suffices	the classic "enough but useless" trap
H	Compaction outcome	holes merge → request now succeeds
I	Word problem (real units, KB/MB)	translate English → the formulas
J	Exam twist	paging vs. compaction confusion / limiting behaviour

Example 1 — Cell A (internal, non-exact fit)

Example 2 — Cell B (exact fit, degenerate: zero waste)

Example 3 — Cell C (tiny process, $S < B$ )

Example 4 — Cell D (system total, many processes)

Worked example Three processes on a system with block

$B = 4096$ B (4 KB). Sizes: $P_{1} = 6000$ B, $P_{2} = 4096$ B, $P_{3} = 100$ B. Total internal fragmentation across the system? Forecast: which single process contributes the most waste?

$P_{1}$ : $N = ⌈ 6000/4096 ⌉ = ⌈ 1.46 ⌉ = 2$ ; given $= 8192$ ; waste $= 8192 - 6000 = 2192$ B. Why this step? Same per-process formula, applied once each, then summed.
$P_{2}$ : $6000$ ? No — $4096/4096 = 1.0$ , $N = 1$ ; waste $= 4096 - 4096 = 0$ B. (Exact fit, Cell B inside a system.)
$P_{3}$ : $N = ⌈ 100/4096 ⌉ = 1$ ; waste $= 4096 - 100 = 3996$ B. (Tiny, Cell C inside a system.)
Total: $2192 + 0 + 3996 = 6188$ B. Why this step? System internal fragmentation is the sum of every process's last-block leftover.

Verify: the average- $B /2$ rule predicts $\approx 3 \times (4096/2) = 6144$ B; our exact total 6188 B sits right beside it. ✓ Close because two of the three processes had "random-ish" tails; the estimate is only an average.

Example 5 — Cell E & G (external: scattered holes, request fails)

Figure — Fragmentation — internal vs external, compaction

Total free: $40 + 30 + 50 = 120$ K. Why this step? The ratio compares the biggest usable piece against all the free memory.

Largest block: $max (40, 30, 50) = 50$ K (the amber bar in the figure).

Ratio: $1 - 50/120 = 1 - 0.4167 = 0.5833$ . Why this step? A ratio near 1 means the free memory is badly shattered; here over half is unusable for any request above 50 K.

The 100 K request: must land in one contiguous hole. Largest is 50 K $< 100$ K → fails, even though $120 > 100$ . Why this step? Memory handed to a process must be contiguous; you cannot stitch three separate holes together for one request.

Verify: $0.5833 \approx 7/12$ ; and indeed $1 - 50/120 = (120 - 50) /120 = 70/120 = 7/12$ . ✓ Request fails because no single hole $\geq 100$ K.

Example 6 — Cell F (degenerate external: one hole, ratio zero)

Example 7 — Cell H (compaction merges the holes)

Slide A, B, C to the front: all used blocks pack against one end (top of figure → bottom). Why this step? Compaction physically copies allocated blocks together; this requires run-time relocatable addresses (a base/relocation register), else the copied code would point at the wrong places.

Holes merge: the freed space becomes one block of $40 + 30 + 50 = 120$ K. Why this step? Nothing was freed or created — the same 120 K is now contiguous instead of scattered.

New ratio: $1 - 120/120 = 0$ .

100 K request: $120 \geq 100$ in one block → succeeds. Why this step? Now a single hole is large enough, which is exactly what the request needs.

Verify: total free unchanged ( $120$ K before and after — compaction moves, never deletes); ratio dropped $0.5833 \to 0$ . ✓ And $120 \geq 100$ , so success. Note internal waste inside A, B, C is untouched — compaction cures external only.

Example 8 — Cell I (word problem, real units)

Worked example A file server allocates disk in 4 KB clusters. A user stores 12,000 files, each exactly 1 KB. (a) How much space is

charged? (b) How much is internal fragmentation? (Use $1 KB = 1024$ B.) Forecast: each 1 KB file into a 4 KB cluster — guess the waste per file.

Per file: $S = 1024$ B, $B = 4096$ B. $N = ⌈ 1024/4096 ⌉ = ⌈ 0.25 ⌉ = 1$ cluster. Why this step? A 1 KB file still needs a whole 4 KB cluster — this is Cell C repeated 12,000 times.
Waste per file: $4096 - 1024 = 3072$ B $= 3$ KB.
Total charged: $12000 \times 4096 = 49, 152, 000$ B $= 48000$ KB $= 46.875$ MB. Why this step? Every file occupies one full cluster; multiply by count.
Total internal waste: $12000 \times 3072 = 36, 864, 000$ B $= 36000$ KB $= 35.156$ MB. Why this step? Sum the per-file tails.

Verify: useful data $= 12000 \times 1024 = 12, 288, 000$ B; and $12, 288, 000 + 36, 864, 000 = 49, 152, 000$ = total charged. ✓ Fully $75%$ of the disk is wasted — the danger of large blocks with tiny files.

Example 9 — Cell J (exam twist: which cure, and the limit)

Worked example Exam claim to judge:

"Switching from segmentation to paging will remove ALL fragmentation." Under paging with frame $B$ , what is the worst-case internal waste for one process, and what fragmentation remains? Forecast: true or false — does paging give zero waste?

External under paging: any free frame fits any request (all frames identical size), so there are no unusable external holes → external fragmentation $= 0$ . Why this step? This is the strength of fixed-size units — no awkward-size gaps can form.
Internal under paging: the last page of a process is partial. Worst case the process overshoots a page boundary by 1 byte, so it takes a whole extra frame of which $B - 1$ bytes are wasted. Why this step? Maximum tail waste is just under one full frame.
Worst-case internal per process $= B - 1$ bytes. Why this step? $S mod B = 1$ gives waste $B - 1$ , the largest a single leftover byte can force.
Verdict: the claim is false. Paging removes external fragmentation but keeps up to $B - 1$ bytes of internal waste per process.

Verify: take $B = 4096$ , $S = 4097$ . $N = ⌈ 4097/4096 ⌉ = 2$ ; waste $= 2 \times 4096 - 4097 = 8192 - 4097 = 4095 = B - 1$ . ✓ The bound is tight.

Recall One-line recall of the whole matrix

Internal formula ::: $⌈ S / B ⌉ B - S$ ; zero only when $S$ is a multiple of $B$ ; worst case $B - 1$ ; system total = sum of tails ( $\approx B /2$ each on average). External ratio ::: $1 - \frac{largest free block}{total free}$ ; equals 0 for one hole, rises toward 1 as memory shatters; compaction drives it to 0 without changing total free.

Back to the parent topic. Related machinery: Paging, Segmentation, Dynamic Memory Allocation, Memory Allocation Strategies, Virtual Memory, Address Binding.