操作系统基础45-伙伴系统和slab内存分配

2021-01-25 13:48·重学IT的老猫

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

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

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

伙伴系统

伙伴系统从物理连续的大小固定的段上进行分配。从这个段上分配内存，采用 2 的幂分配器来满足请求分配单元的大小为 2 的幂（4KB、 8KB、16KB 等）。请求单元的大小如不适当，就圆整到下一个更大的 2 的幂。例如，如果请求大小为 11KB，则按 16KB 的段来请求。让我们考虑一个简单例子。假设内存段的大小最初为 256KB，内核请求 21KB 的内存。最初，这个段分为两个伙伴，称为 AL 和 AR，每个的大小都为 128KB；这两个伙伴之一进一步分成两个 64KB 的伙伴，即 BL 和 BR。然而，从 21KB 开始的下一个大的 2 的幂是 32KB，因此 BL 或 BR 再次划分为两个 32KB 的伙伴 CL 和 CR。因此，其中一个 32KB 的段可用于满足 21KB 请求。这种方案如下图所示，其中 CL 段是分配给 21KB 请求的。

伙伴系统分配

伙伴系统的一个优点是：通过称为合并的技术，可以将相邻伙伴快速组合以形成更大分段。例如，在图 1 中，当内核释放已被分配的 CL 时，系统可以将 CL 和 CR 合并成 64KB 的段。段 BL 继而可以与伙伴 BR 合并，以形成 128KB 段。最终，可以得到原来的 256KB 段。伙伴系统的明显缺点是：由于圆整到下一个 2 的幂，很可能造成分配段内的碎片。例如，33KB 的内存请求只能使用 64KB 段来满足。事实上，我们不能保证因内部碎片而浪费的单元一定少于 50%。

slab分配

分配内核内存的第二种策略称为slab分配。每个slab由一个或多个物理连续的页面组成，每个cache由一个或多个slab组成，每个内核数据结构都有一个cache。例如，用于表示进程描述符、文件对象、信号量等的数据结构都有各自单独的cache。每个cache 含有内核数据结构的对象实例（称为object）。例如，信号量cache有信号量对象，进程描述符cache有进程描述符对象，等等。

slab 分配

上图显示了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可以处于三种可能状态之一：

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

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

没有因碎片而引起内存浪费。碎片不是问题，因为每个内核数据结构都有关联的cache，每个 cache都由一个或多个slab组成，而slab按所表示对象的大小来分块。因此，当内核请求对象内存时，slab 分配器可以返回刚好表示对象的所需内存。
可以快速满足内存请求。因此，当对象频繁地被分配和释放时，如来自内核请求的情况，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性能也更好。