Memory allocation — contiguous (first-fit, best-fit, worst-fit): Visual walkthrough

We use one running scenario (the parent's Worked Example 1):

Holes in address order: $A = 100, B = 500, C = 200, D = 300, E = 600$ (all KB).
Requests in arrival order: $P_{1} = 212, P_{2} = 417, P_{3} = 112, P_{4} = 426$ (KB).

Step 1 — Draw the shelf and name every piece

WHAT. RAM is one long horizontal strip. The dark bars are memory already used by other programs; the light bars between them are holes — unbroken stretches of free space. We label each hole with a letter and its size in KB.

WHY. Every algorithm we study does exactly one thing: it looks at this list of holes and picks one. So the only state that matters is "which holes exist, in what order, at what size." Before we can pick, we must be able to read the shelf.

PICTURE. Look at the strip below. Reading left to right (this direction is address order — low address on the left, high on the right) the free holes are $A, B, C, D, E$ . Their sizes are printed inside them. "Address order" is just the physical left-to-right order on the shelf — remember it, because first-fit scans in exactly this order.

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

Step 2 — One placement: cutting a chunk and leaving a leftover

WHAT. Take request $s$ , choose a hole of size $H$ with $H \geq s$ , and place the program at the left end of that hole. The hole splits into two parts: the program (size $s$ ) and a new smaller hole (size $H - s$ ).

WHY. This is the atomic move every rule performs; the rules differ only in which $H$ they choose. Understand this one cut and you understand all three algorithms — they are just three answers to "which $H$ ?".

PICTURE. In the figure, the teal hole of size $H$ is sliced by the orange knife at position $s$ from its left edge. Left of the knife becomes used; right of the knife (the plum sliver, width $H - s$ ) becomes a new hole.

$new tiny hole leftover = hole we cut H - program size s$

If $H - s = 0$ : the knife lands exactly on the right edge — the hole vanishes completely.
If $H - s > 0$ : a real sliver remains, sitting at address (hole's base $+ s$ ).
If $H < s$ : illegal — the knife would cut past the hole's right edge. This hole is not a candidate at all.

Step 3 — First-fit runs: stop at the first hole that fits

WHAT. For each request, scan holes in address order ( $A \to B \to C \to D \to E$ ) and stop at the very first one with size $\geq s$ . Cut there.

WHY. Because we stop early, first-fit is the fastest rule: on average it touches only the first few holes. First-fit still tests each hole it visits (is $size (h_{i}) \geq s$ ?), but it does not compare candidates against each other — the moment one passes the test, we commit. That early stop is the source of its speed.

PICTURE. The green check marks where the scan stops; grey crosses are holes it skipped past (too small) or never reached. Watch $P_{1} = 212$ : it steps over $A = 100$ (cross, $100 < 212$ ), lands on $B = 500$ (check), and cuts — leaving $B = 288$ .

Full run:

$P_{1} = 212$ : $A = 100$ ✗, $B = 500$ ✓ → leftover $B = 288$ .
$P_{2} = 417$ : $A, B = 288, C = 200, D = 300$ all too small, $E = 600$ ✓ → leftover $E = 183$ .
$P_{3} = 112$ : $A = 100$ ✗, $B = 288$ ✓ → leftover $B = 176$ .
$P_{4} = 426$ : holes now $A = 100, B = 176, C = 200, D = 300, E = 183$ — none $\geq 426$ . $P_{4}$ FAILS.

Step 4 — Best-fit runs: pick the tightest hole

WHAT. For each request, scan all holes, collect every candidate with size $\geq s$ , and pick the smallest such candidate — the tightest fit.

WHY. A tight fit shaves off the smallest possible leftover this step, so intuitively it "wastes least right now." Price: we must scan the entire free list to be sure we found the smallest — slower than first-fit.

PICTURE. For $P_{1} = 212$ the candidates ( $\geq 212$ ) are $B = 500, D = 300, E = 600$ ; the shortest of them, $D = 300$ , glows plum (chosen), leaving only $88$ . Compare this to first-fit, which grabbed the big $B = 500$ and wasted $288$ .

Full run:

$P_{1} = 212$ : candidates ${B = 500, D = 300, E = 600}$ → smallest $D = 300$ → leftover $88$ .
$P_{2} = 417$ : candidates ${B = 500, E = 600}$ → smallest $B = 500$ → leftover $83$ .
$P_{3} = 112$ : candidates ${C = 200, E = 600}$ (note $D = 88 < 112$ , $B = 83 < 112$ ) → smallest $C = 200$ → leftover $88$ .
$P_{4} = 426$ : candidate ${E = 600}$ → $E$ → leftover $174$ . All four succeed.

Step 5 — Worst-fit runs: pick the widest hole

WHAT. For each request, scan all holes and pick the largest one (regardless of how much bigger it is than $s$ ).

WHY. The hope: cutting $s$ out of the biggest hole leaves the biggest possible leftover, which stays "reusable." The danger, which the picture reveals, is that you eat your big holes first — so a big future request has nothing left.

PICTURE. For $P_{1} = 212$ every hole is a candidate (all could be widest-compared); the tallest bar $E = 600$ is chosen and shrinks to $388$ . Notice $E$ getting nibbled twice — by the end there is no large hole for $P_{4}$ .

Full run:

$P_{1} = 212$ : largest $E = 600$ → leftover $388$ .
$P_{2} = 417$ : largest $B = 500$ → leftover $83$ .
$P_{3} = 112$ : largest now $E = 388$ → leftover $276$ .
$P_{4} = 426$ : holes $A = 100, B = 83, C = 200, D = 300, E = 276$ — largest is $D = 300 < 426$ . $P_{4}$ FAILS.

Step 6 — The degenerate cases (never leave the reader stranded)

WHAT. The corners the running example didn't hit. Each is a legal input the algorithm must handle.

WHY. A rule you only understand on "nice" inputs will surprise you on real workloads. Here are the four edges.

PICTURE. Four mini-shelves, labelled ① ② ③ ④ top to bottom, matching the four numbered cases below:

① Exact fit ( $H = s$ ): leftover $= 0$ . The hole disappears entirely — no sliver, no fragmentation from this step. Best possible outcome.
② No hole fits ( $size (h_{i}) < s$ for every $i$ ): the request fails even if the total free space $\sum_{i} size (h_{i}) \geq s$ . Two 30 KB holes cannot host a 50 KB program — contiguity forbids splitting. (This is external fragmentation biting.)
③ Zero-size request ( $s = 0$ ): trivially satisfiable by any hole; changes nothing — a well-behaved allocator returns immediately.
④ Ties (two holes equally good): best-fit and worst-fit break ties by address order (lowest first), matching first-fit's scan direction — a convention, but a fixed one, so results are reproducible.

The one-picture summary

Below, all three rules face the same request $P_{1} = 212$ on the same starting shelf. A legend in the corner maps each arrow's color to its algorithm: orange → first-fit (grabs $B$ , first that fits), plum → best-fit (grabs $D$ , tightest), teal → worst-fit (grabs $E$ , widest). Each arrow is also labelled in words next to its target, so the mapping never depends on color alone — the entire chapter in one image.

Recall Feynman: the whole walkthrough in plain words

Picture a long shelf with a few empty gaps of different widths. A new book needs a gap wide enough to fit in one piece — it can't be sawn in half. First-fit: walk from the left, drop the book in the first gap it fits — quick, but you might jam a small book into a huge gap and waste it. Best-fit: check every gap and use the snuggest one — barely any space wasted this time, but you leave behind lots of gaps just a hair too small for anything. Worst-fit: always use the widest gap so the leftover stays roomy — but you chew through your big gaps fast, and later a fat book has nowhere to go. On our shelf best-fit happened to save the last big book because it left the widest gap alone until the end; first-fit and worst-fit had already eaten it. The trick is: which gap you pick reshapes all the gaps that remain, and that decides who gets in later. No rule always wins — it depends on who shows up next.

Active Recall

Best-fit's choice for

P_{1} = 212

among

A = 100, B = 500, C = 200, D = 300, E = 600

D = 300

(smallest candidate

\geq 212

), leftover

88

Why does first-fit fail

P_{4} = 426

in the example?

It burned into

B

and

E

early; remaining holes max out at

300 < 426

What is the leftover formula and its exact-fit case?

leftover = H - s

; when

H = s

leftover is

0

and the hole vanishes.

Can a request with

s = 50

fail when two

30

KB holes are free?

Yes — contiguity forbids splitting; no single hole reaches

50

Which rule leaves the biggest hole untouched longest, and why did that matter here?

Best-fit — it kept

E = 600

free for the large

P_{4} = 426

Connections

Parent topic (Hinglish)
Fragmentation — the slivers left by these cuts are external fragmentation.
Compaction — slides allocated blocks together to merge scattered leftovers.
Free List Management — how the OS stores and scans the hole list you saw here.
Paging — removes the contiguity requirement that made the corner case fail.
Segmentation — variable-size contiguous chunks, same placement rules per segment.
Buddy System — a different splitting scheme that bounds leftover sizes.