Buddy System Allocation
When an operating system manages memory, it constantly faces a tug-of-war between speed and efficiency. Fixed partitioning causes severe internal fragmentation, while variable partitioning leads to external fragmentation and slow search times.
The Buddy System is an elegant memory allocation algorithm that tries to strike a perfect balance between the two by rapidly splitting and merging memory blocks.
What is the Buddy System?
The Buddy System manages memory in blocks whose sizes are strictly powers of two (e.g., 4 KB, 8 KB, 16 KB, 32 KB, 64 KB, etc.).
When a process requests memory, the OS searches for a block of the appropriate size. If the available block is too large, the OS splits it perfectly in half. These two resulting halves are called "buddies". The OS continues splitting the buddies in half until it finds the smallest power-of-two block that is still large enough to hold the process.
How Allocation Works (Splitting)
Let's assume the OS manages a total memory space of 1024 KB. A new process arrives and requests exactly 100 KB of memory.
Step 1: The OS rounds the 100 KB request UP to the nearest power of 2.
Nearest power of 2 >= 100 KB is 128 KB.
Step 2: The OS checks for a free 128 KB block. There are none. It only has the massive 1024 KB block.
Step 3: The OS splits the 1024 KB block into two 512 KB "buddies".
[512 KB] [512 KB]
Step 4: 512 KB is still too big. It splits one of the 512 KB blocks into two 256 KB "buddies".
[256 KB] [256 KB] [512 KB]
Step 5: 256 KB is still too big. It splits one of the 256 KB blocks into two 128 KB "buddies".
[128 KB] [128 KB] [256 KB] [512 KB]
Step 6: We now have a 128 KB block! The OS allocates the first 128 KB block to the process.How Deallocation Works (Merging)
The true genius of the Buddy System lies in how it frees memory. When a process terminates and releases its block, the OS immediately checks the status of that block's exact "buddy" (the specific block it was originally split away from).
If the buddy is also free, the OS instantly merges them back together into a single, larger block. It then recursively checks the buddy of this newly merged block. This rapid "coalescing" aggressively fights external fragmentation by ensuring free space is constantly consolidated into the largest possible chunks.
Advantages and Disadvantages
| Advantages | Disadvantages |
|---|---|
| Lightning Fast: Because all block sizes and addresses are powers of two, the OS can calculate buddy addresses using basic binary math. | Severe Internal Fragmentation: Every request must be rounded up to the nearest power of two. |
| Excellent Coalescing: The recursive merging of free buddies happens instantly upon deallocation, keeping the system clean. | Wasted Space: If a process requests 130 KB, it MUST be given a 256 KB block, meaning 126 KB of memory is trapped inside the block and completely wasted. |
| Low External Fragmentation: The constant merging ensures that large contiguous blocks are quickly reformed. | Strict Rules: A block can ONLY merge with its exact mathematical buddy, even if a different, identically sized block is sitting free right next to it. |
Summary
The Buddy System is a highly efficient compromise algorithm widely used in underlying kernel memory allocators (like Linux's physical memory manager). It trades a predictable amount of internal memory waste (due to power-of-two rounding) in exchange for incredibly fast allocation and highly effective defragmentation capabilities.
Buddy Allocation Math
Question 1 of 1Test your understanding of how the Buddy System rounds requests.