伙伴系统和slab内存分配机制详解

当在用户模式下运行进程请求额外内存时，从内核维护的空闲页帧列表上分配页面。这个列表通常使用页面置换算法来填充，如前所述，它很可能包含散布在物理内存中的空闲页面。也要记住，如果用户进程请求单个字节内存，那么就会导致内部碎片，因为进程会得到整个帧。

用于分配内核内存的空闲内存池通常不同于用于普通用户模式进程的列表。这有两个主要原因：

1. 内核需要为不同大小的数据结构请求内存，其中有的小于一页。因此，内核应保守地使用内存，并努力最小化碎片浪费。这一点非常重要，因为许多操作系统的内核代码或数据不受调页系统的控制。
2. 用户模式进程分配的页面不必位于连续物理内存。然而，有的硬件设备与物理内存直接交互，即无法享有虚拟内存接口带来的便利，因而可能要求内存常驻在连续物理内存中。

下面讨论两个策略，以便管理用于内核进程的空闲内存：“伙伴系统”和 slab 分配。

伙伴系统

伙伴系统从物理连续的大小固定的段上进行分配。从这个段上分配内存，采用 2 的幂分配器来满足请求分配单元的大小为 2 的幂（4KB、 8KB、16KB 等）。请求单元的大小如不适当，就圆整到下一个更大的 2 的幂。例如，如果请求大小为 11KB，则按 16KB 的段来请求。

让我们考虑一个简单例子。假设内存段的大小最初为 256KB，内核请求 21KB 的内存。最初，这个段分为两个伙伴，称为 A_L 和 A_R，每个的大小都为 128KB；这两个伙伴之一进一步分成两个 64KB 的伙伴，即 B_L 和 B_R。然而，从 21KB 开始的下一个大的 2 的幂是 32KB，因此 B_L 或 B_R 再次划分为两个 32KB 的伙伴 C_L 和 C_R。因此，其中一个 32KB 的段可用于满足 21KB 请求。这种方案如图 1 所示，其中 C_L 段是分配给 21KB 请求的。
伙伴系统的一个优点是：通过称为合并的技术，可以将相邻伙伴快速组合以形成更大分段。例如，在图 1 中，当内核释放已被分配的 C_L 时，系统可以将 C_L 和 C_R 合并成 64KB 的段。段 B_L 继而可以与伙伴 B_R 合并，以形成 128KB 段。最终，可以得到原来的 256KB 段。

伙伴系统的明显缺点是：由于圆整到下一个 2 的幂，很可能造成分配段内的碎片。例如，33KB 的内存请求只能使用 64KB 段来满足。事实上，我们不能保证因内部碎片而浪费的单元一定少于 50%。

slab分配

分配内核内存的第二种策略称为slab分配。每个 slab 由一个或多个物理连续的页面组成，每个 cache 由一个或多个 slab 组成，每个内核数据结构都有一个 cache。

例如，用于表示进程描述符、文件对象、信号量等的数据结构都有各自单独的 cache。每个 cache 含有内核数据结构的对象实例（称为 object）。例如，信号量 cache 有信号量对象，进程描述符 cache 有进程描述符对象，等等。
图 2 显示了 slab、cache 及 object 三者之间的关系。该图显示了 2 个大小为 3KB 的内核对象和 3 个大小为 7KB 的对象，它们位于各自的 cache 中。

slab 分配算法采用 cache 来存储内核对象。在创建 cache 时，若干起初标记为 free 的对象被分配到 cache。cache 内的对象数量取决于相关 slab 的大小。例如，12KB slab（由 3 个连续的 4KB 页面组成）可以存储 6 个 2KB 对象。最初，cache 内的所有对象都标记为空闲。当需要内核数据结构的新对象时，分配器可以从 cache 上分配任何空闲对象以便满足请求。从 cache 上分配的对象标记为 used（使用）。

让我们考虑一个场景，这里内核为表示进程描述符的对象从 slab 分配器请求内存。在 Linux 系统中，进程描述符属于 struct task_struct 类型，它需要大约 1.7KB 的内存。当 Linux 内核创建一个新任务时，它从 cache 中请求 struct task_struct 对象的必要内存。cache 利用已经在 slab 中分配的并且标记为 free (空闲）的 struct task_struct 对象来满足请求。

在 Linux 中，slab 可以处于三种可能状态之一：

1. 满的：slab 的所有对象标记为使用。
2. 空的：slab 上的所有对象标记为空闲。
3. 部分：slab 上的对象有的标记为使用，有的标记为空闲。

slab 分配器首先尝试在部分为空的 slab 中用空闲对象来满足请求。如果不存在，则从空的 slab 中分配空闲对象。如果没有空的 slab 可用，则从连续物理页面分配新的 slab，并将其分配给 cache；从这个 slab 上，再分配对象内存。

slab 分配器提供两个主要优点：

1. 没有因碎片而引起内存浪费。碎片不是问题，因为每个内核数据结构都有关联的 cache，每个 cache 都由一个或多个 slab 组成，而 slab 按所表示对象的大小来分块。因此，当内核请求对象内存时，slab 分配器可以返回刚好表示对象的所需内存。
2. 可以快速满足内存请求。因此，当对象频繁地被分配和释放时，如来自内核请求的情况，slab 分配方案在管理内存时特别有效。分配和释放内存的动作可能是一个耗时过程。然而，由于对象已预先创建，因此可以从 cache 中快速分配。再者，当内核用完对象并释放它时，它被标记为空闲并返回到 cache，从而立即可用于后续的内核请求。

slab 分配器首先出现在 Solaris 2.4 内核中。由于通用性质，Solaris 现在也将这种分配器用于某些用户模式的内存请求。最初，Linux 使用的是伙伴系统；然而，从版本 2.2 开始，Linux 内核采用 slab 分配器。

现在，最近发布的 Linux 也包括另外两个内核内存分配器，SLOB 和 SLUB 分配器（Linux 将 slab 实现称为 SLAB）。

简单块列表（SLOB）分配器用于有限内存的系统，例如嵌入式系统。SLOB 工作采用 3 个对象列表：小（用于小于 256 字节的对象）、中（用于小于 1024 字节的对象）和大（用于小于页面大小的对象）。内存请求采用首先适应策略，从适当大小的列表上分配对象。

从版本 2.6.24 开始，SLUB 分配器取代 SLAB，成为 Linux 内核的默认分配器。SLUB 通过减少 SLAB 分配器所需的大量开销，来解决 slab 分配的性能问题，一个改变是，在 SLAB 分配下每个 slab 存储的元数据，移到 Linux 内核用于每个页面的结构 page。此外，对于 SLAB 分配器，每个 CPU 都有队列以维护每个 cache 内的对象，SLUB 会删除这些队列。

对于具有大量处理器的系统，分配给这些队列的内存量是很重要的。因此，随着系统处理器数量的增加，SLUB 性能也更好。