2022年操作系统设计方案与实现四 .pdf

《2022年操作系统设计方案与实现四 .pdf》由会员分享，可在线阅读，更多相关《2022年操作系统设计方案与实现四 .pdf（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章存储器管理存储器是一种必须仔细管理的重要资源。虽然现在一台普通家用计算机的存储器容量可能是60年代早期全世界最大的计算机IBM 7094的五倍以上，但是程序长度的增长速度和存储器容量的增长一样快。用类似于帕金森定律的话来说： 存储器有多大，程序就会有多长 。在这一章中我们将讨论操作系统是怎样管理存储器的。在理想的情况下，每个程序员都会喜欢的是无穷大、快速并且内容不易变（即掉电后内容不会丢失）的存储器，同时又希望它是是廉价的。但不幸的是当前的技术没有能够提供这样的存储器，因此大部分的计算机都有一个存储器层次结构，它由少量的非常快速、昂贵、易变的的高速缓存（cache），若干兆字节的中等速度

2、、中等价格、易变的主存储器（RAM ），和数百兆或数千兆字节的低速、廉价、不易变的磁盘组成。操作系统的工作就是协调这些存储器的使用。操作系统中管理存储器的部分称为存储管理器，它的任务是跟踪哪些存储器正在被使用、哪些存储器空闲，在进程需要时为它分配存储器，使用完毕后释放存储器，并且在主存无法容纳所有进程时管理主存和磁盘间的交换。在这一章中我们将讨论许多不同的存储器管理方案，从非常简单的到高度复杂的。我们从最简单的存储管理系统开始，然后逐步过渡到更加精密的系统。4.1 基本的内存管理存储管理系统可以分为两类：在运行期间将进程在主存和磁盘之间移动的系统（交换和分页）和不移动的系统。后一种比较简单，因

3、此我们首先讨论。随后在本章的后半部分我们将讨论交换和分页。在本章中读者应该自始至终清醒地认识到：交换和分页在很大程度上是由于缺少足够的主存以同时容纳所有的进程而引入的。随着主存越来越便宜，选择某种存储器管理方案的理由也许会变得过时，除非程序变大的速度比存储器降价的速度还要快。4.1.1 没有交换和分页的单道程序最简单的存储器管理方案是同一时刻只运行一道程序，应用程序和操作系统共享存储器。这种方案的三个变种如图4-1所示。操作系统可以位于主存最低端的随机存取存储器（RAM ）中，如图 4-1(a) 所示；它也可以位于主存最高端的只读存储器（ROM ）中，如图 4-1(b) 所示；还可以让设备驱动

4、程序位于内存高端的ROM 中而让操作系统的其他部分位于低端的 RAM 中，如图 4-1(c) 所示。例如小型的MS-DOS 系统使用的就是最后一种模型。在IBM PC 计算机中，系统位于ROM 中的部分称为基本输入输出系统（BIOS）。图4-1 在一个操作系统一个用户进程时三种简单的内存组织方法，其他方法也是存在的。当这样组织系统时，同一时刻只能有一个进程在存储器中运行。一旦用户输入了一个命令，操作系统就把需要的程序从磁盘拷贝到存储器中并执行它；在进程运行结束后，操作系统显示出一个提示符并等待新的命令。当收到新的命令时它把新的程序装入存储器，覆盖掉原来的程序。4.1.2 固定分区的多道程序虽然

5、单道程序常常用于带有简单操作系统的小型计算机上，但我们往往更加希望同时能有多个进程同时运行。在分时系统中，允许多个进程同时在存储器中，这意味着当一个进程因为等待 I/O 结束而阻塞时，其他的进程可以利用CPU ，因而提高了 CPU 的利用率。即使在个人计算机上，同时运行两个或多个进程也常常是很有用的。实现多道程序的最容易的办法是把主存简单地划分为n个分区（可能不相等），分区的划分可以在系统启动时手工完成。当一个作业到达时，可以把它放到能够容纳它的最小的分区的输入队列中。因为在这种方精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 46 页

6、案中分区大小是固定的，一个分区中未被作业使用的空间就白白浪费掉了。图4-2(a) 所示的就是这种固定分区、各分区有自己独立的输入队列的系统。图4-2 (a)各分区具有独立输入队列固定内存分区。(b) 仅有单个输入队列的固定内存分区。把输入作业排成多个队列时，在大分区的队列为空而小分区的队列为满的情况下，其缺点就变得很明显，如图4-2(a) 中的分区 1和3所示。另一种方法如图4-2(b) 所示，只使用一个队列，当一个分区空闲时，选择最靠近队列头可以被该分区容纳的作业装入其中运行。因为我们不希望为了一个小作业而浪费一个大分区，所以另一个策略是搜索整个输入队列找出该分区能容纳的最大的作业，这种算法

