自考操作系统概论-第3章

1、第3章 存储管理3.1计算机系统中的存储器假设把CPU中的存放器看作是一种特殊的存储器，那么，可把存储器分为：存放器、主存储器和高速缓冲存储器、辅助存储器包括磁带、软盘、硬盘、光盘等三个层次。处理器能直接访问存放器、主存储器和高速缓冲存储器，但不能直接访问辅助存储器。必须在输入输出控制系统的管理下，才能够使辅助存储器与主存储器之间相互传送信息。 3.1计算机系统中的存储器存放器是计算机系统中价格最昂贵的存储器。它的存取速度最快，但容量小，一般每个存放器只能存储一个字长的信息，故只用来存放临时的工作数据和控制信息。常用的存放器有：指令存放器用于存放当前从主存储器中读出的指令。通用存放器用于存放当

2、前参加运算的操作数、运算结果等。控制存放器用于存放控制信息以保证程序的正确执行和系统的平安。例如，程序状态字存放器存放当前PSW、基址存放器和界限存放器限定程序执行时可访问的主存空间的范围等都属于控制存放器。3.1计算机系统中的存储器主存储器的存储容量较大，存取速度也较快。存储单元以字节为单位进行编址。假设干个字节可组成一个字。处理器能按地址读/写一个字节或一个字。主存储器用于存放用户当前需执行的程序和数据，以及操作系统进行控制和管理的信息。高速缓冲存储器的存取速度快于主存储器，但造价要比主存储器高，因而存储容量不大。当存放在主存储器中的某些信息经常要被访问时，可以把这些信息复制到高速缓冲存储

3、器中，需要时就可以从高速缓冲存储器中直接读取信息，以提高程序的执行速度。3.1计算机系统中的存储器辅助存储器的存储容量很大，可用来长期存储信息，但处理器不能直接读/写辅助存储器上的信息。辅助存储器通常用业存放经常要用的程序、数据、等待处理的作业信息和作业的执行结果等。当要执行一个程序或处理一个作业时，必须把它们的程序和数据等信息读到主存储器中。当要保存运算结果时又可把在主存储器中的执行结果写到辅助存储器中。但从辅助存储器读/写信息时必须启动相应的外设，因此存取速度较慢。3.1计算机系统中的存储器从上述的简单介绍中可以知道，存放器是用来存放控制信息或供当前运行程序临时存放工作数据的。哪个进程占用

4、处理器，这些存放器就为哪个进程效劳，故不存在存放器的分配问题，主存储器和辅助存储器中经常存放多个程序和数据，经常会发生竞争存储空间的现象，因此合理的分配和使用存储空间是尤为重要的。对辅助存储器空间的管理将在下一章介绍。本章讨论如何对主存储器空间进行管理。由于操作系统自身必须占用主存储器的一局部存储空间，用来存放操作系统的程序、数据、管理信息如PCB以及操作系统与硬件的接口信息如新、旧PSW等，我们把这局部空间称为系统区。除系统区外的其余主存空间可用来存放用户的程序和数据，称为用户区。存储管理是对主存储器中的用户区域进行管理，包括主存空间的分配与回收、主存空间的共享与保护、地址转换以及主存空间的

5、扩充等工作。3.2重定位绝对地址和逻辑地址主存储器的存储单元以字节为单位，每个存储单元都有一个地址与其对应。假定主存储器的容量为n，那么该主存储器就有n个存储单元即n个字节的存储空间，其地址编号为：0，1，2，n-1。把主存空间的地址编号称为主存储器的绝对地址，与绝对地址对应的主存空间称为物理地址空间。采用多道程序设计技术后，往往在主存储器中同时存放多个用户作业，而每个用户不能预先知道自己的作业将被放到主存储器中的什么位置。这样用户编制程序时就不能使用绝对地址。为了方便用户，每个用户都可以认为自己作业的程序和数据存放在一组从“0地址开始的连续空间中。用户程序中使用的地址称为逻辑地址，与逻辑地址

6、对应的存储空间称为逻辑地址空间。3.2重定位重定位当用户作业进入计算机系统执行时，存储管理就要为其分配一个适宜的主存空间，这个分配到的主存空间可能是从某单元开始的一组连续地址空间。该主存空间的起始地址是不固定的。这样就会出现两个问题。一是作业中的逻辑地址经常与分到的主存空间的绝对地址不一致。二是每个逻辑地址也没有一个固定的绝对地址与其对应。例如，当某作业被装到主存中A单元开始的区域中，假设作业程序中指定访问K单元的话，那么实际应访问主存的A+K单元。但是当该作业被装到主存中B单元开始的区域中，那么作业程序中指定访问的K单元在主存中的实际位置应该是B+K单元。可见程序执行时不能按照其逻辑地址到主

7、存储器中存取信息，处理器必须按照绝对地址去访问主存储器才能保证程序的正确执行。为了保证作业的正确执行，必须根据分配给作业的主存空间对作业中指令和数据的存放地址进行重定位，即要把逻辑地址转换成绝对地址。把逻辑地址转换成绝对地址的工作称为重定位或地址转换。 3.2重定位重定位的方式可以有静态定位和动态定位两种。1.静态重定位在装入一个作业时，把作业中的指令地址和数据地址全部转换成绝对地址。由于地址转换工作是在作业执行前集中一次完成的，所以在作业执行过程中就无需再进行地址转换工作。这种定位方式称为静态重定位。图3-1指出了静态重定位的过程。假定作业中第8条指令是从032单元取出操作数3465执行加法

