从理论到代码：手把手实现一个简易Buddy内存分配器
从理论到代码：手把手实现一个简易Buddy内存分配器
在操作系统的内存管理模块中，Buddy算法以其独特的设计哲学成为物理内存管理的经典方案。本文将带您从底层原理出发，逐步构建一个可运行的Buddy内存分配器原型。不同于单纯的概念讲解，我们会用300行左右的C代码实现核心功能，让您真正掌握伙伴系统的设计精髓。
1. Buddy算法核心原理
伙伴系统的核心思想就像俄罗斯套娃——内存块总是被对半分割或合并。想象一下整理衣柜时，我们把大衣柜分成两个中等柜子，中等柜子再分成小格子，这种分而治之的策略正是Buddy算法的直观体现。
三个黄金法则决定了两个内存块能否成为伙伴：
- 等分原则：两个块的大小必须完全相同
- 地址连续：两个块的物理地址必须首尾相接
- 同源分裂：必须来自同一个父块的拆分
实际系统中常用位图(bitmap)来记录伙伴状态。例如：
#define MAX_ORDER 10 // 最大2^10=1024个页面 unsigned long buddy_bitmap[MAX_ORDER];提示：位图的每个bit对应一对伙伴块，0表示双空闲，1表示其中一个在使用
2. 关键数据结构设计
我们采用分层自由链表结构来管理不同大小的内存块。先定义核心数据结构：
typedef struct mem_block { struct mem_block *next; int order; // 当前块的大小等级 bool allocated; } mem_block_t; #define MAX_ORDER 10 mem_block_t* free_lists[MAX_ORDER]; // 各阶自由链表内存池初始化时需要计算实际可用空间：
void init_buddy_system(void *mem_pool, size_t size) { // 对齐到最大块尺寸 size_t adjust_size = size & ~((1<<MAX_ORDER)-1); // 初始化最大块链表 free_lists[MAX_ORDER-1] = (mem_block_t*)mem_pool; free_lists[MAX_ORDER-1]->next = NULL; free_lists[MAX_ORDER-1]->order = MAX_ORDER-1; }3. 内存分配算法实现
分配过程就像在图书馆找书——先从合适的书架开始查找，没有就找更大的书架：
void* buddy_alloc(size_t request_size) { int order = get_order(request_size + sizeof(mem_block_t)); // 向上查找可用块 int current = order; while (current < MAX_ORDER && !free_lists[current]) { current++; } if (current == MAX_ORDER) return NULL; // 内存不足 // 分割大块 mem_block_t *block = free_lists[current]; while (current > order) { remove_from_list(block, current--); // 对半分割 mem_block_t *buddy = (void*)block + (1<<current); buddy->order = current; buddy->allocated = false; add_to_list(buddy, current); } block->allocated = true; return (void*)(block + 1); // 跳过管理头 }关键分割操作示例（以16KB内存池为例）：
| 操作步骤 | 自由链表状态 (order 0-3) |
|---|---|
| 初始状态 | [空, 空, 空, 16KB块] |
| 申请4KB | [空, 空, 8KB块, 空] |
| 再次申请4KB | [空, 4KB块, 空, 空] |
4. 内存释放与合并
释放内存时就像玩拼图游戏，需要不断尝试与相邻块合并：
void buddy_free(void *ptr) { mem_block_t *block = (mem_block_t*)ptr - 1; int order = block->order; while (order < MAX_ORDER - 1) { // 计算伙伴地址 mem_block_t *buddy = (void*)((size_t)block ^ (1<<order)); if (!is_valid_buddy(buddy, order)) break; // 合并伙伴块 remove_from_list(buddy, order); block = MIN(block, buddy); order++; } block->order = order; add_to_list(block, order); }合并过程的状态变化示例：
- 释放4KB块A，其伙伴块B空闲
- 合并A+B得到8KB块C
- 检查C的伙伴块D是否空闲
- 继续合并直到无法合并为止
5. 实战优化技巧
在实际项目中，我们还需要考虑以下关键点：
内存对齐处理：
// 保证块地址按当前阶对齐 #define BUDDY_ALIGN(addr, order) (((size_t)(addr)) & ~((1<<(order))-1))碎片监控机制：
void check_fragmentation() { for (int i = 0; i < MAX_ORDER; i++) { int count = 0; mem_block_t *curr = free_lists[i]; while (curr) { count++; curr = curr->next; } printf("Order %d: %d free blocks\n", i, count); } }性能优化方向：
- 使用位运算加速伙伴查找
- 实现预分配策略减少实时分割开销
- 添加线程安全锁机制
6. 测试用例设计
完整的测试应该覆盖各种边界条件：
void test_alloc_free() { void *p1 = buddy_alloc(100); // 实际分配128 void *p2 = buddy_alloc(200); // 实际分配256 assert(get_order(100) == 7); // 128=2^7 buddy_free(p1); buddy_free(p2); // 应该合并回原大块 // 测试内存耗尽情况 for (int i = 0; i < 100; i++) { assert(buddy_alloc(1024)); // 持续分配直到失败 } }在实现过程中，最常遇到的坑是忘记更新块头信息。比如在一次分割后，必须正确设置两个新块的order值，否则后续合并逻辑会完全失效。