A process requests 70 KB of memory from a buddy allocator managing 512 KB total. How much memory is actually allocated to this process?
A70 KB — the buddy system allocates exactly the requested amount
B64 KB — the buddy system rounds down to the nearest power of two to save space
C128 KB — the buddy system rounds up to the next power of two that fits the request
D512 KB — the entire managed region is always allocated as a single block
The buddy system requires all allocations to be a power of two in size. 64 KB is too small for a 70 KB request, so the smallest power of two that fits is 128 KB. This means 58 KB is wasted inside the block — this is internal fragmentation, the core tradeoff of the buddy system. The benefit is that every block has a predictable buddy address, enabling fast coalescing when freed.
Question 2 Multiple Choice
The buddy system can locate a freed block's buddy extremely quickly using:
AA linear scan through all free lists to find a block of matching size
BA single XOR operation on the block's starting address
CA hash table lookup keyed on block size
DTraversal of a binary search tree sorted by starting address
Because block sizes are powers of two and blocks are aligned to their own size, a block's buddy is always at a predictable address that differs in exactly one bit — the bit corresponding to the block size. This means the buddy address = block_address XOR block_size. A single XOR is O(1) and is one of the key reasons the buddy system is practical in kernels like Linux: both allocation and deallocation are efficient.
Question 3 True / False
The buddy system eliminates both internal and external fragmentation, making it the ideal general-purpose memory allocator.
TTrue
FFalse
Answer: False
The buddy system reduces *external* fragmentation (scattered unusable gaps between allocations) by enforcing power-of-two sizes that enable fast, predictable coalescing. But it introduces *internal* fragmentation: any request that isn't exactly a power of two wastes space within its allocated block. A 33 KB request wastes nearly half of its 64 KB block. This is why the buddy system is used for kernel page-frame management — where sizes cluster near powers of two — rather than as a general user-space allocator.
Question 4 True / False
When a block is freed in the buddy system, the allocator checks whether its buddy is also free, merges them into a double-sized block, then checks whether that merged block's buddy is also free, continuing up the hierarchy.
TTrue
FFalse
Answer: True
This recursive coalescing is the buddy system's primary defense against external fragmentation. Each merge doubles the block size, and the check continues up the hierarchy until a non-free buddy is found or the entire memory region is merged into one block. The XOR property makes each buddy check O(1), so the entire coalescing process is O(log n) where n is the number of levels. This aggressive merging means free memory naturally reassembles into large blocks without any compaction.
Question 5 Short Answer
Why does the buddy system impose power-of-two block sizes, and what problem does this constraint create?
Think about your answer, then reveal below.
Model answer: Power-of-two sizes are required so that every block has a unique, easily computed buddy at a predictable address (found via a single XOR operation). This mathematical regularity is what enables O(1) buddy lookup and O(log n) coalescing — the system can quickly merge free blocks back into larger ones, combating external fragmentation without scanning through arbitrary block sizes. The problem this creates is internal fragmentation: every allocation is rounded up to the next power of two, so a 100 KB request wastes 28 KB of its 128 KB block. In the worst case, nearly 50% of each block is wasted. This is why the buddy system is layered with a slab allocator in Linux — the slab allocator handles small, fixed-size objects that would otherwise waste too much space under buddy constraints.
The design tension in the buddy system is between algorithmic efficiency (power-of-two sizes make buddy finding trivial) and space efficiency (power-of-two sizes cause rounding waste). The system optimizes for time at the cost of space, which is an acceptable tradeoff in kernel page-frame management where allocation sizes tend to be page-sized or multiples of pages.