4. 内存池核心数据结构：空闲链表、伙伴系统、slab分配器、红黑树的选择与对比

好，咱们进入第四章。这一章我打算聊聊内存池的“骨架”——核心数据结构。

你想想看，一个内存池，说白了就是一块大内存，怎么把它切碎、怎么管理、怎么快速分配和回收？这背后全靠数据结构撑着。我这些年做GPU内存管理，见过太多因为选错数据结构导致性能翻车的案例。今天就把四种主流方案掰开揉碎了讲清楚。

4.1 空闲链表（Free List）——最朴素的方案

空闲链表，这玩意儿最简单。就是把所有空闲内存块串成一个链表。分配时从头遍历，找到大小合适的块；释放时再插回去。

核心思路： 用链表管理空闲块，简单粗暴。

// 一个简单的空闲链表节点
struct FreeBlock {
    size_t size;        // 块大小
    FreeBlock* next;    // 下一个空闲块
    // 实际数据区紧随其后
};

我在项目里见过有人直接用这个做小规模内存池。说实话，代码量确实少，但坑也不少。

  • 优点： 实现简单，插入和删除都是O(1)操作。
  • 缺点： 分配时要遍历链表找合适块，最坏情况O(n)。碎片化严重，容易产生大量无法利用的小碎片。

我的经验： 空闲链表适合分配大小固定的场景，或者作为其他数据结构的辅助。比如在slab分配器里，就用空闲链表管理同尺寸的对象。

4.2 伙伴系统（Buddy System）——对抗碎片的好手

伙伴系统，这个名字挺有意思。它把内存按2的幂次分成块，每次分配都找刚好能装下请求的最小块。如果找不到，就分裂更大的块。释放时，如果相邻的“伙伴”也是空闲的，就合并回去。

核心思路： 以2的幂次为粒度，分裂与合并，减少外部碎片。

// 伙伴系统的核心：维护多个空闲链表，每个链表管理一种大小的块
struct BuddySystem {
    FreeBlock* free_lists[MAX_ORDER]; // 每个order对应一种大小
    // order 0: 最小块 (比如 4KB)
    // order 1: 8KB
    // order 2: 16KB
    // ...
};

为什么会选2的幂次？因为这样分裂和合并的地址计算特别快，用位运算就行。我当年在优化一个GPU驱动时，就用的伙伴系统管理显存。嗯，这里要注意：伙伴系统内部碎片（分配了比实际需求大的块）是它的硬伤。

  • 优点： 分配和释放速度快（O(log N)），外部碎片少。
  • 缺点： 内部碎片最多可达50%（比如你只要3KB，它给你4KB的块）。

避坑指南： 我曾经在一个项目中，用伙伴系统管理小对象（几十字节），结果内部碎片率高达70%！后来改用slab分配器才解决问题。记住：伙伴系统适合管理大块内存（比如页级别），不适合小对象。

4.3 Slab分配器——小对象的救星

Slab分配器，这玩意儿在Linux内核里用得特别多。它的思路很巧妙：预先为每种常用大小的对象创建专属缓存（slab），每个slab里是一堆固定大小的对象。分配时直接从slab里拿一个，释放时放回去。

核心思路： 为每种大小创建专属缓存，消除内部碎片和外部碎片。

// Slab分配器的简化结构
struct SlabCache {
    size_t object_size;    // 对象大小
    FreeBlock* free_list;  // 空闲对象链表
    void* slab_memory;     // 实际内存区
    int num_objects;       // 对象总数
    int num_free;          // 空闲对象数
};

说白了，slab分配器就是“专物专用”。你想想看，如果频繁分配和释放同一大小的对象（比如网络包、文件描述符），用slab分配器再合适不过了。

  • 优点： 分配和释放都是O(1)，无内部碎片，无外部碎片。
  • 缺点： 需要预先知道对象大小，不适合大小变化很大的场景。

我的习惯： 在CUDA内存池里，我会用slab分配器管理固定大小的临时缓冲区。比如线程块共享内存、寄存器溢出缓冲区，这些大小都是固定的，用slab分配器效率极高。

4.4 红黑树（Red-Black Tree）——平衡的艺术

红黑树，这玩意儿是平衡二叉搜索树的一种。用它管理内存池，通常是把空闲块按地址或大小组织成树。分配时，可以快速找到最合适的块（比如最佳适配、最差适配）。

核心思路： 用平衡树维护空闲块，支持快速查找、插入、删除。

// 红黑树节点
struct RBNode {
    size_t start_addr;  // 起始地址
    size_t size;        // 块大小
    RBNode* left;
    RBNode* right;
    bool is_red;        // 红黑树颜色标记
};

红黑树的好处是，所有操作都是O(log N)。但代价是代码复杂度高，而且每个节点需要额外的指针和颜色标记，内存开销不小。

  • 优点： 查找、插入、删除都是O(log N)，支持多种分配策略（最佳适配、最差适配等）。
  • 缺点： 实现复杂，内存开销大（每个节点需要额外指针和颜色标记）。

我曾经踩过的坑： 在GPU上实现红黑树内存池，结果发现树旋转操作在GPU上性能很差，因为GPU的线程调度和分支预测对树结构不友好。后来我改用跳表（Skip List）替代红黑树，性能提升明显。记住：在GPU上，尽量用数组和索引代替指针和树结构。

4.5 四种方案对比总结

好了，四种方案都讲完了。咱们来做个对比，方便你选型。

特性 空闲链表 伙伴系统 Slab分配器 红黑树
分配时间复杂度 O(N) O(log N) O(1) O(log N)
释放时间复杂度 O(1) O(log N) O(1) O(log N)
内部碎片 无 高（最多50%） 无 无
外部碎片 高 低 无 低
实现复杂度 低 中 中 高
适用场景 固定大小对象、辅助结构 大块内存、页级别管理 固定大小小对象 通用、需要灵活分配策略
GPU友好度 高 中 高 低

我的建议： 实际项目中，很少只用一种数据结构。我通常的做法是：用伙伴系统管理大块内存（比如4KB以上），用slab分配器管理小对象（比如64B、128B、256B等），再用空闲链表作为slab内部的空闲对象管理。至于红黑树，除非你需要非常灵活的分配策略，否则在GPU上尽量别用。

嗯，这一章就到这里。下一章我会讲如何把这些数据结构组合起来，设计一个完整的CUDA内存池。到时候会给出具体的代码实现，敬请期待。

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