Fragmentation — internal vs external, compaction: Exercises

Before we start, here is the one-screen toolbox we will reuse. Every symbol is spelled out in words so line one is readable by anyone.

Formula The three tools we will use over and over

Internal waste of one allocation. A process asks for $S$ bytes ( $S$ = "size wanted"). Memory is handed out only in fixed blocks of size $B$ bytes ( $B$ = "block size"). The number of whole blocks needed is $N = ⌈ \frac{S}{B} ⌉$ , where $⌈ x ⌉$ ("ceiling of $x$ ") means round up to the next whole number — because you cannot get a fraction of a block. $Internal = N \cdot B - S = ⌈ \frac{S}{B} ⌉ B - S$ This is "what we were given" minus "what we needed".
External fragmentation ratio. When free memory is scattered into separate holes, this number between $0$ and $1$ says how badly: $Ratio = 1 - \frac{largest single free hole}{total free memory}$ $0$ = all free memory is one clean block; near $1$ = badly scattered.
Compaction slides allocated blocks to one side so all the holes merge into one contiguous free block. It cures external fragmentation only, and it needs run-time address binding (a base/relocation register) so code can move.

Level 1 — Recognition

Goal: just name the flavour of waste and read the formulas — no arithmetic tricks yet.

Exercise 1.1

A process is given one $4 KB$ page but uses only $3 KB$ of it. Name the fragmentation type and give the wasted amount.

Recall Solution 1.1

The waste sits inside a single block the process already owns → internal fragmentation. Wasted $= 4 KB - 3 KB = 1 KB$ .

Exercise 1.2

Free memory is split as holes of $20 KB$ , $10 KB$ , $20 KB$ . A process wants $40 KB$ and is refused. Name the fragmentation type.

Recall Solution 1.2

Total free $= 20 + 10 + 20 = 50 KB \geq 40 KB$ , yet no single hole is big enough. Waste lives between blocks → external fragmentation.

Exercise 1.3

Which of the two schemes, Paging or Segmentation, suffers from external fragmentation, and which from internal?

Recall Solution 1.3

Paging uses fixed-size frames → any free frame fits any request → no external, but a partly-used last page gives internal. Segmentation uses variable-size segments → awkward leftover holes → external.

Level 2 — Application

Goal: plug numbers into the two formulas correctly, especially the ceiling.

Exercise 2.1

A process needs $S = 5300$ bytes. Blocks are $B = 1024$ bytes. Compute the number of blocks and the internal fragmentation.

Recall Solution 2.1

Blocks: $N = ⌈ \frac{5300}{1024} ⌉ = ⌈ 5.176 ⌉ = 6$ . Why 6? Five blocks give $5 \times 1024 = 5120 < 5300$ , so one more is forced. Given: $6 \times 1024 = 6144$ bytes. Internal waste: $6144 - 5300 = 844$ bytes.

Exercise 2.2

Three processes of sizes $S_{1} = 2000$ , $S_{2} = 4097$ , $S_{3} = 8192$ bytes are each paged with $B = 4096$ . Find the total internal fragmentation across all three.

Recall Solution 2.2

$P_{1}$ : $N = ⌈ 2000/4096 ⌉ = 1$ , given $4096$ , waste $= 4096 - 2000 = 2096$ .
$P_{2}$ : $N = ⌈ 4097/4096 ⌉ = 2$ , given $8192$ , waste $= 8192 - 4097 = 4095$ . Why 2 blocks? One byte over a full block still forces a whole second block.
$P_{3}$ : $N = ⌈ 8192/4096 ⌉ = 2$ , given $8192$ , waste $= 8192 - 8192 = 0$ . A perfect multiple wastes nothing. Total internal $= 2096 + 4095 + 0 = 6191$ bytes.

Exercise 2.3

Free holes are $40 KB$ , $30 KB$ , $50 KB$ . Compute the external fragmentation ratio.

Recall Solution 2.3

