Memory allocation — contiguous (first-fit, best-fit, worst-fit): Worked examples

Before we start, one symbol we lean on constantly:

The scenario matrix

Every case a contiguous-allocation problem can throw at you is one of these cells. Each worked example below is tagged with the cell(s) it covers.

Cell	Case class	What is unusual	Covered by
C1	Exact fit ( $H = s$ , leftover $= 0$ )	hole vanishes entirely	Ex 1
C2	Tie — two holes equally "best" or "worst"	tie-break rule (lowest address)	Ex 2
C3	Request fails: no hole big enough	allocation returns failure	Ex 3
C4	Fails despite total free ≥ request	fragmentation, not shortage	Ex 3
C5	Zero / degenerate input ( $s = 0$ , empty free list)	boundary behaviour	Ex 4
C6	Sliver accumulation (best-fit worst case)	tiny dead leftovers pile up	Ex 5
C7	Big-hole starvation (worst-fit weakness)	large future request starves	Ex 6
C8	Same workload, all 3 rules diverge	rule choice changes success	Ex 7
C9	Real-world word problem (parking lot / disk)	translate story → holes	Ex 8
C10	Exam twist: 50% rule / after a free merges holes	analysis + coalescing	Ex 9, Ex 10

We visualise the shelf-of-holes idea once so every later example can lean on it:

Figure — Memory allocation — contiguous (first-fit, best-fit, worst-fit)

Ex 1 — Exact fit (Cell C1)

Step 1. List holes that satisfy $∣ h ∣ \geq 250$ : B=250, C=400. Why this step? Best-fit only ever chooses among holes that actually fit. A=100 is disqualified immediately ( $100 < 250$ ).

Step 2. Pick the smallest qualifying hole. Between 250 and 400 the smallest is B=250. Why this step? "Best-fit = tightest fit" means minimum $∣ h ∣ - s$ ; here $250 - 250 = 0$ , the tightest possible.

Step 3. Compute leftover: $H - s = 250 - 250 = 0$ . Why this step? The leftover formula tells us the shard size. Zero leftover means the hole is fully consumed and is removed from the free list — not left as a 0-size hole.

Result: B disappears entirely. Free list becomes A=100, C=400.

Verify: leftover $= 250 - 250 = 0$ ; remaining free total $= 100 + 400 = 500$ ; original free was $100 + 250 + 400 = 750$ ; we allocated 250, so $750 - 250 = 500$ . ✓

Ex 2 — The tie-break (Cell C2)

Step 1. Qualifying holes ( $\geq 180$ ): A=300, B=200, C=300. Smallest is B=200. Why this step? Wait — B=200 is smaller than both 300s and still $\geq 180$ . So there is no tie for best-fit here; B wins outright.

Step 2. But suppose instead the request were P=250. Now qualifying holes are A=300, C=300 (B=200 fails). Both are size 300 — a genuine tie. Why this step? We engineered the actual tie so you see the rule.

Step 3. Tie-break: choose the hole at the lowest address (first in the list). So A, not C. Why this step? When sizes are equal, the standard convention is address order — it makes the algorithm deterministic and matches how the free list is traversed.

Result: For P=250, best-fit picks A, leftover $= 300 - 250 = 50$ ; C stays 300.

Verify: leftover $= 300 - 250 = 50$ ; free list becomes A=50, B=200, C=300, total $= 550$ ; original $= 800$ ; $800 - 250 = 550$ . ✓

Ex 3 — Failure despite plenty of free memory (Cells C3, C4)

Step 1. Total free $= 30 + 30 + 30 + 30 = 120 \geq 50$ . Tempting to say "yes". Why this step? To expose the trap: summing free memory is the wrong test.

Step 2. Apply the contiguity requirement: a request needs one single hole $\geq s$ . Scan every hole: $30 < 50$ for all four. Why this step? Contiguous allocation cannot stitch two holes together. No matter which rule (first/best/worst), the set of qualifying holes is empty.

Step 3. Since no hole qualifies, allocation fails — for all three rules identically.

Result: P=50 FAILS even though 120 KB is free. This is pure external fragmentation.

Verify: $max (30, 30, 30, 30) = 30 < 50$ so no single hole fits; total $= 120 \geq 50$ but that is irrelevant to a contiguous allocator. ✓

Ex 4 — Degenerate inputs (Cell C5)