7、认为不值得给小作业一个完整的分区，然而通常我们更加期望给小作业（假设是交互作业）最好的服务，而不是最差的。一个解决方法是至少保留一个小分区，这样就不必为了使小作业运行而为其分配大的分区。另一个方法是采用这样一个规则：一个可运行的作业最多只能够被跳过k次。一个作业每被跳过一次就得一分，当它得到k分时它就不能再被跳过了。这种由操作员在早晨设置好随后就不能再被改变的固定分区的系统曾在IBM大型机的OS/360中使用了许多年，它被称为MFT （具有固定数目任务的多道程序，或OS/MFT ），它易于理解也易于实现：输入作业被送入队列排队直到有合适的分区可用，随后作业被装入分区运行直到它结束。现在只有极少

8、数操作系统，如果还有的话，支持这种模式。重定位和保护多道程序引入了两个必须解决的问题-重定位和保护。从图4-2可以清楚地看出不同的作业将在不同的地址区间运行。在一个程序被链接时（即把主程序、用户编写的例程、库例程结合到同一个地址空间中），链接器必须知道程序将在主存的什么地址开始运行。例如，假设程序的第一条指令是调用在链接器产生的二进制文件中绝对地址为100的一个过程。如果程序被装入分区1，这条指令跳转的目的地址将是绝对地址100，这会造成混乱，因为该地址在操作系统的内部。其实真正应该被调用的地址是100K+100。如果程序被装入分区 2，它就应该去调用200K+100，等等。这就是重定位问题。

9、一个可能的解决方法是在程序装入主存时直接修改指令，装入分区1的程序在每个地址上加100K，装入分区 2的程序在每个地址上加200K，等等。为了在装入时能这样重定位，链接器必须在二进制程序中包含位图或链表，由他们指明那些程序字是需要进行重定位的地址，那些是操作码、常数和其他不能进行重定位的元素。OS/MFT 就是这样工作的，一些微机也是这样工作的。在装入时重定位并没有解决保护问题，一个恶意的程序总可以生成一条新指令并跳转到这条指令执行。因为在这个系统中使用的是绝对地址而不是相对于某个寄存器的地址，没有办法能阻止程序生成读或写主存任何位置的指令。在多用户系统中，我们不希望一个进程读写属于另一个用户

10、的主存空间。IBM采用的保护 360机器的办法是将主存划分为2K字节的块并为每个块分配4位的保护码。PSW 中包含一个 4位的密钥，若运行进程试图对保护码不同于PSW 中密钥的主存进行访问，则由硬件引起一个陷入。因为只有操作系统能够修改保护码和密钥，这种办法能有效地阻止用户进程干涉其他进程或操作系统本身。另一个既针对重定位又针对保护问题的解决方法是在机器中设置两个专门的寄存器，称为基址和界限寄存器。在一个进程被调度到时，它的分区的起始地址被装入基址寄存器，分区的长度被装入界限寄存器。进程产生的每一个地址在访问主存前被自动加上基址寄存器的内容，因此如果基址寄存器是100K，不用修改指令，一条 C

11、ALL 100 指令就被有效地转换为一条 CALL 100K+100指令。指令还被自动地用界限寄存器进行检查以确保他们没有试图访问当前分区以外的地址。基址和界限寄存器受到硬件保护，以防止用户程序修改他们。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 46 页CDC 6600-世界上第一台巨型机-使用了这个方案。用于初期IBM PC的Intel 8088 CPU使用了这个方案的一个较弱的版本-有基址寄存器，但没有界限寄存器。从286开始，采用了一种更好的方案。4.2 交换在批处理系统中，把主存组织为固定的分区是简单而且高效的，每个作业在

12、排到队列头时被装入一个分区，它停留在主存中直到运行完毕。只要有足够的作业能被保持在主存中以使CPU 始终处于忙的状态，那么就没有理由使用任何更加复杂的方案。但在分时系统或面向图形的个人计算机中情形就不同了，有时会没有足够的主存以容纳所有当前活动的进程，多出的进程必须被保存在磁盘上并动态地调入主存运行。在硬件支持下，有两个通用的内存管理方法可以使用。最简单的策略称为交换（swapping ），它把各个进程完整地调入主存，运行一段时间，再放回到磁盘上；另一种策略称为虚拟存储器（virtual memory），它使进程在只有一部分在主存的情况下也能运行。下面我们将先讨论交换系统，在4-3中我们将讨论

