Linux Kernel Architecture

Chapter 1: Introduction and Overview

The BuddySystem

Numerous allocation requests in the kernel must be fulfilled by a continuous range of pages. To quickly

detect where in memory such ranges are still available, the kernel employs an old, but proven technique:

Thebuddy system.

Free memory blocks in the system are always grouped as two buddies. The buddies can be allocated

independently of each other; if, however, both remain unused at the same time, the kernel merges them

into a larger pair that serves as a buddy on the next level. Figure 1-8 demonstrates this using an example

of a buddy pair consisting initially of two blocks of 8 pages.

24

20

23

22

21

24

20

23

22

21

24

20

23

22

21

Allocated

Allocated

Figure 1-8: The buddy system.

All buddies of the same size (1, 2, 4, 8, 16,...pages) are managed by the kernel in a special list. The

buddy pair with two times 8 (16) pages is also in this list.

If the system now requires 8 page frames, it splits the block consisting of 16 page frames into two buddies.

While one of the blocks is passed to the application that requested memory, the remaining 8 page frames

are placed in the list for 8-page memory blocks.

If the next request requires only 2 contiguous page frames, the block consisting of 8 blocks is split into

2 buddies, each comprising 4 page frames. One of the blocks is put back into the buddy lists, while the

other is again split into 2 buddies consisting of 2 blocks of two pages. One is returned to the buddy

system, while the other is passed to the application.