Memory Management in Operating Systems: A Detailed Explanation of the Buddy System

The Buddy System is an algorithm for managing physical memory, primarily designed to address the issue of external fragmentation. It efficiently manages memory allocation and deallocation by dividing memory into blocks of equal size and performing allocation and release based on powers of two.

1. Basic Concept of the Buddy System
The core idea of the Buddy System is to treat the available memory space as a block of size 2^N. When memory needs to be allocated, the system searches for a sufficiently large block. If the found block is too large, it is repeatedly split in half into two equal-sized "buddy" blocks until a block of suitable size is obtained. When releasing memory, if both buddy blocks are free, they are merged into a larger block.

2. Data Structure of the Buddy System
The system maintains a set of linked lists (often called free lists), each corresponding to memory blocks of specific sizes:

• Linked list for blocks of size 2^0
• Linked list for blocks of size 2^1
• Linked list for blocks of size 2^2
• ...
• Linked list for blocks of size 2^N

3. Memory Allocation Process (Example: Allocating memory of size k)
Step 1: Calculate the smallest block size that meets the requirement

• Find the smallest m such that 2^m ≥ k
• Example: To allocate 10KB of memory, 2^3=8 is insufficient, 2^4=16 is sufficient, so m=4

Step 2: Search in the corresponding free list

• Check the free list for blocks of size 2^m
• If the list is not empty, directly allocate the first block

Step 3: If the current list is empty, search upward

• Check the free list for blocks of size 2^(m+1)
• If not empty, take one block and split it into two buddy blocks of size 2^m
• One block is used for allocation, the other is added to the 2^m free list

Step 4: Recursively search upward

• If the list for 2^(m+1) is also empty, continue checking 2^(m+2)
• Repeat the splitting process until an available block is found

4. Memory Release Process
Step 1: Release the memory block and mark it as free
Step 2: Check the status of the buddy block

• Calculate the address of the current block's buddy: buddy_addr = block_addr XOR block_size
• Example: For a block at address 0x1000 with size 16KB, its buddy address is 0x1000 XOR 0x400 = 0x1400

Step 3: If the buddy block is also free, merge them

• Remove both buddy blocks from their current linked list
• Merge them into a block twice the size
• Add the merged block to the free list of the larger size

Step 4: Recursively merge

• Check if the buddy of the merged block is free
• If further merging is possible, repeat Step 3
• Continue until no more merging is possible or the maximum block size is reached

5. Advantages of the Buddy System

• Effectively reduces external fragmentation: The merging mechanism keeps larger blocks of memory available
• High allocation efficiency: Operations such as searching, splitting, and merging have O(1) time complexity
• Relatively simple implementation: Only requires maintaining a set of free lists

6. Limitations of the Buddy System

• Internal fragmentation problem: If the requested size is not a power of two, memory is wasted
• Strict merging conditions: Can only merge with a buddy block at a specific address
• Memory alignment requirements: Block addresses must be multiples of the block size

7. Practical Application Scenarios
The Buddy System is widely used in the Linux kernel's page allocator for managing physical page allocation. Modern operating systems typically combine the Buddy System with other memory management techniques to balance fragmentation issues and allocation efficiency.