操作系统教程第5章.ppt

第3章 存储管理,计算机系统中的存储器可以分为两种：内存储器和辅助存储器。前者可被CPU直接访问，后者不能。辅助存储器与CPU之间只能够在输入输出控制系统的管理下，进行信息交换。既然内存储器可被CPU直接访问，因此它是计算机系统中的一种极为重要的资源。在操作系统中，把管理内存储器的部分称为“存储管理”。能否合理地使用内存，会在很大程度上影响到整个计算机系统的性能。,退出,本章将要介绍两个重要概念。一个是“地址重定位”。在多道程序设计环境下，用户无法事先约定各自占用内存的哪个区域，也不知道自己的程序会放在内存的什么位置，但程序地址如果不反映其真实的存储位置，就不可能得到正确的执行。所以在存储管理中，必须解决地址的重定位问题。二是“虚拟存储”。曾经有人说过：“存储器有多大，程序就会有多大”。因此，在计算机系统中，虽然内存的容量随着硬件的发展得到了很大的扩充，但仍然无法满足实际的需要，必须打破“程序只有全部在内存，才能得以运行”的限制。为此，通过“虚拟存储”这一技术手段，可以达到不用真正扩充内存而“扩充”内存的目的。,本章着重讲述四个方面的内容：（1）地址的静态重定位和动态重定位；（2）不同的存储管理方案；（3）存储共享和存储保护；（4）存储扩充和虚拟存储器。,3.1 固定分区存储管理3.2 可变分区存储管理3.3 分页式存储管理3.4 虚拟存储与请求页式存储管理,3.1 固定分区存储管理,3.1.1 地址重定位举例说，假定用户程序A的相对地址空间为03KB(03071)，在该程序中地址为3000的地方，有一条调用子程序（其入口地址为100）的指令：“call 100”，如图3-1(a)所示。,很清楚，用户程序指令中出现的都是相对地址，即都是相对于“0”的地址。若当前操作系统在内存储器占用020KB的存储区。这时，如果把程序A装入到内存储器中20KB往下的存储区域中，那么，它这时占据的是内存储器中20KB23KB的区域。这个区域就是它的绝对地址空间。现在它还不能正确运行，因为在执行到位于绝对地址23480（20KB+3000）处的“call 100”指令时，它会到绝对地址100处去调用所需的子程序，但这个地址却在操作系统里面，如图3-1(b)所示。之所以出错是因为call后面所跟随的子程序入口地址现在应该是20580，而不应该保持原来的100。这表明，当把一个程序装入内存后，如果不将其指令中的地址进行调整，以反映当前所在的存储位置，那么执行时势必会引起混乱。,在操作系统中，把用户程序指令中的相对地址变换成为所在绝对地址空间中的绝对地址的过程，称为“地址重定位”。也就是说，把指令“call 100”中的100变换成20580，就是地址重定位，如图3-1(c)所示。地址重定位与用户程序占用的绝对地址空间的起始地址有关。在图3-1(c)中，由于是把程序A装入到（20KB23KB）绝对地址空间里，因此call指令中相对地址100所对应的绝对地址是20KB+100=20580。如果把程序A装入到（22KB25KB）的绝对地址空间里，那么call指令中相对地址100所对应的绝对地址就应该是22KB+100=22628了。如图3-1(d)所示。,3.1.2 地址的静态重定位如果在程序运行之前，就为用户程序实行了地址重定位的工作，那么称这种地址重定位为地址的“静态重定位”。一般地，静态重定位工作是由操作系统中的重定位装入程序来完成的。用户把自己的作业链接装配成一个相对于“0”编址的目标程序，它就是重定位装入程序的输入，即加工对象。重定位装入程序根据当前内存的分配情况，按照分配区域的起始地址逐一调整目标程序指令中的地址部分。于是，目标程序在经过重定位装入程序加工之后，不仅进入到分配给自己的绝对地址空间中，而且程序指令里的地址部分全部进行了修正，反映出了自己正确的存储位置，从而保证程序的正确运行。,3.1.3 单一连续分区存储管理就早期计算机或个人微机而言，每次只有一个用户使用计算机，无从提及多道程序设计，因此，在这些机器上运行的操作系统，其存储管理都采用单一连续分区的分配策略。单一连续分区分配策略的基本思想是总体上把内存储器分为两个分区。一个分区固定分配给操作系统使用；另一个分配给用户使用，称为“用户区”。如图3-2(a)所示。,可以看出，采用单一连续分区存储管理方案的系统有如下特点：（1）系统总是把整个用户区分配给一个用户使用，比如图3-2(a)中的ab区域。（2）实际上，内存用户区又被分为“使用区”和“空闲区”两部分。见图3-2(b)，其中使用区为ac，空闲区为cb。使用区是用户作业程序真正占用的那个连续存储区域；空闲区是分配给了用户、但未被使用的区域。在操作系统中，把分配给了用户、但又未使用的区域称为“内部碎片”。内部碎片的存在是对内存资源的一种浪费。,（3）由于任何时刻内存储器的用户区中只有一个作业运行，因此这种系统只适用于单用户（或单道）的情况。（4）进入内存的作业，独享系统中的所有资源，包括内存中的整个用户区。（5）由于整个用户区都分配给了一个用户使用，因此作业程序进入用户区后，没有移动的必要。采用这种存储分配策略时，将对用户程序实行静态重定位。,（6）实行静态重定位，并不能阻止用户有意无意地通过不恰当的指令闯入操作系统所占用的存储区域。如何阻止对操作系统的侵扰，这就是所谓的“存储保护”问题。在单一连续分区存储管理中，为了有效阻止用户程序指令中的地址闯入操作系统所占用的区域，在CPU中设置一个用于存储保护的专用寄存器“界限寄存器”，如图3-2(c)所示。在界限寄存器中，总是存放着内存用户区的起始地址（比如图3-2(c)中为a）。当CPU在管态下工作时，允许访问内存中的任何地址；当CPU在目态下工作时，对内存储器的每一次访问，都要在硬件的控制下，与界限寄存器中的内容进行比较。一旦发现该访问的地址小于界限寄存器中的地址，就会产生“地址越界”中断，阻止这次访问的进行，从而将作业限制在规定的存储区域内运行，确保被保护区中的信息不受外来的破坏。,单一连续分区存储管理有如下缺点：（1）由于每次只能有一个作业进入内存，故它不适用于多道程序设计，整个系统的工作效率不高，资源利用率低下。（2）只要作业比用户区小，那么在用户区里就会形成碎片，造成内存储器资源的浪费。如果用户作业很小，那么这种浪费是巨大的。,（3）若用户作业的相对地址空间比用户区大，那么该作业就无法运行。即大作业无法在小内存上运行。早期计算机在一定的条件下，可以采用所谓的“覆盖”技术，使得大作业在小内存上得以运行。举例说，有一个用户作业程序的调用结构如图3-3(a)所示。主程序MAIN需要存储量10KB。运行中，它要调用程序A或B，它们各需要存储量50KB和30KB。程序A在运行中要调用程序C，它需要的存储量是30KB。程序B在运行中要调用程序D或程序E，它们各需要存储量20KB或40KB。通过连接装配的处理，该作业将形成一个需要存储量180KB的相对地址空间，如图3-3(b)所示。这表明，只有系统分配给它180KB的绝对地址空间时，它才能够全部装入并运行。,其实不难看出，该程序中的子程序A和B不可能同时调用，即MAIN调用程序A，就肯定不会调用程序B，反之亦然。同样地，子程序C、D和E也不可能同时出现，所以，除了主程序必须占用内存中的10KB外，A和B可以共用一个存储量为50KB的存储区，C、D和E可以共用一个存储量为40KB的存储区，如图3-3(c)所示。也就是说，只要分给该程序100KB的存储量，它就能够运行。由于A和B共用一个50KB的存储区，C、D和E共用一个40KB的存储区，我们就称50KB的存储区和40KB的存储区为覆盖区。因此，所谓“覆盖”，是早期为程序设计人员提供的一种扩充内存的技术，其中心思想是允许一个作业的若干个程序段使用同一个存储区，被共用的存储区被称为“覆盖区”。不过，这种技术并不能彻底解决大作业与小内存的矛盾。,为了让单一连续分区存储管理能具有“多道”的效果，在一定条件下，可以采用所谓的“对换”技术来实现。“对换”的中心思想是：将作业信息都存放在辅助存储器上，根据单一连续分区存储管理的分配策略，每次只让其中的一个进入内存投入运行。当运行中提出输入输出请求或分配给的时间片用完时，就把这个程序从内存储器“换出”到辅助存储器，把辅助存储器里的另一个作业“换入”内存储器运行，如图3-4所示。这样，从宏观上看，系统中同时就有几个作业处在运行之中。不过要注意，由于单一连续分区存储管理实行的是静态重定位，所以，“换出”的作业程序再被“换入”时，仍应该装到与它“换出”前相同的存储区中去，以保证能够正确地继续运行。不难看出，“对换”是以辅助存储器作为内存的后援而得以实行的，没有它的支持，就谈不上“对换”。,3.1.4 固定分区存储管理1对作业的组织一般地，固定分区存储管理总是把内存用户区划分成几个大小不等的连续分区。由于分区尺寸在划分后保持不变，因此系统可以为每一个分区设置一个后备作业队列，形成多队列的管理方式，如图3-5(a)所示。在这种组织方式下，一个作业到达时，总是进入到“能容纳该作业的最小分区”的那个后备作业队列中去排队。比如图3-5(a)中，作业A、B、C排在第1分区的队列上，说明它们对内存的需求都不超过8KB；作业D排在第2分区的队列上，表明它对内存的需求大于8KB小于32KB；作业E和F排在第4分区的队列上，表明它们对内存的需求大于64KB小于132KB。,把到达的作业根据上述原则排成若干个后备队列时，可能会产生有的分区队列忙碌、有的分区队列闲置的情形。比如图3-5(a)中，作业A、B、C都在等待着进入第1分区。按照原则，它们不能进入目前空闲的第3分区，虽然第3分区的大小完全能够容纳下它们。作为一种改进，可以采用多个分区只设置一个后备作业队列的办法，如图3-5(b)所示。当某个分区空闲时，统一都到这一个队列里去挑选作业，装入运行。,2分区的分配与释放在操作系统中，要确定选用某一种管理策略时，应该考虑多方面的因素，权衡利弊，绝对好的方案是少见的。为了具体管理内存中的各个分区，操作系统的做法是设置一张名为“分区分配表”的表格，用它记录各分区的信息以及当前的使用情况。表3-1即为一种分区配表。,分区分配表中至少应该有每个分区的起始地址和长度，并且有一个使用标志。当某分区的使用标志为“0”时，表示该分区当前是空闲的，可以分配；当某分区的使用标志不为“0”时，表示该分区已经分配给一个作业使用，该标志里存放的即是这个作业的名称。从表3-1可以看出，该系统共有4个分区。第1分区已经分配给作业1使用，第2分区分配给了作业6使用，第4分区分配给了作业2使用。当前只有第3分区是空闲的。,当需要把一个作业装入内存时，按照分区号扫视分区分配表，找到使用标志为“0”的分区，随后把要装入内存的作业尺寸与该分区的长度进行比较。若能够容纳该作业，并符合所采取的分配策略，那么就把它分配给这个作业，同时修改分区分配表中该分区表目的使用标志为非0（即把该作业的名字填入），从而完成分区的分配工作；当一个作业运行结束时，只需根据作业名，在分区分配表里找到它所使用的表目，然后将该表目的使用标志改为“0”，从而完成该分区的释放工作。,3地址重定位与存储保护在固定分区存储管理中，不仅要防止用户程序对操作系统形成的侵扰，也要防止用户程序与用户程序之间形成的侵扰。因此必须在CPU中设置一对专用的寄存器，用于存储保护，如图3-6所示。在图3-6中，将两个专用寄存器分别起名为“低界限寄存器”和“高界限寄存器”。当进程调度程序调度某个作业进程运行时，就把该作业所在分区的低边界地址装入低界限寄存器，把高边界地址装入高界限寄存器。比如现在调度到分区1里的作业1运行，于是就把第1分区的低地址a装入到低界限寄存器中，把第1分区的高地址b装入到高界限寄存器中。作业1运行时，硬件会自动检测指令中的地址，如果超出a或b，那么就产生出错中断，从而限定作业1只在自己的区域里运行。,3.2 可变分区存储管理,3.2.1 可变分区存储管理的基本思想固定分区存储管理中的“固定”有两层含义，一是分区数目固定，一是每个分区的尺寸固定。采用这种内存管理技术时，分配出去的分区总可能会有一部分成为内部碎片而浪费掉。究其原因，是因为进入分区的作业大小，不可能刚好等于该分区的尺寸。那么能否不事先划分好分区，而是按照进入作业的相对地址空间的大小来分配存储，从而避免固定式分区所产生的存储浪费，这实际上就是可变分区存储管理考虑问题的出发点。,可变分区存储管理的基本思想是：在作业要求装入内存储器时，如果当时内存储器中有足够的存储空间满足该作业的需求，那么就划分出一个与作业相对地址空间同样大小的分区分配给它。,图3-7是可变分区存储管理思想的示意图。图3-7(a)是系统维持的后备作业队列，作业A需要内存15KB，作业B需要20KB，作业C需要10KB，等等；图3-7(b)表示系统初启时的情形，整个系统里因为没有作业运行，因此用户区就是一个空闲分区；图3-7(c)表示将作业A装入内存时，为它划分了一个分区，尺寸为15KB，此时的用户区被分为两个分区，一个是已经分配的，一个是空闲区；图3-7(d)表示将作业B装入内存时，为它划分了一个分区，尺寸为20KB，此时的用户区被分为三个分区；图3-7(e)表示将作业C装入内存时，为它划分了一个分区，尺寸为10KB，此时的用户区被分为四个分区。由此可见，可变分区存储管理中的“可变”也有两层含义，一是分区的数目随进入作业的多少可变，一是分区的边界划分随作业的需求可变。,由于实施可变分区存储管理时，分区的划分是按照进入作业的尺寸进行的，因此在这个分区里不会出现内部碎片。这就是说，可变分区存储管理消灭了内部碎片，不会出现由于内部碎片而引起的存储浪费现象。但是，为了克服内部碎片而提出的可变分区存储管理模式，却引发了很多新的问题。只有很好地解决这些问题，可变分区存储管理才能真正得以实现。下面我们通过图3-8来看一下可变分区存储管理的工作过程，归纳出需要解决的一些技术问题。,假定有作业请求序列：作业A需要存储16KB，作业B需要存储100KB，作业C需要存储70KB，作业D需要存储75KB，等等。内存储器共256KB，操作系统占用20KB，系统最初有空闲区236KB，如图3-8(a)所示。下面着重讨论236KB空闲区的变化。作业A到达后，按照它的存储要求，划分一个16KB大小的分区分配给它，于是出现两个分区，一个已经分配，一个为空闲，如图3-8(b)所示。作业B到达后，按照它的存储要求，划分一个100KB大小的分区分配给它，于是出现三个分区，两个已经分配，一个为空闲，如图3-8(c)所示。紧接着为作业C划分一个分区，从而形成四个分区，三个已经分配，一个空闲，如图3-8(d)所示。,当作业D到达时，由于系统内只有50KB的空闲区，不够D的需求，因此作业D暂时无法进入。如果这时作业B运行完毕，释放它所占用的100KB存储量，这时系统中虽然仍保持为四个分区，但有的分区的性质已经改变，成为两个已分配，两个空闲，如图3-8(e)所示。由于作业B释放的分区有100KB大，可以满足作业D的需要，因此系统在36KB136KB的空闲区中划分出一个75KB的分区给作业D使用。这样36KB136KB分区被分为两个分区，一个分配出去（36KB111KB），一个仍为空闲（111KB136KB），如图3-8(f)所示。这样，总共有五个分区：三个已经分配，两个空闲。,3.2.2 地址的动态重定位图3-9是对动态重定位过程的一个描述。这里仍沿用图3-1的信息。现在为了对图3-9(a)中的用户作业A实行可变分区存储管理，假定按照当前内存储器的分配情况，把它原封不动地装入到22KB25KB的分区里面。可以看到，在其绝对地址空间里，位于22KB+3000单元处的指令仍然是“call 100”，未对它做任何的修改。如果现在调度到该作业运行，操作系统就把它所占用的分区的起始地址22KB装入到定位寄存器中，如图3-9(b)所示。当执行到位于单元22KB+3000中的指令“call 100”时，硬件的地址变换线路就把该指令中的地址100取出来，与定位寄存器中的22KB相加，形成绝对地址22628（=22KB+100）。然后就按照这个地址去执行call指令。于是，程序就正确转移到22628的子程序处去执行了。,3.2.3 空闲区的合并在可变分区存储管理中实行地址的动态重定位后，用户程序就不会被“钉死”在分配给自己的存储分区中。必要时，它可以在内存中移动，为空闲区的合并带来了便利。内存区域中的一个分区被释放时，与它前后相邻接的分区可能会有四种关系出现，如图3-10所示。在图中，我们做这样的约定：位于一个分区上面的分区，称为它的“前邻接”分区，一个分区下面的分区，称为它的“后邻接”分区。,（1）图3-10(a)表示释放区的前邻接分区和后邻接分区都是已分配区，因此没有合并的问题存在。此时释放区自己形成一个新的空闲区，该空闲区的起始地址就是该释放区的起始地址，长度就是该释放区的长度。（2）图3-10(b)表示释放区的前邻接分区是一个空闲区，后邻接分区是一个已分配区，因此，释放区应该和前邻接的空闲区合并成为一个新的空闲区。这个新空闲区的起始地址是原前邻接空闲区的起始地址，长度是这两个合并分区的长度之和。,（3）图3-10(c)表示释放区的前邻接分区是一个分配区，后邻接分区是一个空闲区，因此，释放区应该和后邻接的空闲区合并成为一个新的空闲区。这个新空闲区的起始地址是该释放区的起始地址，长度是这两个合并分区的长度之和。（4）图3-10(d)表示释放区的前邻接分区和后邻接分区都是一个空闲区，因此，释放区应该和前、后两个邻接的空闲区合并成为一个新的空闲区。这个新空闲区的起始地址是原前邻接空闲区的起始地址，长度是这三个合并分区的长度之和。,空闲分区的合并，有时也被称为“存储紧凑”。何时进行合并，操作系统可以有两种时机的选择方案：一是调度到某个作业时，当时系统中的每一个空闲分区尺寸都比它所需要的存储量小，但空闲区的总存储量却大于它的存储请求，于是就进行空闲存储分区的合并，以便能够得到一个大的空闲分区，满足该作业的存储需要；另一是只要有作业运行完毕归还它所占用的存储分区，系统就进行空闲分区的合并。比较这两种方案可以看出，前者要花费较多的精力去管理空闲区，但空闲区合并的频率低，系统在合并上的开销少；后者总是在系统里保持一个大的空闲分区，因此对空闲分区谈不上更多的管理，但是空闲区合并的频率高，系统在这上面的开销大。,3.2.4 分区的管理与组织方式采用可变分区方式管理内存储器时，内存中有两类性质的分区：一类是已经分配给用户使用的“已分配区”，另一类是可以分配给用户使用的“空闲区”。随着时间的推移，它们的数目在不断地变化着。如何知道哪个分区是已分配的，哪个分区是空闲的，如何知道各个分区的尺寸是多少，这就是分区管理所要解决的问题。对分区的管理，常用的方式有三种：表格法、单链表法和双链表法。下面逐一介绍它们各自的实现技术。,1表格法为了记录内存中现有的分区以及各分区的类型，操作系统设置两张表格，一张为“已分配表”，一张为“空闲区表”，如图3-11(b)和3-11(c)所示。表格中的“序号”是表目项的顺序号，“起始地址”、“尺寸”和“状态”都是该分区的相应属性。由于系统中分区的数目是变化的，因此每张表格中的表目项数要足够的多，暂时不用的表目项的状态被设为“空”。,假定图3-11(a)为当前内存中的分区使用情况，那么图3-11(b)记录了已分配区的情形，图3-11(c)记录了空闲区的情形。当作业进入而提出存储需求时，就去查空闲区表里状态为“空闲”的表目项。如果该项的尺寸能满足所求，那么就将它一分为二：分配出去的那一部分在已分配表中找一个状态为“空”的表目项进行登记，剩下的部分（如果有的话）仍在空闲区表中占据一个表目项。如果有一个作业运行结束，则根据作业名到已分配表中找到它的表目项，将该项的“状态”改为“空”，随之在空闲区表中寻找一个状态为“空”的表目项，把释放分区的信息填入，并将表目项状态改为“空闲”。当然，这时可能还会进行空闲区的合并工作。,2单链表法把内存储器中的每个空闲分区视为一个整体，在它的里面开辟出两个单元，一个用于存放该分区的长度（size），一个用于存放它下一个空闲分区的起始地址（next），如图3-14(a)所示。操作系统开辟一个单元，存放第1个空闲分区的起始地址，这个单元被称为“链首指针”。最后一个空闲分区的next中存放标志“NULL”表明它是最后一个。这样一来，系统中的所有空闲分区被连接成为一个链表。从链首指针出发，顺着各个空闲分区的next往下走，就能到达每一个空闲分区。图3-14(b)所反映的是图3-11(a)当前内存储器中空闲区的链表。为了看得更加清楚，有时也把这些空闲区抽出来，单独画出它们形成的链表，如图3-14(c)所示。,用空闲区链表管理空闲区时，对于提出的任何一个请求，都顺着空闲区链表首指针开始查看一个一个空闲区。如果第1个分区不能满足要求，就通过它的next找到第2个空闲区。如果一个空闲区的next是NULL，那么就表示系统暂时无法满足该作业这一次所提出的存储请求。在用这种方式管理存储器时，无论分配存储分区还是释放存储分区，都要涉及到next（指针）的调整。,3双链表法如前所述，当一个已分配区被释放时，有可能和与它相邻接的分区进行合并。为了寻找释放区前、后的空闲区，以利于判别它们是否与释放区直接邻接，可以把空闲区的单链表改为双向链表。也就是说，在图3-14(a)所表示的每个空闲分区中，除了存放下一个空闲区起址next外，还存放它的上一个空闲区起址（prior）的信息，如图3-15(a)所示。这样，通过空闲区的双向链表，就可以方便地由next找到一个空闲区的下一个空闲区，也可以由prior找到一个空闲区的上一个空闲区。,比如，在把一个释放区链入空闲区双向链表时，如果通过它的prior发现，在该链表中释放区的前面一个空闲区的起始地址加上长度，正好等于释放区的起始地址，那么说明是属于图3-10(b)的情形，即它前面的空闲区与它直接相邻接，应该把这个释放区与原来的空闲区合并。另外，如果释放区起始地址加上长度正好等于next所指的下一个空闲区的起始地址，那么说明是属于图3-10(c)的情形，即它后面的空闲区与它直接相邻接，应该把这个释放区与原来的空闲区合并。如同单链表一样，在利用双向链表管理存储空闲分区时，无论分配存储分区还是释放存储分区，都要涉及到next和prior两个指针的调整。图3-15(b)是图3-11(a)的双向链表形式。,3.2.5 空闲分区的分配算法当系统中有多个空闲的存储分区能够满足作业提出的存储请求时，究竟将谁分配出去，这属于分配算法问题。在可变分区存储管理中，常用的分区分配算法有：最先适应算法、最佳适应算法以及最坏适应算法。下面分别介绍它们的含义。,1最先适应算法实行这种分配算法时，总是把最先找到的、满足存储需求的那个空闲分区作为分配的对象。这种方案的出发点是尽量减少查找时间，它实现简单，但有可能把大的空闲分区分割成许多小的分区，因此对大作业不利。,2最佳适应算法实行这种分配算法时，总是从当前所有空闲区中找出一个能够满足存储需求的、最小的空闲分区作为分配的对象。这种方案的出发点是尽可能地不把大的空闲区分割成为小的分区，以保证大作业的需要。该算法实现起来比较费时，麻烦。,3最坏适应算法实行这种分配算法时，总是从当前所有空闲区中找出一个能够满足存储需求的、最大的空闲分区作为分配的对象。可以看出，这种方案的出发点是照顾中、小作业的需求。,3.3 分页式存储管理,3.3.1 分页式存储管理的基本思想如上所述，可变分区存储管理按照作业对存储的需求量进行分区的划分，因此它不出现内部碎片。但由此会招致某些分区过小而无法满足作业存储请求的情形，从而产生外部碎片。在那里，解决外部碎片的办法是通过移动作业对空闲分区进行合并。这不仅不方便，还增加了系统的开销。,之所以要移动内存中的作业，主要是因为在此之前，用户作业必须被装入一个连续的存储区域，才能正确运行。不移动，就不能获得大的空闲分区，就不能有一个大的连续分区分配给用户作业使用。如果可以把用户作业分散装入到几个不连续的分区里，仍然能保证它得到正确的运行，那么就无须去移动内存中的作业了。分页式存储管理正是打破了这种“连续”的禁锢，把对存储器的管理大大向前推进了一步。,分页式存储管理是将固定式分区方法与动态重定位技术结合在一起提出的一种存储管理方案，它需要硬件的支持。其基本思想是：首先把整个内存储器划分成大小相等的许多分区，每个分区称为“块”（这表明它具有固定分区的管理思想，只是这里的分区是定长罢了）。比如把内存储器划殖n个分区，编号为0,1,2,n-1。例如，在图3-17(a)中，内存储器总的容量为256KB，操作系统要求20KB。若块的尺寸为4KB，则共有64块，操作系统占用前5块，其他分配给用户使用。在分页式存储管理中，块是存储分配的单位。,其次，用户作业仍然相对于“0”进行编址，形成一个连续的相对地址空间。操作系统接受用户的相对地址空间，然后按照内存块的尺寸对该空间进行划分。用户程序相对地址空间中的每一个分区被称为“页”，编号从0开始，第0页、第1页、第2页、。比如，图3-17(b)中，作业A的相对地址空间大小为11KB。按照4KB来划分，它有2页多不到3页大小，但把它作为3页来对待，编号为第0页、第1页和第2页。,这样一来，用户相对地址空间中的每一个相对地址，都可以用“页号，页内位移”来表示。并且不难看出，数对（页号，页内位移）与相对地址是一一对应的。比如说，图3-17(b)中，相对地址5188与数对（1，1092）相对应，其中“1”是相对地址所在页的页号，而“1092”则是相对地址与所在页起始位置（4KB=4096）之间的位移。又比如，相对地址9200与数对（2，108）相对应，“2”是相对地址所在页的页号，“108”是相对地址与所在页起始位置（8KB=8192）之间的位移。,有了这些准备，如果能够解决作业原封不动地进入不连续存储块后也能正常运行的问题，那么分配存储块是很容易的事情，因为只要内存中有足够多的空闲块，那么作业中的某一页进入哪一块都是可以的。比如图3-17(a)中，就把作业A装入到了第8块、第11块和第6块这样的三个不连续的存储块中。,下面以图例来说明如何确保原封不动地进入不连续存储块后的作业能够正常的运行。假定块的尺寸为1KB，作业A的相对地址空间为3KB大小，在相对地址100处有一条调用子程序的指令call，子程序的入口地址为3000（当然是相对地址）。作业A进入系统后被划分成3页，如图3-18(a)所示。现在把第0、1、2页依次装入到内存储器的第4、9、7三个不连续的块中，如图3-18(b)所示。,为了确保原封不动放在不连续块中的用户作业A能够正常运行，可以采用如下方法。（1）记录作业A的页、块对应关系，如图3-18(c)所示，它表示作业A的第0页放在内存中的第4块，第1页放在内存中的第9块，第2页放在内存中的第7块。（2）当运行到指令“call 3000”时，把它里面的相对地址3000转换成数对：(2，952)，表示该地址在作业相对地址空间里位于第2页，距该页起始位置的位移是952。具体的计算公式是：页号=相对地址/块尺寸（注：这里的“/”运算符表示整除）；页内位移=相对地址%快尺寸（注：这里的“%”运算符表示求余）。,（3）用数对中的“页号”去查作业A的页、块对应关系表（如图3-18(c)所示），得知相对地址空间中的第2页内容，现在是在内存的第7块中。（4）把内存第7块的起始地址与页内位移相加，就得到了相对地址3000现在的绝对地址，即7KB+952=8120。至此，系统就去做指令“call 8120”，从而得到了正确地执行。,从以上的讲述可以看到，在分页式存储管理中，用户程序是原封不动地进入各个内存块的。指令中相对地址的重定位工作，是在指令执行时进行，因此属于动态重定位，并且由如下的一些内容一起来实现地址的动态重定位：（1）将相对地址转换成数对（页号，页内位移）；（2）建立一张作业的页与块对应表；（3）按页号去查页、块对应表；（4）由块的起始地址与页内位移形成绝对地址。,3.3.2 分页式存储管理的地址转换1地址结构与数对(页号，页内位移)的形成如上所述，在分页式存储管理的地址变换中，首先遇到的是系统要把指令中的相对地址转换成它所对应的数对，并且也给出了进行这种变换时使用的计算公式。但是，如果每次地址变换都要做这种映射计算，不仅费时，而且麻烦。,如果把块（或页）的尺寸限定只能是2的方幂，那么利用计算机系统设定的地址结构，就很容易得到一个相对地址所对应的数对，根本不用进行上面的复杂计算。例如，某系统的地址结构长为16个二进制位，如图3-19(a)所示。它表示该地址空间有64KB（2的16次方）大，即065535。现在图3-19(a)中是相对地址3000的二进制表示。我们假定系统的块尺寸为1KB=1024字节。,按照前面给出的公式，算出3000对应的数对是“2，952”。其实分析一下就可以知道，现在一页的尺寸为1KB，表明每一页中有1024个字节，它需要用10个二进制位来表示。因此，我们在第10个二进制位处画一条粗的竖线，如图3-19(b)所示。这样，第0位到第9位这10个二进制位就可以表示一页中01023这1024个字节。如果超过1024个字节，就往前进位。于是，前面的第10位到第15位就表示第几页。根据这个分析，图3-19(b)中高6位的二进制数值是2，正是3000对应的页号，低10位的二进制数值是952，正是3000对应的页内位移。,假定现在把一页的尺寸设置为256个字节。为了说明相对地址3000应该与哪个数对相对应，在图3-19(a)的基础上，在第7位和第8位之间画一条粗的竖线，如图3-19(c)所示。之所以这样做，是因为2的8次方等于256。计算高8位（815）相应的二进制数值是11；计算低8位（07）相应的二进制数值是184。因此，当每页长度为256个字节时，相对地址3000应该在第11页的第184处。,2页表与快表在分页式存储管理中，系统按照内存块的尺寸，把每一个用户作业的相对地址空间划分成若干页，然后把这些页装入到内存的空闲块中投入运行。系统为了知道一个作业的某一页存放在内存中的哪一块中，就需要建立起它的页、块对应关系表。在操作系统中，把这张表称为“页表”。因此，在分页式存储管理中，每一个作业都有自己的页表。用户作业相对地址空间划分成多少页，其页表就有多少个表项，表项按页号顺序排列。,页表的构成是应该考虑的问题。一种方法是利用内存储器。这时，只需要硬件设置一个专用寄存器：“页表控制寄存器”。每当进程调度时，把调度到作业的页表起始地址和页表长度（即页表表项的数目）放入寄存器中，就能达到映射不同作业地址的目的。图3-20给出了地址转换过程：先把CPU指令中的相对地址分解成数对（页号，页内位移），接着由页号与页表起始地址得到该页号在页表中对应的表目，从而查到相应的块号，再由块号与页内位移拼出绝对地址。此时才去执行所需要的指令。页表控制寄存器中的“长度”起到存储保护的作用，每一个相对地址中的页号都不能大于该长度，否则出错。,由于页表存放在内存，因此不仅增加了系统在存储上的花销，更为重要的还是降低了CPU的访问速度。这是因为每次对某一地址的访问，首先要访问内存中的页表，形成绝对地址后，才能进行所需要的真正访问。也就是说，以前只须一次访问就能实现的操作，现在要两次访问内存储器才能实现。为了提高地址的转换速度，另一种实现页表的方法是用一组快速的硬件寄存器构成公用的页表。调度到谁时，就把谁在内存的页表内容装入该组寄存器中。这组硬件寄存器是这样工作的：硬件把页号与寄存器组中所有的表项同时并行比较，立即输出与该页号匹配的块号。如图3-21所示。这种做法无须访问内存，并且通过并行匹配直接完成地址的变换，因此速度是极快的。,由于快速寄存器价格昂贵，因此完全由它来组成页表的方案是不可取的。比如，当地址结构为32个二进制位、块尺寸定为4KB时，地址空间最多可以有100万个页面。由于一个页面在页表中要有一个表目项，于是要有100万个快速寄存器组构成页表，实在无法想象。考虑到大多数程序在一次调度运行时，倾向于在少数页面中进行频繁的访问（这被称为程序的“局部性”原理），因此实际系统中的做法是采用内存页表与快速寄存器组相结合的解决方案，并且利用程序的局部性原理，只用极少数几个（一般是816个）快速寄存器来构成快速寄存器组，这时把快速寄存器组单独起名为：“相联寄存器”，或简称“快表”。这时分页式存储管理的地址转换过程如图3-22所示。,通过查快表就能实现内存访问的成功率为“命中率”，可见，命中率越高，性能就越好。表3-2给出了平均命中率与相联寄存器个数的关系。从表中可以看出，设置快表，确实能够达到提高地址转换速度的目的。,3.3.3 内存块的分配与回收分页式存储管理是以块为单位进行存储分配的，并且每块的尺寸相同。因此，在有存储请求时，只要系统中有足够的空闲块存在，就可以进行存储分配，把谁分配出去都一样，没有好坏之分。为了记住内存块谁是已分配的，谁是空闲的，可以采用“存储分块表”、“位图”以及“单链表”等管理方法。,所谓“存储分块表”，就是操作系统维持一张表格，它的一个表项与内存中的一块相对应，用来记录该块的使用情况。比如，图3-23(a)表示内存总的容量是64KB，每块4KB，于是被划分成16块。这样，相应的存储分块表也有16个表项，它恰好记录了每一块当前的使用情况，如图3-23(b)所示。当有存储请求时，就查存储分块表。只要表中“空闲块总数”记录的数目大于请求的存储量，就可以进行分配，同时把表中分配出去的块的状态改为“已分配”。当作业完成归还存储块时，就把表中相应块的状态改为“空闲”。,当内存储器很大时，存储分块表也就会很大，要花费掉相当多的存储量，于是出现了用位图记录每一块状态的方法。所谓“位图”，即是用二进制位与内存块的使用状态建立起关系，该位为“0”，表示对应的块空闲；该位为“1”，表示对应的块已分配。这些二进制位的整体，就称为“位图”。比如图3-23(c)就是由3个字节组成的位图，前两个字节是真正的位图（共16个二进制位），第三个字节用来记录当前的空闲块数。,进行块分配时，首先查看当前空闲块数能否满足作业提出的存储需求。若不能满足，则该作业不能装入内存。在满足时，一方面根据需求的块数，在位图中找出一个个当前取值为“0”的位，把它们改为取值“1”，修改“空闲块总数”。这样，就把原来空闲的块分配出去了；另一方面，按照所找到的位的位号以及字节号，可以按下面的公式计算出该位所对应的块号（注：下面给出的不是通用公式）：块号=字节号8+位号把作业相对地址空间里的页面装入这些块，并在页表里记录页号与块号的这些对应关系，形成作业的页表。,在作业完成运行归还存储区时，可以按照下面的公式，根据归还的块号计算出该块在位图中对应的是哪个字节的哪一位，把该位置成“0”，实现块的回收。字节号=块号/8；位号=块号%8（注：这里的“/”运算符表示整除；这里的“%”运算符表示求余）。如同可变分区方式管理内存储器时采用的单链表法一样，在这里也可以把空闲块链接成一个单链表加以管理，如图3-23(a)所示。当然，系统必须设置一个链表的起始地址指针，以便进行存储分配时能够找到空闲的内存块。,3.4 虚拟存储与请求页式存储管理,3.4.1 虚拟存储器的概念回忆一下前面所介绍的各种存储管理方案。固定分区和可变分区存储管理要求把作业一次全部装入到一个连续的存储分区中；分页式存储管理也要求把作业一次全部装入，但是装入到的存储块可以不连续。但无论如何，这些存储管理方案都要求把作业“一次全部装入”。,这就带来了一个很大的问题：如果有一个作业太大，以至于内存都容纳不下它，那么，这个作业就无法投入运行。多年来，人们总是受到小内存与大作业之间矛盾的困扰。在多道程序设计时，为了提高系统资