8、操作。那么，采用静态重定位方式把作业装入到分配到的主存区假定从100单元开始，那么第8条指令被放到108单元，指令中的逻辑地址032被转换成绝对地址132，操作数3465存放在132单元中。3.2重定位重定位的方式可以有静态定位和动态定位两种。2.动态重定位动态重定位是由软件和硬件相互配合来实现的。硬件设置一个基址存放器，当存储管理为作业分配了一个主存区域后，装入程序原封不动地把作业装入到所分配的区域中，然后把该主存区域的起始地址存入基址存放器中。在作业执行过程中，由硬件的地址转换机构动态地进行地址转换，在执行指令时只要把逻辑地址与基址存放器中的值相加就可得到绝对地址。这种定位方式是在指令执行

9、过程中进行的，所以称为动态重定位。图3-2指出了动态重定位的过程。3.2重定位采用动态重定位时，由于装入主存的作业仍保持原来的逻辑地址，所以必要时可改变它在主存中的存放区域。当作业被移到一个新区域后，只需要改变基地址存放器的值，使基址存放器的内容变为新区域的起始地址。这样在作业执行时，硬件的地址转换机构将按照新区域的起始地址与逻辑地址相加，转换成新区域的绝对地址，使作业仍可正确执行。采用静态重定位时，由于装入主存储器的作业信息已经都是用绝对地址指示，故作业在执行过程中是不能移动位置的。3.3单用户连续存储管理 单用户连续存储管理是一种最简单的存储管理方式。在这种管理方式下，操作系统占了一局部主

10、存空间，其余剩下的主存空间都分配给一个作业使用，即在任何时刻主存储器中最多只有一个作业，故适合于单道运行的计算机系统。个人计算机上可采用这种管理方式。图3-3是单用户连续存储管理的示意图。3.3单用户连续存储管理采用这种管理方式时，处理器中设置一个界限存放器Boundary Register,存放器的内容为当前可供用户使用的主存区域的起始地址。一般情况下，界限存放器中的内容是不变的。只有当操作系统功能扩充或修改时，改变了所占区域的长度，才更改界限存放器的内容。等待装入主存储器的作业排成一个作业队列，当主存储器中无作业或一个作业执行结束，可允许作业队列中的一个作业装到主存储器。作业总是被装到由界

11、限存放器指示的用户区起始地址a开始的区域。如果作业的地址空间小于用户区，那么它可只占用一局部，其余局部作为空闲区如图3-3中bc局部。不管空闲区有多大，都不用来装另一个作业。3.3单用户连续存储管理在分时系统中可用对换Swapping方式让多个用户的作业轮流进入主存储器执行。系统中必须要有一个大容量的高速辅助存储器例如磁盘，多个用户的作业信息都被保存在磁盘上，把一个作业先装入主存储器让它执行。以后在调度时，假设选中另一个作业，就换出已在主存储器中的作业并把选中的作业换入到主存储器中。以两个作业为例，对换的过程如图3-4所示。这两个作业按时间片轮转的方法轮流地被换出和换入。3.3单用户连续存储管

12、理3.3单用户连续存储管理由于单用户连续存储管理每次只允许一个作业装入主存储器，因此不必考虑作业在主存储器中的移动问题。于是可采用静态定位方式进行地址转换，即在作业被装入到主存储器时一次性地完成地址转换。硬件也不必有地址转换机构。但处理器在执行指令时要检查其绝对地址是否界限地址a，且最大地址c。假设绝对地址在规定的范围内，那么可执行，否那么产生一个“地址越界中断事件，由操作系统进行处理，以到达存储保护的目的。3.4固定分区存储管理固定分区存储管理是把主存储器中可分配的用户区域预先划分成假设干个连续区，每一个连续区称为一个分区。一旦划分好后，主存储器中分区的个数就固定了。各个分区的大小可以相同，

13、也可以不同，但每个分区的大小固定不变。每个分区可以装入一个作业，所以当有多个分区时，就可同时在每个分区中装入一个作业，但不允许多个作业同时存入在同一个分区中。这种管理方式适用于多道程序设计系统。图3-5是有三个分区的固定分区存储管理的示意图。主存空间的分配与回收怎样知道主存储器中哪个分区已被作业占用，哪个分区是空闲的呢？为此，存储管理设置了一张“分区分配表，用来说明各分区的分配和使用情况。表中指出各分区的起始地址和长度，并为每个分区设置一个标志位。当标志位为“0时，表示分区空闲，当标志位非“0时，表示分区已被占用。分区分配表的长度应根据主存储器中被划分的分区多少来决定。图3-6表示主存储器被分

14、成三个分区，其中分区2已装入了一个作业时的分区分配表。主存空间的分配与回收当作业队列中有作业要装入分区，存储管理分配主存区域时，先查分区分配表，选择标志为“0的分区。然后根据作业地址空间的长度与标志为“0的分区的长度比较，当有分区长度能容纳该作业时，那么把作业装入该分区，且把作业名填到占用标志位上。如果作业长度大于空闲分区长度，那么该作业暂时不能装入。作业运行结束时，根据作业名查分区分配表，从占用标志位的记录可知该作业占用的分区，把该分区的占用标志置成“0，表示该分区现在空闲了，可用来装入新作业。地址转换和存储保护由于固定分区管理方式是预先把主存划分成假设干个区，每个区只能用来装入一个作业，因