Step 1 — (a) $s = 0$ . Any hole (or none) satisfies $∣ h ∣ \geq 0$ . A well-behaved allocator treats a 0-size request as a no-op: allocate nothing, leave the free list untouched. Why this step? The condition $∣ h ∣ \geq s$ is trivially true, so first-fit would "pick" the first hole and split it with leftover $H - 0 = H$ — i.e. no change. Cleanest to reject/ignore.

Step 2 — (b) empty free list. There are zero holes to scan. Every rule returns failure immediately. Why this step? All three rules begin by scanning the free list; an empty list gives an empty candidate set → fail. No special case needed.

Step 3 — (c) exact whole-hole request. One hole remains, say H=400, request P=400. Leftover $= 400 - 400 = 0$ , hole removed, free list becomes empty. Why this step? Same mechanic as Ex 1 but it empties memory. Confirms exact fit works at the boundary too.

Result: (a) no-op, (b) fail, (c) succeed with the free list emptied.

Verify: (a) leftover $= H - 0 = H$ ⇒ free unchanged. (b) candidate count $= 0$ ⇒ fail. (c) $400 - 400 = 0$ ⇒ list empty. ✓

Ex 5 — Best-fit slivers the memory (Cell C6)

Step 1. P1=12. Qualifying ( $\geq 12$ ): 20, 15, 13. Tightest = 13, leftover $= 13 - 12 = 1$ . Why this step? Best-fit grabs the closest match, shaving off a 1 KB sliver — too small to ever reuse.

Step 2. P2=12. Remaining holes: 20, 15, (1). Qualifying: 20, 15. Tightest = 15, leftover $= 15 - 12 = 3$ . Why this step? Another tiny 3 KB dead shard is born.

Step 3. P3=12. Remaining: 20, (3), (1). Qualifying: 20 only. Leftover $= 20 - 12 = 8$ . Why this step? Even the big hole now yields an 8 KB shard.

Result: leftovers 1, 3, 8 — total $12$ KB free but no single hole ≥ 12. A fourth P4=12 would FAIL.

Verify: leftovers $13 - 12 = 1$ , $15 - 12 = 3$ , $20 - 12 = 8$ ; $max (1, 3, 8) = 8 < 12$ so a 4th request of 12 fails; sum $= 12$ . ✓

Ex 6 — Worst-fit starves a big request (Cell C7)

Step 1. P1=200. Largest hole = 600, leftover $= 600 - 200 = 400$ . Why this step? Worst-fit always chops the biggest hole, hoping the remainder stays useful.

Step 2. P2=200. Holes now 400, 500, 300. Largest = 500, leftover $= 500 - 200 = 300$ . Why this step? We just ate into the second-biggest hole.

Step 3. P3=450. Holes now 400, 300, 300. Largest = 400 $< 450$ — and no other hole $\geq 450$ . FAILS. Why this step? By spreading requests across the biggest holes, worst-fit demolished both large holes; the 450 has nowhere to land.

Result: the 450 FAILS — the exact starvation the parent warned about.

Verify: after two placements holes are ${600 - 200, 500 - 200, 300} = {400, 300, 300}$ ; $max = 400 < 450$ ⇒ fail. ✓

Ex 7 — Same workload, three rules diverge (Cell C8)

Step 1 — First-fit. P1→B(500), lo 288. P2→E(600), lo 183. P3→B(288)→176. P4: holes {100,176,200,300,183}, max=300<426 → FAIL. Why this step? First-fit stops at the first fit each time — no size comparison — so it left no big enough hole for P4.

Step 2 — Best-fit. P1→D(300)lo88. P2→B(500)lo83. P3→C(200)lo88. P4→E(600)lo174. ALL SUCCEED. Why this step? Tightest fits preserved E=600 untouched until P4 needed it.

Step 3 — Worst-fit. P1→E(600)lo388. P2→B(500)lo83. P3→E(388)lo276. P4: max hole 300<426 → FAIL. Why this step? Worst-fit gnawed the big holes early; 426 starved.

Result: Best-fit places all four; first-fit and worst-fit strand P4.

Verify (best-fit leftovers): $300 - 212 = 88$ , $500 - 417 = 83$ , $200 - 112 = 88$ , $600 - 426 = 174$ , all $\geq 0$ ⇒ all succeed. ✓

Ex 8 — Word problem: the parking lot (Cell C9)

Step 1. Car 4 m, first-fit: scan 5≥4 → park in gap-1. Leftover $5 - 4 = 1$ . Why this step? First-fit takes the first gap that fits, in position order along the street.

