8. 分段

上一节末尾 提到，由于程序并不会把堆区或栈区用的十分极限，因此简单的把进程的整个地址空间放入内存会导致堆栈之间大量的空闲空间被浪费，即产生了 内部碎片。由于内部碎片归进程所有，在当前的机制下操作系统无法收回这部分空间供其他进程使用。一旦操作系统可以分配的空闲内存无法再装入进程完整的地址空间，就无法再运行新的进程。

原理

为了解决此问题，我们有必要去掉我们先前对于地址空间的第一条假设。由于内部碎片产生的一大直接原因是堆栈之间存在大量的空闲空间，一种直接的解决方法是与其为整个地址空间分配一对基址与界限寄存器，不如为地址空间内的每个逻辑段分配一对寄存器。在我们的简化情境下，我们需要三对寄存器，分别分配给代码段、堆区、栈区。这样，操作系统可以将不同的段放到不同的物理区域。这种解决方法即为 分段。下面是一个地址空间分段放入物理内存的举例：

从图中可以看到，操作系统此时只会为明确使用的内存分配地址空间，提高了物理内存的利用率。

当程序访问地址空间内的某个地址时，硬件会首先根据该地址位于哪个段内，将该地址减去该段在虚拟空间内的偏移量后加上其在基址寄存器中的基址，即可得到物理地址。同样的，如果硬件发现该地址越界，会触发中断，操作系统随后终止该程序，这就是 段错误（Segmentation Fault）。

硬件通过两种方式来获知虚拟地址对应着哪一个逻辑段。在 显式 方式中，虚拟地址的前几位标识该地址属于哪一个段，其余位用作段内偏移。在进行地址转换前，硬件检查虚拟地址的偏移量是否超出界限，若超出会触发越界异常。在 隐式 方式中，硬件通过地址产生的方式确定地址属于哪个段。例如，由程序计数器产生的地址属于代码段；基于栈指针或基址指针的地址属于栈区；其余属于堆区。

操作系统同样需要实现更多的功能。例如当发生上下文切换时，操作系统需要保存与恢复进程存储在 MMU 中的所有内容。操作系统同样需要为新进程的地址空间中每个段分配空闲空间。

需要注意的是，栈在地址空间中是由高地址向低地址反向增长的。因此除了基本的基址与界限寄存器外，我们需要设计一些标志位通知硬件某一段是向哪个方向增长的。此外，我们还可以通过添加 保护位 标识程序可以对某一个段执行的操作，尝试执行不被允许的操作将会触发异常中断。一般而言，代码段是可读可执行的，堆栈段是可读可写的。对于共享库而言，通过将保护位设置为可读可执行，就能将库的代码段放心在多个地址空间之间共享，供多个进程使用。而在进程的视角中，虽然进程不能修改这段代码，但每个进程都认为自己独占该共享库代码段的内存空间。

前面的叙述仅仅简单将地址空间分为了代码段、堆区、栈区三个段，但一些早期系统（如 Multics）支持更加细粒度的分段，从而更灵活、高效地利用内存。当然，将地址空间分为更多更小的段也需要进一步的硬件支持，操作系统也需要在内存中保存某种段表。

然而，分段虽然解决了由堆栈中间的空闲空间导致的内部碎片的问题，但引入了新的问题：

如果我们维持 我们先前对于地址空间的第三条假设，在每个段的大小都相同的前提下，我们就可以简单把地址空间划分为固定大小的单元，维护一个关于某个单元空闲或占用的列表，当新的内存请求到来时挑选一个空闲单元返回即可。

一旦去掉这条假设，我们就会发现，由于每个分段的大小不同，系统运行一段时间后，物理内存就会充满许多碎片化的空闲空间，这些空间合计占据了物理内存的很大一部分，但由于每个片空间空间的大小很小，因此很难分配出新的段或扩大已有的段，这个问题被称作 外部碎片，如下图所示：

外部碎片的一种解决方法是定期 紧凑 内存，即重新安排内存中所有的段到连续的内存区域中以消除外部碎片。但完整拷贝所有地址空间的开销极大，且紧凑后某些段可能无法继续扩张。

另一种解决方法将在下面详细论述，这就是 空闲列表管理算法，其目的是尽可能保留大的内存块进行分配，减少外部碎片的产生。空闲列表管理算法多种多样，各有优劣，但没有一个算法能完美避免外部碎片的产生。下面将简单举几个典型算法。

除了外部碎片之外，分段也无法支持更一般化的 稀疏地址空间（即具有大量未使用地址的地址空间）。例如对于大而稀疏的堆而言，分段仍然需要将整个堆放置在物理内存中。

空闲空间管理的机制

由于空闲空间的管理不仅仅存在于操作系统层面，下面的讲解将以用户级内存分配库（malloc() 与 free()）为例，但其算法可以用于任何类似的情境中。

