分段式内存管理

这是 《Operating System: Three Easy Pieces》 的第 5 篇读书笔记。

上篇笔记 介绍了管理内存的一种简单实现方式,基于 base registerbound register 实现的 虚拟地址翻译、内存管理方式。

这种方式简单直观,但是缺点也是明显的——太浪费内存空间了,每个进程的 堆内存 和 栈内存 之间有很大的空隙是不被使用的,但是还是分配给了物理内存;而且空间利用率不够好,进程未使用的空闲内存不能操作系统 “抢夺” 回来被分配给更多的进程使用。

这篇笔记是有关一种改进的内存管理方式的。

中文名应该翻译做 段式的内存管理 ( segmentation )。

关键点:如何使进程能够获得更大的地址空间,比如说 4 GB。

分段:更一般化的 基址 和 边界

原标题是, Segmentation: Generalized Base and Bound,可能我翻译的有点难以理解。

我这么理解,分段其实是指将内存均分,而更一般化是相对于上篇比较介绍的每个进程有一对独立的基址寄存器和边界寄存器而言的,在分段的含义里,是每个 “段(segment)” 都会有一个固定的边界和开始,而不仅限于某个进程,因而说是 Generalized 的。

分段,这个古老的思想可以追溯到 20 世纪 60 年代(参见笔记结尾处的 ”引用“——《 Program Organization and Record Keeping for Dynamic Storage 》和《 Fact Segmentation 》)。

基本思想非常简单,*与其在 内存管理单元( MMU )保存一对独立的寄存器(基址和边界),不如每个地址空间里逻辑上的段( segment )都保存一对独立的基址和边界寄存器。*

一个 ”段( segment )“ 指的是一段特定长度的、连续的内存地址空间。

在我们一直使用的进程内存地址空间里,如上图,我们划分了 3 个逻辑不同的段:代码段、栈和堆。

操作系统采用段式内存管理方法要做的,就是把这些逻辑上不同的段存放到物理内存中去。

我们先看一个简单的例子,如下图:

我们还注意到,Stack 和 Heap 的大小都很小,而且增长方向也不再是对头了,它们之间也不再是相邻且中间留有大段已分配的空白内存——除了操作系统自身保留的内存之外,一个进程只有使用到了的内存空间被放进了物理内存。

对于 MMU 里的基址和边界寄存器,如果看了下图,可能你就睁大眼睛,说 ”真的如我猜想的那样,它就是这样工作的“。

下面我们来描述下采用分段式内存管理方式的地址翻译过程吧。

假设有个对虚拟地址 100 处的访问(代码段),

  • 首先,硬件会把 代码段的基址( 32 KB )的值和偏移量( 100 )相加,得到 32868 KB
  • 接着,检查本次内存访问是否越界,100 远小于 2 KB,所以本次访问是合法的
  • 发起对物理内存地址 32868 KB 处的访问

我们再看下访问堆内存时的地址翻译过程,假设有个对虚拟地址 4200 出的访问(堆),

  • 首先,如果我们直接把偏移量( 4200 )加上 堆的基址( 34 KB ),得到 39016 的物理,这肯定不是我们想要的
  • 问题出在了 4200 不是正确的偏移量,堆空间在虚拟地址起始于 4 KB 处,也就是 4096,真正的偏移量其实是 104 ( 4200 - 4096 )
  • 我们得到了正确的偏移量,将其加上堆的基址,得到物理地址 34920

另一个疑惑是,如果我们访问了非法的地址呢?这时候就会跳转到操作系统指定的错误处理代码处,控制权交回操作系统,很可能操作系统会终止进程的继续执行。如果是经常写 C/C++ 程序的同学,当发生越界访问时,可能就会经常遇到这个错误: segmentation violation 或者叫 segmentation fault

如何知道我们要访问的是哪个段?

