Buddy Allocator

Big idea

One of the core responsibilities of an operating system is memory management—specifically, allocating and deallocating RAM efficiently while maintaining system integrity. The challenge is balancing speed, simplicity, and low fragmentation.
A buddy allocator is a memory management algorithm designed to meet this challenge by structuring memory allocation in a way that is fast, deterministic, and relatively resistant to fragmentation.

Within the context of A1.3.2, buddy allocators are an example of how an operating system manages memory dynamically while background processes and user programs compete for resources, helping ensure stable and predictable system behavior .

What is a buddy allocator?

A buddy allocator is a memory allocation scheme in which:

• Physical memory is divided into blocks whose sizes are powers of two
• Each block has a uniquely defined “buddy” block of the same size
• Blocks can be split to satisfy smaller requests and merged (coalesced) when freed

This structure allows the operating system to allocate and free memory efficiently with low overhead.

How memory is organized

At system startup, the operating system treats available memory as one or more large contiguous blocks (for example, 2ⁿ bytes). These blocks are managed in free lists, one list per block size:

• 2⁰ (smallest block size)
• 2¹
• 2²
• …
• 2ⁿ (largest block size)

Each free list tracks blocks of exactly that size.

Allocation process (step-by-step)

When a process requests memory:

1. Round up
   The requested size is rounded up to the nearest power of two.
2. Search free lists
   The allocator checks the free list for a block of that size.
3. Split if necessary
   • If no block of the required size exists, a larger block is taken.
   • That block is split into two equal halves.
   • These halves are “buddies.”
   • The process repeats until the correct size is reached.
4. Allocate
   One block is allocated to the process; its buddy is returned to the appropriate free list.

This process is fast because splitting follows a strict, predictable structure.

Deallocation and coalescing

When a process frees memory:

1. The allocator identifies the block’s buddy using its address.
2. If the buddy is also free and the same size:
   • The two blocks are merged into a single larger block.
3. This merging continues recursively up the size hierarchy where possible.

This automatic merging reduces external fragmentation, a key goal of operating system memory management.

Why buddy allocators are efficient

Buddy allocators provide several advantages aligned with OS responsibilities in A1.3.2:

• Fast allocation and deallocation
  Operations are largely constant or logarithmic time.
• Simple bookkeeping
  Block sizes and buddies are determined mathematically from addresses.
• Reduced external fragmentation
  Merging ensures free memory does not remain unnecessarily scattered.
• Predictable behavior
  Deterministic structure is valuable for kernel-level operations.

Limitations of buddy allocators

Despite their strengths, buddy allocators are not perfect:

• Internal fragmentation
  Rounding requests up to powers of two can waste memory.
• Inefficiency for irregular sizes
  Small or oddly sized allocations may lead to unused space.
• Not ideal for all workloads
  Many modern operating systems pair buddy allocators with slab or object allocators for small objects.

Understanding these trade-offs is important when evaluating operating system design choices.

Real-world use in operating systems

Buddy allocators are commonly used:

• In kernel-level memory management
• For allocating physical memory frames
• As a foundational allocator, layered with higher-level allocators (e.g. slab allocators in Linux)

They exemplify how operating systems maintain system integrity while managing limited hardware resources, a central expectation of A1.3.2 .

Summary

Buddy allocators are a structured, efficient memory management strategy used by operating systems to allocate and reclaim memory dynamically. By organizing memory into power-of-two blocks with deterministic buddy relationships, they allow fast allocation, controlled fragmentation, and predictable system behavior—directly supporting the operating system functions outlined in A1.3.2.