Buddy System Memory: How It Works and When to Use It

The buddy system memory is a memory management technique that divides memory into blocks of sizes that are powers of two. It works by splitting and merging these blocks (called buddies) to efficiently allocate and free memory with minimal fragmentation.

How It Works

The buddy system manages memory by splitting a large block into two equal smaller blocks called buddies whenever a smaller memory allocation is needed. If the requested size is not a power of two, the system rounds up to the nearest power of two and splits blocks accordingly.

When memory is freed, the system checks if the freed block's buddy is also free. If yes, it merges them back into a larger block. This splitting and merging help keep memory usage efficient and reduce wasted space, similar to how you might split a pizza into halves or quarters and then put slices back together.

Example

This simple Python example simulates buddy system allocation and freeing of memory blocks by splitting and merging blocks of sizes that are powers of two.

python

class BuddySystem:
    def __init__(self, size):
        self.size = size
        self.free_blocks = {size: [0]}  # key: block size, value: list of start addresses

    def allocate(self, request_size):
        size = 1
        while size < request_size:
            size <<= 1  # round up to next power of two

        block_size = size
        while block_size <= self.size and (block_size not in self.free_blocks or not self.free_blocks[block_size]):
            block_size <<= 1

        if block_size > self.size:
            return -1  # no block available

        addr = self.free_blocks[block_size].pop(0)

        while block_size > size:
            block_size >>= 1
            buddy_addr = addr + block_size
            self.free_blocks.setdefault(block_size, []).append(buddy_addr)

        return addr

    def free(self, addr, size):
        block_size = size
        while True:
            buddy_addr = addr ^ block_size
            buddies = self.free_blocks.get(block_size, [])
            if buddy_addr in buddies:
                buddies.remove(buddy_addr)
                addr = min(addr, buddy_addr)
                block_size <<= 1
            else:
                self.free_blocks.setdefault(block_size, []).append(addr)
                break


buddy = BuddySystem(64)
addr1 = buddy.allocate(10)
addr2 = buddy.allocate(20)
buddy.free(addr1, 16)
buddy.free(addr2, 32)
print("Free blocks after freeing:", buddy.free_blocks)

Output

Free blocks after freeing: {64: [0]}

When to Use

The buddy system is useful in operating systems and memory allocators where fast allocation and deallocation of memory blocks are needed with low fragmentation. It works well when memory requests vary but tend to be powers of two or close to it.

Real-world use cases include kernel memory management, embedded systems, and situations where predictable and efficient memory handling is critical, such as in real-time systems.

Key Points

• Memory is split into blocks of sizes that are powers of two.
• Buddies are pairs of blocks that can be merged when both are free.
• This system reduces fragmentation by merging free blocks.
• Allocation rounds up to the nearest power of two.
• Commonly used in operating system kernels and real-time systems.

Key Takeaways

Buddy system memory manages memory by splitting and merging blocks sized in powers of two.

It reduces fragmentation by merging free buddy blocks back into larger blocks.

Allocation rounds up requests to the nearest power of two for efficient use.

Ideal for systems needing fast, predictable memory allocation and deallocation.

Commonly used in operating system kernels and embedded or real-time systems.