The Buddy System Algorithm

Key Insight

The 'buddy system' is a dynamic storage allocation method specifically designed for binary computers, requiring all blocks to be of lengths 2^k (e.g., 1, 2, 4, 8, ..., 2^m). If a requested block size is not a power of 2, the next higher power of 2 is allocated, potentially leading to some internal fragmentation. This system uses a one-bit TAG field in each block (reserved or free) and, for available blocks, includes `LINKF` and `LINKB` for doubly linked lists, plus a `KVAL` field to specify 'k' for their size 2^k. Separate lists are maintained for available blocks of each size 2^k.

The method operates on a total memory pool of 2^m words, initially available as a single large block. When a block of size 2^k is requested, and no such block is directly available, a larger available block (2^j, where j > k) is recursively split into two equal parts until a block of the correct size 2^k is created. These two halves resulting from a split are called 'buddies'. When both buddies later become available again, they coalesce back into a single larger block. This splitting and coalescing process continues indefinitely, dynamically adjusting available memory.

A key feature of the buddy system is the simple calculation of a block's buddy address. For a block of size 2^k starting at address 'x', its buddy's address is `x XOR 2^k` using the exclusive-or instruction. Algorithm R (Reservation) finds the smallest 'j' greater than or equal to 'k' with an available block, removes it, and repeatedly splits it (decreasing 'j') until a 2^k block is obtained. The unused buddy is placed into its corresponding available list. Algorithm S (Liberation) checks if the freed block's buddy is also available and of the same size. If so, they are merged into a larger block, and the process repeats with the larger block until no further coalescing is possible, or the maximum size 2^m is reached.