13、虚拟存储器。交换系统的操作如图4-3 所示，开始时只有进程A在主存，随后进程B和C被创建或从磁盘上被调入，在图 4-3(d) 中A结束了或被交换到了磁盘上，然后D进入，接着 B离开，最后 E进入。图4-3 内存分配情况随着进程进出内存而变化，阴影表示的区域是未使用的内存。图4-2 所示的固定分区与图4-3 所示的可变分区的主要区别是：在后者中分区的数量、位置、大小随着进程的出入是动态变化的，而在前者中他们是固定不变的。这种可变分区不再受固定分区可能太大或太小的约束，从而提高了主存的利用率，但它也使内存的分配、释放和对各个内存块的跟踪更加复杂。当交换在主存中生成了多个空洞时，可以把所有的进程向下

14、移动至相互靠紧，从而把这些空洞结合成一大块，这种技术称为内存紧缩（memory compaction ）。我们通常不进行这个操作，因为它需要大量的CPU 时间，例如在一个有32M 主存，每微秒可以拷贝16个字节的计算机上把全部内存紧缩一次需要两秒钟。一个值得关心的问题是在一个进程被创建或换进时应该为它分配多大的内存。如果进程创建时的大小是固定的并且不会改变，那么分配是很简单的：完全根据需要的大小进行分配。然而如果进程的数据段可以增长，例如在许多程序设计语言中都允许动态地从堆中分配内存，那么进程一旦试图增长时问题就出现了，如果该进程邻接着一个空洞就可以把这个空洞分配给它；然而如果进程邻接的是另一

15、个进程，则需要增长的进程或者不得不被移动到内存中一个足够大的空洞中去，或者必须把一个或多个进程交换出去以生成一个足够大的空洞。如果一个进程不能在内存中增长并且磁盘上的交换区已经满了，那么这个进程必须等待或被杀死。如果大部分进程在运行时都要增长，那么为了减少进程因为所在的内存区域不够而引起的交换和移动所带来的开销，可以采用的一种方法是：在进程被换进或移动时为其分配一点额外的内存。当然，在进程被换出到磁盘上时应该只交换进程实际使用的内存中的内容，将额外的内存交换出去纯粹是浪费。在图4-4(a) 中我们可以看到一个已经为两个进程分配了增长空间的内存配置。图4-4 (a)为能够增长的数据段预留空间。(

16、b) 为能够增长的数据段和堆栈段预留空间。如果进程有两个可增长的数据部分，例如一个供动态分配和释放的变量使用的作为堆的数据段和一个存放普通局部变量和返回地址的栈段，那么可以使用另一种安排，如图4-4(b)所示。在这个图中我们可以看到所示进程的栈段在进程所占内存的顶端并向下增长，紧接在正文段后面的数据段向上增长，处于这两个段之间的内存，他们都可以使用，如果用完了，则这个进程或者必须被移动到足够大的空洞中，或者交换出内存直到内存中有足够的精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 46 页空间，或者被杀死。4.2.1 使用位图的内存管理

17、动态分配的内存必须由操作系统管理。一般来说有两种方法跟踪内存的使用情况：位图和自由链表。本节和下一节将逐个讨论这两种方法。在使用位图方法时，内存被划分为可能小到几个字或大到几千字节的分配单位，每个分配单位对应于位图中的一位，0表示空闲 1，表示占用（或者反过来）。图4-5表示出了一个内存片段和对应的位图。图4-5 (a)一段有五个进程和三个空洞的内存，刻度表示内存分配的单位，阴影表示空闲区域（在位图中用0表示）。 (b) 对应的位图。 (c) 用列表表示的同样的信息。分配单位的大小是一个重要的设计因素。分配单位越小，位图越大，但是即使分配单位只有4个字节大小， 32位的内存也只需要位图中的1位

18、，32n位的内存只需要 n位的位图，因此位图只占用了 1/33 的内存。如果分配单位选的比较大，需要的位图就比较小，但是如果进程的大小不是分配单位的整数倍，那么最后一个分配单位中相当数量的内存就可能被浪费掉。因为位图的大小仅仅取决于内存和分配单位的大小，它提供了一个简单的使用固定大小内存就能对内存使用情况进行跟踪的方法。它的主要问题是当它决定把一个占k个分配单位的进程调入内存时，内存管理器必须搜索位图以找出一串k个连续的 0。在位图中查找指定长度的连续 0串是一个缓慢的操作（因为串可能跨越字边界）。这是反对使用位图的一个理由。4.2.2 使用链表的内存管理跟踪内存使用的另一个方法是维持一个已分

