20/32 · 5 min
Fitting programs into memory
Before virtual memory, a program went into a contiguous block of real memory. Everything difficult about memory management comes from that word: contiguous.
The two fragmentations
External fragmentation. Free memory exists but is scattered. Holes of 100 KB, 60 KB and 80 KB total 240 KB, and a request for 200 KB fails. There is enough memory and not enough in one piece.
Internal fragmentation. Space wasted inside a block you were given, because allocation rounds up. A 4 KB page holding 100 bytes wastes 3,996.
Placement
Given several holes, which one do you use?
| Strategy | Picks | Behaviour |
|---|---|---|
| First fit | The first hole big enough | Fastest, and fragments the start of memory |
| Best fit | The smallest hole big enough | Leaves many unusably small holes |
| Worst fit | The largest hole | Leaves large usable holes, wastes big ones |
Best fit sounds best and usually is not: the leftovers are too small for anything. First fit performs about as well and is far cheaper to compute.
The escape
Compaction slides processes together to merge the holes, and is expensive: every relocated process needs its addresses fixed.
Paging avoids the problem entirely by dropping the requirement that memory be contiguous. That is the next page, and it is why external fragmentation is mostly a historical concern.