Step 2. Van 7 m: scan 1(no), 8≥7 → gap-2. Leftover $8 - 7 = 1$ . Why this step? 1 m is too short; 8 m is the first that fits.

Step 3. Bus 11 m: scan 1,1,3,12≥11 → gap-4. Leftover $12 - 11 = 1$ . Why this step? First-fit reaches the 12 m gap and parks. The bus succeeds.

Result: all three park; leftovers are three useless 1 m slivers.

Verify: leftovers $5 - 4 = 1$ , $8 - 7 = 1$ , $12 - 11 = 1$ ; the bus's chosen gap $12 \geq 11$ ⇒ parks. ✓

Ex 9 — Exam twist: the 50% rule (Cell C10)

Step 1. The 50% rule (a classic analysis of first-fit) states: for $N$ allocated blocks, about $0.5 N$ blocks' worth of memory is lost to fragmentation. Why this step? It is an empirical/analytical result quoted in the parent's mistakes section — the exam expects the number $N /2$ .

Step 2. Compute lost $= 0.5 \times 1000 = 500$ block-equivalents. Why this step? Direct substitution.

Step 3. Fraction of free memory that is unusable: free $= 0.4 N = 400$ blocks; but the rule counts fragmentation relative to allocated. A common exam form: if memory $=$ allocated $+$ free $= 1000 + 400 = 1400$ blocks and $\approx 500$ are fragmentation-bound within the free/hole structure, the wasted fraction $\approx \frac{500}{1400} \approx 0.357 = 35.7%$ . Why this step? Shows how to convert the count into a percentage the exam wants.

Result: $\approx 500$ blocks lost; $\approx 35.7%$ of total memory affected.

Verify: $0.5 \times 1000 = 500$ ; $500/1400 = 0.357 \dots$ ✓

Ex 10 — Exam twist: a free() coalesces holes (Cell C10)

Step 1. Freeing the 60 block makes it a hole. Now address order is: [hole 40][hole 60][hole 30][used 50][hole 20]. Why this step? A free() turns an allocated block back into a hole — but adjacency matters next.

Step 2. Coalescing: adjacent holes merge. The 40 and the newly-freed 60 are neighbours ⇒ merge to 100. The 30 sits after them but is separated from 100? Check adjacency: order is 40,60,30 all contiguous in address (no used block between the first three) ⇒ they merge into $40 + 60 + 30 = 130$ . Why this step? Compaction and Free List Management rely on merging neighbours so holes don't stay artificially fragmented. Only address-adjacent holes merge.

Step 3. New free list: [hole 130][used 50][hole 20]. Request 120: is any hole $\geq 120$ ? Yes, 130. SUCCEEDS, leftover $130 - 120 = 10$ . Why this step? Coalescing converted three small holes into one big enough hole — the request that failed before now fits.

Result: free list after coalescing = 130, 20; the 120 request succeeds with leftover 10.

Verify: merged hole $= 40 + 60 + 30 = 130 \geq 120$ ; leftover $= 130 - 120 = 10$ ; the un-merged max $= 60 < 120$ so coalescing was essential. ✓

Active Recall

What is the outcome when a request exactly equals the chosen hole size?

Leftover is 0, the hole is removed from the free list — zero fragmentation.

Best-fit tie-break rule when two holes are equally tight?

Choose the hole at the lowest address (first in list).

Can a 50 KB request fail when four 30 KB holes (120 KB total) are free?

Yes — no single contiguous hole is ≥ 50; total free is irrelevant.

What does a first-fit allocator do with a size-0 request?

Nothing — it is a no-op; the free list is unchanged.

Why does worst-fit starve large future requests?

It consumes the biggest holes first, leaving no large hole for a later big request.

What must happen to address-adjacent holes when a block is freed?

They coalesce (merge) into one larger hole.

The 50% rule predicts how much loss for N allocated blocks?

About N/2 blocks' worth lost to fragmentation.

Connections

Paging — removes contiguity so Ex 3's failure never happens.
Compaction — slides blocks to merge scattered holes (fixes Ex 3, Ex 5).
Free List Management — the coalescing of Ex 10 lives here.
Fragmentation — the sliver accumulation of Ex 5 quantified.
Buddy System — an alternative allocator with power-of-two rounding.
Segmentation · Virtual Memory — build on these placement ideas.