15、此作业在执行过程中是不会被改变存放区域的。于是可以采用静态重定位的方式把作业装入到分配的分区中去。为了实现存储保护，处理器设置了一对存放器，称为“下限存放器和“上限存放器见图3-5。当一个已经被装入主存储器的作业得到处理器运行时，进程调度应记录当前运行作业所在的分区号，且把该分区的下限地址和上限地址分别送入下限存放器和上限存放器中。处理器执行该作业的指令时必须核对：下限地址绝对地址上限地址如果上述不等式不成立，那么为防止破坏其他分区中的信息，硬件产生“地址越界中断事件，停止执行该指令，以到达存储保护的目的。运行的作业在让出处理器时，调度程序选择另一个可运行的作业，同时修改当前运行作业的分区号和

16、下、上限存放器内容，以保证处理器能控制作业在所在的分区内正确运行。如何提高主存空间的利用率用固定分区方式管理主存储器时，总是为作业分配一个不小于作业长度的分区。因此，有许多作业实际上只占用了分区的一局部，使分区中有一局部区域闲置不用，降低了主存空间的利用率。但固定分区方式管理简单，又能适合多道程序设计系统，所以对微型机多用户系统，例如IBM OS/MFT，采用这种方式管理是适宜的。为了提高主存空间的利用率，可以采用如下几种措施：1根据经常出现的作业的大小和数量来划分分区，尽可能使各个分区被充分利用。2划分分区时按分区的大小顺序排列，低地址局部是较小的分区，高地址局部是较大的分区。各分区按从小到

17、大的顺序依次记录在分区分配表中。于是只要顺序查找分区分配表就可方便地找出一个能满足作业要求的最小空闲区分配给作业。一方面使闲置的空间尽可能减少，另一方面又尽量保存较大的空闲区以利于大作业的装入。3按作业对主存空间的需求量排成多个作业队列，规定：每个作业队列中的各作业只能依次装入一个固定的分区中，每次装一个作业；不同作业队列中的作业分别依次装入不同的分区中；不同的分区中可同时装入作业；某作业队列为空时，该作业队列对应的分区也不用来装入其他作业队列中的作业，空闲的分区等到对应作业队列有作业时再被使用。图3-7是一种多个作业队列的固定分区法。图中队列1中的作业长度小于L1，规定它们只能被装入分区1；

18、队列2中的作业长度大于L1但小于L2，这些作业只能被装入分区2；队列3中的作业长度大于L2但小于L3，队列中的作业只能被装入分区3。采用多个作业队列的固定分区法能有效地防止小作业进入大分区，从而减少闲置的主存空间量。但是划分分区时应特别注意可能出现的作业大小和作业出现的频率，如果划分不得当，会造成某个作业队列经常是空队列，反而影响分区的使用效率。3.5可变分区存储管理可变分区存储管理不是预先把主存储器中的用户区域划成分区，而是在作业要求装入主存储器时，根据作业需要的主存空间大小和当时主存空间使用情况来决定是否为作业分配一个分区。因此分区的长度不是预先固定的，而是按作业的实际需求来划分的；分区的

19、个数也不是预先确定的，而是由装入的作业数决定的。主存空间的分配与回收系统初始启动时，主存储器中除操作系统占用局部外，把整个用户区看作是一个大的空闲区。当有作业要装入主存储器时，根据作业对主存空间的需要量，从空闲区中划出一个与作业长度一致的分区来装入作业，剩余局部仍为空闲区。当空闲区能满足需求时，作业可装入，当作业对主存空间的需要量超过空闲区长度时，那么作业暂时不能装入。图3-8是可变分区存储空间分配示意。由于分区的大小是按照作业的实际需求量来定的，因此能克服固定分区方式中分区空间不能被充分利用的缺陷。装入主存储器的作业执行结束后，它所占的分区被收回成为一个空闲区，这个收回后的空闲区仍可用来装作

20、业。随着作业不断地被装入和作业执行结束后的撤离，主存空间被分成许多分区，有的分区被作业占用，而有的分区是空闲的。 如图3-9所示，当一个空闲区用来装入一个作业后，该区被分成两局部，其中一局部被作业占用了，而另一局部又成为一个较小的空闲区，如作业F被装入后的情况。可见，采用可变分区方式管理主存储器时，主存储器中空闲区的数目和大小是在不断变化的。为了便于管理，必须设置一张空闲区表，用来记录空闲区的起始地址和长度。当有作业要装入主存储器时，在空闲区表中查找状态为“未分配的栏目，从中找出一个能容纳作业的空闲区。假设该空闲区大于作业长度，那么被分成两局部，一局部分配给作业，另一局部仍作为空闲区登记在表格