通过对上面地址翻译过程的阐述,我们意识到两个问题

  1. 硬件是如何知道一次地址访问里,段里的偏移是多少的?—— 堆和代码段的偏移量显然不是一样的计算方式
  2. 硬件又是如何确定一个地址想要访问的是哪个段的呢?—— 确定了访问的段的类型可以确定基址寄存器的值是多少

一个通用的方法是把虚拟地址的不同位数赋予不同的含义。

在我们所使用的内存模型中,我们把地址空间划分为三个段,每个地址由 14 位构成。我们把高 2 位的值看作 段 的类型,低 12 位的值是偏移量。

在上图中,高 2 位的值位 01,此时硬件就知道即将要使用 堆 的基址寄存器的值,而低 12 位的值是 0000 0110 1000,也即 16 进制的 0x068,也就说 10 进制的 104,硬件此时就将会直接使用这个偏移量。

下面的伪代码展示了此时地址翻译的基本逻辑:

// get top 2 bits of 14-bit VA
Segment = (VirtualAddress & SEG_MASK) >> SEG_SHIFT
// now get offset
Offset  = VirtualAddress & OFFSET_MASK
if (Offset >= Bounds[Segment])
    RaiseException(PROTECTION_FAULT)
else
    PhysAddr = Base[Segment] + Offset
    Register = AccessMemory(PhysAddr)

在这个例子中,SEG_MASK 等于 0x3000,SEG_SHIFT 等于 12,OFFSET_MASK 等于 0xFFF。

类似的技术被应用于 VAX/VMS 系统中。还有别的技术也可以使用,硬件通过判断地址处于哪个范围来觉得使用哪个段的基址寄存器。

栈的内存如何管理?

目前为止,我们还剩下栈的内存管理方式没有讲。

在上图 Figure-16.2 中,栈的起始地址被分配在物理内存的 28 KB 处,而且向低地址处增长。在图中,它从物理地址 28 KB 处向 26 KB 处增长,对应的虚拟地址空间从 16 KB 向 14 KB 增长。

根据上面对代码段和堆的地址翻译过程的解释,我们可以猜测栈的地址翻译过程可能会与它们不一样。

首先,我们得需要点硬件的支持。除了基址和边界寄存器,硬件需要知道每个逻辑段往哪个方向增长(比如说,可以通过一个位来记录,1 往正方向,0 往反方向)。那么我们的基址和边界寄存器的值就变成了下图:

硬件知道了每个段的增长方向之后,就知道了如果区别对待地翻译虚拟地址了。

我们再来举个例子进行说明。

还是上面那个地址空间模型,假设我们需要访问 15 KB 处的虚拟地址,通过口算我们就能得知对应的物理地址是 27 KB。虚拟地址的二进制是 11 1100 0000 00000x3C00 ),硬件使用高 2 位来判断即将访问的地址属于哪个逻辑段,然后剩下的位代表偏移( 3 KB )。然而我们即将要访问的是栈的地址,它的增长方向是相反的,为了得到正确的偏移量,偏移量必须重新计算。

在上面那个地址空间模型中,一个段是 4 KB,所以正确的偏移应该是 -1 KB( 3 KB - 4 KB)。

所以,将偏移量加上基址寄存器的值,得到 27 KB( 28 KB - 1 KB ),边界寄存器通过检查偏移量的绝对值( 1 KB )判定地址访问没有越界。

支持共享内存

随着分段式内存管理方式的发展,操作系统的设计者意识到他们实际上可以更充分的利用硬件提供的支持。更准确地说,利用硬件的支持,在不同的进程间(不同的独立的内存地址空间)间共享内存,从而节省内存。

特别地是,代码段共享技术,在如今的操作系统中仍然使用。

我们在一个段的一些位置方式一些特殊的标志位,来表明这个段是否可读、可写或者可执行等等。这里翻译叫做 保护位( Protection bit )

