Memory Management in Operating Systems: Buddy System

Memory Management in Operating Systems: Buddy System

Description
The Buddy System is a dynamic memory management algorithm primarily used for allocating contiguous physical page frames, effectively reducing external fragmentation. Its core idea is to divide memory into blocks of varying sizes (typically powers of two). During allocation, it finds the block closest in size to the request. If no suitable block is found, a larger block is split in half. Upon deallocation, it checks whether the adjacent "buddy" block is free to merge. It is suitable for paged memory allocation or kernel object management.

Key Points

  1. Block Size Rule: All block sizes are 2^k (e.g., 4KB, 8KB).
  2. Buddy Block Definition: Two blocks of the same size, contiguous in address space, and differing only in the k-th bit of their low-order k+1 bits are buddies (e.g., two 8KB blocks at addresses 0x1000 and 0x1400 within a 16KB block are buddies).
  3. Allocation and Merging: Allocation is satisfied by splitting blocks, and the buddy relationship is used for merging to reduce fragmentation.

Problem-Solving Process
Assume the system initially has 16KB of contiguous memory, with a minimum allocation unit of 1KB (i.e., block sizes range from 1KB to 16KB), and 3KB of memory needs to be allocated:

Step 1: Initialize Free Lists

  • Create 5 free lists (corresponding to sizes 1KB, 2KB, 4KB, 8KB, 16KB).
  • Initially, the 16KB block is added to the largest list:
    free_list[4] → [16KB block] (indices 0~4 correspond to 1KB~16KB respectively).

Step 2: Allocate 3KB Memory

  • Calculate the smallest sufficient block: find the smallest 2^k block greater than or equal to 3KB, which is 4KB (2^2 KB).
  • Check if the 4KB list (free_list[2]) has a free block: if empty, search upward for a larger block.
  • Splitting process:
    • Split the 16KB block into two 8KB buddy blocks (add both 8KB blocks to free_list[3]).
    • Take one 8KB block and split it further into two 4KB buddy blocks (add both 4KB blocks to free_list[2]).
  • Allocate one 4KB block to the request, return its address, and update the list with the remaining block:
    free_list[2] → [remaining 4KB block].

Step 3: Deallocate the Allocated Block

  • When deallocating the previously allocated 4KB block, check the status of its buddy block (adjacent 4KB block):
    • If the buddy block is free, merge them into an 8KB block and recursively check if the 8KB block's buddy can be merged further.
    • If the buddy block is occupied, simply add the current block to the 4KB free list.
  • Merge example: If both 4KB buddies become free after deallocation, merge them into an 8KB block and add it to free_list[3].

Key Mechanisms

  1. Fast Buddy Location: Calculate buddy address via address XOR block size (e.g., for a 4KB block at address 0x2000, the buddy address is 0x2000 XOR 0x1000 = 0x3000).
  2. Fragmentation Control: The merge mechanism effectively reduces external fragmentation, but internal fragmentation may occur due to the enforced 2^k size (e.g., requesting 3KB results in a 4KB allocation).

Application Scenarios
Variants of the Buddy System have been used in the Linux kernel's page allocator and early user-space memory management (e.g., libc's malloc implementation). It is suitable for scenarios requiring fast allocation and tolerating minor internal fragmentation.