19、配和空闲的内存段的链表，这里，一个段或者是一个进程，或者是两个进程间的一个空洞。图4-5(a) 的内存可以用图 4-5(c) 所示的段链表来表示。表中的每一个表项都包含下列内容：指明是空洞(H)还是进程 (P) 的标志、开始地址、长度、和指向下一个表项的指针。在这个例子中，段链表是按照地址排序的，这样作的好处是在进程结束或被换出时更新链表十分直观。一个要结束的进程一般有两个邻居（除非它是在内存的最低端或最高端），他们可能是进程也可能是空洞，这导致了图4-6 所示的四种组合。在图4-6(a) 中更新链表需要把 P替换为 H；在图 4-6(b) 和4-6(c) 中两个表项被合并成为一个，链表变短了

20、一个表项；在图 4-6(d) 中三个表项被合并为一个，两个表项被从表中删除。因为结束进程的进程表表项中通常含有指向对应于它的段链表表项的指针，因此这个链表使用双链表可能要比图4-5(c) 所示的单链表更方便，这样更易于找到上一个表项以检查是否可以合并。图4-6 进程 X终止时四种与邻居合并的方式。当进程和空洞按照地址顺序存放在链表中时，好几种算法都可以用来为新创建和换进的进程分配空间，这里我们假设存储管理器知道要分配的内存的大小。最简单的算法是首次适配算法，存储管理器沿着内存段链表搜索直到找到一个足够大的空洞，除非空洞大小和要分配的空间大小刚好一样，否则的话这个空洞将被分为两部分，一部分供进程

21、使用，另一部分是未用的内存。首次适配算法是一种快速的算法，因为它尽可能地少搜索。首次适配的一个较小变形是下次适配，它的工作方式和首次适配相同，区别是每次找到合适的空洞时都记住当时的位置，在下次寻找空洞时从上次结束的地方开始搜索，而不是每次都从头开始。 Bays(1977) 的仿真指出下次适配的性能略低于首次适配。另一个大家熟知的算法是最佳适配算法，它搜索整个链表以找出够用的最小的空洞。最佳适配算法试图找出最接近实际需要的大小的空洞，而不是把一个以后可能会用到的大空洞先使用。作为首次适配和最佳适配算法的例子，让我们再观察图4-5，假如需要一个大小为2的块，首次适配将分配在位置5的空洞，而最佳适配

22、将分配在位置18的空洞。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 46 页由于最佳适配算法每次被调用时都要搜索整个链表，它要比首次适配算法慢，有点出乎意料的是它还会导致比首次适配更多的内存浪费，因为它倾向于生成大量没用的很小的空洞，而总的来说首次适配算法生成的空洞更大。为了避免最接近适配的空洞会分裂出极小空洞的问题，大家可能会想到最差适配，即总是分配最大的空洞，以使分裂出来的空洞比较大从而可以继续使用，但仿真说明最差适配也同样不是一个好主意。如果把进程和空洞放在不同链表中，那么这四个算法的速度都能得到提高，这样他们就能只检查空洞而

23、不是进程。但这种分配速度的提高的一个不可避免的代价就是复杂度提高和内存释放速度变慢，因为一个释放的内存段必须从进程链表中删除并插入空洞链表。如果进程和空洞使用不同的链表，空洞链表可以按照大小排序以提高最佳适配的速度。在最佳适配算法搜索由小到大排列的空洞链表时，当它找到一个合适的空洞时它就知道这个空洞是能容纳这个作业的最小的空洞，因此是最佳的，不需要象在单个链表的情况那样继续进行搜索。当空洞链表按大小排序时，首次适配与最佳适配一样快，而下次适配则毫无意义。在空洞被保存在不同于进程的链表中时我们可以作一个小小的优化：不用单独的数据结构存放空洞链表，取而代之用空洞自己。每个空洞的第一个字可以是空洞大

24、小，第二个字指向下一个空洞，于是图4-5(c) 中三个字加一位 (P/H) 的那些链表结点就不再需要了。还有一种分配算法叫做快速适配，它为一些经常被用到长度的空洞设立单独的链表。例如，它可能有一个n个项的表，这个表的第一个项是指向长度为4K的空洞的链表的表头的指针，第二个项是指向长度为8K的空洞的链表的指针，第三个项指向长度12K的空洞链表，等等。象 21K 这样的空洞既可以放在20K的链表中也可以放在一个专门的存放大小比较特别的空洞的链表中。快速适配算法寻找一个指定大小的空洞是十分迅速的，但它有一个所有将空洞按大小排序的方案所共有的一个缺点，即在一个进程结束或被换出时寻找它的邻接块以查看是否

