从理论到代码：手把手实现一个简易Buddy内存分配器

从理论到代码手把手实现一个简易Buddy内存分配器在操作系统的内存管理模块中Buddy算法以其独特的设计哲学成为物理内存管理的经典方案。本文将带您从底层原理出发逐步构建一个可运行的Buddy内存分配器原型。不同于单纯的概念讲解我们会用300行左右的C代码实现核心功能让您真正掌握伙伴系统的设计精髓。1. Buddy算法核心原理伙伴系统的核心思想就像俄罗斯套娃——内存块总是被对半分割或合并。想象一下整理衣柜时我们把大衣柜分成两个中等柜子中等柜子再分成小格子这种分而治之的策略正是Buddy算法的直观体现。三个黄金法则决定了两个内存块能否成为伙伴等分原则两个块的大小必须完全相同地址连续两个块的物理地址必须首尾相接同源分裂必须来自同一个父块的拆分实际系统中常用位图(bitmap)来记录伙伴状态。例如#define MAX_ORDER 10 // 最大2^101024个页面 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 ~((1MAX_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 (1current); 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 ^ (1order)); 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空闲合并AB得到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); // 1282^7 buddy_free(p1); buddy_free(p2); // 应该合并回原大块 // 测试内存耗尽情况 for (int i 0; i 100; i) { assert(buddy_alloc(1024)); // 持续分配直到失败 } }在实现过程中最常遇到的坑是忘记更新块头信息。比如在一次分割后必须正确设置两个新块的order值否则后续合并逻辑会完全失效。