3. 内存池进阶：伙伴算法与Slab分配器原理

上一章我们聊了基础内存池的设计，说白了就是预先挖好一个池子，需要时从里面捞。但实际项目中，内存分配的场景远比这复杂。比如内核里要频繁分配小对象，或者要分配连续的大块内存——这时候基础池就不够用了。

我个人习惯把内存分配器分成两类：一类管「大小」，一类管「碎片」。伙伴算法解决的是前者，Slab解决的是后者。今天我们就来拆开看看。

3.1 伙伴算法：解决大块内存的连续性问题

先问个问题：为什么需要伙伴算法？

你想想看，系统运行久了，内存会不断分配释放。如果每次分配都是随机大小，内存就会变得支离破碎。比如你分配了 64KB、128KB、256KB，然后释放了中间的 128KB——这时候你想分配一个 256KB 的连续块，可能就失败了，因为中间有个空洞。

伙伴算法的核心思想很简单：把内存按 2 的幂次分成块。每次分配时，找刚好能装下请求大小的最小块。如果找不到，就拆更大的块。释放时，检查相邻的块是否也是空闲的，如果是，就合并回去。

关键点：伙伴算法保证所有分配的内存块大小都是 2 的幂次，且地址对齐到块大小。这样相邻块就能快速合并。

我在项目中遇到过一个问题：某嵌入式系统需要频繁分配 1MB 左右的 DMA 缓冲区。用普通 malloc 分配，时间长了就会出现分配失败。后来换成伙伴算法，把 16MB 内存按 2 的幂次分成 1MB、2MB、4MB、8MB 的块，问题就解决了。

3.2 伙伴算法的数据结构

实现上，我们通常维护一个空闲链表数组。数组下标 i 对应大小为 2^i 的空闲块链表。

// 伙伴算法的核心结构
#define MAX_ORDER 10  // 最大阶数，2^10 = 1024 页

struct buddy_system {
    struct list_head free_area[MAX_ORDER + 1];  // 每个阶的空闲链表
    unsigned long total_pages;                  // 总页数
    void *base_addr;                            // 内存基地址
};

分配时，从请求大小对应的阶开始找。如果该阶有空闲块，直接取走。如果没有，就找更高阶的块，拆成两个「伙伴」，一个分配出去，另一个挂到低一阶的链表里。

释放时，找到这个块的伙伴地址。如果伙伴也是空闲的，就合并，然后递归向上检查。

小技巧：判断两个块是不是伙伴，只需要看它们的地址异或后是否等于块大小。比如两个 4KB 的块，地址分别是 0x1000 和 0x2000，异或得 0x1000，正好是 4KB，说明它们是伙伴。

3.3 伙伴算法的优缺点

优点 缺点
分配和释放速度快，O(log N) 内部碎片严重，比如分配 3KB 实际给 4KB
能有效合并碎片，避免外碎片 不适合小对象频繁分配
实现简单，适合嵌入式场景 内存利用率不高，平均浪费约 25%

嗯，这里要注意：伙伴算法虽然解决了外碎片问题，但内部碎片其实挺多的。你想想，分配 65KB 要给你 128KB，将近一半浪费了。所以它更适合分配中等以上大小的内存块。

3.4 Slab 分配器：专治小对象频繁分配

Slab 分配器是另一种思路。它不解决连续性问题，而是解决小对象频繁分配释放的问题。

我记得在做一个网络协议栈时，需要频繁分配和释放 socket 结构体、sk_buff 等小对象。每次用 kmalloc 分配，都要走一遍伙伴算法，开销很大。而且这些对象大小固定，完全可以复用。

Slab 的思想就是：为每种对象类型维护一个专属缓存。缓存里预先分配好一批对象，用的时候直接取，用完放回去，不释放给伙伴系统。

核心优势：Slab 分配器消除了创建和销毁对象时的内存分配开销，同时避免了小对象造成的内存碎片。

3.5 Slab 的数据结构

