Buddy System

operating-systems algorithms

Definition

Buddy System

The buddy system is a memory allocation algorithm that attempts to compromise between fixed and dynamic partitioning. it uses power-of-two block sizes to manage memory and minimize fragmentation.

Algorithm

Memory is initially represented as a single block of size $2^K$. When a block of size $S$ is requested:

1. Find the smallest power of two $2^U$ such that $2^{U-1}<S\le 2^U$.
2. If an available block of size $2^U$ exists, allocate it.
3. If no such block exists, find the next largest available block and split it into two equal “buddies.”
4. Repeat the splitting process until a block of size $2^U$ is created.

When a block is released, the OS checks if its buddy is also free. If so, they are coalesced back into a single larger block.

Visual Representation

The following diagram illustrates the recursive splitting process for a 1GB block when 100MB is requested:

Characteristics

• Efficiency: Coalescing and splitting are very fast operations.
• Fragmentation: Reduces external fragmentation compared to dynamic partitioning, but still suffers from internal fragmentation (up to 50% in the worst case).