25、可以合并是非常费时间的。如果不作合并，内存会很快分裂成大量的进程无法使用的小空洞。4.3 虚拟存储器许多年以前人们第一次遇到了太大以至于内存容纳不下的程序，通常采取的解决方法是把程序分割成多个叫做覆盖块的片段，覆盖块0首先运行，在它结束时它将调用另一个覆盖块。有一些覆盖系统非常复杂，允许多个覆盖块同时在内存中。覆盖块存放在磁盘上，在需要时由操作系统动态地换入换出。虽然覆盖块换入换出的实际操作都是由系统完成的，但是必须由程序员把程序分割成片段。把一个大程序分割成小的、模块化的片段是非常费时和枯燥的。不久就有人找到了一个把全部工作都交给计算机的办法。这个方法 (Fotheringham, 1961

26、)被称作虚拟存储器（virtual memory）。虚拟存储器的基本思想是程序、数据、堆栈的总的大小可以超过可用物理存储器的大小，操作系统把程序当前使用的那些部分保留在存储器中，而把其他部分保存在磁盘上。例如一个16M 的程序，通过仔细地选择在各个时刻将哪4M 内容保留在内存中，并在需要时在内存和磁盘间交换程序的片段，那么就可以在一个4M 的机器上运行。虚拟存储器也可以工作在许多程序的片段同时存放在内存的多道程序系统中。当一个程序等待它的一部分被调入时，它是在等待I/O 操作而不能运行，因此CPU 可以象在任何其他多道程序系统中一样，交给另一个进程使用。4.3.1 分页大部分虚拟存储器系统都使

27、用了一种称为分页（paging ）的技术，我们这里将讨论它。在任何一台计算机上，都存在一个程序能够产生的内存地址的集合。当程序执行这样一条指令时：精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 46 页MOVE REG, 1000 它把地址为 1000的内存单元的内容复制到REG 中（或者反过来，这取决于计算机的型号）。地址可以通过索引、基址寄存器、段寄存器和其他方式产生。这些由程序产生的地址被称为虚地址（virtual addresses），他们构成了一个虚地址空间（ virtual address space）。在没有虚拟存储器的计

28、算机上，虚地址被直接送到内存总线上，使具有同样地址的物理存储器字被读写；而在使用虚拟存储器的情况下，虚地址不是被直接送到内存总线上，而是送到内存管理单元(MMU) ，它由一个或一组芯片组成，其功能是把虚地址映射为物理地址，如图4-7所示。图4-7 MMU的位置和功能。图4-8 是一个非常简单的的例子，它演示这个映射如何工作。在这个例子中，我们有一台可以生成 16位地址的计算机，地址变化范围从0到64K，这些地址是虚地址。然而这台计算机只有 32K的物理存储器，因此虽然可以编写64K的程序，他们却不能被完全调入内存运行。在磁盘上必须有一个可以大到64K的程序的完整内核映象，以保证程序片段在需要时

29、能被调入。图4-8 虚地址与物理内存地址之间的关系由页表给出。虚地址空间被划分成称为页（pages）的单位，在物理存储器中对应的单位称为页框（page frames ），页和页框总是同样大小的，在这个例子中是4K，但在现有的系统中常用的页的大小是从512字节到 64K。对应于 64K的虚地址空间和 32K的物理存储器，他们分别包含有 16个虚页和 8个页框。内存和磁盘之间的传输总是以页为单位的。当程序试图访问地址0时，比如使用这条指令：MOVE REG, 0 虚地址 0将被送往 MMU ，MMU 看到虚地址落在页0范围内（ 0到4095），根据它的映射这个页对应的是页框 2（8192到1228

30、7），因此 MMU 把地址变换为 8192并把地址 8192送到总线上。内存板对 MMU 一无所知，它只看到一个对地址8192读或写的请求并且执行它。MMU 从而有效地把所有从 0到4095的虚地址映射到了8192到12287的物理地址。同样地，指令：MOVE REG, 8192 被有效地转换为：MOVE REG, 24576 因为虚地址 8192在虚页 2中并且这个虚页被映射到了物理页框6（物理地址从 24576到28671）。第三个例子，虚地址20500在虚页 5（虚地址 20480到24575）距开头 20字节处，被映射到物理地址12288 + 20 = 12308。通过适当地设置 MM

31、U ，它可以把 16个虚页映射到 8个页框中的任何一个，但是这种能力本身并没有解决虚地址空间比物理存储器大的问题。在图4-8 中我们只有 8个物理页框，于是只有8个虚页被映射到了物理存储器中，其他在图中用叉号表示的页没有被映射。在实际的硬件中，每个虚页都有一个Present/absent位指出该页是否被映射了。在程序试图访问未映射的页时，例如通过下列指令，会发生什么？MOVE REG, 32780 虚页 8（从 32768开始）的第 12个字节所对应的物理地址是什么呢？MMU 注意到这个页没有映射（在图中用叉号表示），于是使CPU 陷入操作系统，这个陷入称为缺页故障。操作系统找到一个很少使用的

