本篇位置 第 10 篇留下的问题：外部碎片。这一篇讲怎么应付它——以及为什么应付不掉
运行环境 容器里的 Linux，gcc

一、先看看碎片有多真

第 9 篇那个"仓库管理员"要解决的核心问题就一个：手上有一堆大小不一的空格子，来了一个租客要 512 字节，给他哪一块？

在讲策略之前，先看看做不好的后果。下面这段 C 分配 20 万块、每块 512 字节，然后用两种方式释放：

#define N 200000
static char *p[N];

printf("  一开始                       RSS %7ld kB\n", rss());
for (int i = 0; i < N; i++) { p[i] = malloc(512); memset(p[i], 1, 512); }
printf("  分配 %d 块 512 字节之后    RSS %7ld kB\n", N, rss());

if (mode == 1) {
    for (int i = 0; i < N; i++) free(p[i]);          /* 全部释放 */
    printf("  全部释放之后                 RSS %7ld kB\n", rss());
} else {
    for (int i = 0; i < N; i += 2) free(p[i]);       /* 隔一个释放一个 */
    printf("  隔一个释放一个（释放了一半）  RSS %7ld kB\n", rss());
}
printf("  malloc_trim 之后             RSS %7ld kB\n", (malloc_trim(0), rss()));

=== A. 全部释放 ===
  一开始                       RSS    1180 kB
  分配 200000 块 512 字节之后    RSS  105988 kB
  全部释放之后                 RSS    2992 kB
  malloc_trim 之后             RSS    2864 kB

=== B. 隔一个释放一个 ===
  一开始                       RSS    1176 kB
  分配 200000 块 512 字节之后    RSS  105984 kB
  隔一个释放一个（释放了一半）  RSS  105984 kB
  malloc_trim 之后             RSS  105980 kB

把这两组并排看。

  • A：释放了 100 MB，RSS 从 106 MB 掉到 3 MB。地还回操作系统了。
  • B：同样释放了 50 MB（一半），RSS 从 105984 kB 变成 105984 kB——一个字节都没降。 连 malloc_trim（明确要求把空闲的还回去）也只挤出了 4 kB。

⭐ 释放了一半的内存，占用一点没变。 这不是 glibc 写得差，这是外部碎片的定义：空间是有的，但它是碎的。

原因很直白：B 里每个被释放的 512 字节，两边都紧挨着一个还在用的 512 字节。这些空洞没有一个能和邻居拼起来，也没有一个大到可以整页还给内核——内核只能按页（4096 字节）收回，而每一页里都还嵌着几块活的。

回到仓库：你把整排格子隔一个退一个。 走廊上现在有一半是空的，但没有任何一段连续的空位大到能腾出一整个货架还给楼管。

二、分配器手里有什么

先把问题说清楚。分配器管着一大块地，它要维护：

  • 哪些区间是空的——用一个空闲链表串起来。
  • 每块用出去的地有多大——第 9 篇说过，这个 header 就贴在每块地前面。

⚠️ 那个 header 是有代价的。glibc 上通常是 8 到 16 字节。所以你 malloc(1) 实际占掉的远不止 1 字节——上面那个演示，20 万 × 512 字节 = 102 MB 的请求，实际用掉 106 MB，多出来的 4 MB 就是 header 和对齐。

两个基本动作

切分（splitting）：空闲块比请求大，切一块给他，剩下的留在链表里。

合并（coalescing）：释放的时候，看看左右邻居是不是也空着。是的话合成一大块。

⭐ 合并是对付碎片的主力。没有它，一块 100 KB 的地被切成 100 个 1 KB 用完再释放，你会得到 100 个 1 KB 的空闲块，再也没法满足一个 2 KB 的请求——明明有 100 KB 空着。

上面演示 B 之所以救不回来，正是因为每个空洞的左右邻居都还活着，一次合并都做不成。

三、给谁？三种经典策略

链表里有好几块都够大，选哪块？

最先适配（first fit）：从头找，第一个够大的就用。快，但会把链表头部搅得很碎。

最佳适配（best fit）：找最接近请求大小的那块。剩下的边角最小。听起来最聪明，但要遍历整个链表，而且会产生大量小到没用的碎渣。

最差适配（worst fit）：找最大的那块切。想法是"剩下的部分还足够大，还能用"。实测效果最差，而且也要全表遍历。

⚠️ 这里有个反直觉的结论值得记住：“最佳适配"通常并不最佳。 它留下的边角往往小到谁也用不了，等于把内存磨成粉。而"最先适配"配合合并，实际表现常常更好，还快得多。

这是这门课里第二次遇到"局部最优不等于全局最优”——第 5 篇的 SJF 在单个指标上最优，但它对响应时间是灾难。

折中：分离空闲链表

现代分配器的做法是不再去"挑"：

按大小分成很多档（8、16、24、32……），每档一条独立链表。来一个请求，直接算出它属于哪一档，从那条链表头上摘一个——O(1)，不用比较，不用遍历。

