4、伙伴系统（Buddy System）：原理、合并与分裂算法、优缺点、在Linux内核中的应用

说到内存管理，伙伴系统是个绕不开的话题。我刚开始接触RTOS时，总觉得动态内存分配不就是malloc和free嘛，有啥好研究的？直到有一次，一个跑了大半年的设备突然死机，查了三天才发现是内存碎片惹的祸。从那以后，我对内存管理的态度就彻底变了。

伙伴系统，说白了就是解决内存碎片问题的一种经典方案。它最早出现在1963年的一个操作系统中，后来被Linux内核借鉴并发扬光大。今天咱们就来聊聊它的原理、算法，以及在实际项目中的坑和技巧。

4.1 伙伴系统的核心思想

伙伴系统的想法其实很朴素：把内存按2的幂次方划分成块。比如2KB、4KB、8KB、16KB……一直到整个内存区域。每个大小的块都放在一个独立的链表中管理。

你申请内存时，系统会找一个大小刚好满足需求的块。如果没有，就把大块一分为二，直到分出合适的大小。释放时，如果相邻的块也是空闲的，就合并成一个更大的块。

嗯，这里要注意一个关键点：只有互为“伙伴”的两个块才能合并。什么叫伙伴？就是由同一个大块分裂出来的两个大小相等、地址连续的块。

4.2 分裂算法详解

假设你申请一块大小为n的内存，系统会怎么做？

1. 找到满足2^k ≥ n的最小k值（即向上取整到2的幂）
2. 检查大小为2^k的空闲链表
3. 如果链表不为空，直接分配第一个块
4. 如果链表为空，从更大的块（比如2^(k+1)）中分裂出一个
5. 分裂出来的两个块互为伙伴，一个分配出去，另一个放入2^k的链表

举个例子。你申请3KB内存，系统会向上取整到4KB。如果4KB链表是空的，就从8KB块中分裂。8KB一分为二，两个4KB块。一个给你用，另一个挂到4KB链表里。

// 伪代码：伙伴系统分配
void *buddy_alloc(size_t size) {
    // 1. 计算需要的阶数
    int order = ceil_log2(size);
    
    // 2. 从当前阶数开始查找
    for (int i = order; i <= MAX_ORDER; i++) {
        if (!free_list[i].empty()) {
            // 3. 找到可用块，开始分裂
            block = free_list[i].remove_first();
            
            // 4. 如果阶数比需要的大，就分裂
            while (i > order) {
                i--;
                // 分裂成两个伙伴
                buddy = block + (1 << i);
                free_list[i].add(buddy);
            }
            
            return block;
        }
    }
    
    // 5. 没有足够内存
    return NULL;
}

我在项目中遇到过一个问题：频繁的小块分配会导致大量分裂操作，产生很多小碎片。比如你反复申请和释放几十字节的数据，系统每次都给你一个4KB的块，浪费很严重。后来我改用slab分配器配合伙伴系统，才解决了这个问题。

4.3 合并算法详解

释放内存时，合并算法是分裂的逆过程。但这里有个关键点：必须找到伙伴才能合并。

怎么找伙伴？有个小技巧。假设一个块的起始地址是addr，大小是2^k，那么它的伙伴地址就是：

buddy_addr = addr ^ (1 << k)

这个公式很巧妙。你想想看，两个伙伴块的区别就在第k位上。一个为0，一个为1。用异或操作就能快速定位。

// 伪代码：伙伴系统释放
void buddy_free(void *addr, size_t size) {
    int order = get_order(size);
    
    // 尝试向上合并
    while (order < MAX_ORDER) {
        // 计算伙伴地址
        void *buddy = (void *)((uintptr_t)addr ^ (1 << order));
        
        // 检查伙伴是否空闲且可合并
        if (!is_buddy_free(buddy, order)) {
            break;
        }
        
        // 合并：从链表中移除伙伴
        free_list[order].remove(buddy);
        
        // 合并后的地址取较小的那个
        if (buddy < addr) {
            addr = buddy;
        }
        
        order++;
    }
    
    // 将合并后的块放入对应链表
    free_list[order].add(addr);
}

4.4 伙伴系统的优缺点

优点	缺点
分配和释放速度快，时间复杂度O(log N) 外部碎片少，合并机制能有效回收 实现相对简单，代码量不大 适合大块内存分配场景	内部碎片严重，最小分配单位是2的幂 小块分配效率低，浪费空间 合并操作有延迟，不是立即执行 对实时性要求高的场景不太友好

说白了，伙伴系统是个“粗粒度”的管理器。它擅长管理大块内存，但处理小对象时就很吃力。我个人的习惯是：大块用伙伴系统，小块用slab分配器。两者配合，效果最好。

4.5 在Linux内核中的应用

Linux内核的页分配器就是基于伙伴系统实现的。它管理着物理内存的分配和释放，是内核最核心的模块之一。

Linux的伙伴系统有几个特点：

• 最大阶数MAX_ORDER：通常是11，对应2^11=2048页。如果页大小是4KB，最大可管理8MB的连续内存。
• 每CPU页框缓存：为了提升性能，每个CPU维护一个小的页缓存，减少对全局链表的竞争。
• 内存迁移类型：把内存按用途分类（可回收、不可移动等），减少碎片。

// Linux内核中的伙伴系统相关结构
struct free_area {
    struct list_head    free_list[MIGRATE_TYPES];
    unsigned long       nr_free;
};

struct zone {
    // ...
    struct free_area    free_area[MAX_ORDER];
    // ...
};

我记得有一次，一个嵌入式设备运行几个月后出现内存分配失败。我查看/proc/buddyinfo，发现高阶内存块几乎全被用完了，只剩下大量4KB的小块。这就是典型的碎片问题。后来通过调整内存迁移策略和定期压缩，才解决了这个问题。

4.6 实际项目中的建议

如果你要在自己的RTOS中实现伙伴系统，我有几点建议：

1. 不要单独使用：配合slab或对象池使用，各取所长。
2. 合理设置最大阶数：根据你的内存大小来定，不要盲目设大。
3. 考虑碎片整理：定期检查高阶内存块的使用情况，必要时进行内存压缩。
4. 注意实时性：合并操作可能耗时较长，实时任务中要小心。

嗯，伙伴系统就聊到这里。它虽然有些缺点，但作为内存管理的基础设施，地位还是不可动摇的。下一节我们聊聊slab分配器，看看它是怎么解决小块分配问题的。