32、页框并把它的内容写入磁盘，随后把需引用的页取到刚才释放的页框中，修改映射，然后重新启动引起陷入的指令。例如，假设操作系统决定放弃页框1，那么它将把虚页8装入物理地址 4K，并对 MMU 作两处修改：首先，它要标记虚页1为未映射，以使以后任何对虚地址4K到8K的访问都引起陷入；随后把虚页 8对应表项的叉号改为1，因此在引起陷入的指令重新启动时，它将把虚地精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 46 页址32780映射为物理地址4108。现在让我们看看 MMU 的内部结构以了解它是怎么工作的、以及为什么我们选用的页面大小是2的次幂。

33、在图 4-9 中我们可以看到一个虚地址的例子，虚地址8196（二进制是0010000000000100）用图 4-8所示的 MMU 的映射进行映射，输入的16位虚地址被分为4位的页号和 12位的偏移量， 4位的页号可以表示16个页面， 12位的偏移可以为一页内的全部4096个字节编址。图4-9 在16个4K页的情况下 MMU 的内部操作。页号用作页表的索引，以得出对应于这个虚页的页框号。如果Present/absent位是 0，则将引发一个操作系统的陷入；如果这个位是1，在页表中查到的页框号将被复制到输出寄存器的高三位中，加上输入虚地址中的12位偏移，就构成了15位的物理地址。输出寄存器的内容

34、随即被作为物理地址送到内存总线。4.3.2 页表从理论上来讲，虚地址到物理地址的映射就象我们刚才描述的那样。虚地址被分成虚页号（高位）和偏移（低位）两部分，虚页号被用做页表的索引以找到该虚页对应的页表项，从页表项中可以找到页框号（如果有的话）。随后页框号被拼接到偏移的高位端，形成送往内存的物理地址。页表的目的是把虚页映射为页框。从数学角度而言，页表是一个函数，它的参数是虚页号，结果是物理页框号。通过这个函数可以把虚地址中的虚页域替换成页框域，从而形成物理地址。在这个简单的描述之外，我们还必须面对两个主要问题：1. 页表可能会非常大。2. 地址映射必须十分迅速第一点是因为现代计算机使用的虚地址最

35、少也有32位，在页长为 4K时32位的地址空间有 1百万个页， 64位的地址空间则更要多得多。虚地址空间中的1百万个页需要有 1百万个表项的页表，并且每个进程都需要有自己的页表。第二点是因为虚地址到物理地址的映射在每次内存访问时都要进行。一条典型的指令有一个操作字，通常还有一个内存操作数，因此每条指令都要进行一次、两次或多次的页表引用。假如执行一条指令需要10纳秒，则页表的查找必须在几个纳秒内完成以避免成为一个主要的瓶颈。对大而快速的页映射的需要是计算机构造方式的一个重要限制，这个问题不仅在最高档的计算机中是最重要的，在强调性能/ 价格比的低档机中也是一个重要的问题。在本节和下几节中我们将详细

36、研究页表的设计和已经实际使用的一些解决方法。最简单的设计（至少在理论上）是使用一个由一组快速的硬件寄存器组成的页表，虚页号作为索引，每个虚页一个表项。在启动一个进程时，操作系统把位于主存中的进程页表装入寄存器，在进程运行期间不用因为页表而访问内存。这一方法的优点是直观并且在映射时不需要访问内存，它的一个缺点是非常昂贵（如果页表很大的话），而且在每次进程切换时都要装入位于主存中的页表，这也会降低性能。另外一个极端是把页表全部放在主存中，这时，需要的全部硬件仅仅是一个指向页表起始地址的寄存器，在上下文切换时只要重新装入这个寄存器就可以改变内存映射。当然，它的一个严重缺点是在执行每条指令时都需要一次

37、或多次访问内存读取页表项，因此这个这种方法很少以它最单纯的方式使用，下面我们将研究它一些性能要好得多的变种。多级页表为了避免把庞大的页表始终保存在内存中，许多计算机使用了多级页表，图4-10是一个简单的例子。在图 4-10(a) 中，32位的虚地址划分为 10位的 PT1域、10位的 PT2 域和 12位的偏移。因为偏移是 12位，所以页长是 4K，页面共有 220个。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 46 页图4-10 (a)一个有两个页表域的32位地址。 (b) 二级页表。多级页表的秘密是避免把所有的页表一直保存在内存

