Memory Partitioning

Buddy System

The buddy system is based on dividing the memory into fixed-size blocks, and whenever a process requests memory, the system finds the smallest available block that can accommodate the requested memory size.

• Entire space available is treated as a single block of $2^U$
• If a request of size $s$ such that $2^U-1<s\le 2^U$ then the entire block will be allocated
  • Otherwise the block is split into two equal sized buddies
  • Process continues until smallest block greater than or equal to $s$ is generated

It's not that complicated

Split memory into 2, until splitting more would not fit.

Pseudocode

void get_hole(int i) {
    if (i == (U + 1)) <failure>;
    if (<i_list empty>) {
    get_hole(i + 1);
    <split hole into buddies>;
    <put buddies on i_list>;
    }
    <take first hole on i_list>;
}

Resources

• https://www.geeksforgeeks.org/buddy-system-memory-allocation-technique/

We can represent this as a tree: