What are Allocation Lists? When an operating system kernel manages physical memory, it cannot simply guess which bytes of RAM are available. It must maintain rigorous bookkeeping structures known as allocation lists. These consist of Free Lists (grouping unallocated blocks or holes) and Used Lists/Trackers (recording active process ownership, starting addresses, and block lengths).
Why are they used? Without allocation lists, the kernel would be forced to perform exhaustive linear scans across every byte of raw hardware RAM every time a program requests or releases memory. Allocation lists enable structured, rapid metadata lookups, prevent memory corruption, and allow efficient coalescing of adjacent free blocks to mitigate external fragmentation.
A Brief History: Early computer systems in the 1950s and early 1960s used primitive bitmaps and sequential linked lists of variable-length holes. To solve the persistent problem of external fragmentation and slow search times, the Binary Buddy System was introduced by Harry M. Markowitz in 1963, refined by Kenneth C. Knowlton in 1965, and standardized across computer science by Donald Knuth.
Group unallocated blocks by power-of-two sizes (`free_area[0..MAX_ORDER]`). Enables instant O(1) pop operations when allocating memory.
Record active allocations and metadata. When a process frees a pointer, the kernel inspects this tracker to know the exact block boundaries for buddy coalescing.
Harry M. Markowitz
Formulated the binary buddy allocation algorithm (1963). Nobel laureate.
Kenneth C. Knowlton
Refined buddy allocation structures at Bell Labs (1965) for Lisp architectures.
Donald E. Knuth
Rigorously analyzed and popularized buddy systems in The Art of Computer Programming.
Memory is partitioned into fixed allocation units (e.g., 4 KB blocks). Each unit corresponds to a single bit in a bitmap: 0 if free, and 1 if allocated to a process.
The operating system maintains a linked list where each node indicates whether a region is a Process (P) or a Hole (H), its starting address, and its length.
When allocating memory from a linked list of holes, the kernel uses placement algorithms to decide which hole to assign:
- First Fit: Scan from the start and pick the first hole that is big enough. Fast, but clutters the front of memory with small splinters.
- Best Fit: Search the entire list and pick the hole closest in size to the request. Minimizes leftover waste per allocation, but is slow and leaves tiny, unusable slivers.
- Worst Fit: Allocate from the largest hole so leftovers remain useful. In practice, it rapidly exhausts large blocks.
- Next Fit: Like First Fit, but starts scanning from the location of the last allocation rather than the beginning.
Physical DRAM is partitioned by hardware into fixed-sized slots called page frames (commonly 4096 bytes or 212). The PFN is simply the sequential integer index of that frame:
0x0000 is PFN 0, 0x1000 is PFN 1, 0x2000 is PFN 2, and so on. The buddy system performs all pairing directly on this integer index.
free_area[0..4])