设定一个代码段位只读的,那么这个段对应的物理内存就可以在都使用这段代码的不同进程间共享了。不用担心隔离问题,因为每个进程都独占一个程序计数器,每个进程每次访问的时候硬件都根据程序计数器的指示访问这块儿内存,但是只读的访问权限限制了进程只能读取内存的内容而不能修改,因此达到了隔离的目的。

好的,那么上图 Figure-16.4.1 就更新成了下面这样:

我们可以看到,代码段的保护位信息被设置成了可读可执行的,因此这段所对应的内存就可以被映射到多个不同进程的虚拟地址空间中。

有了保护位之后,硬件对虚拟地址的翻译过程除了需要检查是否越界之外,还需要检查对一个的段的操作是否在权限的限制范围之内。

段的划分力度:粗粒度还是细粒度?

大家读到这里不知道有没有点疑惑:有时会我们的分段是指 代码段、堆和栈,但有时候我们的段似乎又是指一个 4 KB 的划分,到底是哪个?

其实都算。按照代码段、堆、栈划分的是粗粒度的划分,它把内存地址切分成了比较大的、稀疏的片段。

然而一些早期的系统(比如说 Multics ),是支持更细粒度、更灵活地段划分的,它包含了很多的更小的*段*。

当然啦,支持更细粒度的段划分需要更多的硬件支持,和存在内存中的分段记录表(可能是一个类似进程页表、操作系统的空闲内存列表之类的数据结构)。

细粒度的段划分有利于更有效的使用内存,空间浪费会相对少一些。

操作系统的支持

为了支持分段分内存管理,操作系统需要做出什么改变呢?
第一个,上下文切换,为每个进程保存和恢复基址、边界寄存器

第二个,管理空闲内存。当一个进程被创建的时候要给它分配物理内存。之前的一篇笔记里,内存都是相同大小的一大块一大块,每个进程占据一大块,现在每个块不一定是相同的大小了。

通常遇到的的问题就是内存中充满了空洞,这样导致的问题前面也有提过,压缩合并之后还能挤出更多的内存的来分配给进程的,但由于没有合并因此不能分配,内存效率使用率不高,也就说通常所说的 外部碎片( external fragmentation )问题。

下图可以看到合并前和合并后的内存空间对比:

在分配的时候寻找内存有很多的算法,

  • best-fit 算法
  • worst-fit 算法
  • first-fit 算法

等等...各有优劣各有试用的地方,比较著名的算法是 伙伴算法(buddy algorithm),有兴趣的可以去搜索相关的论文,Linux 就是使用这个分配算法的。

注意的是,这些著名的算法都不是为了百分之百消除外部碎片而设计的,它们设计的共识是尝试最小化外部碎片带来的影响。

总结( Summary )

分段式的内存管理方式解决了上篇笔记提到的很多问题,可以使得操作系统提供一个更好的内存抽象。分段式内存管理也给我们带来了额外的好处,代码共享。

然而, 变长的分段式内存管理方式也给我们的带来了新的挑战,比如说外部碎片问题,还有更加复杂的内存分配方式,这些我们可以使用更加聪明的算法或者是周期性的压缩内存来减少这些问题带来的影响。

虽然分段式的内存管理方式解决了我们的一些问题,但是还有一些问题依旧可以优化,比如说内部碎片,堆的很多内存依旧没被使用,但是依旧被分配在那儿,也就是说浪费了。

我们需要寻找新的解决办法。

准备好下一章吧。

参考
《 Fact Segmentation 》
《 Program Organization and Record Keeping for Dynamic Storage 》
《 Virtual Memory Management in the VAX/VMS Operating System 》
http://pages.cs.wisc.edu/~remzi/OSTEP/vm-segmentation.pdf

Comments
Write a Comment
  • Jason reply

    写的不错。这本书的作者是我们教授,明天考midterm今天复习的时候意外找到了我们课本的笔记,很有意思hh

  • Farmville coins are used to make experience points and to purchae things for tthe farm. bfffegecdeabdcbf