Total free $= 40 + 30 + 50 = 120 KB$ . Largest hole $= 50 KB$ . $Ratio = 1 - \frac{50}{120} = 1 - 0.4167 = 0.5833$ Over half the free memory is unusable for any request larger than $50 KB$ .

Level 3 — Analysis

Goal: reason about averages, trade-offs, and sequences of allocations.

Exercise 3.1

A system runs $200$ processes, each paged with $B = 4096$ bytes, and process sizes are effectively random relative to $B$ . Estimate the total internal fragmentation, and explain the reasoning.

Recall Solution 3.1

For a random size, the last (partial) block is on average half full, so expected waste per process $\approx B /2 = 4096/2 = 2048$ bytes. Why $B /2$ ? The leftover $S mod B$ is uniform over $[0, B)$ , so the wasted tail $B - (S mod B)$ averages $B /2$ . Total estimate $= 200 \times 2048 = 409600$ bytes $\approx 400 KB$ .

Exercise 3.2

Same $200$ processes. An engineer halves the block size to $B = 2048$ . What happens to expected internal fragmentation, and what is the hidden cost?

Recall Solution 3.2

New expected waste per process $\approx B /2 = 1024$ bytes; total $\approx 200 \times 1024 = 204800$ bytes $\approx 200 KB$ . Internal waste roughly halves. Hidden cost: smaller blocks mean more blocks per process, so the page table grows (more entries to store and walk). It is a trade-off, not a free win — see Memory Allocation Strategies.

Exercise 3.3

Memory of $100 KB$ is allocated with variable partitions. Requests arrive: allocate $30 KB$ (A), $20 KB$ (B), $30 KB$ (C); then free B; then request $25 KB$ (D). Using first-fit (Dynamic Memory Allocation / Memory Allocation Strategies), does D fit? Compute the external fragmentation ratio at the moment D arrives.

Recall Solution 3.3

Layout after A, B, C (addresses low→high): $[A 30] [B 20] [C 30]$ , with a tail hole of $100 - 80 = 20 KB$ . Free B: layout $[A 30] [free 20] [C 30] [free 20]$ . Free holes now: $20 KB$ and $20 KB$ ; total free $= 40 KB$ , largest $= 20 KB$ . D needs $25 KB$ : first-fit scans holes, finds $20 < 25$ and $20 < 25$ → D fails, even though $40 \geq 25$ . $Ratio = 1 - \frac{20}{40} = 0.5$ See the picture below.

Figure — Fragmentation — internal vs external, compaction

Level 4 — Synthesis

Goal: combine tools — compaction, ratios, and before/after reasoning.

Exercise 4.1

Take the failing state from Exercise 3.3: $[A 30] [free 20] [C 30] [free 20]$ inside $100 KB$ . Apply compaction, then re-attempt request D ( $25 KB$ ). Show the layout, the new ratio, and how many kilobytes were moved.

Recall Solution 4.1

Compact: slide C down against A so both holes pool at the top: $[A 30] [C 30] [free 40]$ . Now the single free block is $40 KB \geq 25 KB$ → D fits. After placing D: $[A 30] [C 30] [D 25] [free 15]$ . New ratio (before placing D): one hole of $40 KB$ → $Ratio = 1 - \frac{40}{40} = 0$ (perfectly consolidated). Bytes moved: only $C$ had to slide (A already at the bottom). So $30 KB$ were copied. Cost is proportional to bytes moved.

Exercise 4.2

A colleague proposes: "compact after every free to keep the ratio at $0$ ." Give two reasons this is a bad idea, and name the scheme that sidesteps the whole problem.

Recall Solution 4.2

Compaction copies memory and pauses processes ("stop the world"); doing it after every free wastes huge CPU time relocating blocks that may be freed again seconds later.
It requires processes to be relocatable at run time and re-updates base registers each time — overhead on every event. Sidestep: Paging uses fixed frames so external fragmentation cannot occur — any frame fits any request — at the price of small internal waste. See also Virtual Memory, which layers on top of paging.

