Writing an OS Kernel from Scratch | Physical Memory Management — The Buddy System

A 64KB memory request, but the smallest free block you have is 128KB — do you split it in half and use half, or allocate the whole thing?

That’s the core problem the Buddy System solves.

Physical memory management is one of the kernel’s most critical infrastructures. When your program needs memory, the kernel must find a suitable block in physical memory, allocate it, and eventually reclaim and merge it for reuse. The Buddy System is the physical page allocation algorithm used natively by Linux.

---

1. Why the Buddy System?

Can you use “Best Fit” directly? Yes, but you’ll quickly encounter a problem: memory fragmentation.

Suppose you have a 1MB free block. Programs request: 64KB, 64KB, 64KB, 64KB. You allocate 4 × 64KB. Now programs free blocks 2 and 4 — you have 128KB free, but they’re not contiguous (blocks 1 and 3 are in between).

This is External Fragmentation: total free memory is sufficient but physically non-contiguous, unable to satisfy large block requests.

The Buddy System solves this with a simple but effective strategy: allocate in powers of 2, each split is “cut in half,” each merge is “find the neighbor and merge.”

---

2. Core Rules: Split and Merge

On allocation:

1. Find the closest 2ⁿ pages (e.g., request 7 pages → find 8 pages)
2. Check the free list for that size
3. If none, look for a larger block (2ⁿ⁺¹), split into two “buddies”
4. Recurse until a suitable block is found

On free:

1. Free the block
2. Check if its “buddy” (one of the two blocks split from the same parent) is also free
3. If buddy is free, merge into larger block
4. Recurse upward until unable to merge