Foundations — Fragmentation — internal vs external, compaction

Before you can read the parent note, you must own every symbol it throws at you. This page builds each one from absolute zero — plain words, then a picture, then why the topic cannot live without it.

0. The stage: what "memory" actually is

Look at the figure: memory is one straight line of numbered boxes. Everything in this topic is about cutting this line into pieces and handing pieces out. The topic needs this picture because both kinds of fragmentation are just "which boxes are wasted" — and you can only point at a wasted box if you can see the ruler.

1. The symbols the parent uses

The parent note fires off $S$, $B$, $N$, $\lceil \rceil$, $\mathrm{mod}$, and a "ratio" formula. Here is each one, in the order that lets the next one make sense.

$S$ — the size a process needs

Why the topic needs it: fragmentation is always given minus needed, and $S$ is the "needed".

$B$ — the block the OS hands out in

In the figure, the ruler is pre-scored into equal blocks of length $B$. A program needing $S$ bytes must take whole blocks only — it cannot stop half-way through a block. That "whole blocks only" rule is the entire cause of internal fragmentation, so $B$ must exist before we can even name that waste.

$N$ — how many blocks that forces

To turn "$S$ bytes" into "$N$ blocks" we need one more symbol.

$\lceil \rceil$ — the ceiling (round UP)

The figure shows $S=5000$, $B=2048$: two blocks reach $4096<5000$ (not enough), so the ceiling jumps us to a third block. The red tail is the boxes in the third block that nobody uses — the internal waste made visible.

$\mathrm{mod}$ — the remainder / leftover

Why the topic needs it: the wasted tail in the last block is $B-(S\mathrm{mod}B)$ — the empty part of the final block. Here $2048-904=1144$, matching the parent's answer. The average-case claim ("last block half full → waste $\approx B/2$") is just the statement that this leftover $S\mathrm{mod}B$ is equally likely to be anywhere in $[0,B)$, so the empty tail averages $B/2$.

2. The "holes" symbols for external fragmentation

External fragmentation needs no ceiling — it needs the idea of holes and a ratio.

The figure shows holes of $40$K, $30$K, $50$K. The total free is their sum $=120$K, but the largest single hole is only $50$K — so a $100$K request fails even though enough total memory exists. That gap between "total free" and "largest usable" is external fragmentation.

3. The one prerequisite behind compaction

Why the topic needs it: compaction slides all used blocks to one end to merge holes into one big block. You can only slide a program if its addresses can be re-bound — hence compaction requires run-time binding. Without it, programs are "nailed down" and cannot be shuffled. See also Virtual Memory and Segmentation for where run-time binding shows up.

4. How it all feeds the topic

Read top-down: the memory line and block size give you $N$ and thus internal waste; the memory line plus scattered holes give you the external ratio; run-time binding unlocks compaction. All three streams pour into the parent topic the Fragmentation note.

Equipment checklist

Test yourself — cover the right side, say the answer aloud.