我们称在堆上管理空闲空间的数据结构为 空闲列表，其包含了库所管理的内存区域（下称堆）中所有空闲块的引用。

我们同时做出如下方便叙述的假设：

• 内存一旦被分配就不可重定位，不能进行紧凑操作。
• 堆区连续且在整个生命周期内固定。

大多数操作系统中管理空闲列表的程序逻辑如下：

• 空闲列表存储在 链表 中，每个结点代表一块空闲区域，结点维护两个信息：空闲内存的 起始地址 与 大小。
• 当用户请求内存时，分配程序依据空闲列表找到一块可以满足请求的空闲区域，将其 分割，一块返回给用户，另一块放回空闲列表。
• 分配程序释放一块无用内存时，会尝试与相邻的所有空闲块相合并。

前面 提到过，free() 调用无需指定释放对象的大小，这表明库函数维护了一些额外的信息。这些信息存放在 头块 中。头块位于用户通过 malloc() 获得的内存块之前。也即，当用户请求一块内存时，库需要寻找能容纳这块内存加上头块的空闲空间；同理当用户释放这块内存时，头块所占用的内存也被释放。头块包含了如下内容：分配空间的大小、用于完整性检查的 Magic Number，以及其他信息。

与头块相同，空闲列表也不是凭空存在，其也会占用空闲空间的一部分，一般是堆最开始的一块区域。

如果堆中的内存耗尽，向堆申请更多资源的请求会返回 NULL。不过分配程序通过系统调用可以向操作系统申请空间使堆扩张。

空闲空间管理的典型策略

理想的分配程序应同时保证快速且碎片少，然而 前面 已经提到过目前没有完美的分配策略。下面将简单介绍集中典型的策略：

最优匹配策略

遍历整个空闲列表，找到最小的满足要求的空闲块分割并返回。基本思想是尽可能利用较难利用的小块来避免空间浪费。优点：简单；缺点：需要遍历整个空闲列表，性能差。

最差匹配策略

遍历整个空闲列表，找到最大的满足要求的空闲块分割并返回。基本思想是尽可能留下一个大块。优点：同最优匹配；缺点：碎片多且性能差。

首次匹配策略

从头遍历空闲列表，在找到一块满足要求的空闲块后就立刻分割并返回。优点：性能更好；缺点：大量小碎片堆积在地址空间开头区域。

下次匹配策略

从上一次查找结束的位置开始遍历空闲列表，在找到一块满足要求的空闲块后就立刻分割并返回。基本思想是优化首次匹配策略，将对空闲空间的查找操作扩散到整个列表中，避免开头过度碎片化。优点：性能与首次匹配相近。

分离空闲列表

维护多个空闲列表。如果某个应用程序经常申请一种或几种大小的内存空间，则使用一个独立的列表管理这样大小的空间；其余大小的请求交给通用的内存分配程序在通用空闲列表中管理。以 Solaris 的 厚块分配程序（Slab Allocator） 为例：在内核启动时，其为频繁请求的内核对象（如锁与文件系统 inode）创建一些 对象缓存，每个对象缓存分离了特定大小的空闲列表，因此可以快速相应内存的请求与释放操作。若缓存空间耗尽，则向通用内存分配程序申请一些 内存厚块（Slab）；若缓存空间全部处于空闲状态，则通用内存分配程序回收这些内存。除此之外，分配程序还会将列表中的对象保持在预初始化的状态，避免对象频繁创建与销毁带来的开销。

这种方式的好处是在分离出的具有特定大小的空闲列表中不会出现碎片问题，此外这些内存也易于跟踪，因此也易于分配与释放。缺点是为整个系统引入了额外复杂性，此外对于通用分配程序来说查找速度会变慢，导致整个系统缺乏 可拓展性。

伙伴系统

类比树状数组的思想，将整个内存视作大小为 $2^N$ 的空间，随后递归地将空间一分为二，直至刚好可以满足请求的大小（无法继续再分），并将分出的一块空间返回给用户。这样整个内存空间被划分为一颗二叉树，如下图所示：

块被释放需要合并相邻空闲空间时，检查被释放块的兄弟块，如果其空闲，则将其合并成父亲结点代表的块，递归执行以上操作，直到兄弟块正被占用或无法继续合并。

这样做的优点是当我们对这些块进行编制时会发现基于二叉树的良好结构，互为兄弟的结点所代表的块的起始地址只有一位不同，且这一位正代表了两块在整个树中的深度。

缺点是由于划分出的块大小必须为 2 的整数次幂，因此存在 内部碎片 问题。同样的，分配程序如果采用线性查找，速度也很慢。为了解决这一点，更先进的分配程序可能会采用更复杂的数据结构，例如平衡树、伸展树与偏序树，牺牲简单性来换取更好的性能。