Buddy System

Default memory allocator for Linux kernel

• 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

1. Start with entire block

2. When request of size S is made



Example

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

4. 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

/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