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

第四章储备器治理储备器是一种必需认真治理的重要资源；虽然现在一台一般家用运算机的储备器容量可能是60岁月早期全世界最大的运算机IBM 7094 的五倍以上，但是程序长度的增长速度和储备器容量的增长一样快；用类似于帕金森定律的话来说：" 储备器有多大，程序就会有多长" ；在这一章中我们将争论操作系统是怎样治理储备器的；在抱负的情形下，每个程序员都会喜爱的是无穷大、快速并且内容不易变（即掉电后内容不会丢失）的储备器，同时又期望它是是廉价的；但不幸的是当前的技术没有能够供应这样的储备器，因此大部分的运算机都有一个储备器层次结构，它由少量的特别快速、昂 贵、易变的的高速缓存（ cache），如干兆字节的中等速度、中等价格、易变的主储备器（RAM），和数百兆或数千兆字节的低速、廉价、不易变的磁盘组成；操作系统的工作就是和谐这些储备器的使用；操作系统中治理储备器的部分称为储备治理器，它的任务是跟踪哪些储备器正在被使用、哪些储备器闲暇，在进程需要时为它安排储备器，使用完毕后释放储备器，并且在主存无法容纳全部进程时治理主存和磁盘间的交换；在这一章中我们将争论很多不同的储备器治理方案，从特别简洁的到高度复杂的；我们从最简洁的储备治理系统开头，然后逐步过渡到更加精密的系统；4.1 基本的内存治理储备治理系统可以分为两类：在运行期间将进程在主存和磁盘之间移动的系统（交换和分页）和不移动的系统；后一种比较简洁，因此我们第一争论；随后在本章的后半部分我们将争论交换和分页；在本章中读者应当自始至终清醒地熟识到：交换和分页在很大程度上是由于缺少足够的主存以同时容纳全部的进程而引入的；随着主存越来越廉价，选择某种储备器治理方案的理由或许会变得过时，除非程序变大的速度比储备器降价的速度仍要 快；4.1.1 没有交换和分页的单道程序最简洁的储备器治理方案是同一时刻只运行一道程序，应用程序和操作系统共享储备器；这种方案的三个变种如图 4-1 所示；操作系统可以位于主存最低端的随机存取储备器（RAM）中，如图 4-1a所示；它也可以位于主存最高端的只读储备器（ROM）中，如图 4-1b 所示；仍可以让设备驱动程序位于内存高端的ROM中而让操作系统的其他部分位于低 端的 RAM中，如图 4-1c所示；例如小型的 MS-DO系S 统使用的就是最终一种模型；在IBM PC运算机中，系统位于ROM中的部分称为基本输入输出系统（BIOS）；图4-1在一个操作系统一个用户进程时三种简洁的内存组织方法，其他方法也是存在的；当这样组织系统时，同一时刻只能有一个进程在储备器中运行；一旦用户输入了一个命 令，操作系统就把需要的程序从磁盘拷贝到储备器中并执行它；在进程运行终止后，操作系统显示出一个提示符并等待新的命令；当收到新的命令时它把新的程序装入储备器，掩盖掉原先的程序；4.1.2 固定分区的多道程序虽然单道程序常常用于带有简洁操作系统的小型运算机上，但我们往往更加期望同时能有多个进程同时运行；在分时系统中，答应多个进程同时在储备器中，这意味着当一个进程由于等待 I/O 终止而堵塞时，其他的进程可以利用CPU，因而提高了 CPU的利用率；即使在个人运算机上，同时运行两个或多个进程也常常是很有用的；实现多道程序的最简洁的方法是把主存简洁地划分为n个分区（可能不相等），分区的划分可以在系统启动时手工完成；当一个作业到达时，可以把它放到能够容纳它的最小的分区的输入队列中；由于在这种方案中分区大小是固定的，一个分区中未被作业使用的空间就白白铺张掉了；图4-2a 所示的就是这种固定分区、各分区有自己独立的输入队列的系统；图4-2 a各分区具有独立输入队列固定内存分区；b 仅有单个输入队列的固定内存分区；把输入作业排成多个队列时，在大分区的队列为空而小分区的队列为满的情形下，其缺点就变得很明显，如图 4-2a中的分区 1和3所示；另一种方法如图 4-2b 所示，只使用一个队列，当一个分区闲暇时，选择最靠近队列头可以被该分区容纳的作业装入其中运行；因为我们不期望为了一个小作业而铺张一个大分区，所以另一个策略是搜寻整个输入队列找出该分区能容纳的最大的作业，这种算法认为不值得给小作业一个完整的分区，然而通常我们更加期望给小作业（假设是交互作业）最好的服务，而不是最差的；一个解决方法是至少保留一个小分区，这样就不必为了使小作业运行而为其安排大的分区；另一个方法是采纳这样一个规章：一个可运行的作业最多只能够被跳过k次；一个作业每被跳过一次就得一分，当它得到 k分时它就不能再被跳过了；这种由操作员在早晨设置好随后就不能再被转变的固定分区的系统曾在IBM大型机的OS/360中使用了很多年，它被称为 MFT（具有固定数目任务的多道程序，或OS/MFT），它易于懂得也易于实现：输入作业被送入队列排队直到有合适的分区可用，随后作业被装入分区运行直到它终止；现在只有极少数操作系统，假如仍有的话，支持这种模式；重定位和爱护多道程序引入了两个必需解决的问题- 重定位和爱护；从图4-2 可以清晰地看出不同的作业将在不同的地址区间运行；在一个程序被链接时（即把主程序、用户编写的例程、库例程结合到同一个地址空间中），链接器必需知道程序将在主存的什么地址开头运行；例如，假设程序的第一条指令是调用在链接器产生的二进制文件中确定地址为100的一个过程；假如程序被装入分区1，这条指令跳转的目的地址将是确定地址100，这会造成混 乱，由于该地址在操作系统的内部；其实真正应当被调用的地址是100K+100；假如程序被装入分区 2，它就应当去调用 200K+100，等等；这就是重定位问题；一个可能的解决方法是在程序装入主存时直接修改指令，装入分区1的程序在每个地址上加100K，装入分区 2的程序在每个地址上加 200K，等等；为了在装入时能这样重定位，链接器必需在二进制程序中包含位图或链表，由他们指明那些程序字是需要进行重定位的地址，那些是操作码、常数和其他不能进行重定位的元素；OS/MFT就是这样工作的，一些微机也是这样工作的；在装入时重定位并没有解决爱护问题，一个恶意的程序总可以生成一条新指令并跳转到这条指令执行；由于在这个系统中使用的是确定地址而不是相对于某个寄存器的地址，没有方法能阻挡程序生成读或写主存任何位置的指令；在多用户系统中，我们不期望一个进程读写属于另一个用户的主存空间；IBM采纳的爱护 360机器的方法是将主存划分为 2K字节的块并为每个块安排 4位的爱护码；PSW中包含一个 4位的密钥，如运行进程试图对爱护码不同于PSW中密钥的主存进行拜访，就由硬件引起一个陷入；由于只有操作系统能够修改爱护码和密钥，这种方法能有效地阻止用户进程干涉其他进程或操作系统本身；另一个既针对重定位又针对爱护问题的解决方法是在机器中设置两个特地的寄存器，称为基址和界限寄存器；在一个进程被调度到时，它的分区的起始地址被装入基址寄存器，分区的长度被装入界限寄存器；进程产生的每一个地址在拜访主存前被自动加上基址寄存器的内容，因此假如基址寄存器是100K，不用修改指令，一条CALL 100指令就被有效地转换为一条 CALL 100K+100指令；指令仍被自动地用界限寄存器进行检查以确保他们没有试图拜访当前分区以外的地址；基址和界限寄存器受到硬件爱护，以防止用户程序修改他 们；CDC 6600-世界上第一台巨型机- 使用了这个方案；用于初期IBM PC的Intel 8088 CPU使用了这个方案的一个较弱的版本- 有基址寄存器，但没有界限寄存器；从286开头，采纳了一种更好的方案；4.2 交换在批处理系统中，把主存组织为固定的分区是简洁而且高效的，每个作业在排到队列头时被装入一个分区，它停留在主存中直到运行完毕；只要有足够的作业能被保持在主存中以使CPU始终处于忙的状态，那么就没有理由使用任何更加复杂的方案；但在分时系统或面对图形的个人运算机中情形就不同了，有时会没有足够的主存以容纳所有当前活动的进程，多出的进程必需被储存在磁盘上并动态地调入主存运行；在硬件支持下，有两个通用的内存治理方法可以使用；最简洁的策略称为交换（swapping ），它把各个进程完整地调入主存，运行一段时间，再放回到磁盘上；另一种策略称为虚拟储备器（ virtual memory），它使进程在只有一部分在主存的情形下也能运行；下面我们将先争论交换系统，在4-3 中我们将争论虚拟储备器；交换系统的操作如图 4-3 所示，开头时只有进程 A在主存，随后进程 B和C被创建或从磁盘上被调入，在图 4-3d 中A终止了或被交换到了磁盘上，然后D进入，接着 B离开，最终 E进入；图4-3内存安排情形随着进程进出内存而变化，阴影表示的区域是未使用的内存；图4-2 所示的固定分区与图 4-3 所示的可变分区的主要区分是：在后者中分区的数量、位置、大小随着进程的出入是动态变化的，而在前者中他们是固定不变的；这种可变分区不再受固定分区可能太大或太小的约束，从而提高了主存的利用率，但它也使内存的安排、释放和对各个内存块的跟踪更加复杂；当交换在主存中生成了多个空洞时，可以把全部的进程向下移动至相互靠紧，从而把这些空洞结合成一大块，这种技术称为内存紧缩（memory compaction ）；我们通常不进行这个操作，由于它需要大量的CPU时间，例如在一个有32M主存，每微秒可以拷贝 16个字节的运算机上把全部内存紧缩一次需要两秒钟；一个值得关怀的问题是在一个进程被创建或换进时应当为它安排多大的内存；假如进程创建时的大小是固定的并且不会转变，那么安排是很简洁的：完全依据需要的大小进行分 配；然而假如进程的数据段可以增长，例如在很多程序设计语言中都答应动态地从堆中安排内存，那么进程一旦试图增长时问题就显现了，假如该进程邻接着一个空洞就可以把这个空洞安排给它；然而假如进程邻接的是另一个进程，就需要增长的进程或者不得不被移动到内存中一个足够大的空洞中去，或者必需把一个或多个进程交换出去以生成一个足够大的空洞；假如一个进程不能在内存中增长并且磁盘上的交换区已经满了，那么这个进程必需等待或被杀死；假如大部分进程在运行时都要增长，那么为了削减进程由于所在的内存区域不够而引起的交换和移动所带来的开销，可以采纳的一种方法是：在进程被换进或移动时为其安排一点额外的内存；当然，在进程被换出到磁盘上时应当只交换进程实际使用的内存中的内容，将额外的内存交换出去纯粹是铺张；在图4-4a 中我们可以看到一个已经为两个进程安排了增长空间的内存配置；图4-4 a为能够增长的数据段预留空间；b 为能够增长的数据段和堆栈段预留空间；假如进程有两个可增长的数据部分，例如一个供动态安排和释放的变量使用的作为堆的数据段和一个存放一般局部变量和返回地址的栈段，那么可以使用另一种支配，如图4-4b所示；在这个图中我们可以看到所示进程的栈段在进程所占内存的顶端并向下增长，紧接在正文段后面的数据段向上增长，处于这两个段之间的内存，他们都可以使用，假如用完了，就这个进程或者必需被移动到足够大的空洞中，或者交换出内存直到内存中有足够的空间，或者被杀死；4.2.1 使用位图的内存治理动态安排的内存必需由操作系统治理；一般来说有两种方法跟踪内存的使用情形：位图和自由链表；本节和下一节将逐个争论这两种方法；在使用位图方法时，内存被划分为可能小到几个字或大到几千字节的安排单位，每个安排单位对应于位图中的一位，0表示闲暇 1，表示占用（或者反过来）；图4-5 表示出了一个内存片段和对应的位图；图4-5 a一段有五个进程和三个空洞的内存，刻度表示内存安排的单位，阴影表示闲暇区域（在位图中用 0表示）； b 对应的位图； c 用列表表示的同样的信息；安排单位的大小是一个重要的设计因素；安排单位越小，位图越大，但是即使安排单位只有4个字节大小， 32位的内存也只需要位图中的 1位， 32n位的内存只需要 n位的位图，因此位图只占用了 1/33 的内存；假如安排单位选的比较大，需要的位图就比较小，但是假如进程的大小不是安排单位的整数倍，那么最终一个安排单位中相当数量的内存就可能被铺张掉；由于位图的大小仅仅取决于内存和安排单位的大小，它供应了一个简洁的使用固定大小内存就能对内存使用情形进行跟踪的方法；它的主要问题是当它打算把一个占 k个安排单位的进程调入内存时，内存治理器必需搜寻位图以找出一串 k个连续的 0；在位图中查找指定长度的连续 0串是一个缓慢的操作（由于串可能跨过字边界）；这是反对使用位图的一个理由；4.2.2 使用链表的内存治理跟踪内存使用的另一个方法是维护一个已安排和闲暇的内存段的链表，这里，一个段或者是一个进程，或者是两个进程间的一个空洞；图 4-5a 的内存可以用图 4-5c 所示的段链表来表示；表中的每一个表项都包含以下内容：指明是空洞 H 仍是进程 P 的标志、开头地址、长度、和指向下一个表项的指针；在这个例子中，段链表是依据地址排序的，这样作的好处是在进程终止或被换出时更新链表特别直观；一个要终止的进程一般有两个邻居（除非它是在内存的最低端或最高端），他们可能是进程也可能是空洞，这导致了图4-6 所示的四种组合；在图 4-6a 中更新链表需要把 P替换为 H；在图 4-6b 和4-6c中两个表项被合并成为一个，链表变短了一个表项；在图 4-6d 中三个表项被合并为一个，两个表项被从表中删除；由于终止进程的进程表表项中通常含有指向对应于它的段链表表项的指针，因此这个链表使用双链表可能要比图4-5c所示的单链表更便利，这样更易于找到上一个表项以检查是否可以合并；图4-6进程 X终止时四种与邻居合并的方式；当进程和空洞依据地址次序存放在链表中时，好几种算法都可以用来为新创建和换进的进程安排空间，这里我们假设储备治理器知道要安排的内存的大小；最简洁的算法是首次适配算法，储备治理器沿着内存段链表搜寻直到找到一个足够大的空洞，除非空洞大小和要安排的空间大小刚好一样，否就的话这个空洞将被分为两部分，一部分供进程使用，另一部分是未用的内存；首次适配算法是一种快速的算法，由于它尽可能地少搜寻；首次适配的一个较小变形是下次适配，它的工作方式和首次适配相同，区分是每次找到合适的空洞时都记住当时的位置，在下次查找空洞时从上次终止的地方开头搜寻，而不是每次都从头开头； Bays1977 的仿真指出下次适配的性能略低于首次适配；另一个大家熟知的算法是正确适配算法，它搜寻整个链表以找出够用的最小的空洞；正确适配算法试图找出最接近实际需要的大小的空洞，而不是把一个以后可能会用到的大空洞先使用；作为首次适配和正确适配算法的例子，让我们再观看图 4-5 ，假如需要一个大小为 2的块，首次适配将安排在位置 5的空洞，而正确适配将安排在位置 18的空洞；由于正确适配算法每次被调用时都要搜寻整个链表，它要比首次适配算法慢，有点出乎意料的是它仍会导致比首次适配更多的内存铺张，由于它倾向于生成大量没用的很小的空 洞，而总的来说首次适配算法生成的空洞更大；为了防止最接近适配的空洞会分裂出微小空洞的问题，大家可能会想到最差适配，即总是安排最大的空洞，以使分裂出来的空洞比较大从而可以连续使用，但仿真说明最差适配也同样不是一个好想法；假如把进程和空洞放在不同链表中，那么这四个算法的速度都能得到提高，这样他们就能只检查空洞而不是进程；但这种安排速度的提高的一个不行防止的代价就是复杂度提高和内存释放速度变慢，由于一个释放的内存段必需从进程链表中删除并插入空洞链表；假如进程和空洞使用不同的链表，空洞链表可以依据大小排序以提高正确适配的速度；在正确适配算法搜寻由小到大排列的空洞链表时，当它找到一个合适的空洞时它就知道这个空洞是能容纳这个作业的最小的空洞，因此是正确的，不需要象在单个链表的情形那样连续进行搜寻；当空洞链表按大小排序时，首次适配与正确适配一样快，而下次适配就毫无意义；在空洞被储存在不同于进程的链表中时我们可以作一个小小的优化：不用单独的数据结构存放空洞链表，取而代之用空洞自己；每个空洞的第一个字可以是空洞大小，其次个字指向下一个空洞，于是图 4-5c 中三个字加一位 P/H 的那些链表结点就不再需要了；仍有一种安排算法叫做快速适配，它为一些常常被用到长度的空洞设立单独的链表；例如，它可能有一个 n个项的表，这个表的第一个项是指向长度为4K的空洞的链表的表头的指针，其次个项是指向长度为8K的空洞的链表的指针，第三个项指向长度12K的空洞链表，等等；象 21K这样的空洞既可以放在 20K的链表中也可以放在一个特地的存放大小比较特殊的空洞的链表中；快速适配算法查找一个指定大小的空洞是特别快速的，但它有一个全部将空洞按大小排序的方案所共有的一个缺点，即在一个进程终止或被换出时查找它的邻接块以查看是否可以合并是特别费时间的；假如不作合并，内存会很快分裂成大量的进程无法使用的小空洞；4.3 虚拟储备器很多年以前人们第一次遇到了太大以至于内存容纳不下的程序，通常实行的解决方法是把 程序分割成多个叫做掩盖块的片段，掩盖块0第一运行，在它终止时它将调用另一个掩盖块；有一些掩盖系统特别复杂，答应多个掩盖块同时在内存中；掩盖块存放在磁盘上，在 需要时由操作系统动态地换入换出；虽然掩盖块换入换出的实际操作都是由系统完成的，但是必需由程序员把程序分割成片 段；把一个大程序分割成小的、模块化的片段是特别费时和枯燥的；不久就有人找到了一个把全部工作都交给运算机的方法；这个方法 Fotheringham, 1961被称作虚拟储备器（ virtual memory）；虚拟储备器的基本思想是程序、数据、堆栈的总的大小可以超过可用物理储备器的大小，操作系统把程序当前使用的那些部分保留在储备器中，而把其他部分储存在磁盘上；例如一个16M的程序，通过认真地选择在各个时刻将哪4M内容保留在内存中，并在需要时在内存和磁盘间交换程序的片段，那么就可以在一个4M的机器上运行；虚拟储备器也可以工作在很多程序的片段同时存放在内存的多道程序系统中；当一个程序等待它的一部分被调入时，它是在等待I/O 操作而不能运行，因此 CPU可以象在任何其他多道程序系统中一样，交给另一个进程使用；4.3.1 分页大部分虚拟储备器系统都使用了一种称为分页（paging ）的技术，我们这里将争论它；在任何一台运算机上，都存在一个程序能够产生的内存地址的集合；当程序执行这样一条指令时：MOVE REG, 1000它把地址为 1000的内存单元的内容复制到 REG中（或者反过来，这取决于运算机的型号）；地址可以通过索引、基址寄存器、段寄存器和其他方式产生；这些由程序产生的地址被称为虚地址（virtual addresses），他们构成了一个虚地址空间（ virtual address space）；在没有虚拟储备器的运算机上，虚地址被直接送到内存总线上，使具有同样地址的物理储备器字被读写；而在使用虚拟储备器的情形下，虚地址不是被直接送到内存总线上，而是送到内存治理单元MMU，它由一个或一组芯片组成， 其功能是把虚地址映射为物理地址，如图4-7 所示；图4-7 MMU的位置和功能；图4-8 是一个特别简洁的的例子，它演示这个映射如何工作；在这个例子中，我们有一台可以生成 16位地址的运算机，地址变化范畴从0到64K，这些地址是虚地址；然而这台运算机只有 32K的物理储备器，因此虽然可以编写64K的程序，他们却不能被完全调入内存运 行；在磁盘上必需有一个可以大到64K的程序的完整内核映象，以保证程序片段在需要时 能被调入；图4-8虚地址与物理内存地址之间的关系由页表给出；虚地址空间被划分成称为页（pages）的单位，在物理储备器中对应的单位称为页框（page frames ），页和页框总是同样大小的，在这个例子中是4K，但在现有的系统中常用的页的大小是从 512字节到 64K；对应于 64K的虚地址空间和 32K的物理储备器，他们分别包含有 16个虚页和 8个页框；内存和磁盘之间的传输总是以页为单位的；当程序试图拜访地址 0时，比如使用这条指令：MOVE REG, 0虚地址 0将被送往 MMU， MM看U 到虚地址落在页 0范畴内（ 0到4095），依据它的映射这个页 对应的是页框 2（8192到12287），因此 MMU把地址变换为 8192并把地址 8192送到总线上；内存板对 MM一U 无所知，它只看到一个对地址8192读或写的恳求并且执行它；MM从U 而有效地把全部从 0到4095的虚地址映射到了 8192到12287的物理地址；同样地，指令：MOVE REG, 8192被有效地转换为：MOVE REG, 24576由于虚地址 8192在虚页 2中并且这个虚页被映射到了物理页框6（物理地址从 24576到28671）；第三个例子，虚地址 20500在虚页 5（虚地址 20480到24575）距开头 20字节处， 被映射到物理地址 12288 + 20 = 12308；通过适当地设置 MMU，它可以把 16个虚页映射到 8个页框中的任何一个，但是这种才能本身并没有解决虚地址空间比物理储备器大的问题；在图4-8 中我们只有 8个物理页框，于是只有8个虚页被映射到了物理储备器中，其他在图中用叉号表示的页没有被映射；在实际的硬件中，每个虚页都有一个Present/absent位指出该页是否被映射了；在程序试图拜访未映射的页时，例如通过以下指令，会发生什么？MOVE REG, 32780虚页 8（从 32768开头）的第 12个字节所对应的物理地址是什么呢？MMU留意到这个页没有映射（在图中用叉号表示），于是使CPU陷入操作系统，这个陷入称为缺页故障；操作系 统找到一个很少使用的页框并把它的内容写入磁盘，随后把需引用的页取到刚才释放的页框中，修改映射，然后重新启动引起陷入的指令；例如，假设操作系统打算舍弃页框1，那么它将把虚页 8装入物理地址 4K，并对 MMU作两处修改：第一，它要标记虚页1为未映射，以使以后任何对虚地址4K到8K的拜访都引起陷 入；随后把虚页 8对应表项的叉号改为1，因此在引起陷入的指令重新启动时，它将把虚地址32780映射为物理地址 4108；现在让我们看看 MMU的内部结构以明白它是怎么工作的、以及为什么我们选用的页面大小是2的次幂；在图 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位的物理地址；输出寄存器的内容立刻被作为物理地址送到内存总线；4.3.2 页表从理论上来讲，虚地址到物理地址的映射就象我们刚才描述的那样；虚地址被分成虚页号（高位）和偏移（低位）两部分，虚页号被用做页表的索引以找到该虚页对应的页表项， 从页表项中可以找到页框号（假如有的话）；随后页框号被拼接到偏移的高位端，形成送往内存的物理地址；页表的目的是把虚页映射为页框；从数学角度而言，页表是一个函数，它的参数是虚页号，结果是物理页框号；通过这个函数可以把虚地址中的虚页域替换成页框域，从而形成物理地址；在这个简洁的描述之外，我们仍必需面对两个主要问题：1. 页表可能会特别大；2. 地址映射必需特别快速第一点是由于现代运算机使用的虚地址最少也有 32位，在页长为 4K时32位的地址空间有 1 百万个页， 64位的地址空间就更要多得多；虚地址空间中的 1百万个页需要有 1百万个表项的页表，并且每个进程都需要有自己的页表；其次点是由于虚地址到物理地址的映射在每次内存拜访时都要进行；一条典型的指令有一 个操作字，通常仍有一个内存操作数，因此每条指令都要进行一次、两次或多次的页表引 用；假如执行一条指令需要10纳秒，就页表的查找必需在几个纳秒内完成以防止成为一个主要的瓶颈；对大而快速的页映射的需要是运算机构造方式的一个重要限制，这个问题不仅在最高档的 运算机中是最重要的，在强调性能/ 价格比的低档机中也是一个重要的问题；在本节和下几节中我们将具体争论页表的设计和已经实际使用的一些解决方法；最简洁的设计（至少在理论上）是使用一个由一组快速的硬件寄存器组成的页表，虚页号作为索引，每个虚页一个表项；在启动一个进程时，操作系统把位于主存中的进程页表装入寄存器，在进程运行期间不用由于页表而拜访内存；这一方法的优点是直观并且在映射时不需要拜访内存，它的一个缺点是特别昂贵（假如页表很大的话），而且在每次进程切换时都要装入位于主存中的页表，这也会降低性能；另外一个极端是把页表全部放在主存中，这时，需要的全部硬件仅仅是一个指向页表起始地址的寄存器，在上下文切换时只要重新装入这个寄存器就可以转变内存映射；当然，它的一个严峻缺点是在执行每条指令时都需要一次或多次拜访内存读取页表项，因此这个这种方法很少以它最单纯的方式使用，下面我们将争论它一些性能要好得多的变种；多级页表为了防止把巨大的页表始终储存在内存中，很多运算机使用了多级页表，图4-10 是一个简洁的例子；在图 4-10a 中， 32位的虚地址划分为 10位的 PT1域、 10位的 PT2域和 12位的偏移；由于偏移是 12位，所以页长是 4K，页面共有 220个；图4-10 a一个有两个页表域的32位地址； b 二级页表；多级页表的隐秘是防止把全部的页表始终储存在内存中，特殊是那些不需要的就不应当保留；比如一个需要 12兆字节的进程，最低端是 4兆程序正文，后面是4兆数据，顶端是 4兆堆栈，在数据顶端上方和堆栈底端之间的上吉（千兆）字节的空洞根本没有使用；让我们看看图 4-10b 的例子中二级页表是怎样工作的；在左边是顶级页表，它具有1024个表项，对应于 10位的 PT1域；当一个虚地址被送到 MMU时， MM首U 先抽出虚地址的 PT1域并把它作为拜访顶级页表的索引；整个4G虚地址空间（ 32位）已经被切成 1024块，每块 4兆字节，这 1024个表项中每个表项都表示其中的一块；通过索引得到的顶级页表项包含有二级页表的地址或页框号，顶级页表的表项0指向程序正文的页表、表项 1指向数据的页表、表项 1023指向堆栈的页表；其他的表项（用阴影表示的）未用； PT2域被用作拜访选定的二级页表的索引以找到该虚页的页框号；举一个例子，虚地址 0x00403004（十进制 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 ）；这个表项含有虚地址 0x00403004所在页的页框号；假如这个页不在内存中，Present/absent位将是 0，一个页面故障将被引发；假如这个页在内存中，从二级页表中得到的页框号将和偏移 4 结合构成物理地址并通过总线送到储备器；在图 4-10 中值得留意的是虽然地址空间超过一百万个页，实际上只需要四个页表：顶级页表， 0到4M、4M到8M和顶端 4M的二级页表；顶级页表中有1021个表项的 Present/absent位都被设为 0，使得拜访他们时强制产生一个页面故障；假如这种情形发生了，操作系统将留意到进程在试图拜访一个不期望被拜访的地址并实行适当的行动，比如向进程发出一个信号或杀死进程；在这个例子中各种长度我们选择的都是整的数（正文、数据、堆栈都是4M长），并且选择 PT1与PT2等长，但在实际中其他的值当然也是可能的；图4-10 的二级页表可以扩充为三级、四级或更多级；更多的级别带来了更多的敏捷性，但页表超过三级所带来的复杂性是否值得令人怀疑；现在让我们把留意力从页表的总体结构转移到单个页表项的细节上来，表项的结构是与机器亲密相关的，但不同机器的表项储备的信息大致相像；在图4-11 中我们给出了页表项的样本，不同运算机页表项的大小不一样，但32位是一个一般的尺寸；最重要的域是页框号，究竟页映射的目的是找到这个值；其次是存在/ 不在 Present/absent位，这一位是 1时这个表项是有效的可以被使用，假如是0，表示这个表项对应的虚页现在不在内存中， 拜访这一位为 0的页会引起一个页面故障；图4-11一个典型的页表项；爱护位指出这个页答应什么样的拜访；在最简洁的形式下这个域只有一位，0表示读写， 1表示只读；一个更先进的支配是使用三位，各位分别指出是否答应读、写、执行这个页； 修改 Modified和引用 Referenced位跟踪页的使用；在一个页被写入时硬件自动设置修改位，此位在操作系统重新安排页框时是特别有用的，假如一个页已经被修改过（即它是" 脏" 的），就必需把它写回磁盘，否就只用简洁地把它丢弃就可以了，由于它在磁盘上的拷贝仍旧是有效的；此位有时也被称为脏dirty位，由于这反映了该页的状态； 引用位在该页被引用时设置，不管是读仍是写；它的值被用来帮忙操作系统在发生页面故障时选择剔除的页，不在使用的页要比在使用的页更适合于被剔除；这个位在我们即将争论的好几个页面替换算法中都将扮演重要的角色；最终一位可以禁止该页被缓存，这个特性对那些映射到设备寄存器而不是常规内存的页面是特别重要的；假如操作系统正在紧急地循环等待某个I/O 设备对它刚发出的命令作出响应，保证硬件是不断地从设备中读取而不是读取一个旧的被缓存的拷贝是特别重要的，通过这个位可以禁止缓存；具有独立的I/O 空间而不使用内存映射 I/O 的机器不需要这个位；值得留意的是当一个页面不在内存时储存该页的磁盘地址不是页表的一部分，缘由很简单，页表只储存硬件把虚地址转换为物理地址时所需要的信息，操作系统在处理页面故障时需要的信息储存在操作系统内部的软件表格中；4.3.3 TLBs-翻译后援储备器 Translation Lookaside Buffers由于页表尺寸较大，因此很多分页方案都只能把它储存在内存中，但这种设计对性能有很大的影响；例如一条把一个寄存器的内容复制到另一个寄存器中指令，在不使用分页时只需要拜访内存一次取指令，而在使用分页时需要额外的内存拜访去读取页表；由于系统的运行速度一般都是被 CPU从内存中取得指令和数据的速率限制的，在每次拜访内存时都要去拜访两次页表会使机器的性能降低2/3 ，这样的系统是没有人会情愿用的；运算机设计者们很早就意识到了这个问题并提出了一个解决方案，这个方案基于这样的观看：大部分程序倾向于对较少的页面进行大量的拜访；因此只有一小部分页表项常常被用到，其他的很少被使用；实行的解决方法是为运算机装备一个不需要经过页表就能把虚地址映射成物理地址的小的硬件设备，这个设备叫做 TLB 翻译后援储备器， Translation Lookaside Buffer，有时也叫做相联储备器（ associative memory），如图 4-12 所示；它通常在 MM内U 部，条目的数量较少，在这个例子中是8个，一般很少超过 64个；每个条目包含一个页的信息，主要有虚页号、在页被修改时将被设置的一个位、爱护码（读/ 写/ 执行答应）、和页所在的物理页框号，这些域和页表中的域是一一对应的，仍有另外一位指出这个条目是否有效；图4-12一个用于加速分页操作的 TLB；生成图 4-12 所示的 TLB的一个可能的例子是一个正在执行某个循环的进程，该循环跨过虚页19、20、21，因此这些页面的爱护码是读和执行；正在使用的主要数据（比如一个正在被处理的数组）在页面 129和130，页 140包含了数组演算中用到的索引；最终，堆栈在页面860和861；现在让我们看一看 TLB是怎样工作的，当一个虚地址被送到MM翻U 译时，硬件第一把它和TLB中的全部条目同时（并行地）进行比较，看它的虚页号是否在TLB中，假如找到了并且这个拜访没有违反爱护位，它的页框号将直接从TLB中取出而不用去查页表；假如虚页号 在TLB中但当前指令试图写一个只读的页面，这时将发生一个爱护故障，与直接拜访页表时相同；好玩的是当虚页号不在 TLB中时会发生什么？假如 MMU发觉在 TLB中没有命中，它将立刻进行一次常规的页表查找，然后从TLB中剔除一个条目并把它替换为刚刚找到的页表项；因此假如这个页很快会再被用到的话，其次次拜访时它就能在 TLB中直接找到；在一个 TLB条目被剔除时，被修改的位被复制回在内存中的页表项，其他的值就已经在那里了；当 TLB 从页表中装入时，全部的域都从内存中取得；软件 TLB治理直到现在我们始终假设，每个带有页式虚拟储备器的机器都有能被硬件识别的页表外加一个TLB，在这个设计中 TLB的治理和 TLB故障的处理都完全由MM硬U 件完成，只有一个页不在内存时才会陷入操作系统；在过去，这个假设是对的，但是在一些现代的RISC机中，包括 MIPS、Alpha 、HP PA，几乎全部的这种页治理工作都是由软件完成的；在这些机器中，TLB条目是由操作系统显式地 装入的，在 TLB没有命中时， MMU不是到页表中找到并装入需要的页面信息，而是产生一个 TLB故障把问题交给操作系统，操作系统必需找到页面，从TLB中剔除一个条目，装入一个新的，然后重新启动产生故障的指令；当然，全部这些都必需用很少几条指令完成，由于TLB不命中发生的频率远比页面故障大得多；令人诧异的是，假如 TLB的尺寸取一个合理的较大值（比如64个条目）以削减不命中的频率，那么软件治理的 TLB效率可能相当高；这里主要的收益是一个简洁得多的MM，U 它在 CPU芯片上为高速缓存和其他能提高性能的部件让出了相当大的面积；Uhlig 等具体地争论了软件 TLB治理 1994 ；人们已经使用了很多方法来提高使用软件治理TLB机器的性能，有一个方法既能削减TLB的不命中率又能削减在 TLB不命中的确发生时的开销（ Bala 等， 1994）；为了削减 TLB的不命中，操作系统有时可