《第4章操作系统.ppt》由会员分享，可在线阅读，更多相关《第4章操作系统.ppt（195页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4章存储管理4.1 存储管理的基本概念 4.2 早期的存储管理 4.3 分页存储管 4.4 请求分页存储管理 4.5 分段存储管理 4.6 段页式存储管理4.7 Windows NT虚拟内存管理 4.8 小结 习题 第4章存储管理4.1.1 存储管理研究的课题存储管理研究的课题众所周知，在单道程序阶段，人们就已经意识到存储资源的不足，并开始研究用覆盖技术来解决程序长度超过主存可用空间时程序的运行问题。在多道程序出现之后，这种要求就更为突出，而且又提出存储器的分配(即共享)问题。由于多道程序(或多作业，或多进程)共享一个主存，因此必须考虑各程序之间有意或无意地互相侵犯和破坏的问题，即考虑对它们
2、的保护问题。又因为用户程序或非常驻系统程序是随机、动态地纳入系统，所以不论是用户还是系统，均不能预先知道这些程序将要放在内存中什么位置。4.1 存储管理的基本概念存储管理的基本概念第4章存储管理这就要求人们必须改变以前那种按绝对地址编写程序的观念。因此，我们应该研究地址转换或地址再定位问题。综上所述，目前关于存储管理的主要研究课题可归纳为以下四个方面：(1)存储分配问题：重点是研究存储共享和各种分配算法。(2)地址再定位问题：研究各种地址变换机构，以及静态和动态再定位方法。(3)存储保护问题：研究保护各类程序、数据区的方法。(4)存储扩充问题：主要研究虚拟存储器问题及其各种调度算法。第4章存储
3、管理4.1.2 地址再定位地址再定位1.地址空间和存储空间地址空间和存储空间在我们用汇编语言或高级语言编写程序时，总是通过符号名来访问某一单元。我们把程序中由符号名组成的空间称为名空间。源程序经过汇编或编译后，再经过链接装配程序加工形成程序的装配模块形式，即转换为相对地址编址形式，它是以 0 为基址顺序进行编址的。相对地址也叫逻辑地址或虚地址，把程序中由相对地址组成的空间叫做逻辑地址空间。逻辑地址空间通过地址再定位机构转换到绝对地址空间。绝对地址空间也叫物理地址空间。第4章存储管理简单说来，逻辑地址空间(简称地址空间)是逻辑地址的集合，物理地址空间(简称存储空间)是物理地址的集合。程序的名空间
4、、地址空间和存储空间的关系如图 4.1 所示。第4章存储管理图 4.1 名空间、地址空间和存储空间 第4章存储管理2.地址的再定位地址的再定位上面已经指出，一个逻辑地址空间的程序装入到物理地址空间时，由于两个空间不一致，就需要进行地址变换，或称地址映射，即地址的再定位。地址再定位有两种方式：静态再定位和动态再定位。静态再定位是在程序执行之前进行地址再定位。这一工作通常是由装配程序完成的。例如在图 4.2 中的装配模块可以在执行前装入到内存始址为 50 KB的一段区域，也可以装到其它的内存连续区域中，其地址再定位过程如图 4.2 所示。第4章存储管理图 4.2 静态地址再定位 第4章存储管理静态
5、地址再定位的优点是容易实现，无需硬件支持，它只要求程序本身是可再定位的，即对那些要修改的地址部分具有某种标识。地址再定位由专门设计的程序来完成，在早期的操作系统中大多数都采用这种方法。其主要缺点是：(1)程序经地址再定位后就不能再移动了，因而不能重新分配内存，不利于内存的有效利用。(2)程序在存储空间中只能连续分配，不能分布在内存的不同区域。(3)若干用户很难共享内存中的同一程序，如若共享同一程序，则各用户必须使用自己的副本。第4章存储管理动态地址再定位是在程序执行期间，在每次存储访问之前进行的。在这种情况下，通常通过基地址寄存器、变址寄存器计算出指令的有效地址，再利用硬件机构实现地址变换。通
6、常采用的办法是利用一个再定位寄存器，对每一个有效地址都要加上再定位寄存器中的内容，以形成绝对地址，即存储空间的地址，而再定位寄存器中的内容就是程序装入内存区的起始地址。在图 4.3 中，把某一相对地址程序装入到地址 1000 开始的内存区域时，只要把 1000 装入再定位寄存器，程序即可运行。这一动态地址再定位的过程如图 4.3 所示。图中的BR是再定位寄存器，亦称基址寄存器。此外又增设了一个界限(或限长)寄存器LR，它用于防止该程序使用的地址超过程序的界限。第4章存储管理图 4.3 动态地址再定位第4章存储管理动态地址再定位的优点是：(1)在执行过程中，用户程序在内存中可以移动，这有利于内存
7、的充分利用。(2)程序不必连续存放在内存中，可以分散在内存的若干个不同区域，这只需增加几对基址-限长寄存器，每对寄存器对应一个区域。(3)若干用户可以共享同一程序。动态地址再定位的缺点是需要附加的硬件支持，实现存储管理的软件算法比较复杂。第4章存储管理4.1.3 虚拟存储器概念的引入虚拟存储器概念的引入为了给大作业(其地址空间超过主存可用空间)用户提供方便，使他们不再承担主存和辅存的具体分配管理工作，由操作系统把主存和辅存统一管理起来，实现自动覆盖。即一个大作业程序在执行时，有一部分地址空间在主存，另一部分在辅存，当访问的信息不在主存时，则由操作系统(而不是由程序员安排的I/O指令)把它从辅存
8、调入主存。从效果上看，这样的计算机系统，好像为用户提供了一个容量比主存大得多的存储器。这个存储器称为虚拟存储器。这样的存储器实际上并不存在，而只是在系统增加了自动覆盖功能后，使用户感到他有了一个很大的主存，在编写程序时再不受主存容量的限制了。第4章存储管理虚拟存储器的基本思想是把作业地址空间和实际主存的存储空间，视为两个不同的概念。一个计算机系统为程序员提供了一个足够大的地址空间，而完全不必考虑实际主存的大小。由此，可以引出虚拟存储器更一般的概念，即把系统提供的这个地址空间，想象成有一个存储器(虚存)与之对应，正像存储空间有一个主存与之对应一样。这就是说，虚拟存储器实际上是一个地址空间。第4章
9、存储管理根据地址空间结构不同，虚拟存储器有两种形式。一种是单段式虚存，它是一个连续的线性地址空间，其地址顺序为：0，1，2，n-1。其中n=2k,k为CPU给出的有效地址的长度。另一种是多段式虚存，它是把地址空间分成若干段，而每一段Si是一个连续的线性地址空间。每个地址可用Si,W来表示，Si为段名或段号，W为段内的相对地址。第4章存储管理一个虚存的最大容量由计算机的地址结构确定。若CPU给出的有效地址长度为18，则可以编址的范围是从 0 到 218-1，即容量为256 KB；若地址长度为24 位，则虚存容量为161024 KB(即 16 MB)。由此可见，虚存容量与主存(也称实存)大小没有直
10、接关系。虚存容量可以比实存大，也可以比实存小，而且在多道程序环境下，一个系统可以为每个用户建立一个虚存，每个用户可以在自己的地址空间(最大容量为虚存容量)内编程，这对用户来说是十分方便的。第4章存储管理在引入了虚拟存储器的系统中，一方面要在主存和辅存中交换信息，另一方面系统自动地将地址空间中给出的逻辑地址变换成主存的物理地址。这样，既消除了程序员的存储分配问题，又能实现根据主存的具体情况和用户作业实际需要完全动态地分配主存，从而使主存的利用率大大地提高了。第4章存储管理4.2.1 单一连续分配单一连续分配在早期的计算机或某些小型、微型机系统中，没有采用多道程序设计技术。每次只有一个用户作业使用
11、计算机。在用户使用计算机的整个过程中，占有了全部计算机资源，当然也包括主存资源。这时的存储管理方案是采用单一连续分配方案。4.2 早期的存储管理早期的存储管理第4章存储管理在单一连续分配方案中，存储器在概念上分成三个连续区域，其中之一固定给操作系统使用，其余部分由作业占用，但实际上作业只能占用一部分，最后总要剩下一块连续区域，这部分实际上是浪费了。例如，有一个容量为 256 KB的内存，一个简单的操作系统占用了 32 KB，剩下的224 KB全部分给用户作业。如果一个典型作业仅需 64 KB，那么就有 160 KB的存储区没有被利用，如图 4.4 所示。第4章存储管理图 4.4 单一连续分配第
12、4章存储管理对于上述单一连续分配方案，它不要求专用的硬件支持。但为实现存储保护，有时需要设置界限寄存器，以防用户作业侵犯操作系统。界限寄存器内置入被保护区(主要是操作系统)的地址。如果CPU处于算态工作方式，则对于存储器的每一次访问，硬件均要进行检验，以确保被保护区域不受侵犯。如果出现了用户程序对被保护区域的访问，便产生中断，控制转给操作系统。如果CPU在管态方式下工作，此时可以访问被保护的区域。第4章存储管理当操作系统的作业调度程序希望调度一个作业投入运行时，仅当内存中没有其它作业时才有可能。被调度的作业所需主存的大小仅当不超过可用的主存容量时，才能将其装入主存并投入运行，否则该作业无法运行
13、，而只能打印出错信息，通知操作员。单一连续分配方案的优点是方法简单，易于实现；缺点是：它仅适用于单道程序，因而不能使处理机和主存得到充分利用。第4章存储管理4.2.2 分区分配分区分配分区分配是能满足多道程序设计需要的一种最简单的存储管理技术，分区管理法也称界地址存储管理法。通常，按照分区的划分方式，它又可分为固定式分区、可变式分区、可再定位式分区和多重分区四种。第4章存储管理1.固定式分区法固定式分区法固定式分区法的基本思想是在系统生成时就将主存划分为若干个分区，每个分区的大小可以不等，但事先必须固定，以后也不能改变。譬如说，将主存的可用区域划分为五个分区，如图 4.5 所示。图 4.5(a
14、)为固定分区说明表，图 4.5(b)为主存空间的分区及分配图。当系统采用固定分区分配法时，首先由用户提出其作业所需的最大容量，然后由系统找出一个足够大的分区分配给它。例如有五个作业，其容量分别为 1 KB，9KB，9 KB，33 KB，121 KB，它们都将进入系统，此时系统可按表 4-1 分配给各分区。第4章存储管理图 4.5 固定式分区 第4章存储管理第4章存储管理在这种情况下，所有分区都是尽可能按最佳方式分配的，但在 712 KB的有效主存中实际上只用 173 KB，结果大约 75%以上的有效主存被浪费掉了。第4章存储管理2.可变式分区法可变式分区法可变式分区法也就是动态划分存储器的分区
15、方法，它是在作业装入和处理过程中建立的分区，并且要使分区的容量能正好适应作业的大小。在作业进入系统前，根据作业的大小来申请所需存储容量，然后由系统实施分配。系统为了管理主存分区分配情况，需建立两张表，分别登记已分配区和未分配区的分区容量、位置和状态信息。第4章存储管理图 4.6 给出了一个可变式分区管理的例子。在某一时刻，系统已分配了三个分区，留下两个空白区，如图 4.6(a)。两个表的形式如表 4-2 所示。现在假定又有三个作业要求进入系统，为此要在空白区内为它们开辟新的分区（图4.6WTBX（b）)，最后当一些作业完成时，相应的分区被释放，变成空白区（图4.6WTBX(c)）。显然，对于这
16、两种情况，相应的两个表均要作适当的修改。第4章存储管理图 4.6 可变式分区的例子第4章存储管理第4章存储管理现在我们来讨论在可变式分区管理中，请求和释放分区的算法。假定有一作业，它申请分配给它一个主存分区，于是它首先在未分配的分区状态表中查找一个空白区，该区的容量必须大于或等于该作业所要求的容量。如果它大于作业所需要的容量，则将其分成两份，一份分配给该作业，另一份变成较小的空白区。反之，当一个作业完成之后，将该作业所占用的分区释放，即将该分区变成空白区，并且将该空白区与邻接的空白区进行合并，使之成为一个较大的空白区。图 4.7、图 4.8 给出了可变式分区的请求和释放算法的流程。第4章存储管
17、理图 4.7 可变式分区中请求一个分区的流程第4章存储管理图 4.8 可变式分区中释放一个分区的流程第4章存储管理表 4-2(b)是未分配的分区状态表，即空白区表，各空白区的排列至少有如下几种方法，它们分别对应不同的算法。(1)最佳适应(Best Fit)算法。空白区表中的空白区按其容量以递增的次序排列。当要求分配一个空白区时，由小到大进行查找，即x1x2x3xn。如果要求分配一个分区其容量为S，则从x1开始顺序比较，直至Sxi；然后从xi中分配S，如有剩余部分，作为一个空白区将其插入适当的位置；如果比较到xn仍不能满足要求，则分配失败。第4章存储管理最佳适应算法的优点是：平均而言，只要查找一
18、半的表格便能找到最佳适应的空白区；如果有一个空白区的容量正好满足要求，则它必被选中；如果不存在恰好满足需要的空白区，则选中一个容量接近的空白区，而较大的空白区被保留下来。以后如果要求分配一个较大的空白区时，就容易得到满足。最佳适应算法的主要缺点是，空白区一般不可能恰好满足要求，在分配之后的剩余部分通常非常小，以致小到无法使用。换言之，发展下去最后剩下许多非常小的空白区(即碎片)。第4章存储管理(2)最差适应(Worst Fit)算法。与最佳适应算法相反，空白区按容量递减次序排列，即x1x2x3xn。如果要求的分区容量为S，并且x1S，则从x1中分配S；如有剩余部分，则将其插入适当位置；如果x1
19、S，则分配失败。第4章存储管理最差适应算法的优点是：只要比较S和x1就能判定能否满足要求，如满足要求便立即进行分配；x1分配后剩下的空白区可能比较大，仍能满足一般要求，可供以后使用。最差适应算法的缺点是各空白区比较均匀地减小，工作一段时间后就不能满足对于较大空白区的分配要求。(3)最先适应(First Fit)算法。空白区按地址大小递增顺序排列。对于要求分配的分区容量S，从头开始比较，直至找到满足xiS为止。如果满足，则从xi中分配S，剩余部分保留在空白区表中原来的位置。第4章存储管理最先适应算法的优点是：在释放内存分区时，如果有相邻的空白区就进行合并，使其成为一个较大的空白区；本算法的实质是
20、尽可能利用存储器的低地址部分，在高地址部分则保留较多的或较大的空白区，以后如果要求较大的空白区，就比较容易满足。最先适应算法的缺点是在低地址部分很快集中了许多非常小的空白区，因而在空白区分配时，搜索次数增加，影响了工作效率。第4章存储管理综上所述，固定式分区和可变式分区分配有如下三个优点：有助于多道程序设计；不受过多的硬件限制，只需要界地址寄存器，用于存储保护；所采用的算法大都比较简单，易于实现。第4章存储管理固定式分区和可变式分区分配有如下缺点：会产生一些碎片，这些碎片散布在存储器的各处，不能集中使用，因而降低了存储器的有效利用；分区的大小，受到主存容量的限制，这种方法无法扩充主存容量。解决
21、碎片问题的一种最简单办法是采用可再定位式分区分配。第4章存储管理3.可再定位式分区分配可再定位式分区分配可再定位式分区分配即浮动分区分配，是解决碎片问题的简单而有效的办法。其基本思想是移动所有被分配了的分区，使之成为一个连续区域，而留下一个较大的空白区，如图 4.9 所示。这好像在一个队列中有些人出列以后，指挥员命令队列向前(或向右)靠拢一样。这种过程我们称之为“靠拢”或“紧凑”。在一个队列中实现靠拢是简单的，然而各作业分区的移动却是复杂的。把一个作业移动位置后，通常无法保证程序在新位置上能够正确运行。这是因为一个程序总要涉及到基址寄存器、访问内存指令、访问参数表或数据结构的缘故。为此，应解决
22、程序的可再定位(浮动)问题。第4章存储管理图 4.9 可再定位式分区分配的靠拢过程第4章存储管理为解决程序浮动问题，使用模块装入程序，将程序的装配模块重新装入到指定位置，并从头开始启动执行。但这种办法有两个缺点，一是要花费较多的处理机时间，二是如果该程序已经执行了一段时间，则不能再从头开始，否则将引起混乱。较好的办法是采用动态再定位技术。本章第一节已经指出，当一个作业装入与其地址空间不一致的存储空间时，可在访问指令或数据时，通过再定位寄存器(或称浮动寄存器)来自动修改访问存储器的地址。因此，一个作业在主存中移动后，只需要改变再定位寄存器的内容即可。例如，将图 4.9(a)中的作业 4，从 35
23、2 KB开始的 24 KB内存区域移动到 320 KB开始的内存区域，其过程如图 4.10 所示。第4章存储管理图 4.10 利用浮动寄存器进行地址变换第4章存储管理由图 4.10 可以看出，在移动前，在 352 KB+50 处的指令“L1，352 KB+9800”被移动到 320 KB+50 处，数据 01557100 原在 352 KB+9800 处，现被移动到320 KB+9800 处了。为了使得程序能正确执行，这里设置了一个硬件寄存器，称为再定位寄存器或浮动寄存器，由它实现地址变换。当执行每条指令时，由处理机计算出有效地址。例如移动后处于320KB+50 处的指令“L1，352 KB+
24、9800”的有效地址为 352 KB+9800，为了能得到正确结果，操作系统应在浮动寄存器内置入一个常数-32 KB，即 320 KB-352 KB，在访问操作数之前，将浮动寄存器的内容与计算出的有效地址相加，得到实际的物理地址。第4章存储管理在这种情况下，指令L1，352 KB+9800 的执行，仍将位于 320KB+9800 处的数据 01557100 取至 1 号寄存器。应该指出，作业 4 的指令和数据在移到新的位置后都没有改变，每条指令在执行时是利用浮动寄存器自动完成地址变换的。这种浮动称为动态浮动。第4章存储管理可再定位分区分配算法和固定式(或可变式)分区分配算法基本相同。两者的差别
25、仅在于可再定位式分区分配需要将作业分区进行靠拢，以便减少碎片，使存储器的利用率提高。关于如何靠拢的问题已经给出了常用的方法，现在的问题是何时进行靠拢，也即是如何选择靠拢的时机问题。有两个时机可以选择，即：(1)当某个分区内的作业一完成，就立即靠拢。这样的靠拢操作是比较频繁的，由于实施程序的移动要花费较多的处理机时间，因此应尽可能减少靠拢操作的次数。第4章存储管理(2)在为某一作业请求一个分区时，当时内存没有足够大的空白区，但各空白区之和可以满足该作业存储要求，此时须进行靠拢操作。显然这样的靠拢比前述的靠拢次数要少得多，从而可以节省处理机时间。描述可再定位式分区分配算法的流程如图 4.11 所示
26、。综上所述，可再定位式分区分配技术把存储空间内的所有碎片集中起来统一使用，提高了存储器的使用效率。但是它也有一些缺点，例如，由于需要硬件支持，因而提高了计算机成本，降低了计算机速度，尤其是执行靠拢操作要花费不少计算机时间。第4章存储管理图 4.11 可再定位式分区分配算法流程第4章存储管理4.多重分区分配多重分区分配如果我们不想采用靠拢的办法，又想使存储器分区的碎片问题适当地得到解决，那么可以采用多重分区分配方案。通常一个作业由一些相对独立的程序段和数据段组成，如主程序、子程序、数据组等。这些程序段中的每一个在逻辑上必须是连续的，但是相应的各分区却不要求是连续的，只要有足够的保护措施就可以了。
27、例如一个要求 100 KB存储空间的作业，实际上由五个 20 KB的段组成时，则可以分配给该作业一个 100 KB的分区或者五个 20 KB的分区，或者两个 40 KB的分区和一个 20 KB的分区等等。这种给一个作业分配一个以上分区的方法，称为多重分区分配。采用这种方法时，作业可以在其执行期间申请附加的分区。第4章存储管理采用多重分区分配方案，可使存储空间的利用率提高。例如一个作业由两段组成，分别要求10 KB和 5 KB的存储空间，在我们前述的可变式分区分配方案中，如果没有一个 15KB以上的空白区，那么该作业便无法分配。但是它可能有两个较小的，比如两个10 KB的空白区，那么，在多重分区
28、分配方案中，该作业的存储要求仍可得到满足。但是，作业的分段越多，分区越小，结果使存储器分得过碎，以致造成没有较大的空白区。所以，分区太多反而是一个缺点。另外，实现多重分区要求更多的硬件支持，管理也比较复杂。第4章存储管理5.分区的保护措施分区的保护措施为了防止一个作业有意或无意地破坏操作系统或其它作业，应对各分区采取保护措施，通常采用界地址寄存器的办法，所以分区分配亦称界地址存储管理。在图 4.12 中，某作业所在的分区是 60 KB124 KB的连续区域，操作系统在该作业进入这一分区时，将下界地址寄存器置成 60 KB，上界地址寄存器置成 124 KB。在作业运行过程中,每访问一次存储器都要
29、计算一下存储地址D，并与该分区的上、下界进行比较。在正常情况下，应满足 60KBD124KB。如果访问地址超出了这一范围，便发生存储越界中断(属程序性中断)，此时控制自动转向操作系统，它将停止执行该作业，并输出错误信息。第4章存储管理图 4.12 分区的界地址寄存器保护第4章存储管理同样道理，也可以用基址、限长寄存器代替上、下界地址寄存器。即在我们的例子中，基址寄存器置成 60 KB，而限长寄存器置成 64 KB，基址寄存器实际上起再定位(浮动)寄存器的作用，它存放作业所在分区的首址。限长寄存器内存放作业地址空间的长度。在作业运行过程中，在访问存储器时所计算出的存储地址，如果超过限长，则发越界
30、中断信号。第4章存储管理顺便指出，上面我们讲了每个分区都要有一对硬件寄存器，或者是上、下界地址寄存器，或者是基址、限长寄存器。实际上是不必要的，也是不经济的。通常只要有一对硬件寄存器就够了。因为在多道程序环境下，各分区的作业在共行执行，某一作业在运行前，在硬件寄存器内装入对应分区的界地址，在终止运行后，硬件寄存器的内容连同其它信息(如PSW)一起保护到现场保护区，以便下次运行时重新装入。第4章存储管理6.分区分配方案的评价分区分配方案的评价分区分配方案的主要优点可归纳如下：(1)实现了主存的共享，因而有助于多道程序设计，更有效地利用了处理机和I/O设备，从而使系统的吞吐量和作业周转时间得到了相
31、应的改善。至于主存利用率，可变式分区比固定式分区高些，可再定位式分区则更高些。(2)相对于后面介绍的存储管理方式，本方案为实现分区分配所使用的表格、占用的存储容量相对较少，算法也相对简单。(3)实现存储保护的措施也比较简单。(4)多重分区分配方案能实现对子程序、数据段的共享。第4章存储管理分区分配的主要缺点有：(1)主存仍不能充分利用，除了可再定位式分区法外，都存在着严重的碎片问题。另外，即使不把存储器分碎，整个空白区也可能因容纳不下一个作业而造成浪费。例如，有156KB的存储空间可用，而某个作业序列是由 100 KB和 60 KB的作业组成的。如果分配了一个 100 KB的分区后，则剩下的
32、56KB存储空间就要浪费掉。(2)不能实现对主存的扩充。因此，作业的大小受到主存可用空间的限制。第4章存储管理(3)和单一连续分配一样，要求一个作业在执行之前必须全部装入主存，因此在主存中可能包含从未使用过的信息。(4)采用靠拢方法，虽然能解决碎片问题，但有时需移动大量信息，从而损失了处理机时间。(5)除多重分区外，几个共行作业之间不能共享存入主存的单一信息副本(如公用子程序、数据段等)。第4章存储管理上节我们讨论了可再定位(即浮动)式分区分配技术，使用这种分配技术可以消除碎片，使一些零散的空白区汇合成较大的连续的空白区，提高了主存的利用率。然而，由于各作业分区的靠拢花费了较多的处理机时间，使
33、得这一方法并不可取。实际上，那里我们提出了一条要求，就是每个作业占有的存储空间必须是连续的。现在，我们避开这一要求，寻找另外的途径，于是引进了分页存储管理技术。4.3 分页存储管理分页存储管理第4章存储管理4.3.1 分页原理分页原理前已指出，用户作业地址空间的起点与分区的物理位置无关，所以作业的地址空间通常从 0 开始。分页存储管理就是从逻辑地址空间到物理地址空间的一种变换，即 f:LS其中，L、S 分别表示逻辑地址空间和物理地址空间。第4章存储管理我们把逻辑地址空间划分为一些相等的片，这些片称为页面。同样，物理地址空间也被划分为同样大小的片，称为块。于是通过适当变换，就能使逻辑空间的一页对
34、应物理空间的一块。一个作业的逻辑地址空间的所有页面是邻接的，而变换到物理存储空间的各块可以不邻接。页面(或块)的大小可以任意规定，通常是 2 的幂，例如 1 KB、2 KB、4 KB等。图 4.13 给出页面大小为 1 KB的分页存储管理的例子。10 KB的物理地址空间被划分为 10 块。现在，三个作业：作业 1、作业 2 和作业 3 的地址空间分别被划分为 2、3、1 个页面。逻辑地址空间和物理地址空间的对应关系由称为页面变换表的PMT指出，PMT也可简称为页表。第4章存储管理图 4.13 分页存储管理第4章存储管理分页存储管理可以解决碎片问题，例如再有一个作业 4 要求2 KB的存储空间，
35、可将这剩余的两块分配给作业 4，0 页对应第 3 块，1 页对应第 9 块。第4章存储管理由图 4.13 可以看出，作业地址空间的所有页面都是邻接的，而为该作业分配的各存储块是可以不邻接的。那么，把一个作业分配在不连续的内存中，是否能保证作业执行的正确性呢?回答是肯定的。请看图 4.14，作业 2 的三个页面依次装入到内存的2、4、7 块。假定在 0 页 518 单元处有一取数指令L 1，2 KB+60，其操作数的有效地址为 2 KB+60，在第 2 页上 2 KB+60 单元有一常数 01557100，该指令要求将此常数取到 1 号寄存器。但是，存放此常数的页(页号为 2)被装入到主存的第
36、7 块。在主存中，当作业 2 执行到指令L 1，2 KB+60 时，取出操作数的地址是 2 KB+60，由作业 2 的页面变换表指出，第4章存储管理该页已变换到主存的第 7 块，于是在主存的第 7 块相应位置 7KB+60 处找到这一常数。由此可见，一个作业在主存中所分配的各块即使不连续，也能保证程序执行的正确性。之所以如此，是因为页面变换表在起作用。第4章存储管理图 4.14 页面变换表保证了作业的正确执行 第4章存储管理4.3.2 地址变换机构地址变换机构为了实现从逻辑地址空间到物理存储空间的地址变换，在硬件上必须提供一套地址变换机构。1.动态地址变换机构动态地址变换机构DAT首先，让我们
37、考察某计算机系统中的一条典型指令：L R1,D2(X2,B2)其中，X2、B2、D2 为第二操作数域使用的变址寄存器、基址寄存器和位移量，R1 是第一操作数域的通用寄存器。指令格式为 第4章存储管理指令的第二操作数的有效地址为 E2=(X2)+(B2)+D2该指令的有效地址占 24 位。因此，逻辑地址空间最大可达 224=16 MB。现在假定页面大小为 4 KB，于是逻辑地址空间最多可达 4096 个页面，每个页面 4096 个字节。于是 24 位的有效地址自然地被划分为两部分，前 12 位为页号，后 12 位为页内地址。第4章存储管理 动态地址变换机构自动地将所有地址划分为页号和页内地址两部
38、分。它利用PMT表将页号代之以块号，这样就得到了要使用的物理存储地址。图 4.15 给出了逻辑地址变换到物理存储地址的实例。假定原来作业 2 的 0 页上的一条取数指令L R1，D2(X2，B2)，由处理机产生一个有效地址为第4章存储管理 它表示该地址为页 2 的 144 号单元。根据PMT表得到块 7，在该块上的 144 号单元(144147)存放着该指令的第二操作数。第4章存储管理图 4.15 动态地址变换机构第4章存储管理每个作业都有一个页面变换表，通常各作业的页面变换表放在操作系统的一个工作区中，由页面变换地址寄存器(PMTAR)指出作业的页面变换表的起始地址。当处理机执行一个新作业或
39、恢复一个旧作业时，只要修改PMTAR的内容，使之指向要执行作业的PMT起始地址即可。假如某计算机系统的一个作业的逻辑空间最大为 16 MB，因此最多可有 4096 个页面，即一个作业的PMT表最多可包含 4096 项，而每项中包含的存储块号用 2 个字节表示，那么一个作业的PMT表最大需要 8192 个字节。然而由于大多数的作业都在 256 KB(64 页)以下，因此，大多数作业的PMT表不超过 128 个字节。图 4.16 给出了PMTAR、PMT、页面和块之间的关系。第4章存储管理图 4.16 PMTAR、PMT、页面和块之间的关系第4章存储管理2.高速页面变换寄存器高速页面变换寄存器为了
40、实现从作业地址空间到物理地址空间的变换，可采用硬件的高速寄存器来实现。因为任一时刻在处理机中只有一个作业在执行，所以只有一组高速寄存器就可满足要求。假定页面大小为 4 KB，那么对于 100 KB的作业来说，就需要 25 个高速寄存器。由于高速寄存器的成本高，因此它适用于地址空间小的作业。如果系统所接受的作业都在 64 KB以下，那么只需要 16 个寄存器就够了，每个寄存器的位数可根据主存的最大存储块号确定。在多道程序环境下，当处理机把控制转移到另一新作业时，应保存原作业的寄存器内容并重置相应于新作业的寄存器内容(即存储块号)。第4章存储管理3.联想存储器联想存储器页面变换表存放在主存中，由操
41、作系统实施管理，在作业执行时，每条指令的执行都必须进行地址变换。因此，每条指令都必须两次访问存储器：一次是把页号变成物理块号，另一次是实际存取所要的数据或指令，从而增加了指令执行的机器时间，影响了计算机的速度。另外，采用高速寄存器方法，如果作业地址空间较大，则所需的寄存器较多，所花的费用就较高。为此通常采用一种折衷办法来解决这一矛盾，即把高速寄存器作为DAT的辅助机构来实行地址变换。为了加快查表速度，在地址变换机构中加入一组高速寄存器(8 个或 16 个)，这些寄存器连同管理它们的硬件构成了一个容量较小的存储器，第4章存储管理称之为联想存储器，也称快表。在联想存储器中，存放正运行作业的当前最常
42、用的页号和相应块号，这个联想存储器具有并行查询能力。例如，CPU给出有效地址为(P、W)，地址变换机构自动地把页号P送入输入寄存器，随后立即和其中的所有页号比较，如与某个单元的页号符合，则把该单元的块号B送入输出寄存器。因而，我们就可以根据(B、W)来访问存储器，图 4.17 给出了利用联想存储器加速查表的过程。这个联想存储器的查找速度可以做到比一般随机存储器的速度快一个数量级。第4章存储管理图 4.17 利用联想存储器加速查表第4章存储管理在采用联想存储器的系统中，通常采用“双管齐下”的方针，既按给出的页号检索联想存储器中的相应块号，而同时又按PMT表进行查找块号，两者同时进行。在联想存储器
43、中，一旦检索到所要的块号，便立即停止PMT表的查找，这时利用联想存储器给出的块号访问主存。如果在联想存储器中检索不到所要的块号，应利用PMT表进行查找，并将页号以及所对应的块号一起填入联想存储器内的空白单元中。如果没有空白单元，应根据某种规则(如先进先出)淘汰一个单元内容后再行填入。在多道程序系统中，当把处理机的控制权由一道作业转到另一道作业时，相应地把控制寄存器(PMTAR)以及联想存储器内容加以更换。第4章存储管理4.3.3 分页存储管理算法分页存储管理算法为实现分页存储管理，在软件方面应建立如下表格，并由操作系统实施管理。(1)作业表(JT)。整个系统一张表。每个作业在作业表中对应一个表
44、目，包括该作业的页表始址、页表长度和状态信息。当作业调度程序调度到某个作业时，如果存储要求可以得到满足，就在此表上进行登记。当作业轮到处理时，就从此表把页表始址和页表长度送到控制寄存器中。(2)存储分块表(MBT)。整个系统一张表。该表中每一表目对应一个存储块，记录了该块的状态：已分配或空闲。第4章存储管理(3)页面变换表(PMT)。每个作业一张表。页面变换表，用于该作业的地址变换，该作业有多少页面就有多少表目，表目内记录对应的存储块号。图 4.18 给出了上述三种表格的结构及其关系。第4章存储管理图 4.18 分页存储管理的数据结构及其关系第4章存储管理上述三种表格都存放在操作系统所使用的工
45、作区内。当有一个作业进入系统时，就在作业表上登记页表的长度及状态信息，并为PMT表分配一个存储区，然后将PMT表的起始地址填入作业表中。最后搜索存储分块表，看有哪些存储块是空闲的，如有，则将作业号填入该表的相应表目中，用以指出“已分配”的状态，再把存储块号填入PMT表。当该作业所需的块数都分配完了时，系统便可按照PMT的内容对该作业进行处理。图 4.19 说明了分页存储管理分配算法的流程。当一个作业完成后，应将该作业所占用的存储区释放，读者不难画出分页存储的释放算法。第4章存储管理图 4.19 分页存储分配算法流程第4章存储管理4.3.4 分页存储管理方案的评价分页存储管理方案的评价综上所述，
46、分页存储管理方案不必像浮动分区法那样执行费时的靠拢操作，消除了碎片，便于多道程序设计，从而提高了处理机和主存的利用率。但分页存储管理仍然存在如下严重缺点：(1)采用动态地址变换会增加计算机成本和降低处理机的速度。(2)各种表格要占用一定容量的主存空间，而且还要花费一部分处理机时间用来建立和管理这些表格。第4章存储管理(3)虽然说碎片消除了，但每个作业的最后一页一般都有不能充分利用的空白区。例如，假定页面大小为 4 KB，如果某一作业需要 9 KB内存，则应该为它分配三个物理存储块，最后一块的 3 KB空间被浪费了。如果减少页面大小，若页面大小为 2 KB，则对于需要 9 KB内存的作业应分配
47、5 个存储块，其中有 1 KB的内存被浪费了。减少页面大小，可以减少内存的浪费，但PMT表的长度又增加了，这也是一个矛盾。(4)存储扩充问题仍未得到解决。当没有足够的可用空间能装下整个作业地址空间时，该作业还是无法运行的。下节的请求分页管理可以解决存储扩充问题。第4章存储管理到目前为止，关于存储管理已经讨论了存储分配、地址再定位以及存储保护问题，关于存储扩充问题仍未涉及，从本节起，讨论的重点转移到存储扩充问题。与此问题有密切联系的概念是虚拟存储器的概念。请求分页技术可以实现主存的扩充，它为每个用户提供一个虚拟存储器，其地址空间远比主存的存储空间大，一个作业的地址空间存在于一个虚拟存储器中。我们
48、把作业地址空间划分的页，称为虚页。相应地把主存称为实存，把实存中的块称为实页。4.4 请求分页存储管理请求分页存储管理第4章存储管理4.4.1 请求分页原理请求分页原理现在我们回到分页存储管理上来。首先考虑图 4.13，在主存中装入了三个作业后，还剩 2 KB的存储空间，即有两块(块 3，块 9)是空闲的。现在假定又有一个作业 4 要求装入主存运行，它需要 4 KB的主存，即需占 4 个存储块。而现在仅有两块，按照分页存储管理算法，此时无法分配，只好等待其它作业所占空间的释放。为了有效地利用主存，我们决定把作业 4 的 0 页和 1 页分别装入块 3 和块 9，而 2 页和 3 页没有空闲块就
49、暂不装入，让作业 4 先运行一段时间，即使很短也行。第4章存储管理如果作业 4 利用已占有的存储空间运行了一段时间后，那时情况也许会有所变化，或者某些作业已经完成，或者某些作业所占部分空间长久不用。于是我们就可以装入作业 4 的 2 页到空闲块或者将长久不用的存储块腾空后再行装入。作业 4 的0、1、2 页都进入主存后又可运行一段时间，当作业 4 的 3 页不在主存就不能运行时，就把作业 4 的3 页装入主存。在这种情况下，分页存储管理系统根据请求装入所需页面的方法，称为请求分页存储管理。第4章存储管理在请求分页存储管理中，必须解决如下几个问题：(1)如果一个作业不把它的整个地址空间同时全部装
50、入主存，那么该作业能否开始运行并运行一段时间?(2)在作业运行了一段时间后，必然要访问到没有装入的页面，也就是说，要访问的虚页不在实存。那么，这个问题系统是怎样发现的呢?(3)如果系统已经发现某虚页不在实存，就应将其装入实存。现在的问题是从何处装入，装入到何处，如果实存空间已满怎么办?上述三个问题是请求分页存储管理中的基本问题，如果这些问题能得到较好的解决，请求分页存储管理就可以实现。下面我们就来讨论这三个问题。第4章存储管理首先，当一个作业的地址空间不同时全部装入主存时，这个作业可以开始运行并能运行一段时间，其理由如下：(1)作业在运行期间的各个阶段，多数作业只使用全部地址空间的一部分。例如