《Operating Systems: Three Easy Pieces》学习笔记(十二) 分段

结合上一篇文章，堆和栈之间有一大块“空闲”空间，如果没被使用，也占用了物理内存。如果虚拟内存地址空间很大，对物理内存也是极大的浪费，回想一下，进程确实有权力拥有这么大的空间，最大可以拥有最大段大小的地址空间，进程完全可以声明自己需要这么大空间，但可能不会使用，操作系统总得给它预留这么多。

分段：泛化的基址/界限

为了降低物理内存浪费，我们对段做细分，原来每个进程对应一个段，现在让每个进程对应三个段，典型的为：代码、栈和堆

之后在 MMU 中给每个逻辑段（segment）引入一对基址和界限寄存器。这样就能分别对这三个段做映射，三个段的顺序和位置完全可以在物理地址空间中随意排列，只要映射到虚拟地址中的位置符合进程结构就行：

如图所示，对比上一篇文章中的只有一个段的情况，只有已用的内存才在物理内存中分配空间，因此可以容纳巨大的地址空间，不过其中还是会包含大量未使用的地址空间（有时又称为稀疏地址空间，sparse address spaces）。

段的访问方式和上篇文章相同，通过基址加偏移的方式:

段	基址	大小
代码	32KB	2KB
堆	34KB	2KB
栈	28KB	2KB

比如访问 100，是在代码段中，物理地址则是 32KB+100=32868，然后判断是否在界限 32KB+2KB 内，合法时发起对物理地址的访问

比如访问 4200，是在堆段中，先找到相对于堆段起始位置偏移量 4200-4096=104，物理地址是 34KB+104=34920

段错误指的是在支持分段的机器上发生了非法的内存访问。越界访问会造成段异常（segmentation violation）或段错误（segmentation fault）

引用段的方式

• 显式（explicit）方式

  就是用虚拟地址的开头几位来标识不同的段，如01表示堆，11表示栈，00表示代码段（不过这样10开头的虚拟地址就被浪费了）。

  // 获取虚拟地址前两位
  Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
  // 获取虚拟地址偏移量
  Offset = VirtualAddress & OFFSET_MASK
  // 越界检查，Bounds是表示每段边界信息的数组
  if (Offset >= Bounds[Segment])
      RaiseException(PROTECTION_FAULT)
  else
      PhysAddr = Base[Segment] + Offset
      Register = AccessMemory(PhysAddr)
  

• 隐式（implicit）方式

  硬件通过地址从哪里产生来确定段。例如，如果地址由程序计数器产生（即它是指令获取），那么地址在代码段。如果基于栈或基址指针，它一定在栈段。其他地址则在堆段

栈的问题

栈的增长方向和代码及堆相反。

除了基址和界限外，硬件还需要知道段的增长方向（用 一位区分，比如 1 代表自小而大增长，0 反之）

假设要访问虚拟地址 15KB，它应该映射到物理地址 27KB。

该虚拟地址的二进制形式是：11 1100 0000 0000（十六进制 0x3C00）。硬件利用前两位（11）来指定段为栈段，但然后我们要处理偏移量 3KB。为了得到正确的反向偏移，我们必须从 3KB 中减去最大的段地址：在这个例子中，段可以是4KB(图上显示是 2KB，假设最大是能到 4KB 的)，因此正确的偏移量是 3KB 减去 4KB，即−1KB。 只要用这个反向偏移量（−1KB）加上基址（28KB），就得到了正确的物理地址 27KB。用户可以进行界限检查，确保反向偏移量的绝对值小于段的大小。

支持共享

要节省内存，有时候在地址空间之间共享（share）某些内存段是有用的

为了支持共享，需要一些额外的硬件支持，这就是保护位（protection bit）。基本为每个段增加了几个位，标识程序是否能够读写该段，或执行其中的代码。通过将代码段标记为只读，同样的代码可以被多个进程共享，而不用担心破坏隔离。虽然每个进程都认为自己独占这块内存，但操作系统秘密地共享了内存，进程不能修改这些内存，所以假象得以保持

比如同一份二进制文件运行多个进程,可以共享代码段

图中代码段的权限是可读和可执行，因此物理内存中的一个段可以映射到多个虚拟地址空间。

有了保护位，前面描述的硬件算法也必须改变。除了检查虚拟地址是否越界，硬件还需要检查特定访问是否允许。如果用户进程试图写入只读段，或从非执行段执行指令，硬件会触发异常，让操作系统来处理出错进程。

分段的颗粒度

粗粒度

比如只分成三个段，代码、栈、堆

细粒度

将段进一步细分。操作系统可以更好地了解哪些段在使用哪些没有，从而可以更高效地利用内存。这需要进一步的硬件支持，如段表，在段表内能保存成千上万段。

操作系统的问题

上下文切换

由于每个进程拥有独立的虚拟地址空间，上下文切换时，段寄存器需要保存和恢复到进程结构中

内存碎片

对段的细分带了了好处：栈和堆之间没有使用的区域就不需要再分配物理内存

但细分后会产生物理内存上的外部碎片（external fragmentation），细小的碎片很难分配给新的段，如左图：

解决方案：

• 紧凑（compact）物理内存，重新安排原有的段

  操作系统先终止运行的进程，将它们的数据复制到连续的内存区域中去，改变它们的段寄存器中的值，指向新的物理地址，从而得到了足够大的连续空闲空间

• 空闲列表管理算法(碎片处理)

  试图保留大的内存块用于分配。相关的算法可能有成百上千种，包括传统的最优匹配（best-fit，从空闲链表中找最接近需要分配空间的空闲块返回）、最坏匹配（worst-fit）、首次匹配（first-fit）以及像伙伴算法（buddy algorithm）这样更复杂的算法

参考

• Operating Systems: Three Easy Pieces 中文版