Exercise 4.3

A $256 MB$ region is fully carved into fixed partitions of $16 MB$ each. Nine processes of sizes $9, 15, 16, 3, 12, 16, 10, 7, 14$ MB are placed one per partition. Compute total internal fragmentation and the number of empty partitions left.

Recall Solution 4.3

Partitions available $= 256/16 = 16$ . Processes placed $= 9$ , so empty partitions $= 16 - 9 = 7$ . Internal waste per placed process $= 16 - S$ (each fills exactly one $16 MB$ partition): $(16 - 9) + (16 - 15) + (16 - 16) + (16 - 3) + (16 - 12) + (16 - 16) + (16 - 10) + (16 - 7) + (16 - 14)$ $= 7 + 1 + 0 + 13 + 4 + 0 + 6 + 9 + 2 = 42 MB .$ Note: the $7$ empty partitions ( $112 MB$ ) are unallocated free space, not internal fragmentation — internal counts only waste inside allocated partitions.

Level 5 — Mastery

Goal: design, quantify a full trade-off, and defend the choice.

Exercise 5.1

You must serve $1000$ processes averaging $S = 5000$ bytes each, on a machine with a page-table cost of $8$ bytes per page-table entry (one entry per frame a process uses). Compare block size $B = 4096$ vs $B = 1024$ on (a) total expected internal fragmentation and (b) total page-table bytes. Which do you pick, and why?

Recall Solution 5.1

(a) Internal fragmentation (expected $\approx B /2$ per process):

$B = 4096$ : $1000 \times 2048 = 2048000$ bytes $\approx 2.05 MB$ .
$B = 1024$ : $1000 \times 512 = 512000$ bytes $\approx 0.51 MB$ .

(b) Page-table bytes (entries per process $= ⌈ S / B ⌉$ , $\times 1000 \times 8$ ):

$B = 4096$ : $⌈ 5000/4096 ⌉ = 2$ entries → $1000 \times 2 \times 8 = 16000$ bytes.
$B = 1024$ : $⌈ 5000/1024 ⌉ = 5$ entries → $1000 \times 5 \times 8 = 40000$ bytes.

Combined overhead (waste + table):

$B = 4096$ : $2048000 + 16000 = 2064000$ bytes.
$B = 1024$ : $512000 + 40000 = 552000$ bytes.

Pick $B = 1024$ : its total overhead is far smaller here because the internal-fragmentation saving ( $\approx 1.5 MB$ ) dwarfs the extra page-table cost ( $24 KB$ ). Caveat: if processes were tiny (near one page each), the table cost could dominate — always run the numbers.

Exercise 5.2

Design decision: a real-time system cannot tolerate long pauses but runs variable-size segments that fragment externally. It refuses to use compaction (too disruptive). Propose a scheme that removes external fragmentation without a stop-the-world pause, and state the fragmentation cost you accept in return.

Recall Solution 5.2

Switch from Segmentation (variable blocks) to Paging (fixed frames). Because every frame is identical and any frame satisfies any request, external fragmentation is eliminated with no relocation pass at all — no copying, no pause. Cost accepted: a small internal fragmentation on each process's last partial page (expected $\approx B /2$ ). This is the classic trade: give up a little internal waste to buy freedom from external waste and from compaction pauses. Layering Virtual Memory on top then also frees you from needing all frames resident at once.

Recall One-line recap of every level

L1 name the flavour ::: inside a block = internal; between blocks = external. L2 plug the formulas ::: $⌈ S / B ⌉ B - S$ and $1 - \frac{largest}{total}$ ; always round up. L3 reason about averages ::: expected internal waste $\approx B /2$ per process; smaller $B$ helps but bloats the page table. L4 apply compaction ::: it merges holes to ratio $0$ , cost $\propto$ bytes moved; empty partitions are not internal waste. L5 design & defend ::: minimise total overhead = internal waste + table cost; paging kills external without a pause.