21、中。假设找到的空闲区正好等于作业，那么把该区分配给作业后，应把该栏目对应的状态改为“空状态。当有作业执行结束，收回该作业所占的主存空间后，应把收回区域的起始地址和长度登记在状态为“空的栏目中，且把状态改为“未分配。如果收回的区域正好与某一空闲区相邻，那么应将其连成一片后登记。 图3-10指出了主存空间的分配情况及其空闲区表的变化情况。可变分区管理可变分区管理方式常用的主存分配算法有：“最先适应分配算法，“最优适应分配算法，“最坏适应分配算法。1.最先适应分配算法每次分配时总是顺序查找空闲区表，找到第一个能满足作业长度要求的空闲区，分割这个找到的空间区，一局部分配给作业，另一局部仍为空闲区。这种

22、分配算法实现简单，但可能把大的主存空间分割成许多小的空闲区，在主存储器中形成许多不连续的空闲区，我们把这些不连续的空闲区称为碎片。碎片的长度有时不能满足作业的要求，碎片过多时使主存空间的利用率降低。作为改进，可把空闲区按地址顺序从小到大登记在空闲区表中。于是分配时总是尽量利用低地址局部的空闲区，而使高地址局部保持有较大的空闲区，有利于大作业的装入。但是这会给收回分区时带来一些麻烦，每当有作业归还分区时，必须调整空闲区表，把归还区按地址顺序插入到空闲区表的适当位置进行登记。可变分区管理2.最优适应分配算法 按作业要求从所有的空闲区中挑选一个能满足作业要求的最小空闲区，这样可保证不去分割一个更大的

23、区域，使装入大作业时比较容易得到满足。在实现这种算法时，可把空闲区按长度以递增次序登记在空闲区表中。分配时顺序查找空闲区表，因而总是从最小的一个空闲区开始查找，所以，当找到第一个能满足作业要求的空闲区时，一定就是所有能满足作业要求的分区中的最小一个分区。 采用最优适应分配算法，有时找到的一个分区可能只比作业要求的长度略大一些。这样经分割后剩下的空闲区就很小了。这种极小的空闲区往往无法使用，影响主存空间的使用率。当作业归还主存空间时，要把收回的空闲区按长度顺序插入登记到空闲区的适当位置。3.最坏适应分配算法 这种算法总是挑选一个最大的空闲区分割一局部给作业使用，使剩下的局部不至于太小，仍可供分配

24、使用。采用最坏适应分配算法时，空闲区表中的登记项可按空闲区长度以递减顺序排列，于是表中第一个登记项所对应的空闲区总是最大的。同样，在收回一个分区时必须把空闲区表调整成按空闲区长度的递减次序排列登记。图3-11是“最先适应、“最优适应和“最坏适应分配算法的例如。假定有一个作业要求分配13K长度的主存空间，按图3-11指出的空闲区情况，采用“最先适应分配算法时应分割长度为16K的空闲区，采用“最优适应分配算法时应分割长度为14K的空闲区，而采用“最坏适应分配算法时那么应分割长度为30K的空闲区。图中阴影局部为已被占用的主存区域。在可变分区管理方式下，收回主存空间时应检查是否有与收回区相邻的空闲区。

25、假设有，那么应合并成一个空闲区登记。图3-12是与收回区有下邻或上邻空闲区时的回收算法流程。图中使用了赋值符号“：=，它的含义是把右边的值赋给左边的变量。稍作改进可画出“有下邻、“有上邻、“既有上邻又有下邻空闲区的回收算法流程， 4.2 连续分配方式回收内存 当进程运行完毕释放内存时，系统根据回收区首址，在空闲分区链(表)中找到相应插入点，此时可能有四种情况：(1) 回收区与插入点的前一个分区F1邻接：将回收区与F1合并，修改F1的表项的分区大小(2) 回收区与插入点的后一个分区F2邻接：将回收区与F2合并，修改F2的表项的首址、分区大小4.2 连续分配方式(3) 回收区与插入点的前后两个分区

26、F1、F2邻接：将三个分区合并，使用F1的表项和F1的首址，取消F2的表项，大小为三者之和(4) 回收区既不与F1邻接，又不与F2邻接：为回收区单独建立新表项，填写回收区的首址与大小，根据其首址插到空闲链中的适当位置地址转换和存储保护采用可变分区方式管理时，一般均采用动态重定位方式装入作业。因此，要有硬件的地址转换机制作支持。硬件设置两个专用的控制存放器：基址存放器和限长存放器，以及一些加法线路、比较线路等。当作业可以占用处理器执行时，进程调度便把该作业所占分区的起始地址送入基址存放器，把作业所占分区的最大地址送入限长存放器。作业执行过程中，处理器每执行一条指令时都要由硬件的地址转换机构把逻辑

27、地址转换成绝对地址。当取出一条指令后，把该指令中的逻辑地址与基址存放器的内容相加即得到绝对地址。该绝对地址假设满足：基址存放器内容绝对地址限长存放器内容那么该绝对地址就是允许指令访问的主存单元地址。假设上述不等式不成立，那么说明绝对地址已超出了所分到的区域，这时应不允许访问，以到达存储保护的目的。 地址转换和存储保护基址存放器和限长存放器总是存放当前占用处理器的作业所占分区的始址和末址。一个作业暂时让出处理器时，应先把基址/限长存放器的内容保存到该作业所对应进程的进程控制块中，然后才可把新占用处理器的作业所占分区的始址和末址分别送入基址和限长存放器中。这样可保证暂时让出处理器的作业在再次得到处