38、中，特别是那些不需要的就不应该保留。比如一个需要12兆字节的进程，最低端是4兆程序正文，后面是4兆数据，顶端是 4兆堆栈，在数据顶端上方和堆栈底端之间的上吉（千兆）字节的空洞根本没有使用。让我们看看图 4-10(b) 的例子中二级页表是怎样工作的。在左边是顶级页表，它具有1024个表项，对应于 10位的PT1 域。当一个虚地址被送到MMU 时， MMU 首先抽出虚地址的PT1 域并把它作为访问顶级页表的索引。整个4G 虚地址空间（ 32位）已经被切成 1024块，每块 4兆字节，这 1024个表项中每个表项都表示其中的一块。通过索引得到的顶级页表项包含有二级页表的地址或页框号，顶级页表的表项0

39、指向程序正文的页表、表项1指向数据的页表、表项1023指向堆栈的页表。其他的表项（用阴影表示的）未用。 PT2 域被用作访问选定的二级页表的索引以找到该虚页的页框号。举一个例子，虚地址0 x00403004（十进制 4,206,596 ）位于数据部分 12,292 字节处。它对应的 PT1=1 、PT2=3、偏移 =4。MMU 首先用 PT1作为索引访问顶级页表得到表项1，它对应的地址范围是 4M 到8M ；随后它用 PT2作为索引访问刚刚找到的二级页表并得到表项3，它对应的地址范围是在它的4M 块内的 12288到16383（即绝对地址 4,206,592 到4,210,687 ）。这个表项

40、含有虚地址 0 x00403004所在页的页框号。如果这个页不在内存中，Present/absent位将是 0，一个页面故障将被引发；如果这个页在内存中，从二级页表中得到的页框号将和偏移 (4) 结合构成物理地址并通过总线送到存储器。在图 4-10中值得注意的是虽然地址空间超过一百万个页，实际上只需要四个页表：顶级页表， 0到4M 、4M 到8M 和顶端 4M 的二级页表。顶级页表中有1021个表项的 Present/absent位都被设为 0，使得访问他们时强制产生一个页面故障。如果这种情况发生了，操作系统将注意到进程在试图访问一个不期望被访问的地址并采取适当的行动，比如向进程发出一个信号或

41、杀死进程。在这个例子中各种长度我们选择的都是整的数（正文、数据、堆栈都是4M 长），并且选择PT1与PT2等长，但在实际中其他的值当然也是可能的。图4-10 的二级页表可以扩充为三级、四级或更多级。更多的级别带来了更多的灵活性，但页表超过三级所带来的复杂性是否值得令人怀疑。现在让我们把注意力从页表的总体结构转移到单个页表项的细节上来，表项的结构是与机器密切相关的，但不同机器的表项存储的信息大致相似。在图4-11中我们给出了页表项的样本，不同计算机页表项的大小不一样，但32位是一个一般的尺寸。最重要的域是页框号，毕竟页映射的目的是找到这个值；其次是存在/ 不在 (Present/absent)位

42、，这一位是 1时这个表项是有效的可以被使用，如果是0，表示这个表项对应的虚页现在不在内存中，访问这一位为 0的页会引起一个页面故障。图4-11 一个典型的页表项。保护位指出这个页允许什么样的访问。在最简单的形式下这个域只有一位，0表示读写， 1表示只读。一个更先进的安排是使用三位，各位分别指出是否允许读、写、执行这个页。修改 (Modified)和引用 (Referenced)位跟踪页的使用。在一个页被写入时硬件自动设置修改位，此位在操作系统重新分配页框时是非常有用的，如果一个页已经被修改过（即它是 脏 的），则必须把它写回磁盘，否则只用简单地把它丢弃就可以了，因为它在磁盘上的拷贝仍然是有效的

43、。此位有时也被称为脏(dirty)位，因为这反映了该页的状态。引用位在该页被引用时设置，不管是读还是写。它的值被用来帮助操作系统在发生页面故障时选择淘汰的页，不在使用的页要比在使用的页更适合于被淘汰。这个位在我们即将讨论的好几个页面替换算法中都将扮演重要的角色。最后一位可以禁止该页被缓存，这个特性对那些映射到设备寄存器而不是常规内存的页面是非常重要的。假如操作系统正在紧张地循环等待某个I/O 设备对它刚发出的命令作出响应，保证硬件是不断地从设备中读取而不是读取一个旧的被缓存的拷贝是非常重要的，通精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页

44、，共 46 页过这个位可以禁止缓存。具有独立的I/O 空间而不使用内存映射I/O 的机器不需要这个位。值得注意的是当一个页面不在内存时保存该页的磁盘地址不是页表的一部分，原因很简单，页表只保存硬件把虚地址转换为物理地址时所需要的信息，操作系统在处理页面故障时需要的信息保存在操作系统内部的软件表格中。4.3.3 TLBs-翻译后援存储器 (Translation Lookaside Buffers) 由于页表尺寸较大，因此许多分页方案都只能把它保存在内存中，但这种设计对性能有很大的影响。例如一条把一个寄存器的内容复制到另一个寄存器中指令，在不使用分页时只需要访问内存一次取指令，而在使用分页时需要

