4. 固定大小内存块管理（伙伴算法）

伙伴算法，这个名字听起来挺有「团队合作」的感觉。说白了，它是一种专门用来管理固定大小内存块的算法。你可能会问：为什么需要固定大小的管理？动态分配不是更灵活吗？

嗯，这个问题我当年也困惑过。直到我在一个物联网项目里，发现系统频繁地分配和释放小内存块，导致内存碎片化严重，系统跑着跑着就挂了。那时候我才意识到，对于实时系统来说，确定性比灵活性更重要。伙伴算法，就是为解决这个问题而生的。

4.1 伙伴算法的核心思想

伙伴算法的思路其实很朴素：把内存不断地对半切分，直到切出合适的大小。就像你有一块大蛋糕，要分给不同食量的人——先切成两半，如果还不够小，再切一半，直到大小合适。

我习惯把这种结构想象成一棵二叉树。根节点是整块内存，左子树和右子树互为「伙伴」。每次分配时，从根节点往下找，找到大小合适的块就切出来。释放时，如果发现自己的「伙伴」也是空闲的，就把两块合并回去。

举个例子。假设我们有 1MB 的连续内存，系统支持的最小块是 64KB。那么内存会被组织成这样的层级：

层级	块大小	块数量
0	1MB	1
1	512KB	2
2	256KB	4
3	128KB	8
4	64KB	16

每个层级维护一个空闲链表。分配时从对应层级取，释放时尝试合并。

4.2 分配流程：从大到小找合适块

分配流程其实就三步，我总结为「找、切、给」：

1. 找：从请求大小对应的层级开始，向上查找空闲块。如果当前层级有空闲块，直接取走。
2. 切：如果当前层级没有空闲块，就向上找更大的块。找到后，把大块对半切分，一半放入下一层级，另一半继续切，直到切出合适大小。
3. 给：把最终切出来的块分配给请求者。

举个例子。假设要分配 64KB 的内存，而当前 64KB 层级没有空闲块，但 256KB 层级有一个空闲块。那么：

• 把 256KB 块切成两个 128KB 块（互为伙伴）
• 一个 128KB 块放入 128KB 层级
• 把另一个 128KB 块再切成两个 64KB 块
• 一个 64KB 块分配给请求者，另一个放入 64KB 层级

你看，整个过程就像剥洋葱，一层层切下去。我当年第一次实现这个算法时，被递归搞得头晕。后来发现用循环加位运算其实更高效。

4.3 释放流程：检查伙伴，能合则合

释放比分配稍微复杂一点，因为要处理合并。核心逻辑是：

1. 把释放的块放回对应层级的空闲链表
2. 检查它的伙伴是否也在空闲链表中
3. 如果是，把两个块从链表移除，合并成一个大块，放入上一层级
4. 重复步骤 2-3，直到无法合并为止

这里的关键是：如何快速找到伙伴的地址？

伙伴算法有个数学上的巧妙之处。假设块大小为 size，块起始地址为 addr，那么它的伙伴地址就是：

buddy_addr = addr ^ size

没错，就是一个异或操作。为什么？因为伙伴块和当前块的地址，只在第 log2(size) 位上不同。用异或把这一位翻转，就得到了伙伴的地址。

举个例子。假设 64KB 块 A 的起始地址是 0x10000，那么它的伙伴 B 的地址就是：

0x10000 ^ 0x10000 = 0x20000

是不是很优雅？我每次看到这个设计都忍不住感叹：计算机科学里真的有很多美丽的数学。

4.4 优缺点分析

任何算法都有取舍。伙伴算法也不例外。我根据自己的项目经验，总结如下：

优点

• 分配和释放速度快：时间复杂度是 O(log N)，N 是内存块数量。对于实时系统来说，这个确定性非常重要。
• 外部碎片少：因为块大小是固定的，而且伙伴之间可以合并，所以不会出现小碎片散落各处的情况。
• 实现简单：核心逻辑就是二叉树遍历加位运算，代码量不大。
• 可预测性强：最坏情况下的执行时间是可以计算的，这对硬实时系统很关键。

缺点

