Buddy System

operating-systems algorithms

Definition

Buddy System

The buddy system is a memory allocation algorithm that balances fixed and dynamic partitioning. It uses power-of-two block sizes to manage memory and minimise fragmentation.

Algorithm

Memory begins as a single block of size $2^K$. To satisfy a request of size $S$:

1. Find the smallest power of two $2^U$ where $2^{U-1}<S\le 2^U$.
2. If a free block of size $2^U$ exists, allocate it.
3. Otherwise, split the next larger available block into two equal buddies.
4. Repeat splitting until a block of size $2^U$ is created.

Coalescing

When a block is released, the system checks if its buddy (the adjacent block of equal size) is also free. If so, they merge into a single larger block. This process may repeat recursively up to the original size $2^K$.

Properties

Efficiency

Splitting and coalescing are fast. Both operations require $O(1)$ time per level, with at most $K$ levels.

Fragmentation Trade-off

The buddy system reduces external fragmentation compared to pure dynamic partitioning. However, it suffers from internal fragmentation — up to 50% wasted space when a request is slightly larger than $2^{U-1}$.