28、理器时，随同恢复的现场信息而把它所占分区的始址和末址分别送入基址和限长存放器中。图3-13是地址转换的例如。 移动技术可变分区方式的存储管理采用动态重定位方式装入作业，因而对已在主存储器中的作业可根据需要改变存放位置。把作业从一个存储区域移到另一个存储区域的工作称为移动。采用移动技术有以下两个目的：1.集中分散的空闲区用可变分区方式管理主存储器时，可采用移动技术使分散的空闲区集中以容纳新的作业。当主存储器中各个空闲区的长度都不能满足作业的要求，而这些空闲区长度之和又大于作业所需长度时，那么可移动已在主存储器中的作业，使各个分散的空闲区连成一片，形成一个大的空闲区，从而能将作业装入，使主存空间充

29、分被利用。如图3-14bc所示。2.便于作业动态扩充主存一道作业在执行中要求增加主存量时，只需适当移动邻近作业就可增加它所占的连续区的长度，如图3-14d移动作业4来满足作业3的扩充要求。移动技术移动可集中分散的空闲区，提高主存空间的利用率，同时也为作业动态扩充主存空间提供了方便。但是，采用移动技术时必须注意以下问题：1.移动会增加系统开销我们把操作系统所占用的系统资源和所需的处理器时间称为系统开销。由于移动作业时要做信息的传送工作，并且作业被移动后使得作业占用的分区以及空闲区的位置和长度均发生了变化，因而必须修改相应的进程控制块中所保存的所占分区的始址以及空闲区表等信息。这些都将增加操作系统

30、的程序量，也就增加了操作系统占用处理器的时间，使系统开销增大。2.移动是有条件的不是任何一个作业都能随意被移动。例如，某个作业在执行过程中正在等待外围设备传送信息，那么就不能移动该作业。这是因为外围设备与主存储器之间的信息交换是按确定了的主存绝对地址进行传送的。如果这时改变了作业的存放区域，那么该作业就得不到从外围设备传送来的信息，或不能把正确的信息传送到外围设备。所以移动一道作业时，应先判定它是否在与外围设备交换信息。假设为否，那么可以移动该作业；假设是，那么暂时不能移动该作业，必须等信息交换结束后才可移动。于是，在采用移动技术的系统中，应尽可能地减少移动，以降低系统开销，提高系统效率。为此

31、，可改变作业装入主存储器的方式来到达减少移动的目的。图3-15给出了两种装入作业的方式。图3-15指出了主存储器中有四道作业，采用图3-15a的方式那么可减少移动。例如，作业J1执行结束撤离后，主存储器中有两个不连续的空闲区。假定有一个新的作业J5要装入，假设J5需要的主存量比任何一个空闲区都大，但不超过两个空闲区的总量，这时可移动已在主存储器中的作业。按图3-15a的方式，只要移动一道作业J3，而按图3-15b的方式，那么要移动三道作业J2、J3、J4才能把空闲区连在一起。可见，采用两头装入作业的方式可减少移动的作业数和信息量。3.6页式虚拟存储管理前面介绍的几种存储管理方式，要求作业的逻辑

32、地址空间连续地存放在主存储器的某个区域中。当主存储器中无足够大的区域时，那么作业无法装入，或必须移动某些作业后才能装入。是否有可能把作业的连续逻辑地址空间分散到几个不连续的主存区域，且仍能使作业正确执行？假设可行的话，那么既可充分利用主存空间又可减少移动所花费的开销。不仅如此，还可采用虚拟存储管理技术，实现在较小的主存空间里运行较大的作业。页式存储管理的根本原理页式存储管理是把主存储器分成大小相等的许多区，每个区称为一块。与些对应，编制程序的逻辑地址也分成页，页的大小与块的大小相等。这好似写一篇文章时，假设所用的稿纸每张可写400个字，那么这篇文章也就是400字为一页。页号 页内地址 分页式存

33、储器的逻辑地址由两局部组成：页号和页内地址。其格式为：位移量W页号P31 12 11 0地址结构确定了主存储器的分块的大小，也就决定了页面的大小。假定地址总长度为15位，其中页号占5位，页内地址占10位。这样，逻辑地址中可有32页，编号为031。每一页有1024个字节，编号为01023。显然，从地址结构来看，逻辑地址是连续的，在编制程序时无需考虑如何分页。当使用一组顺序的地址时，如果地址是01023，那么只使用了低10位地址局部，而高地址页号局部为“0，自然，这些地址是属第0页的。如果继续使用10242047的地址，实际上在地址结构中表现为页号局部是“1，而页内地址仍为01023个字节。依此类

34、推，一组顺序的连续地址自然地由地址结构被分页了。所以，在编制程序时仍只需用连续的逻辑地址。 页面大小页面大小应选地适中，应是2的幂，通常是512B8KB。位移量W页号P31 12 11 0在进行存储器分配时，总是以块为单位进行分配。一个作业的信息有多少页，把它装入主存时就给它分配多少块。但是分配给作业的主存块可以是不连续的，即作业信息可以按页分散存放在主存的空闲块中。采用见缝插针的方法，主存储器中哪一块空闲，它就可被用业存放作业的一页信息。这防止了为得到连续的存储空间而进行的移动。如图作业执行时根据逻辑地址中的页号找到所在的主存块号，再确定当前指令应访问的主存绝对地址。页式存储管理必须解决两个