Slab 分配器有三个核心概念：缓存（cache）、 slab 和对象（object）。

  • 缓存：管理同一种类型的对象。比如一个缓存专门管 socket 结构体。
  • Slab：缓存里的一个内存块，包含多个连续的对象。一个缓存可以有多个 slab。
  • 对象：实际分配出去的小块内存。
// Slab 分配器的简化结构
struct kmem_cache {
    const char *name;           // 缓存名称
    size_t object_size;         // 对象大小
    size_t slab_size;           // 每个 slab 的大小
    struct list_head slabs_full;    // 已满的 slab 链表
    struct list_head slabs_partial; // 部分空闲的 slab 链表
    struct list_head slabs_free;    // 完全空闲的 slab 链表
    void (*ctor)(void *obj);    // 构造函数
};

分配时，先从 slabs_partial 里找空闲对象。如果没有，就从 slabs_free 里拿一个 slab 出来。如果连空闲 slab 都没有，就向伙伴系统申请新的内存页。

释放时，把对象放回所属 slab。如果 slab 变成完全空闲，可以选择释放回伙伴系统，也可以留着备用。

我曾经踩过的坑：Slab 分配器的构造函数（ctor）不要做太重的初始化工作。比如 memset 整个对象到 0，这在频繁分配时开销很大。我建议只初始化必要的字段，其他留给使用者。

3.6 伙伴算法 + Slab：Linux 内核的实践

Linux 内核实际用的是伙伴算法 + Slab 的混合方案。伙伴算法管理物理页框，Slab 在伙伴算法之上管理小对象。

具体来说：

  • 伙伴算法负责分配和释放物理页（通常 4KB 为单位）
  • Slab 分配器从伙伴算法拿到页，然后切成小对象
  • 对于大于一个页的分配，直接走伙伴算法
  • 对于小于一个页的分配，走 Slab

这种分层设计的好处很明显：大块内存用伙伴算法保证连续性，小块内存用 Slab 提高效率。两者互补，各司其职。

个人建议：如果你在设计自己的内存池，可以考虑类似的思路。比如用伙伴算法管理 64KB 以上的块，用 Slab 管理 64KB 以下的对象。这样既能控制碎片，又能保证性能。

3.7 核心逻辑流程图

下面这张图展示了伙伴算法和 Slab 分配器的协作关系：

内存分配器分层架构 应用层：malloc / new / kmalloc Slab 分配器（小对象 < 4KB） 对象缓存 | 对象复用 | 构造函数 伙伴算法（物理页管理 ≥ 4KB） 2的幂次分块 | 伙伴合并 | 空闲链表数组 物理内存 / 页框 分配流程：应用请求 → Slab（小对象）或伙伴算法（大对象）→ 物理内存

说白了，这套架构就是分层治理。上层应用不用关心底层怎么管理内存，只需要调用统一的接口。底层则根据请求大小，自动选择最合适的分配策略。

3.8 实际项目中的选择建议

最后，我根据经验给几个建议：

  • 嵌入式裸机环境：如果内存不大（比如 64MB 以下），直接用伙伴算法就够了。实现简单，调试方便。
  • 需要频繁分配小对象：比如网络协议栈、文件系统缓存，一定要上 Slab。否则性能会很难看。
  • 混合场景：参考 Linux 的做法，伙伴算法做底层，Slab 做上层。这样大小通吃。
  • 实时系统：注意 Slab 的分配时间不确定（可能触发伙伴系统的页分配）。可以考虑预分配所有 slab。
我曾经踩过的坑：在一个实时音视频项目中，我用了纯伙伴算法管理所有内存。结果小对象分配太多，内部碎片导致内存利用率只有 60%。后来改成 Slab 管理小对象，利用率提升到 85% 以上。所以选型时一定要看你的对象大小分布。

好了，这一章的内容就到这里。伙伴算法和 Slab 分配器是内存池设计的两个重要基石。理解了它们，你就能设计出更高效、更可靠的内存管理系统。

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

← 上一章 📖 返回目录 下一章 →