第4章操作系统

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