Contiguous allocation and fragmentation

The simplest possible scheme: give every process one unbroken block of RAM. The compile job gets 212 MB in a row, starting somewhere.

Programs start and finish all afternoon. The music player exits, freeing 100 MB here. A background helper exits, freeing 300 MB there.

After a few hours, memory looks like a shelf of books with gaps everywhere.

Aisha starts a program needing 700 MB. There is 1,700 MB free. It fails.

Why & what

Contiguous allocation means each process gets one continuous range of physical memory. It is easy to describe with two numbers: a base and a length.

When a request arrives, the OS looks at its list of free holes and picks one. Three strategies, and every exam asks you to apply all three to the same list.

Take the holes 100, 500, 200, 300, 600 MB and a request for 212 MB:

• First fit — scan from the start, take the first hole big enough. Picks the 500 MB hole, leaving 288 MB. Fastest, because it stops searching early.
• Best fit — take the smallest hole that fits. Picks the 300 MB hole, leaving 88 MB. It must scan the whole list to know.
• Worst fit — take the largest hole. Picks the 600 MB hole, leaving 388 MB. The idea is that the leftover is big enough to still be useful.

In practice first fit is usually the winner. Best fit sounds sensible but leaves tiny slivers — that 88 MB piece is too small for most things and will sit there forever.

Two kinds of fragmentation. Get this pair straight; it is asked constantly.

• External fragmentation — free memory exists but is broken into pieces too small to use. 1,700 MB free, largest hole 600 MB, so a 700 MB request fails. The memory is there; it is the wrong shape.
• Internal fragmentation — memory handed out is larger than what was asked for, and the leftover inside the block is wasted. Contiguous allocation with fixed partitions causes this.

Compaction is the obvious fix for external fragmentation: slide all the processes together to merge the holes. It works, and it is expensive — everything stops while gigabytes are copied. It also needs relocation to be possible, which is only true because of the logical addresses from Topic 6.1.

The real fix is to stop requiring one continuous block at all, which is the next topic.

How it works

1. The OS keeps a list of holes, each with a start address and a size.
2. A request arrives for some number of bytes.
3. It applies its strategy — first, best or worst fit — to choose a hole.
4. It splits the hole. The process takes what it needs; the remainder stays on the free list as a smaller hole.
5. When a process exits, its block returns to the list and is merged with any neighbouring hole. Merging is what stops the list growing forever.

Common confusion

"Best fit is the best one." The name is about the fit, not the outcome. It minimises the leftover on each individual placement, which is exactly how you generate unusable slivers. First fit usually performs better overall and runs faster.

"Worst fit is obviously useless." Its logic is defensible: leave a big enough remainder to be reusable. It just does not work well in practice, because it chews through the large holes you will want later.

"Compaction solves fragmentation, so why not just run it?" Because everything freezes while it runs. Moving several gigabytes at RAM speed takes a noticeable fraction of a second, and Aisha would feel every one of them.

Interview angle

You will be given a hole list and a request and asked which hole each strategy picks. Practise it until it is automatic; the arithmetic is trivial and the marks are free.

"Difference between internal and external fragmentation?" External is waste betweenallocations, internal is waste inside one. Give one example of each. Then the follow-up you should volunteer: paging removes external fragmentation and introduces internal fragmentation, which is the trade Topic 6.3 makes.