Memory Allocation: First Fit, Best Fit and Fragmentation
How allocators pick a free block: first, best and worst fit on the same requests (best fit places all four, the others fail one), plus fragmentation, compaction and the buddy system.
First fit takes the first free hole large enough for a request, best fit the smallest hole that fits, and worst fit the largest. Interviewers expect the fragmentation distinction: external fragmentation is free memory split into pieces too small to use, while internal fragmentation is space wasted inside a block because a request was rounded up.
When programs ask for variable-sized chunks of memory, free space breaks into holes. First fit takes the first hole that fits, best fit the smallest that fits, worst fit the largest. On a classic example, best fit placed all four requests while first fit and worst fit failed one, even though total free space was enough.
- With holes of 100, 500, 200, 300 and 600 and requests of 212, 417, 112 and 426, best fit placed all four, while first fit and worst fit could not place 426.
- After first fit in the classic example, the free holes totalled 959 bytes but the largest was only 300, an example of external fragmentation.
- With 4 KB pages, a 5 KB request takes two pages (8 KB) and wastes 3 KB inside the block, which is internal fragmentation.
- The buddy allocator rounds requests up to a power of two and merges a freed block with its buddy, whose address differs by one bit.
- Paging avoids external fragmentation by allocating fixed-size frames, so a process need not be contiguous in physical memory.
- Compaction moves allocated blocks together to merge free holes, but it needs relocation support and costs time.
01The problem
Suppose memory is allocated contiguously in chunks of different sizes, as a malloc heap or a simple OS memory manager does. As blocks are allocated and freed in no fixed order, the free space ends up as a list of holes of various sizes between used blocks. A request must fit entirely inside one hole.
The allocator's job is to choose which hole to use, and the choice affects how much future requests can still be satisfied.
02Three placement policies
First fit scans the holes in order and takes the first one big enough. It is fast because it stops early. Best fit looks at every hole and takes the smallest one that fits, aiming to leave small leftovers. Worst fit takes the largest hole, hoping the leftover stays big enough to be useful.
def alloc(holes, reqs, policy):
holes, placed = list(holes), []
for r in reqs:
fits = [(i, h) for i, h in enumerate(holes) if h >= r]
if not fits:
placed.append(None); continue
if policy == 'first': i, h = fits[0]
elif policy == 'best': i, h = min(fits, key=lambda x: x[1])
else: i, h = max(fits, key=lambda x: x[1])
holes[i] -= r
placed.append(i)
return placed, holesEach request shrinks the chosen hole by its size. Keep this simple model in mind: real allocators also track headers, alignment and coalescing of neighbours.
03The classic example
holes = [100, 500, 200, 300, 600]
reqs = [212, 417, 112, 426]
for p in ['first', 'best', 'worst']:
print(p, *alloc(holes, reqs, p))The results were:
first: placed [1, 4, 1, None] holes left [100, 176, 200, 300, 183]
best: placed [3, 1, 2, 4] holes left [100, 83, 88, 88, 174]
worst: placed [4, 1, 4, None] holes left [100, 83, 200, 300, 276]Best fit placed all four requests. First fit and worst fit each left the 426 request unplaced, even though the total free space after the first three requests was more than 426 under every policy. The space existed, but not in one piece. This is the standard textbook example, and it shows that no policy is best in every case: on other inputs first fit can win. In practice best fit and first fit tend to beat worst fit, with first fit usually faster.
04External fragmentation
That unplaced 426 request is external fragmentation: free memory exists, but it is split into pieces too small to use. After first fit above, the holes were 100, 176, 200, 300 and 183, adding to 959 bytes, yet the largest hole is 300.
Two remedies. Compaction slides used blocks together to merge holes into one large one. It is expensive because every moved block's addresses must be updated, and it is only possible if the system can relocate programs (with paging or base registers). The other remedy is to avoid needing contiguous memory at all, which is what paging does: memory is split into fixed-size frames, and a program's pages can sit in any frames.
05Internal fragmentation
If the allocator hands out memory in fixed-size units, a request is rounded up and the extra is wasted inside the block. With 4 KB pages, a 5 KB request takes two pages (8 KB) and wastes 3 KB. Allocators that round sizes to powers of two have the same issue, up to nearly half of a block wasted in the worst case.
So there is a trade-off. Fixed-size units remove external fragmentation and make allocation fast, at the price of internal waste. Variable-size blocks waste little inside a block but fragment externally.
06The buddy system
The buddy allocator keeps free lists for sizes 1, 2, 4, 8 and so on (in pages). To serve a request it rounds up to a power of two, finds a block of that size, and if none exists it splits a larger block in half repeatedly. Each half is the other's buddy. When a block is freed and its buddy is also free, they merge back into one larger block. The buddy's address is found by flipping one bit of the block address, so merging is quick.
Linux uses this for physical pages. The cost is internal fragmentation from rounding up. Higher layers, like the slab allocator, then carve pages into small fixed-size objects to reduce the waste.
07What this means for programmers
A long-running server that allocates and frees objects of many sizes can end up with a heap full of small holes, so its memory use grows although the live data is stable. Mitigations include allocators designed for multithreaded workloads (jemalloc, tcmalloc), pooling objects of the same size, and avoiding patterns that allocate large short-lived buffers between long-lived small ones. Garbage-collected runtimes with compacting collectors move objects to remove fragmentation, which is one thing they buy with their pauses.
08Common interview questions
Q: First fit, best fit, worst fit?
A: First takes the first hole that fits, best the smallest that fits, worst the largest. First fit is fastest. Best fit can leave tiny unusable holes.
Q: External versus internal fragmentation?
A: External is free space split into unusable pieces between blocks. Internal is wasted space inside an allocated block.
Q: How does paging avoid external fragmentation?
A: It allocates fixed-size frames, and a process need not be contiguous in physical memory.
Q: What is compaction?
A: Moving allocated blocks together to merge free holes. It needs relocation support and costs time.
Q: How does the buddy system merge blocks?
A: A freed block merges with its buddy if the buddy is also free. The buddy's address differs by one bit.
Q: Which fragmentation does the buddy system suffer?
A: Internal, from rounding requests up to powers of two.