操作系统设计与实现第四章

第四章存储器管理存储器是一种必须仔细管理的重要资源。虽然现在一台普通家用计算机的存储器容量可能是60年代早期全世界最大的计算机IBM7094的五倍以上，但是程序长度的增长速度和存储器容量的增长一样快。用类似于帕金森定律的话来说：存储器有多大，程序就会有多长。在这一章中我们将讨论操作系统是怎样管理存储器的。在理想的情况下，每个程序员都会喜欢的是无穷大、快速并且内容不易变（即掉电后内容不会丢失）的存储器，同时又希望它是是廉价的。但不幸的是当前的技术没有能够提供这样的存储器，因此大部分的计算机都有一个存储器层次结构，它由少量的非常快速、昂贵、易变的的高速缓存（cache），若干兆字节的中等速度、中等价格、易变的主存储器（RAM），和数百兆或数千兆字节的低速、廉价、不易变的磁盘组成。操作系统的工作就是协调这些存储器的使用。操作系统中管理存储器的部分称为存储管理器，它的任务是跟踪哪些存储器正在被使用、哪些存储器空闲，在进程需要时为它分配存储器，使用完毕后释放存储器，并且在主存无法容纳所有进程时管理主存和磁盘间的交换。在这一章中我们将讨论许多不同的存储器管理方案，从非常简单的到高度复杂的。我们从最简单的存储管理系统开始，然后逐步过渡到更加精密的系统。4.1基本的内存管理存储管理系统可以分为两类：在运行期间将进程在主存和磁盘之间移动的系统（交换和分页）和不移动的系统。后一种比较简单，因此我们首先讨论。随后在本章的后半部分我们将讨论交换和分页。在本章中读者应该自始至终清醒地认识到：交换和分页在很大程度上是由于缺少足够的主存以同时容纳所有的进程而引入的。随着主存越来越便宜，选择某种存储器管理方案的理由也许会变得过时，除非程序变大的速度比存储器降价的速度还要快。4.1.1没有交换和分页的单道程序最简单的存储器管理方案是同一时刻只运行一道程序，应用程序和操作系统共享存储器。这种方案的三个变种如图4-1所示。操作系统可以位于主存最低端的随机存取存储器（RAM）中，如图4-1(a)所示；它也可以位于主存最高端的只读存储器（ROM）中，如图4-1(b)所示；还可以让设备驱动程序位于内存高端的ROM中而让操作系统的其他部分位于低端的RAM中，如图4-1(c)所示。例如小型的MS-DOS系统使用的就是最后一种模型。在IBMPC计算机中，系统位于ROM中的部分称为基本输入输出系统（BIOS）。图4-1在一个操作系统一个用户进程时三种简单的内存组织方法，其他方法也是存在的。当这样组织系统时，同一时刻只能有一个进程在存储器中运行。一旦用户输入了一个命令，操作系统就把需要的程序从磁盘拷贝到存储器中并执行它；在进程运行结束后，操作系统显示出一个提示符并等待新的命令。当收到新的命令时它把新的程序装入存储器，覆盖掉原来的程序。4.1.2固定分区的多道程序虽然单道程序常常用于带有简单操作系统的小型计算机上，但我们往往更加希望同时能有多个进程同时运行。在分时系统中，允许多个进程同时在存储器中，这意味着当一个进程因为等待I/O结束而阻塞时，其他的进程可以利用CPU，因而提高了CPU的利用率。即使在个人计算机上，同时运行两个或多个进程也常常是很有用的。实现多道程序的最容易的办法是把主存简单地划分为n个分区（可能不相等），分区的划分可以在系统启动时手工完成。当一个作业到达时，可以把它放到能够容纳它的最小的分区的输入队列中。因为在这种方案中分区大小是固定的，一个分区中未被作业使用的空间就白白浪费掉了。图4-2(a)所示的就是这种固定分区、各分区有自己独立的输入队列的系统。图4-2(a)各分区具有独立输入队列固定内存分区。(b)仅有单个输入队列的固定内存分区。把输入作业排成多个队列时，在大分区的队列为空而小分区的队列为满的情况下，其缺点就变得很明显，如图4-2(a)中的分区1和3所示。另一种方法如图4-2(b)所示，只使用一个队列，当一个分区空闲时，选择最靠近队列头可以被该分区容纳的作业装入其中运行。因为我们不希望为了一个小作业而浪费一个大分区，所以另一个策略是搜索整个输入队列找出该分区能容纳的最大的作业，这种算法认为不值得给小作业一个完整的分区，然而通常我们更加期望给小作业（假设是交互作业）最好的服务，而不是最差的。一个解决方法是至少保留一个小分区，这样就不必为了使小作业运行而为其分配大的分区。另一个方法是采用这样一个规则：一个可运行的作业最多只能够被跳过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，不用修改指令，一条CALL100指令就被有效地转换为一条CALL100K+100指令。指令还被自动地用界限寄存器进行检查以确保他们没有试图访问当前分区以外的地址。基址和界限寄存器受到硬件保护，以防止用户程序修改他们。CDC6600-世界上第一台巨型机-使用了这个方案。用于初期IBMPC的Intel8088CPU使用了这个方案的一个较弱的版本-有基址寄存器，但没有界限寄存器。从286开始，采用了一种更好的方案。4.2交换在批处理系统中，把主存组织为固定的分区是简单而且高效的，每个作业在排到队列头时被装入一个分区，它停留在主存中直到运行完毕。只要有足够的作业能被保持在主存中以使CPU始终处于忙的状态，那么就没有理由使用任何更加复杂的方案。但在分时系统或面向图形的个人计算机中情形就不同了，有时会没有足够的主存以容纳所有当前活动的进程，多出的进程必须被保存在磁盘上并动态地调入主存运行。在硬件支持下，有两个通用的内存管理方法可以使用。最简单的策略称为交换（swapping），它把各个进程完整地调入主存，运行一段时间，再放回到磁盘上；另一种策略称为虚拟存储器（virtualmemory），它使进程在只有一部分在主存的情况下也能运行。下面我们将先讨论交换系统，在4-3中我们将讨论虚拟存储器。交换系统的操作如图4-3所示，开始时只有进程A在主存，随后进程B和C被创建或从磁盘上被调入，在图4-3(d)中A结束了或被交换到了磁盘上，然后D进入，接着B离开，最后E进入。图4-3内存分配情况随着进程进出内存而变化，阴影表示的区域是未使用的内存。图4-2所示的固定分区与图4-3所示的可变分区的主要区别是：在后者中分区的数量、位置、大小随着进程的出入是动态变化的，而在前者中他们是固定不变的。这种可变分区不再受固定分区可能太大或太小的约束，从而提高了主存的利用率，但它也使内存的分配、释放和对各个内存块的跟踪更加复杂。当交换在主存中生成了多个空洞时，可以把所有的进程向下移动至相互靠紧，从而把这些空洞结合成一大块，这种技术称为内存紧缩（memorycompaction）。我们通常不进行这个操作，因为它需要大量的CPU时间，例如在一个有32M主存，每微秒可以拷贝16个字节的计算机上把全部内存紧缩一次需要两秒钟。一个值得关心的问题是在一个进程被创建或换进时应该为它分配多大的内存。如果进程创建时的大小是固定的并且不会改变，那么分配是很简单的：完全根据需要的大小进行分配。然而如果进程的数据段可以增长，例如在许多程序设计语言中都允许动态地从堆中分配内存，那么进程一旦试图增长时问题就出现了，如果该进程邻接着一个空洞就可以把这个空洞分配给它；然而如果进程邻接的是另一个进程，则需要增长的进程或者不得不被移动到内存中一个足够大的空洞中去，或者必须把一个或多个进程交换出去以生成一个足够大的空洞。如果一个进程不能在内存中增长并且磁盘上的交换区已经满了，那么这个进程必须等待或被杀死。如果大部分进程在运行时都要增长，那么为了减少进程因为所在的内存区域不够而引起的交换和移动所带来的开销，可以采用的一种方法是：在进程被换进或移动时为其分配一点额外的内存。当然，在进程被换出到磁盘上时应该只交换进程实际使用的内存中的内容，将额外的内存交换出去纯粹是浪费。在图4-4(a)中我们可以看到一个已经为两个进程分配了增长空间的内存配置。图4-4(a)为能够增长的数据段预留空间。(b)为能够增长的数据段和堆栈段预留空间。如果进程有两个可增长的数据部分，例如一个供动态分配和释放的变量使用的作为堆的数据段和一个存放普通局部变量和返回地址的栈段，那么可以使用另一种安排，如图4-4(b)所示。在这个图中我们可以看到所示进程的栈段在进程所占内存的顶端并向下增长，紧接在正文段后面的数据段向上增长，处于这两个段之间的内存，他们都可以使用，如果用完了，则这个进程或者必须被移动到足够大的空洞中，或者交换出内存直到内存中有足够的空间，或者被杀死。4.2.1使用位图的内存管理动态分配的内存必须由操作系统管理。一般来说有两种方法跟踪内存的使用情况：位图和自由链表。本节和下一节将逐个讨论这两种方法。在使用位图方法时，内存被划分为可能小到几个字或大到几千字节的分配单位，每个分配单位对应于位图中的一位，0表示空闲1，表示占用（或者反过来）。图4-5表示出了一个内存片段和对应的位图。图4-5(a)一段有五个进程和三个空洞的内存，刻度表示内存分配的单位，阴影表示空闲区域（在位图中用0表示）。(b)对应的位图。(c)用列表表示的同样的信息。分配单位的大小是一个重要的设计因素。分配单位越小，位图越大，但是即使分配单位只有4个字节大小，32位的内存也只需要位图中的1位，32n位的内存只需要n位的位图，因此位图只占用了1/33的内存。如果分配单位选的比较大，需要的位图就比较小，但是如果进程的大小不是分配单位的整数倍，那么最后一个分配单位中相当数量的内存就可能被浪费掉。因为位图的大小仅仅取决于内存和分配单位的大小，它提供了一个简单的使用固定大小内存就能对内存使用情况