O perating s ystems t hree e asy p ieces

Buddy Allocation

Because coalescing is critical for an allocator, some approaches have been

designed around making coalescing simple. One good example is found

in the binary buddy allocator [K65].

In such a system, free memory is first conceptually thought of as one

big space of size 2

N

. When a request for memory is made, the search for

free space recursively divides free space by two until a block that is big

enough to accommodate the request is found (and a further split into two

would result in a space that is too small). At this point, the requested

block is returned to the user. Here is an example of a 64KB free space

getting divided in the search for a 7KB block:

64 KB

32 KB

32 KB

16 KB

16 KB

8 KB 8 KB

O

PERATING

S

YSTEMS

[V

ERSION

0.80]

WWW

.

OSTEP

.

ORG

---

F

REE

-S

PACE

M

ANAGEMENT

167

In the example, the leftmost 8KB block is allocated (as indicated by the

darker shade of gray) and returned to the user; note that this scheme can

suffer from internal fragmentation, as you are only allowed to give out

power-of-two-sized blocks.

The beauty of buddy allocation is found in what happens when that

block is freed. When returning the 8KB block to the free list, the allocator

checks whether the “buddy” 8KB is free; if so, it coalesces the two blocks

into a 16KB block. The allocator then checks if the buddy of the 16KB

block is still free; if so, it coalesces those two blocks. This recursive coa-

lescing process continues up the tree, either restoring the entire free space

or stopping when a buddy is found to be in use.

The reason buddy allocation works so well is that it is simple to de-

termine the buddy of a particular block. How, you ask? Think about the

addresses of the blocks in the free space above. If you think carefully

enough, you’ll see that the address of each buddy pair only differs by

a single bit; which bit is determined by the level in the buddy tree. And

thus you have a basic idea of how binary buddy allocation schemes work.

For more detail, as always, see the Wilson survey [W+95].