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
- Find the smallest power of two
where . - If a free block of size
exists, allocate it. - Otherwise, split the next larger available block into two equal buddies.
- Repeat splitting until a block of size
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
.
Properties
Efficiency
Splitting and coalescing are fast. Both operations require
time per level, with at most 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
.