Buddy System

Default memory allocator for Linux kernel

Compromise to overcome disadvantages of both fixed and dynamic partitioning schemes

Low-level mechanisms to allocate memory at the page granularity

used with virtual memory system either
Reducing the external fragmentation

Keep the page frames physically continuous as much as possible

Allocations are done in page frames

Algorithm

Start with entire block

When request of size S is made

Example

this process is repeated until the smallest block greater or equal to S is generated.

Two buddies are coalesced whenever both of them become de-allocated.

Given the address and size of a block, the address of buddy is automatically determined. The address of a block and its buddy differ in exactly one bit position

binary branch framework and buddy(share one parent) is has different bit of final address

Data structure
struct free_area

All free pages are grouped into 11(=MAX_ORDER) lists of blocks that contain groups of 1, 2, 4, 8, 16, 32, 64, 128, 256, and 512, 1024 contiguous page frames, respectively That means free_area contains 11 freelist address of

Page descriptor for linear mapping.

`/proc/buddyinfo`

History

modified form is used in UNIX SVR4 (and also in Linux) for kernel memory allocation (KMA) Smallest size of block is page