• 内部碎片：这是最大的问题。比如你只需要 10KB，但系统只能给你 16KB 的块，浪费了 6KB。在内存紧张的系统里，这个浪费可能很致命。
• 内存对齐要求高：所有块的起始地址必须是其大小的整数倍。这限制了内存布局的灵活性。
• 合并操作可能耗时：虽然平均情况很快，但最坏情况下（比如释放一个块后一路合并到根节点），需要遍历多个层级。
• 不适合任意大小分配：如果你需要分配各种不同大小的内存，伙伴算法的效率会下降。这时候可能需要考虑 slab 分配器或其他方案。

4.5 一个简单的实现示例

下面是一个简化版的伙伴算法实现，只展示核心逻辑：

#define MAX_ORDER 10  // 最大层级
#define MIN_BLOCK_SIZE 64  // 最小块大小

struct buddy_block {
    struct buddy_block *next;
    int order;  // 层级
    int free;   // 是否空闲
};

struct buddy_system {
    struct buddy_block *free_lists[MAX_ORDER + 1];
    void *base_addr;
    size_t total_size;
};

// 分配：从指定层级开始找
void *buddy_alloc(struct buddy_system *sys, size_t size) {
    int order = get_order(size);  // 计算需要的层级
    if (order > MAX_ORDER) return NULL;

    // 从当前层级向上找空闲块
    for (int i = order; i <= MAX_ORDER; i++) {
        if (sys->free_lists[i] != NULL) {
            // 找到空闲块，从链表移除
            struct buddy_block *block = sys->free_lists[i];
            sys->free_lists[i] = block->next;

            // 如果层级比需要的大，切分
            while (i > order) {
                i--;
                // 把块对半切，一半放回空闲链表
                struct buddy_block *buddy = (struct buddy_block *)((char *)block + (1 << i));
                buddy->order = i;
                buddy->free = 1;
                buddy->next = sys->free_lists[i];
                sys->free_lists[i] = buddy;
            }

            block->free = 0;
            block->order = order;
            return block;
        }
    }
    return NULL;  // 没有足够内存
}

// 释放：检查伙伴，尝试合并
void buddy_free(struct buddy_system *sys, void *ptr) {
    struct buddy_block *block = (struct buddy_block *)ptr;
    int order = block->order;

    while (order < MAX_ORDER) {
        // 计算伙伴地址
        struct buddy_block *buddy = (struct buddy_block *)((char *)block ^ (1 << order));

        // 检查伙伴是否空闲且层级相同
        if (buddy->free && buddy->order == order) {
            // 从空闲链表移除伙伴
            remove_from_list(sys->free_lists[order], buddy);
            // 合并：取地址较小的块作为新块
            if (buddy < block) block = buddy;
            order++;
        } else {
            break;
        }
    }

    // 把合并后的块放回空闲链表
    block->free = 1;
    block->order = order;
    block->next = sys->free_lists[order];
    sys->free_lists[order] = block;
}

这个实现省略了一些细节，比如地址对齐检查、链表操作函数等。但核心逻辑都在了。你想想看，整个算法最巧妙的地方就是那个异或操作——一行代码就找到了伙伴的地址。

4.6 伙伴算法的可视化

为了让你更直观地理解，我画了一张图。这张图展示了 1MB 内存的伙伴树结构，以及分配和释放的过程。

这张图展示了伙伴算法的核心结构。你可以看到，内存被组织成二叉树的形式。分配时从叶子节点往上找，释放时从叶子节点往下合并。整个过程就像在玩一个「内存俄罗斯方块」——只不过这里的方块大小都是 2 的幂次。

4.7 总结

伙伴算法是实时系统中非常经典的内存管理方案。它的核心优势在于确定性和高效性，特别适合那些分配大小相对固定的场景。当然，内部碎片问题是它的软肋，使用时需要权衡。

我个人觉得，伙伴算法最值得学习的地方不是它的实现细节，而是它背后的思想：用空间换时间，用确定性换灵活性。在实时系统中，有时候「慢但可预测」比「快但不可预测」更重要。这个道理，我是在经历过几次系统崩溃后才真正理解的。

如果你正在设计一个实时系统，不妨考虑把伙伴算法作为内存管理的基础。配合 slab 分配器处理小对象，配合页分配器处理大块内存，可以构建一个高效且可靠的内存管理体系。

---

公众号:蓝海资料掘金营，微信deep3321