Before diving into advanced binary buddy allocators and paged virtual memory, operating systems historically managed raw memory as a continuous pool of free and allocated holes. When a process requests memory, the kernel uses one of several classical placement strategies to find a suitable free hole:
- First Fit: Scan the free list from the beginning and allocate the first hole that is big enough. Pros: Extremely fast. Cons: Tends to clutter the front of memory with small fragmented splinters.
- Best Fit: Search the entire free list and choose the hole that is closest in size to the request (minimizing leftover waste). Pros: Leaves smaller leftover fragments. Cons: Slowest search time, and leaves behind tiny, unusable memory slivers ("external fragmentation").
- Worst Fit: Allocate from the largest available hole. Pros: Leaves behind larger leftover holes that might still be useful for subsequent processes. Cons: Rapidly exhausts large blocks.
- Next Fit: Similar to First Fit, but starts scanning from the location of the last allocation rather than the beginning. Pros: Spreads allocation evenly across memory.
When a kernel manages raw physical RAM (such as through the binary buddy allocator), it must maintain strict bookkeeping to track which memory is available and which is currently assigned to processes or kernel subsystems. This is accomplished using two core data structures:
free_area[0..MAX_ORDER])
An array of linked lists where each entry groups unallocated blocks of a specific power-of-two size (2order pages). When memory is requested, the allocator scans these lists from smallest sufficient order upward to find free blocks instantly.
Tracks active allocations. In Linux and modern kernels, frame metadata (stored in struct page arrays) records ownership flags, reference counts, and order sizes so that when a process frees a pointer, the kernel immediately knows its exact boundaries and buddy address without scanning.
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])