分段

内部碎片

在上一篇文章中使用单对基址/界限寄存器实现了简单的内存管理。

但可以发现分配给线程的整块内存块中有很大一部分未被利用，例如栈和堆之间的动态增长空间。这些未被使用的空间是线程内部的，无法被其他线程使用，被称为内部碎片 (internal fragmentation)。

分段

很自然的想法：既然如此，就不要使用线程的一整个虚拟地址空间作为分配单位了。

将线程的地址空间按照特定长度与用途分为一个个连续段 (segmentation)：

• 文本段
• 数据段
• 堆段
• 栈段

OS 以段为单位将其分配到物理空间中；为此，MMU 需要对每段维护一对基址/界限寄存器。

分段能很容易的支持内存共享 (memory sharing)：如果两个进程共享代码段，只需要将它们代码段的虚拟地址映射到同一个物理地址即可。

假设 2 与 3 被取消。

段表

每个线程都有一个段表 (segment table)，记录与段有关的信息。

一个段表项将记录对应段的：

• 段号 (segment number)
• 段基址 (segment base)
• 段界限 (segment bound)
• 保护位 (protection bit)：该段的访问权限
• 增长位 (growth bit)：该段的增长方向，1 为由低到高，0 为由高到低
• 有效位 (valid bit)：该段是否有效

地址翻译：一个例子

虚拟空间大小为 16KB，段表如下：

虚拟地址 15 KB 将会被翻译成什么？

• 首先 $16$ KB $=2^{14}$ KB，虚拟地址共有 14 位。$15$ KB 写成二进制是 $11101010011000$。
• 共有 3 段，需要至少 2 位来表示（所以实际上是 4 段，其中 1 段为空），前 2 位 $11$ 是段号。
• 查询段表发现这个地址位于栈段。
• 剩余的 12 位是 offset，一共是 $3$ KB。
• 每段的 max size 是 4K（$16$ K / 4 段）：由于栈向负增长，段内偏移量为 $3-4=-1$ K。
• 物理地址 $=$ 基址 $+$ 段内偏移量 $=28-1=27$ K。

外部碎片

由于作为分配单位的段大小不同，物理空间在不断的线程分配与释放过程中产生了越来越多的空洞；这并非段内的，而是段间的，因此被称为外部碎片 (external fragmentation)。

• 内存合并 (memory coalescing)：线程释放内存块时，合并相邻空闲块
• 内存压缩 (memory compaction)：把所有空闲块合并成一个大的连续段移动至一端

空闲列表维护策略

OS 通过维护空闲列表将空闲块分配给各段。

• 最优适配 (best fit)：满足要求的空闲块之中最小的
• 最劣适配 (worst fit)：满足要求的空闲块之中最大的
• 首次适配 (first fit)：第一个满足要求的空闲块
• 下次适配 (next fit)：首次适配，但从上次分配结束的地方继续搜索