35、关键的问题：第一，怎样知道主存储器中哪些块已被占用，哪些块是空闲的；第二，作业信息被分散存放后如何保证作业的正确执行。n页5页4页3页2页1页0页用户程序59483623120页号块号页表内存203456789101页表的作用：页式主存空间的分配与回收页式存储管理把主存储器的可分配区域按页面大小分成假设干块，主存空间按块为单位进行分配。可用一张主存分配表来记录已分配的块和尚未分配的块以及当前剩余的空闲块数。由于块的大小是固定的，所以可以用一张“位示图来构成主存分配表。例如，假设主存储器的可分配区域被分成256块，那么可用字长为32位的8个字的位示图来构成主存分配表。 位示图中的每一位与一个块对

36、应，用0/1表示对应块为空闲/已占有，另用一字节记录当前剩余的空闲块数，如图3-17。进行主存分配时，先查空闲块数能否满足作业要求。假设不能满足，那么作业不能装入。假设能满足，那么找出为“0的一些位，置上占用标志“1，从空闲块数中减去本次占用块数，按找到的位计算出对应的块号，作业可装到这些块中。根据为“0的位所在的字号和位号，按如下公式可计算出对应的块号：块号=字号字长位号当一个作业执行结束时，应收回作业所占的主存块。根据归还的块号计算出该块在位示图中对应的位置，将占用标志改为“0，再把归还块数加到空闲块数中。假定归还块的块号为i，那么在位示图中对应的位置为：字号=i/字长，位号=i mod字

37、长其中 表示取i被字长除后的整数局部，而mod表示取其余数局部。页表和地址转换当主存中空闲块数能满足作业要求时，存储管理就找出这些空闲块分配给作业，同时为作业建立一张页表，指出逻辑地址中页号与主存中块号的对应关系。页表的一般格式如下：每个作业的页表长度是不同的。页表的长度由作业所占页的多少而定。对于图3-16中的作业A，它共有四页，因而作业A的页表长度应为四个登记项。根据作业A得到的主存空间，操作系统为它建立一张页表，如图3-18所示。 页式存储管理也是采用动态重定位的方式装入作业，作业执行时由硬件地址转换机构来完成从逻辑地址到绝对地址的转换工作。在作业执行过程中，处理器每执行一条指令时，都要

38、让地址转换机构按逻辑地址中的页号查页表，得到该页对应的主存块号，再按逻辑地址中的页内地址换算出欲访问的主存单元的绝对地址。由于块的长度都是相等的，所以地址转换的一般公式为：绝对地址=块号块长+页内地址实际上，由于分块和分页的大小是一致的，再利用二进制乘法的特性，所以只要把逻辑地址中的页内地址作为绝对地址中的低地址局部，而根据页号从页表中查得的主存块号作为绝对地址中的高地址局部，就能得到应访问的主存储器的绝对地址。 图3-19是分页式存储管理地址转换例如。 页表长度页表始址页表寄存器页内地址页号(3)逻辑地址L物理地址b1块号页号01234+越界中断页表分页系统的地址变换机构：因此，虽然作业被存

39、放在假设干个不连续的块中，但在作业执行中总是能按确切的绝对地址进行存取，保证了作业的正确执行。但是，页式存储管理中的页表一般是存放在主存储器中的，于是，当要按给定的逻辑地址进行读写时，必须访问两次主存。第一次按页号读出页表中对应的块号，第二次按计算出来的绝对地址进行读写。这样就延长了指令的执行周期，降低了执行速度。为了提高存取速度，通常都设置一个小容量的高速缓冲存储器。高速缓冲存储器可根据指定的特征，对每个存储单元进行并行查找，因而查找速度极快，但造价很高，故一般都是小容量的，例如816个存储单元。 利用高速缓冲存储器存放页表的一局部，把存放在高速缓冲存储器中的局部页表称为快表。快表中登记了页

40、表中的一局部页号与主存块号的对应关系。根据程序执行局部性的特点，在一段时间内总是经常访问某些页，假设把这些页登记在快表中，那么可快速查找并提高指令执行速度。有了快表后，地址转换过程如图3-20所示。根据逻辑地址中的页号同时查快表和页表，假设该页已登记在快表中，那么停止在主存中查页表的工作，并按快表中得到的对应块号与逻辑地址中的页内地址形成绝对地址；假设该页没有登记在快表中，那么从页表中得到对应的块号，再与逻辑地址中的页内地址合成绝对地址，同时将该页登记到快表中，以便下次再访问该页时加快查找速度。由于快表容量较小，当快表被填满后，又要在快表中登记新页时，就必须淘汰快表中的一个旧登记项。最简单的淘

41、汰策略是“先进先出，即总是淘汰最先登记的那一页。页表长度页表始址页表寄存器页内地址页号(3)逻辑地址Ldb物理地址+越界中断b1块号页号页表具有快表的分页系统的地址变换机构：b块号页号快表输入寄存器采用快表的方法后，使得地址转换的时间大大下降。假定访问主存的时间为200毫微秒，访问高速缓冲存储器的时间为40毫微秒，高速缓冲存储器为16个单元时，查快表的命中率可达90%。于是，按逻辑地址转换成绝对地址进行存取的平均时间为：200+4090%+200+20010%=256毫微秒。而不使用快表时需要两次访问主存，其时间是：2002=400毫微秒。两者相比，前者减少了144毫微秒，即所需时间下降了14

