Buddy Algorithm
Understanding the Buddy System Algorithm for Memory Allocation
Memory management is one of the core responsibilities of an operating system. Among several dynamic memory allocation strategies, the Buddy System Algorithm stands out due to its balance between performance and memory fragmentation control.
What is the Buddy System?
The Buddy System is a memory allocation algorithm that divides memory into partitions to try and satisfy a memory request as suitably as possible. It manages memory in blocks of sizes that are powers of 2 (e.g., 2, 4, 8, 16, ... bytes).
When a request for memory is made, the buddy system allocates the smallest block of memory that is a power of 2 and large enough to fulfill the request. If a large enough block is not immediately available, the system splits larger blocks recursively until a suitable size is found.
When a block is freed, the system checks whether its adjacent "buddy" block is also free. If so, it merges them back together to form a larger block. This process helps reduce memory fragmentation over time.
Why Use the Buddy System?
The Buddy System offers a good compromise between:
Fast allocation and deallocation (due to predictable sizes)
Low external fragmentation (due to merging)
Simplicity in implementation
It's widely used in OS kernels and real-time systems where performance is critical.
How It Works – Step-by-Step
Let's assume we have a memory pool of 1024 bytes (2^10).
1. Initial State:
Memory = 1024 bytes
All memory is free as one large block.
2. Memory Request:
A process requests 100 bytes.
The nearest power of 2 >= 100 is 128.
1024 is too big → split into two 512s → split a 512 into two 256s → split a 256 into two 128s.
Allocate one 128 block to the process.
3. Later, another request for 60 bytes:
Nearest power of 2 = 64.
Use one of the remaining 128 blocks → split into 64 + 64 → allocate one.
4. Freeing Memory:
When the 64-byte block is freed, the system checks if its buddy (the other 64-byte block) is also free.
If so, they are merged back into a 128.
If its 128 buddy is free, it continues merging.
Finding a Buddy
Each block has a unique buddy that:
Is of the same size
Shares the same parent when split
To find the buddy:
Assume base address of the memory is
0Let the address of a block be
Aand its size beSThe buddy's address is:
A ^ S(bitwise XOR)
This makes it fast and easy to locate and merge buddies.
Pros and Cons
Pros:
Efficient splitting/merging due to power-of-2 sizes
Low external fragmentation
Fast buddy lookup via bitwise math
Predictable allocation time (O(log n))
Cons:
Internal fragmentation due to power-of-2 constraint
E.g., a 33-byte request results in 64-byte allocation
May not utilize memory optimally for arbitrary-sized requests
Real-World Use Cases
Linux Kernel: Uses buddy allocator for page frame management
Real-Time Systems: Where predictable performance is required
Embedded Systems: Low memory footprint and fast operations
Summary Table
Feature
Buddy System Algorithm
Block Sizes
Power of 2
Allocation Time
O(log n)
Merge Strategy
Recursively merge buddies
Fragmentation
Low external, some internal
Used In
OS kernels, real-time & embedded
Last updated