The room-letting problem
In the last guide the MMU gave each process exactly one base and one limit, which forces each one into a single unbroken run of RAM — what we called contiguous allocation. That keeps the picture simple, but it hands the kernel a real-estate problem. RAM is one long corridor of rooms. Processes arrive wanting a room of some size, stay a while, then leave and hand their room back. The kernel, playing landlord, must decide which stretch of corridor to give each newcomer — and the choices it makes early on quietly shape how much usable space is left later.
Picture the corridor after a busy morning. The system started with one big empty stretch; processes A, B, C, D moved in side by side. Then B and D finished and left, so now the corridor reads: A occupied, then a hole where B was, then C occupied, then a hole where D was, then empty to the end. The kernel keeps a list of these free holes. When the next process arrives needing, say, 40 KB, the landlord scans that list looking for a hole big enough. The interesting question is not whether a hole fits — it is which hole to pick when several would do.
First fit, best fit, worst fit
There are three classic strategies for picking a hole, and they are exactly as their names suggest. First fit (first fit) scans from the start and grabs the very first hole big enough, no matter what comes after — fast, because it stops the moment it finds one. Best fit (best fit) scans the whole list and picks the smallest hole that still fits, on the theory that this wastes the least space right now. Worst fit (worst fit) does the opposite: it picks the largest hole, hoping the big leftover chunk stays useful rather than becoming a useless sliver. All three answer the same question — which gap? — with a different gut instinct.
Free holes (in order): [ 100 KB ] ... [ 50 KB ] ... [ 30 KB ] ... [ 80 KB ] Request: a process needs 45 KB first fit -> 100 KB hole (first one that fits; leftover 55 KB) best fit -> 50 KB hole (smallest that fits; leftover 5 KB) <- tiny scrap worst fit -> 100 KB hole (largest hole; leftover 55 KB) The 30 KB hole can never hold this 45 KB request -- too small.
Here is an honest surprise that catches most people: best fit, despite its hopeful name, is usually not the best. Because it leaves behind the smallest possible leftover each time, it tends to litter the corridor with tiny scraps that no future process can use, and it pays for a full scan of the list every single time. Decades of simulation point to first fit as the practical winner — nearly as good as best fit at saving space, and faster because it stops early. Worst fit tends to do poorly on both counts. The lesson is worth keeping: an allocation rule that looks locally tidy can be globally wasteful.
Two kinds of waste
No matter which fit you choose, memory leaks away into waste in two distinct ways, and it is worth being precise about which is which. External fragmentation (external fragmentation) is the corridor problem we just watched: free space exists, but it is scattered across many small holes between occupied blocks, so no single hole is big enough for the next request even though the total free space would easily cover it. The room is there; it is just chopped into pieces too small to rent. This is the curse of contiguous allocation, and best fit makes it worse by manufacturing tiny scraps.
Internal fragmentation (internal fragmentation) is the opposite kind of waste: space lost inside a block that was handed out. It happens when the kernel allocates in fixed-size chunks and your request does not fill its chunk exactly. Ask for 18 KB when memory is doled out in 20 KB blocks, and you get a whole 20 KB block — the 2 KB you did not need is locked inside your allocation, unusable by anyone but invisible as a free hole. Nobody can rent it because it is officially yours; it is simply wasted. The wasted space is trapped within, not stranded between.
Sliding the rooms together: compaction and swapping
If external fragmentation has chopped your free space into useless slivers, one cure is to slide all the occupied blocks down to one end so the holes merge into a single big one at the other. This is compaction (compaction) — like asking every tenant to shuffle toward the lobby so the empty rooms gather at the back into one rentable suite. It works only because of last guide's gift: since the MMU does execution-time relocation, moving a process is as cheap as copying its bytes and changing its base register — no code rewriting needed. But compaction is not free: copying megabytes of memory takes real time, and during the shuffle those processes cannot run, so the kernel does it sparingly.
There is a second, bolder move when RAM simply runs short: take a whole process that is not currently running and copy its entire memory image out to a reserved area on disk, freeing its room for someone else; later, copy it back in to resume. This is swapping (swapping), and the disk region it uses is the swap space. Crucially, when a swapped-out process is brought back, execution-time binding means it can be dropped into a completely different physical spot than it left — the kernel just sets a new base and it runs as if nothing happened. Swapping is what lets the total memory demand of all processes exceed the physical RAM you actually own, by parking idle ones on the much larger, much slower disk.
Why this whole approach is a dead end (and the way out)
Step back and the real trouble is plain: every pain in this guide traces to the one assumption we inherited — a process must occupy a single contiguous block. That is what makes external fragmentation possible at all, what forces the awkward fit decisions, and what makes compaction necessary. Smart fit strategies and occasional compaction only manage the symptom; they never cure the disease, because the disease is contiguity itself. As long as a process needs one unbroken run of RAM, free space scattered into holes will sometimes be unusable no matter how cleverly you choose.
So the honest conclusion of this guide is a question pointing forward. What if we stop demanding that a process live in one piece? If we could chop a process's memory into many small fixed-size pieces and scatter those pieces into any free frames at all, no matter how far apart, then external fragmentation would simply vanish — any free piece can hold any program piece. That radical idea is paging (paging), and it is where the rest of memory management is headed. It does not come for free (the MMU now needs a whole table instead of one base, and you trade in a little internal fragmentation), but it dissolves the central problem of this guide.
Before that leap, the next two guides finish the contiguous-memory story from the program's own side. Guide 4 follows how the linker and loader actually build the runnable image we have been placing — how separately compiled pieces and libraries get stitched together and dropped into a chosen block. Guide 5 then revisits the single-block assumption from a different angle with segmentation, which gives a process several base-and-limit pairs at once — one per logical part like code, data, and stack. Keep today's vocabulary close: fit strategies, the two fragmentations, compaction, and swapping are the language the rest of the rung speaks.