Contiguous Memory Allocation Strategies
IntermediateFirst Fit, Best Fit, and Worst Fit are strategies for allocating contiguous memory from a free list; each trades allocation speed for fragmentation outcomes, while the buddy system and slab allocator address specific use cases.
Overview
Before paging was universal, OS allocated contiguous memory blocks to processes. The free list is a list of free holes; when a process requests N bytes, the allocator scans the list and picks a hole. First Fit: allocate the first hole that is large enough — fast O(n) search, tends to leave large holes at the end of memory. Best Fit: find the smallest sufficient hole — minimises wasted space per allocation but leaves tiny, unusable holes across memory and requires scanning the entire free list. Worst Fit: allocate from the largest hole — leaves the largest possible leftover, theoretically good for future large requests, but performs poorly in practice. The buddy system uses power-of-2 sized blocks; splitting and coalescing are O(log n) and perfectly deterministic. The Linux slab allocator pre-allocates caches of fixed-size kernel objects (inodes, dentries, task_structs) for O(1) allocation with zero internal fragmentation within a slab.
First Fit, Best Fit, Worst Fit: Comparison
Given free holes and an allocation request, the three algorithms make different choices. First Fit is fastest. Best Fit minimises internal waste per allocation but fragments over time with tiny leftover holes. Worst Fit was theorised to keep leftover holes large enough for future use, but empirically performs worst.
// Free holes: [100, 500, 200, 300, 600] KB
// Allocation request: 212 KB
int[] holes = {100, 500, 200, 300, 600}; // free hole sizes in KB
int request = 212;
// First Fit: first hole >= request
for (int i = 0; i < holes.length; i++) {
if (holes[i] >= request) {
System.out.printf("First Fit: hole[%d]=%d KB → leftover=%d KB%n",
i, holes[i], holes[i] - request);
break; // hole[1]=500 KB, leftover=288 KB
}
}
// Best Fit: smallest hole >= request
int bestIdx = -1;
for (int i = 0; i < holes.length; i++) {
if (holes[i] >= request) {
if (bestIdx == -1 || holes[i] < holes[bestIdx]) bestIdx = i;
}
}
System.out.printf("Best Fit: hole[%d]=%d KB → leftover=%d KB%n",
bestIdx, holes[bestIdx], holes[bestIdx] - request);
// hole[2]=300 KB, leftover=88 KB (smaller leftover, but 88KB may be too small to use)
// Worst Fit: largest hole >= request
int worstIdx = -1;
for (int i = 0; i < holes.length; i++) {
if (holes[i] >= request) {
if (worstIdx == -1 || holes[i] > holes[worstIdx]) worstIdx = i;
}
}
System.out.printf("Worst Fit: hole[%d]=%d KB → leftover=%d KB%n",
worstIdx, holes[worstIdx], holes[worstIdx] - request);
// hole[4]=600 KB, leftover=388 KB (largest leftover for future allocations)Buddy System and Slab Allocator
The buddy system maintains separate free lists for each power-of-2 size (4B, 8B, ..., 4MB). Allocation rounds up to the next power of 2. Coalescing is instant: each block has a unique buddy; if both are free, they merge into a larger block. Used by Linux for page allocation. The slab allocator (Bonwick, 1994) handles kernel object allocation: slabs are pre-allocated, partitioned into fixed-size slots per object type, with a per-CPU cache for lock-free allocation of the most recently freed objects.
// Buddy system: split and merge
// Power-of-2 block sizes: 1, 2, 4, 8, 16, 32, 64 pages
// Allocate 3 pages: round up to 4 pages (next power of 2)
// Available: one 16-page block
// Split 16 → two 8-page buddies
// Split one 8 → two 4-page buddies
// Allocate one 4-page block — done!
// Remaining free: one 8-page + one 4-page (buddy of allocated)
int roundUpPow2(int n) {
int p = 1;
while (p < n) p <<= 1;
return p;
}
int request = 3; // pages
int allocated = roundUpPow2(request); // 4 pages
int internalWaste = allocated - request; // 1 page (internal fragmentation)
System.out.printf("Request: %d pages → Allocated: %d pages → Internal waste: %d pages%n",
request, allocated, internalWaste);
// Buddy address: XOR with the block size to find buddy
// buddy(addr, size) = addr XOR size
int blockAddr = 0; // our 4-page block starts at page 0
int blockSize = 4;
int buddyAddr = blockAddr ^ blockSize; // buddy is at page 4
System.out.printf("Block: page %d Buddy: page %d (XOR: %d ^ %d = %d)%n",
blockAddr, buddyAddr, blockAddr, blockSize, buddyAddr);
// When our block is freed: check if buddy (page 4) is also free → merge into 8-page blockKey Points to Remember
- 1First Fit: fast O(n); allocates first sufficient hole — good average performance.
- 2Best Fit: smallest sufficient hole — minimal per-allocation waste but creates many tiny unusable holes.
- 3Worst Fit: largest hole — large leftovers but poor overall fragmentation outcomes.
- 4Buddy system: power-of-2 blocks with O(log n) split/merge — used in Linux kernel page allocator.
- 5Slab allocator: fixed-size object caches with per-CPU free lists — O(1) kernel object allocation.
- 6In practice, First Fit and Best Fit outperform Worst Fit; First Fit is simplest and widely used.
Interview Questions
Sign in to ask AriaCompare First Fit, Best Fit, and Worst Fit allocation strategies.
Why does Best Fit sometimes cause more fragmentation than First Fit over time?
How does the buddy system make coalescing free blocks efficient?
What problem does the slab allocator solve that the buddy system does not?
Ask Aria about Contiguous Memory Allocation Strategies
Your personal AI tutor — ask anything about this concept
Revision Status
Personal Notes
Sign in to save personal notes for this topic.
Discussion
Sign in to join the discussion.