上面演示里 glibc 打印的 tcache（第 9 篇那句 double free detected in tcache 2）就是这个思路的极致：每个线程自己还带一小份缓存，连锁都不用加。

⭐ 从"找最好的那块"到"按档位直接取"，是分配器设计的一次根本转向。放弃最优，换来确定的 O(1)。

四、伙伴系统：只用 2 的幂

第 10 篇末尾提过一个想法：如果所有块大小都受限，碎片会不会好办？

伙伴系统（buddy allocator）把它做到了：所有块的大小都是 2 的幂。

  • 要 7 KB？给你 8 KB。
  • 手上只有 64 KB 的块？对半切成两个 32 KB，再切成 16、8——切到 8 KB 为止。
  • 释放的时候，看看你的"伙伴"（那个和你同一次切出来的兄弟）是不是也空着。是就合回去，然后接着往上看。

它的妙处在合并极其便宜：伙伴的地址可以直接用一个异或算出来（块地址 XOR 块大小），不用查链表，不用扫邻居。

代价是内部碎片：要 33 KB 给你 64 KB，浪费近一半。

Linux 内核管理物理页用的就是伙伴系统——它分配的单位本来就是页的整数倍，2 的幂这个限制不太亏。

五、slab：干脆放弃通用

再走一步：如果同一种大小的对象要反复分配释放呢？

内核里全是这种情况——task_struct、inode、网络包描述符，每种都是固定大小，每秒成千上万次分配释放。

slab 分配器的做法是：给每一种对象开一个专用的池子。

  • 一次向伙伴系统要几页，切成整整齐齐的 N 个同样大小的槽。
  • 分配就是从这个池子里摘一个，没有搜索，没有切分，没有合并。
  • 而且槽里的对象可以保持已初始化的状态——回收时不销毁，下次分配省掉初始化。

⭐ slab 是"用专用换通用"的典型：它彻底放弃了处理任意大小的能力，换来了这一种大小上的极致性能。 你可以在容器里 cat /proc/slabinfo 看到内核开了几百个这样的池子。

六、代价与取舍

这一层换来了什么： 你写 malloc(37) 就有 37 字节可用，不用关心物理内存里的地是怎么排的。

它花了什么：

  • 每块地的 header（8–16 字节）。分配大量小对象时这是实打实的开销。
  • 碎片。⭐ 而且要记住：碎片是消不掉的，只能推迟和缓解。 只要允许任意大小、任意存活时间，就一定会攒出碎片。

它放弃了什么： “释放了就还回操作系统"这个直觉。 上面演示 B 是这件事最直白的证据：释放了一半，RSS 一点没降。

这有个非常现实的后果：很多"内存泄漏"其实不是泄漏，是碎片。 你的对象都释放了，valgrind 干干净净，但 RSS 就是下不去。这种时候换分配器（jemalloc、tcmalloc、mimalloc）或者改分配模式（对象池、arena），往往比找泄漏有用。

七、小结

  • ⭐ 实测：分配 20 万块 512 字节吃掉 106 MB。全部释放 → RSS 掉到 3 MB；隔一个释放一个（同样释放 50 MB）→ RSS 一个字节没降，malloc_trim 也救不了。
  • 原因是每个空洞的左右邻居都还活着，一次合并都做不成，也凑不出可以整页归还的连续空间。
  • 分配器的两个基本动作是切分和合并。合并是对付碎片的主力。
  • ⚠️ “最佳适配"通常不最佳——它把内存磨成粉，还要全表遍历。这是这门课第二次遇到"局部最优不等于全局最优”。
  • 现代做法是分离空闲链表：按大小分档，直接从对应链表头取，O(1)，不挑。glibc 的 tcache 更进一步，每线程一份缓存，连锁都省了。
  • 伙伴系统限定 2 的幂，让合并便宜到一次异或；代价是内部碎片。Linux 管物理页用它。
  • slab 给每种固定大小的对象开专用池，彻底放弃通用换极致性能。内核里有几百个（/proc/slabinfo）。
  • ⭐ 碎片消不掉，只能推迟。 很多"内存泄漏"其实是碎片——工具查不出来，因为它不是 bug。

思考题

  1. 演示 B 里，如果反过来——先分配 20 万块，然后从后往前隔一个释放一个——结果会不一样吗？为什么？
  2. 假设你的服务每个请求分配一批对象，请求结束时全部释放。有一种分配策略能让这个场景完全没有碎片，而且释放只要一条指令。是什么？（提示：想想"整批”。）
  3. slab 让对象保持已初始化状态来省初始化开销。这在安全上有什么风险？（提示：第 9 篇第三节那个演示。）
  4. 仓库那个比方里，“合并"就是把相邻的空格子打通。那伙伴系统对应仓库里的什么规矩？它为什么让打通变得特别快？

延伸