45、额外的内存访问去读取页表。因为系统的运行速度一般都是被CPU 从内存中取得指令和数据的速率限制的，在每次访问内存时都要去访问两次页表会使机器的性能降低2/3，这样的系统是没有人会愿意用的。计算机设计者们很早就意识到了这个问题并提出了一个解决方案，这个方案基于这样的观察：大部分程序倾向于对较少的页面进行大量的访问。因此只有一小部分页表项经常被用到，其他的很少被使用。采取的解决方法是为计算机装备一个不需要经过页表就能把虚地址映射成物理地址的小的硬件设备，这个设备叫做TLB ( 翻译后援存储器，Translation Lookaside Buffer)，有时也叫做相联存储器（associative

46、memory），如图 4-12 所示。它通常在 MMU 内部，条目的数量较少，在这个例子中是8个，一般很少超过64个。每个条目包含一个页的信息，主要有虚页号、在页被修改时将被设置的一个位、保护码（读/ 写/ 执行允许）、和页所在的物理页框号，这些域和页表中的域是一一对应的，还有另外一位指出这个条目是否有效。图4-12 一个用于加速分页操作的TLB。生成图 4-12所示的 TLB的一个可能的例子是一个正在执行某个循环的进程，该循环跨越虚页19、20、21，因此这些页面的保护码是读和执行。正在使用的主要数据（比如一个正在被处理的数组）在页面129和130，页 140包含了数组演算中用到的索引。最后

47、，堆栈在页面860和861。现在让我们看一看TLB是怎样工作的，当一个虚地址被送到MMU 翻译时，硬件首先把它和TLB 中的所有条目同时（并行地）进行比较，看它的虚页号是否在TLB 中，如果找到了并且这个访问没有违反保护位，它的页框号将直接从TLB 中取出而不用去查页表。如果虚页号在TLB中但当前指令试图写一个只读的页面，这时将发生一个保护故障，与直接访问页表时相同。有趣的是当虚页号不在TLB 中时会发生什么？如果MMU 发现在 TLB 中没有命中，它将随即进行一次常规的页表查找，然后从TLB 中淘汰一个条目并把它替换为刚刚找到的页表项。因此如果这个页很快会再被用到的话，第二次访问时它就能在T

48、LB 中直接找到。在一个TLB条目被淘汰时，被修改的位被复制回在内存中的页表项，其他的值则已经在那里了。当TLB从页表中装入时，所有的域都从内存中取得。软件 TLB 管理直到现在我们一直假设，每个带有页式虚拟存储器的机器都有能被硬件识别的页表外加一个TLB，在这个设计中TLB 的管理和 TLB故障的处理都完全由MMU 硬件完成，只有一个页不在内存时才会陷入操作系统。在过去，这个假设是对的，但是在一些现代的RISC 机中，包括 MIPS 、Alpha、HP PA，几乎全部的这种页管理工作都是由软件完成的。在这些机器中，TLB 条目是由操作系统显式地装入的，在 TLB没有命中时， MMU 不是到页

49、表中找到并装入需要的页面信息，而是产生一个TLB 故障把问题交给操作系统，操作系统必须找到页面，从TLB 中淘汰一个条目，装入一个新的，然后重新启动产生故障的指令。当然，所有这些都必须用很少几条指令完成，因为TLB 不命中发生的频率远比页面故障大得多。令人惊奇的是，如果TLB的尺寸取一个合理的较大值（比如64个条目）以减少不命中的频精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 46 页率，那么软件管理的TLB效率可能相当高。这里主要的收益是一个简单得多的MMU ，它在CPU 芯片上为高速缓存和其他能提高性能的部件让出了相当大的面积。U

50、hlig 等详细地讨论了软件 TLB管理(1994) 。人们已经使用了很多方法来提高使用软件管理TLB 机器的性能，有一个方法既能减少TLB的不命中率又能减少在TLB不命中确实发生时的开销（Bala 等，1994）。为了减少 TLB的不命中，操作系统有时可以用它的直觉来指出那些页可能将被使用并把他们预装入TLB 中。例如当一个客户进程向位于同一台机器上的服务器进程发出一个RPC 请求时，服务器很可能即将运行。知道了这一点，在客户进程因执行RPC 陷入时，系统就可以找到服务器的代码、数据、堆栈的页面，并在TLB中提前为他们建立映射，以避免TLB 故障的发生。无论是硬件还是软件，处理TLB 不命中