42、4400=36%。整个系统只设置一个高速缓冲存储器，只有占用处理器者才能使用它。由于快表是动态变化的，所以，当占用处理器的作业让出处理器时，应把该作业的快表保护到它的进程控制块中。当能再次占用处理器时，就可把它的快表恢复到高速缓冲存储器中。 页的共享和保护页式存储管理有利于实现多个作业共享程序和数据。在多道程序设计系统中，编译程序、编辑程序、解释程序、公共子程序、公共数据等都是可共享的。这些共享的信息在主存储器中只要保存一个副本。各作业共享这些信息时可使它们各自的页表中有关表目指向共享信息所在的主存块。图3-21是页面共享的示意。页的共享可节省主存空间，但实现信息共享必须解决共享信息的保护问题

43、。通常的方法是在页表中增加一些标志，指出该页的信息可读/写或只读或可执行，等等。如图3-21中规定了共享程序只可执行，共享数据只可读。处理器在执行指令时要进行核对，欲想向只读块写入信息就停止执行指令并产生中断。什么是虚拟存储器在前面介绍的各种存储管理方式中，必须为作业分配足够的存储空间，以装入有关作业的全部信息。但在程序运行中，我们发现，程序的有些局部是彼此互斥的，即在程序的一次运行中，执行了这局部程序就不会去执行那局部程序。例如，错误处理局部仅在有错误的情况下才会运行。另一方面，程序的执行往往有局部性，某一时刻可能会循环执行某些指令或屡次地访问某一局部的数据。所以，当把有关作业的全部信息都装

44、入主存储器后，作业执行时实际上不是同时使用这些信息，甚至于有些局部在作业执行的整个过程中都不会被使用到。于是，提出了这样的问题：能否不把作业的全部信息同时装入主存储器，而是将其中一局部先装入主存储器，另一局部暂时存放在磁盘上，作业执行过程中要用到那些不在主存储器中的信息时，再把它们装到主存储器中。如果这个问题能够解决的话，当主存空间小于作业需求量时，作业也能执行，这就使得主存空间能被充分地利用，进而用户编制程序时可以不必考虑主器的实际容量，允许用户的逻辑地址空间大于主存储器的绝对地址空间，对用户来说，好似计算机系统具有一个容量很大的主存储器，称为虚拟存储器。虚拟存储器虚拟存储器的容量由计算机的

45、地址结构和辅助存储器如磁盘的容量决定，与实际主存储器的容量无关。所以，虚拟存储器实际上是为扩大主存容量而采用的一种管理技巧。实现虚拟存储管理必须解决三个关键问题：怎样知道当前哪些信息已在主存储器中，哪些信息尚未装入主存储器中？如果作业要访问的信息不在主存储器中，怎样去找到这引起信息且把它们装入到主存储器中？在把欲访问的信息装入主存储器时，发现主存储器中已无空闲区域，又该自怎么办？页式虚拟存储管理的实现1.实现原理对采用页式管理的存储器来说，能被方便地改造成虚拟存储器。改选的方法很简单，只需将作业的全部信息作为副本存放在磁盘上，作业调度选中一个作业时，至少把作业的第一页信息装入主存储器，在作业执

46、行过程中欲访问不在主存储器中的页时，再把它们装入。为此需要对页表进行改造。首先应在页表中指出哪些页已在主存储器中，哪些页还没装入主存储器，并且指出每一页副本在磁盘上的位置，例如：可将页表修改成如下形式：标志位用来指出对应页是否已经装入主存储器。如果某页对应栏的标志位为“1，那么表示该页已经在主存储器中。此时从“主存块号中可得知该页在主存储器中占用的是哪一块。如果标志位为“0，那么表示该页不在主存储器中。这时根据在磁盘上的位置可从磁盘上找到该页信息，必要时把它装入主存储器。然后，在作业执行中访问某页时，由硬件的地址转换机构查页表。假设该页对应标志位为“1，那么按指定的主存块号进行地址转换，得到绝

47、对地址。假设该页标志位为“0，那么由硬件发出一个“缺页中断，表示该页不在主存储器中。操作系统必须处理这个缺页中断。处理的方法是先查看主存储器是否有空闲块。假设有，那么按该页在磁盘上的位置读出该页，且把它装入主存储器中，并在页表中填上该页所占主存块号，修改该页标志。当要访问的页被调入主存储器后，再重新执行被中断的指令就可找到要访问的主存单元。 图3-22指出当访问的页不在主存储器中时，将其调入的过程示意。 2.页面调度如果欲调入一页时，主存储器中已没有空闲块，那么必须先调出已在主存储器中的某一页，再将当前所需的页调入，同时对页表作相应的修改。采用某种算法选择一页暂时调出，把它存放到磁盘上去让出主

48、存空间，用业存放当前要使用的页面，这一过程称为页面调度。假设被页面调度选中调出的页又要被访问，那么可用类似的方法调出另一些页面而将其调入。页面调度算法的选择是很重要的。如果选用了一个不适宜的高度算法就会出现这样的现象：刚被调出的页又立即要用，因而又要把它调入；而调入不久又被调出；调出不久又再次被调入。如此反复，使调度非常频繁，以至于使大局部时间都花费在来回调度上，这种现象称为抖动，又称颠簸。因而应该选择一种好的调度算法，以减少和防止抖动现象。常用的页面调度算法有：先进先出调度算法总是把先进入主存储器的页面先调出，最近最久未使用高度算法距当前最长时间内没有使用过的页面先调出，最近最不经常使用调度

