Introduction
Memory management is one of the most critical responsibilities of an operating system. Processes continuously request and release memory during execution for:
Variables
Stacks
Buffers
Kernel structures
Data structures
Dynamic allocations
The operating system must allocate memory efficiently while minimizing:
Fragmentation
Allocation overhead
Wasted memory
Slow allocation times
Traditional fixed-size memory allocation methods often waste memory, while variable-size allocation methods can become complex and fragmented.
To solve these problems, operating systems introduced:
Buddy System Memory Allocation
The buddy system is one of the most important dynamic memory allocation techniques because it provides:
Fast allocation
Fast deallocation
Efficient merging
Simplified memory management
Buddy allocation is widely used in:
Operating systems
Linux kernel memory management
Physical page allocation
High-performance systems
What is the Buddy System?
The buddy system is a dynamic memory allocation algorithm that divides memory into partitions whose sizes are powers of two.
Memory blocks can:
Split into smaller blocks
Merge back together efficiently
Core Idea
Memory is recursively divided into equal-sized buddy blocks
Important Insight
Buddy allocation simplifies memory splitting and merging using power-of-two block sizes
Why the Buddy System is Necessary
Suppose process requests:
100 KB memory
Using fixed partitions:
Large memory wastage possible
Using arbitrary variable partitions:
Complex fragmentation management
Buddy system balances:
Flexibility
Efficiency
Simplicity
Main Goals of Buddy System
1. Fast Allocation
Memory requests handled quickly.
2. Fast Deallocation
Released memory easily merged.
3. Reduced External Fragmentation
Adjacent free blocks combined efficiently.
4. Simplified Management
Power-of-two structure simplifies tracking.
Basic Principle of Buddy Allocation
Suppose total memory size:
1024 KB
Buddy system divides memory into:
512 KB buddies
256 KB buddies
128 KB buddies
etc.
All block sizes:
Powers of two
Power-of-Two Allocation
Possible block sizes:
2^0, 2^1, 2^2, 2^3, ...
Examples:
4 KB
8 KB
16 KB
32 KB
64 KB
Important Insight
Buddy systems use power-of-two memory sizes for efficient splitting and merging
How Allocation Works
Suppose:
Process requests 100 KB
OS finds:
Smallest fitting power-of-two block
Result:
128 KB block allocated
Step-by-Step Allocation
Suppose free block:
1024 KB
Request:
128 KB
Step 1
Split 1024 KB → two 512 KB buddies
Step 2
Split one 512 KB → two 256 KB buddies
Step 3
Split one 256 KB → two 128 KB buddies
Step 4
Allocate one 128 KB block
Remaining Buddies
Other blocks remain:
Free for future allocations
Buddy Blocks
Two blocks formed by splitting larger block are called:
Buddies
Example
256 KB block split into:
Buddy A = 128 KB
Buddy B = 128 KB
These two are:
Buddy pairs
Address Relationship
Buddy addresses calculated mathematically.
Advantages:
Efficient lookup
Fast merging
Memory Deallocation in Buddy System
When process frees memory:
Block returned to free list
OS checks:
Is buddy also free?
If yes:
Merge both buddies
This process called:
Coalescing
Example
Two free 128 KB buddies:
Merge into 256 KB block
Then:
Further merging possible recursively
Important Insight
Buddy systems reduce fragmentation through recursive merging of adjacent free buddies
Recursive Merging
Suppose:
Two 256 KB buddies free
They merge into:
512 KB block
Then:
Larger merges may continue
Advantages:
Restores large free regions
Free Lists in Buddy System
Operating system maintains:
Separate free lists
for each block size.
Example
Free lists for:
4 KB
8 KB
16 KB
32 KB
etc.
Advantages:
Fast allocation search
Internal Fragmentation
Very important drawback.
Example
Request:
70 KB
Buddy system allocates:
128 KB block
Unused memory:
58 KB wasted
This called:
Internal Fragmentation
External Fragmentation
Buddy systems reduce:
External Fragmentation
because free buddies merge efficiently.
Comparison of Fragmentation Types
| Fragmentation Type | Meaning |
|---|---|
| Internal | Wasted space inside allocated block |
| External | Free memory exists but fragmented |
Important Insight
Buddy systems trade reduced external fragmentation for increased internal fragmentation
Time Complexity
Buddy system operations generally efficient.
Allocation
Fast due to:
Power-of-two structure
Free lists
Deallocation
Fast because buddy location easily computed.
Buddy Address Calculation
Very important implementation feature.
Buddy determined using:
XOR operations
Advantages:
Extremely fast lookup
Binary Tree Representation
Buddy allocation often visualized as:
Binary tree
Root Node
Entire memory space.
Internal Nodes
Split memory blocks.
Leaf Nodes
Allocated/free blocks.
Buddy System in Linux
Linux kernel uses buddy allocator for:
Physical page allocation
Page Sizes
Memory managed in:
Pages
Page frames
Buddy system efficiently allocates:
Contiguous physical pages
Linux Orders
Linux organizes buddy blocks into:
Orders
Example:
Order 0 = 1 page
Order 1 = 2 pages
Order 2 = 4 pages
etc.
Example
2^n pages per order
Advantages of Buddy System
1. Fast Allocation
Efficient free-list lookup.
2. Fast Merging
Buddy relationships simple.
3. Reduced External Fragmentation
Large blocks restored automatically.
4. Simple Implementation
Power-of-two organization clean.
Disadvantages of Buddy System
1. Internal Fragmentation
Requests rounded up to power-of-two sizes.
2. Memory Waste
Small requests may waste large space.
3. Splitting Overhead
Frequent recursive splitting possible.
Example of Internal Fragmentation
Request:
130 KB
Allocated:
256 KB
Wasted:
126 KB
Buddy System vs Paging
Students commonly confuse these.
Paging
Divides memory into fixed pages.
Buddy System
Dynamic variable-size allocation.
Paging Goal
Virtual memory management.
Buddy Goal
Efficient dynamic allocation.
Buddy System vs Slab Allocation
Buddy System
Allocates raw memory blocks.
Slab Allocator
Optimized for kernel objects.
Modern Linux combines:
Buddy allocator
Slab allocator
Real-World Example
Suppose Linux kernel needs:
16 KB contiguous memory
Buddy allocator:
Finds suitable free block
Splits larger blocks if needed
Allocates requested memory
Merges buddies during deallocation
Result:
Efficient kernel memory management