49、算法在最近一段时间内使用次数最少的页面先调出等。 1先进先出调度算法First-In-First-Out,缩写为FIFO这种调度算法总是淘汰最先进入主存储器的那一页。FIFO算法简单，易实现。一种实现方法是把装入主存储器的那些页的页号按进入的先后次序排成队列页号队列，用指针K指示当前调入新页时应淘汰的那页在队列中的位置，最初应指向队首位置。每当调入一个新页后，在指针指示的位置上填上新页页号，然后指针K加1，指向下一个应淘汰的页。图3-23指出要装入第3页时，采用FIFO算法的例如。这里指针K是循环指针，假定页号队列中有n个页号，每次调出一页后，执行K：=K+1mod n依次要访问的页号为：7，

50、0，1，2，0，3，0，4，2，3，0，3，2，1，2，现在只有三个主存块可供使用，把开始的三页先装入主存。执行时按FIFO算法进行页面调度，将产生9次缺页中断，页面装入和调出的情况如下：这种算法是基于最早进入主存储器的页不再被使用的可能性比最近调入主存储器的页不再被使用的可能性大。但如果某一页要经常地被访问，而它在一定的时间以后就会变成最早进入主存储器的页，这时假设把它调出了，那么可能立即又要被调入。 2最近最久未使用调度算法Least Recently Used,缩写为LRU 最近最久未使用调度算法是基于程序执行的局部性理论，即程序一旦访问到某些位置的数据或指令时，可能在一段时间里会经常访

51、问它们。先进先出算法是淘汰在主存储器中呆得最久的那一页，而不管它是否经常要被用到。最近最久未使用调度算法认为：最近经常被使用到的页很可能马上还要被访问，因此不能把它调出。相反，如果在过去一段时间里没有被访问过的页，在最近的将业也可能暂时不会被访问。所以需要装入新页时，应选择在最近一段时间里最久没有被使用过的页调出。 2最近最久未使用调度算法Least Recently Used,缩写为LRU 实现这种算法的一种方法是在页表中为每一页增加一个“引用位标志，记录该页面自上次被访问以来所经历的时间，每访问一次都应重新计时。当产生缺页中断而要装入新页时，检查页表中各页的引用位，从中选出计时值最大的那一

52、页调出即最久没有被使用过的页，并且把所有的引用位全部置“0，重新计时。这样，当再一次产生缺页中断时，又可找到最近一段时间里最久没有被使用过的页。这种实现方法必须对每一页的访问情况时时刻刻加以记录和更新，实现起来比较困难，且开销也大。在实际应用中，也可用页号队列的方法，这种方法能方便地正确选出最近最久未使用的页。队列中存放当前在主存中的页，但不需要使用指针。规定队首总是为最久未使用的页，而队尾总是最近才被访问的页。因此，每访问一页时就要对队列调整一次，把当前访问的页调到队尾。每当发生缺页中断时总是选择队首所指示的页面调出。我们还是用FIFO算法中的例子，把最先三页装入主存的情况下来看LRU算法的

53、调度情况。可见，用LRU调度算法选择调出的页面，总共产生7次缺页中断。3最近最不经常使用调度算法Least Frequently Used,缩写为LFU 这种算法是基于在过去一段时间里被访问次数多的页可能是经常需要用的页，所以应调出被访问次数少的页。一种简单的实现方法是为每一页设置一个计数器。每当访问一页时，就把该页对应的计数器加1，隔一个周期T，把所有计数器清0。当发生缺页中断时，选择计数值最小的页，它是最近一段时间里最不常用的页，可把它调出，同时把所有计数器清0。这个算法的关键是要选择一个适宜的周期T。多级页表现代计算机普遍采用页式虚拟存储管理，且为用户提供较大的逻辑地址空间。例如，Win

54、dows2000供用户使用的逻辑地址空间由32位组成，规定页面即块的长度为4096个字节，即页内地址占用了逻辑地址中的12位，余下的20位用于页号局部。2的20次幂为1兆，即允许每个用户程序最多可以用100万个页面。100万个页面在页表中就要占100万个表项，这张页表就非常庞大。假设以每个页表表项占用4个字节计算，那么一张页表就要占用400万个字节的连续主存空间。如果是多道并行工作，那么为每个用户都要建立一张页表，多张页表就要占用更多的主存空间，使得主存空间的开销实在太大了。实际上，我们已经知道程序的执行是有局部性的，在一段时间里只涉及到一局部页，因而，也只会在这些页所对应的页表表项中进行查找，而不会去查找另一局部页所对应的页表表项。因此，就没有必要把整张页表一直保存在主存中。正因为此，现在很多系统都采用多级页表结构，如Windows2000就采用了二级页表结构。我们以32位逻辑地址为例来阐述二级页表的原理。把32位逻辑地址分成三局部，其中低12位是页内地址，把高20位的页号分成两局部，每一局部各占10位。其格式如下：由于逻辑地址是连续的，所以这实际上是把页分成了1