操作系统教程课件：第四章存储管理

《操作系统教程课件：第四章存储管理》由会员分享，可在线阅读，更多相关《操作系统教程课件：第四章存储管理（125页珍藏版）》请在金锄头文库上搜索。

1、机械工业出版社操作系统教程课件第1页第四章第四章存储管理存储管理4.1 存储管理概述存储管理概述4.2程序的装入与链接程序的装入与链接4.3连续存储空间管理连续存储空间管理4.4 页式存储管理页式存储管理4.5 段式存储管理段式存储管理4.6 段页式存储管理段页式存储管理4.7 虚拟存储管理方式虚拟存储管理方式本章小结本章小结机械工业出版社4.1存储管理概述存储管理概述n存储器用于存放程序存储器用于存放程序(指令指令)、操作数、操作数(数据数据)以及操作以及操作结果。计算机系统中，存储器一般分为主存储器和辅助存结果。计算机系统中，存储器一般分为主存储器和辅助存储器两大类。储器两大类。CPU可以

2、直接访问主存储器中的指令和数据，可以直接访问主存储器中的指令和数据，但不能直接访问辅助存储器。在但不能直接访问辅助存储器。在I/O控制系统管理下，辅助控制系统管理下，辅助存储器与主存储器之间可以进行信息传递。存储器与主存储器之间可以进行信息传递。n主存储器简称主存，或称为内存。主存可分为系统区主存储器简称主存，或称为内存。主存可分为系统区和用户区两个区域。和用户区两个区域。n存储管理是对主存中的用户区进行管理，其目的是尽存储管理是对主存中的用户区进行管理，其目的是尽可能地方便用户和提高主存空间的利用率，使主存在成本、可能地方便用户和提高主存空间的利用率，使主存在成本、速度和规模之间获得较好的权

3、衡。速度和规模之间获得较好的权衡。操作系统教程课件第2页机械工业出版社4.1.1存储器的存储结构存储器的存储结构n在现代计算机系统中，存储部件通常是采用层次结构来在现代计算机系统中，存储部件通常是采用层次结构来组织，以便在成本、速度和规模等诸因素中获得较好的性组织，以便在成本、速度和规模等诸因素中获得较好的性能价格比。能价格比。n现代通用计算机，存储层次至少应具有三级：最高层现代通用计算机，存储层次至少应具有三级：最高层为为CPU寄存器，中间层为主存，最底层为辅存。在较高档寄存器，中间层为主存，最底层为辅存。在较高档的计算机中，还可以根据具体的功能分工细划为寄存器、的计算机中，还可以根据具体的

4、功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、磁盘、可移动存储介质高速缓存、主存储器、磁盘缓存、磁盘、可移动存储介质等组成等组成操作系统教程课件第3页机械工业出版社4.1.1存储器的存储结构存储器的存储结构n如图如图4-1所示，在存储层次中越往上，存储介质的访问所示，在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也较小。速度越快，价格也越高，相对存储容量也较小。操作系统教程课件第4页其中，寄存器、高速缓存、主存储其中，寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储管理的管辖范畴，掉电后它们存储的信息

5、不再存在。固定磁盘和可移的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。畴，它们存储的信息将被长期保存。而磁盘缓存本身并不是一种实际存而磁盘缓存本身并不是一种实际存在的存储介质，它依托于固定磁盘，在的存储介质，它依托于固定磁盘，提供对主存储器存储空间的扩充提供对主存储器存储空间的扩充。图4-1 计算机系统存储器层次机械工业出版社4.1.2存储管理的功能存储管理的功能1主存空间的分配和去配主存空间的分配和去配2实现地址转换实现地址转换3主存空间的共享和保护主存空间的共享和保护4主存空间的扩充主存空间的扩充操作系统教程课件第

6、5页机械工业出版社4.2.1物理地址和逻辑地址物理地址和逻辑地址n主存储器的存储单元以字节（每个字节为主存储器的存储单元以字节（每个字节为8个二进制位）个二进制位）为单位编址，每个存储单元都有一个地址与其相对应。假为单位编址，每个存储单元都有一个地址与其相对应。假定主存储器的容量为定主存储器的容量为n，则该主存就有，则该主存就有n个字节的存储空间，个字节的存储空间，其地址编号为其地址编号为0，1，2，n1。这些地址称为主存储器。这些地址称为主存储器的的“物理地址物理地址”（绝对地址），由物理地址所对应的主存空（绝对地址），由物理地址所对应的主存空间称间称“物理地址空间物理地址空间”。n在多道程

7、序设计系统中，主存中同时存放了多个用户在多道程序设计系统中，主存中同时存放了多个用户作业。每次调入运行时，操作系统将根据主存的使用情况作业。每次调入运行时，操作系统将根据主存的使用情况为用户分配主存空间。为了方便程序的编制，每个用户可为用户分配主存空间。为了方便程序的编制，每个用户可以认为自己作业的程序和数据存放在一组以以认为自己作业的程序和数据存放在一组以“0”地址开始的地址开始的连续空间中。用户程序中所使用的地址称为连续空间中。用户程序中所使用的地址称为“逻辑地址逻辑地址”，由逻辑地址对应的存储空间称为由逻辑地址对应的存储空间称为“逻辑地址空间逻辑地址空间”。操作系统教程课件第6页机械工业

8、出版社4.2.2程序的装入程序的装入n将一个用户的源程序装入主存中并执行，通常需要经将一个用户的源程序装入主存中并执行，通常需要经过以下几个步骤：首先编译，由编译程序过以下几个步骤：首先编译，由编译程序(Compiler)将用将用户源代码编译成若干个目标模块（户源代码编译成若干个目标模块（ObjectModule）；然）；然后链接，由链接程序（后链接，由链接程序（Linker）将编译后形成的一组目标）将编译后形成的一组目标模块以及它们所需要的库函数链接在一起，形成一个完整模块以及它们所需要的库函数链接在一起，形成一个完整的装入模块的装入模块(LoadModule)；最后装入，由装入程序；最后装

9、入，由装入程序(Loader)将装入模块装入主存。将装入模块装入主存。如图如图4-2所示所示。操作系统教程课件第7页机械工业出版社4.2.2程序的装入程序的装入将将一一个个装装入入模模块块装装入入主主存存，可可以以有有绝绝对对装装入入方方式式、静静态态重定位装入方式和动态重定位装入方式。重定位装入方式和动态重定位装入方式。1绝对装入方式绝对装入方式 如果在编译时知道程序驻留在主存的具体位置，则编译如果在编译时知道程序驻留在主存的具体位置，则编译程序将产生物理地址的目标代码。绝对装入程序按照装入模程序将产生物理地址的目标代码。绝对装入程序按照装入模块中的地址，将程序和数据装入主存。模块装入后，由

10、于程块中的地址，将程序和数据装入主存。模块装入后，由于程序中的逻辑地址与实际主存的地址完全相同，所以不需要对序中的逻辑地址与实际主存的地址完全相同，所以不需要对程序和数据的地址进行修改。程序和数据的地址进行修改。绝绝对对装装入入方方式式只只能能将将目目标标模模块块装装入入到到主主存存储储器器事事先先指指定定的固定位置，它只适用于单道程序环境。的固定位置，它只适用于单道程序环境。操作系统教程课件第8页机械工业出版社4.2.2程序的装入程序的装入 2静态重定位装入方式静态重定位装入方式 在装入作业时，把该作业中的指令地址和数据地址一次在装入作业时，把该作业中的指令地址和数据地址一次性全部转换成物理

11、地址，这样在作业执行过程中无需再进行性全部转换成物理地址，这样在作业执行过程中无需再进行地址转换工作，这种地址转换方式称地址转换工作，这种地址转换方式称“静态重定位静态重定位”。而这种。而这种作业装入的方式称为作业装入的方式称为“静态重定位装入方式静态重定位装入方式”。如图如图4-3所示所示静态重定位装入的过程。静态重定位装入的过程。操作系统教程课件第9页机械工业出版社4.2.2程序的装入程序的装入 3动态重定位装入方式动态重定位装入方式 在装入作业时，装入程序直接把作业装入到所分配的主在装入作业时，装入程序直接把作业装入到所分配的主存区域中。在作业执行过程中，随着每条指令或数据的访问存区域中

12、。在作业执行过程中，随着每条指令或数据的访问由硬件地址转换机制自动地将指令中的逻辑地址转换成对应由硬件地址转换机制自动地将指令中的逻辑地址转换成对应的物理地址。这种地址转换的方式是在作业执行过程中动态的物理地址。这种地址转换的方式是在作业执行过程中动态完成的，故称为完成的，故称为“动态重定位动态重定位”。而这种作业装入的方式称为。而这种作业装入的方式称为“动态重定位装入方式动态重定位装入方式”。如图如图4-4所示所示动态重定位装入过程。动态重定位装入过程。操作系统教程课件第10页机械工业出版社4.2.2程序的装入程序的装入操作系统教程课件第11页图4-4 动态重定位机械工业出版社4.2.2程序

13、的装入程序的装入 采用动态重定位时，由于装入主存的作业仍保持逻辑地采用动态重定位时，由于装入主存的作业仍保持逻辑地址，所以必要时可改变作业在主存储器中的存放区域。作业址，所以必要时可改变作业在主存储器中的存放区域。作业在主存中被移动位置后，只需要把新区域的起始地址代替原在主存中被移动位置后，只需要把新区域的起始地址代替原来基址寄存器中的地址，这样，作业执行时，硬件地址转换来基址寄存器中的地址，这样，作业执行时，硬件地址转换机制将按新区域的起始地址与逻辑地址相加，转换成新的物机制将按新区域的起始地址与逻辑地址相加，转换成新的物理地址，使作业仍可正确执行。理地址，使作业仍可正确执行。 若作业执行时

14、被改变了存储区仍能正确运行，则称程序若作业执行时被改变了存储区仍能正确运行，则称程序是可浮动的。采用动态重定位的系统支持是可浮动的。采用动态重定位的系统支持“程序浮动程序浮动”。而采。而采用静态重定位时，由于被装入主存储器中的作业信息都已转用静态重定位时，由于被装入主存储器中的作业信息都已转换为物理地址，作业执行过程中，不再进行地址的转换，故换为物理地址，作业执行过程中，不再进行地址的转换，故作业执行过程中是不能改变存放位置的，即采用静态重定位作业执行过程中是不能改变存放位置的，即采用静态重定位的系统不支持的系统不支持“程序浮动程序浮动”。操作系统教程课件第12页机械工业出版社4.2.3程序的

15、链接程序的链接 源程序经过编译后，得到一组目标模块，再通过链接源程序经过编译后，得到一组目标模块，再通过链接程序将这组目标模块链接，形成一个完整的装入模块。程序将这组目标模块链接，形成一个完整的装入模块。程序链接示意程序链接示意如图如图4-5所示所示。操作系统教程课件第13页机械工业出版社4.2.3程序的链接程序的链接 根据链接时间不同，程序的链接可分成如下三种方式：根据链接时间不同，程序的链接可分成如下三种方式：1静态链接。静态链接。在在程程序序运运行行之之前前，首首先先将将各各个个目目标标模模块块以以及及所所需需要要的的库库函函数数，链链接接成成一一个个完完整整的的装装入入模模块块，又又称

16、称为为可可执执行行文文件件，运运行时可直接将它装入主存。行时可直接将它装入主存。 经过编译后得到的目标模块，每个模块的起始地址都为经过编译后得到的目标模块，每个模块的起始地址都为“0”，模块中的地址都是相对于起始地址计算的，在链接成一，模块中的地址都是相对于起始地址计算的，在链接成一个装入模块后，程序中被调用模块的起始地址不再是个装入模块后，程序中被调用模块的起始地址不再是“0”，此，此时须修改被调用模块的逻辑地址，同时每个模块中使用的外时须修改被调用模块的逻辑地址，同时每个模块中使用的外部调用符号也相应转变为逻辑地址。如图部调用符号也相应转变为逻辑地址。如图3-5（b）中，）中，B和和C模块

17、的起始地址分别变更为模块的起始地址分别变更为L和和L+M，而原，而原B模块中的所有模块中的所有逻辑地址都要加上逻辑地址都要加上L，原，原C模块中的所有逻辑地址都要加上模块中的所有逻辑地址都要加上L+M。操作系统教程课件第14页机械工业出版社4.2.3程序的链接程序的链接 2装入时动态链接。装入时动态链接。用用户户源源程程序序经经编编译译后后得得到到的的一一组组目目标标模模块块，在在装装入入主主存存时时，采采用用边边装装入入边边链链接接的的方方式式，即即在在装装入入一一个个目目标标模模块块时时，若若需需要要调调用用一一个个模模块块，则则找找出出该该模模块块，并并将将它它装装入入主主存存，并并修改

18、目标模块中的逻辑地址。修改目标模块中的逻辑地址。由由于于采采用用动动态态链链接接的的各各个个目目标标模模块块是是分分开开存存放放的的，操操作作系系统统可可以以方方便便地地将将一一个个目目标标模模块块链链接接到到几几个个应应用用模模块块上上，所所以以采采用用动动态态链链接接方方式式，可可以以容容易易地地实实现现对对目目标标模模块块的的修修改改和和更新，同时便于实现对目标模块的共享。更新，同时便于实现对目标模块的共享。操作系统教程课件第15页机械工业出版社4.2.3程序的链接程序的链接 3运行时动态链接。运行时动态链接。 在很多情况下，由于应用程序每次运行时的条件不同，在很多情况下，由于应用程序每

19、次运行时的条件不同，需要调用的模块有可能是不相同的。如果将所有目标模块装需要调用的模块有可能是不相同的。如果将所有目标模块装入主存，并链接在一起，得到一个非常大的装入模块，其中入主存，并链接在一起，得到一个非常大的装入模块，其中可能存在某些目标模块根本就没有条件运行，这样会引起程可能存在某些目标模块根本就没有条件运行，这样会引起程序装入时间上和主存空间上的浪费。运行时动态链接是指在序装入时间上和主存空间上的浪费。运行时动态链接是指在程序执行过程中当需要该目标模块时，才把该模块装入主存，程序执行过程中当需要该目标模块时，才把该模块装入主存，并进行链接。这样不仅可以加快程序装入的速度，而且可以并进

20、行链接。这样不仅可以加快程序装入的速度，而且可以节省大量的主存空间。节省大量的主存空间。连续存储空间管理，是指把主存储器中的用户区作为一连续存储空间管理，是指把主存储器中的用户区作为一个连续区域或者分成若干个连续区域进行管理。连续存储管个连续区域或者分成若干个连续区域进行管理。连续存储管理方式可分为单一连续分配、固定分区分配以及可变分区分理方式可分为单一连续分配、固定分区分配以及可变分区分配等方式。配等方式。操作系统教程课件第16页机械工业出版社4.3.1单一连续存储管理单一连续存储管理 单一连续存储管理是一种最简单的存储管理方式。在单单一连续存储管理是一种最简单的存储管理方式。在单一连续存储

21、管理方式下，操作系统占用一部分主存空间，一连续存储管理方式下，操作系统占用一部分主存空间，其余的主存空间作为一个连续分区全部分配给一个作业使其余的主存空间作为一个连续分区全部分配给一个作业使用，即在任何时刻主存储器中最多只存有一个作业。这种用，即在任何时刻主存储器中最多只存有一个作业。这种存储管理方式适合于单用户、单任务的操作系统，在个人存储管理方式适合于单用户、单任务的操作系统，在个人计算机和专用计算机系统中可采用。计算机和专用计算机系统中可采用。图图4-6所示所示为单一连续为单一连续存储管理的示意图。存储管理的示意图。操作系统教程课件第17页机械工业出版社4.3.1单一连续存储管理单一连续

22、存储管理 单单一一连连续续存存储储管管理理每每次次只只允允许许一一个个作作业业装装入入主主存存储储器器，因因此此可可以以不不必必考考虑虑作作业业在在主主存存中中的的移移动动问问题题，所所以以当当作作业业被被装装入入主主存存时时，系系统统一一般般采采用用静静态态重重定定位位方方式式进进行行地地址址转转换换，当然也可以采用动态重定位方式。当然也可以采用动态重定位方式。单单一一连连续续存存储储管管理理方方式式下下的的存存储储保保护护比比较较简简单单，即即判判断断物物理理地地址址界界限限地地址址，并并且且物物理理地地址址主主存存最最大大地地址址，若若条条件件成成立立，则则可可执执行行，否否则则有有地地

23、址址错错误误，形形成成“地地址址越越界界”程程序序性性中中断断事事件件。当当采采用用静静态态重重定定位位装装入入方方式式时时，由由装装入入程程序序检检查查其其物物理理地地址址是是否否超超过过界界限限地地址址，若若是是，则则可可以以装装入入；否否则则，将将产产生生地地址址错错误误，程程序序不不能能装装入入。这这样样，一一个个被被装装入入的的作作业业，总总能能保保证证在在用用户户区区中中执执行行，避避免免破破坏坏系系统统区区中中的的信信息息，达到达到“存储保护存储保护”的目的。的目的。操作系统教程课件第18页机械工业出版社4.3.1单一连续存储管理单一连续存储管理单单一一连连续续存存储储管管理理方

24、方式式适适用用于于单单道道程程序序系系统统，在在20世世纪纪70年年代代，由由于于小小型型计计算算机机和和微微型型计计算算机机的的主主存存容容量量有有限限，这这 种种 管管 理理 方方 式式 曾曾 得得 到到 了了 广广 泛泛 应应 用用 ， 例例 如如 IBM 7094FORTRAN监监督督系系统统、CP/M系系统统、DJS0520系系统统等等均均采采用用了了单单一一连连续续存存储储管管理理方方式式，但但采采用用这这种种管管理理方方式式存存在在几几个个主要缺点：主要缺点：CPU利利用用率率比比较较低低。当当正正在在执执行行的的作作业业出出现现某某个个等等待事件时，待事件时，CPU便处于空闲状

25、态。便处于空闲状态。存存储储器器得得不不到到充充分分利利用用。不不管管用用户户作作业业的的程程序序和和数数据量的多少，都是一个作业独占主存的用户区。据量的多少，都是一个作业独占主存的用户区。计算机的外围设备利用率不高。计算机的外围设备利用率不高。操作系统教程课件第19页机械工业出版社4.3.2固定分区存储管理固定分区存储管理操作系统教程课件第20页 固固定定分分区区存存储储管管理理是是预预先先把把主主存存储储器器中中的的用用户户区区分分割割成成若若干干个个连连续续区区域域，每每一一个个连连续续区区域域称称为为一一个个分分区区，每每个个分分区区的的大大小小可可以以相相同同，也也可可以以不不同同。

26、但但是是一一旦旦分分割割完完成成后后，主主存存储储器器中中分分区区的的个个数数固固定定不不变变，每每个个分分区区的的大大小小固固定定不不变变。每每个个分分区区可可以以装装入入一一个个作作业业，不不允允许许一一个个作作业业跨跨分分区区存存储储，也也不不允允许许多多个个作作业业同同时时存存放放在在同同一一个个分分区区中中。因因此此，固固定定分分区区存存储储管管理理适适合合多多道道程程序序设设计计系系统统。图图4-7所所示示为为固固定分区存储管理方式的示意图。定分区存储管理方式的示意图。机械工业出版社4.3.2固定分区存储管理固定分区存储管理 1空间的分配和去配空间的分配和去配 为了管理各分区的分配

27、和使用情况，系统需要设置一为了管理各分区的分配和使用情况，系统需要设置一张张“主存分配表主存分配表”，以说明各分区的分配情况。一个系统，以说明各分区的分配情况。一个系统中分区分配表的长度固定，由主存储器中分区的个数所中分区分配表的长度固定，由主存储器中分区的个数所决定。主存分配表中记录了各个分区的起始地址和长度，决定。主存分配表中记录了各个分区的起始地址和长度，并为每个分区设一个状态标志位，当状态标志位为并为每个分区设一个状态标志位，当状态标志位为“0”时，时，表示该分区是空闲分区，当标志位为非表示该分区是空闲分区，当标志位为非“0”时，表示该分时，表示该分区已被占用。区已被占用。图图4-8表

28、示表示主存储器被划分成四个分区，每主存储器被划分成四个分区，每个分区的大小并不相同，其中分区个分区的大小并不相同，其中分区1、分区、分区3和分区和分区4分别分别被作业名为被作业名为JOBA、JOBB和和JOBC的作业所占用，分区的作业所占用，分区2为空闲分区。为空闲分区。操作系统教程课件第21页机械工业出版社4.3.2固定分区存储管理固定分区存储管理操作系统教程课件第22页图 4-8 四个分区的分区分配表机械工业出版社4.3.2固定分区存储管理固定分区存储管理 当当作作业业队队列列中中有有作作业业要要求求装装入入主主存存时时，存存储储管管理理可可采采用用“顺顺序序分分配配算算法法”进进行行主主

29、存存空空间间的的分分配配。分分配配时时顺顺序序查查找找主主存存分分配配表表，选选择择标标志志位位为为“0”的的分分区区，将将作作业业的的地地址址空空间间大大小小与与该该分分区区长长度度进进行行比比较较，如如果果能能容容纳纳该该作作业业，则则将将此此分分区区分分配配给给该该作作业业，且且在在此此分分区区的的占占用用标标志志栏栏中中填填入入该该作作业业名名。如如果果作作业业的的地地址址空空间间大大于于此此空空闲闲分分区区的的长长度度，则则重重复复上上述述过过程程继继续续查查找找，查查找找空空闲闲区区长长度度大大于于等等于于该该作作业业的的地地址址空空间间大大小小且且标标志志位位为为“0”的的空空闲

30、闲分分区区，若若有有，则则分分配配，否否则则该该作作业业暂暂时时不不能能装装入入主主存存储储器器。图图4-9所所示示给给出出固固定定分分区区顺顺序序分分配配算算法的流程。法的流程。 装装入入后后的的作作业业在在执执行行结结束束后后必必须须归归还还所所占占用用的的分分区区。存存储储管管理理根根据据作作业业名名查查找找主主存存分分配配表表，找找到到该该作作业业所所占占用用的的分分区区，将将该该分分区区的的状状态态标标志志位位重重新新设设置置为为“0”，表表示示该该分分区区现现在是空闲区，可以装入新的作业。在是空闲区，可以装入新的作业。 操作系统教程课件第23页机械工业出版社4.3.2固定分区存储管

31、理固定分区存储管理操作系统教程课件第24页图 4-9 固定分区顺序分配算法流程机械工业出版社4.3.2固定分区存储管理固定分区存储管理 2地址转换和存储保护地址转换和存储保护固固定定分分区区存存储储管管理理下下，作作业业在在执执行行过过程程中中是是不不会会被被改改变变存存储储区域的，因此可以采用静态重定位装入方式装入作业。区域的，因此可以采用静态重定位装入方式装入作业。由由装装入入程程序序把把作作业业中中的的逻逻辑辑地地址址与与分分区区的的下下限限地地址址相相加加，得得到到对对应应的的物物理理地地址址。当当一一个个已已经经被被装装入入主主存存的的作作业业占占有有处处理理器器运运行行时时，进进程

32、程调调度度程程序序将将该该作作业业所所在在分分区区的的下下限限地地址址和和上上限限地地址址分分别别存存储储在在处处理理器器的的“下下限限寄寄存存器器”和和“上上限限寄寄存存器器”中中。处处理理器器执执行行该作业指令时必须判断：下限地址该作业指令时必须判断：下限地址物理地址物理地址上限地址上限地址如如果果物物理理地地址址在在上上、下下限限地地址址范范围围内内，则则可可按按物物理理地地址址访访问问主主存存储储器器；如如果果条条件件不不成成立立，则则产产生生“地地址址越越界界”的的中中断断事事件件，达达到存储保护的目的。到存储保护的目的。 作业运行结束时，调度程序选择另一个可运行的作业，同时修作业运

33、行结束时，调度程序选择另一个可运行的作业，同时修改下限寄存器和上限寄存器的内容，以保证处理器能控制该作业改下限寄存器和上限寄存器的内容，以保证处理器能控制该作业的正确执行。的正确执行。操作系统教程课件第25页机械工业出版社4.3.2固定分区存储管理固定分区存储管理 3主存空间的利用率主存空间的利用率固固定定分分区区存存储储管管理理方方式式总总是是为为作作业业分分配配一一个个不不小小于于作作业业地地址址空空间间的的分分区区，因因此此在在分分区区中中产产生生一一部部分分空空闲闲区区域域，影影响响了了主主存存空空间间的的利利用用率率。为为了了提提高高主主存存空空间间的的利利用用率率采采用用如如下下几

34、种方法：几种方法：（1）根据经常出现的作业的大小和频率划分分区。）根据经常出现的作业的大小和频率划分分区。（2）划分分区时按分区大小顺序排列。）划分分区时按分区大小顺序排列。 （3）按作业对主存空间的需求量排成多个作业队列，规按作业对主存空间的需求量排成多个作业队列，规定每个作业队列中的各作业只能依次装入对应的分区中；不定每个作业队列中的各作业只能依次装入对应的分区中；不同作业队列中的作业分别依次装入不同的分区中，不同的分同作业队列中的作业分别依次装入不同的分区中，不同的分区中可同时装入作业；某作业队列为区中可同时装入作业；某作业队列为“空空”时，该作业队列对时，该作业队列对应的分区也不能用来

35、装其他作业队列中的作业。应的分区也不能用来装其他作业队列中的作业。操作系统教程课件第26页机械工业出版社4.3.2固定分区存储管理固定分区存储管理 图图4-10为多个作业队列的固定分区法。为多个作业队列的固定分区法。操作系统教程课件第27页 采采用用多多个个作作业业队队列列的的固固定定分分区区法法可可以以有有效效地地防防止止小小作作业业占占用用大大分分区区，从从而而减减少少了了闲闲置置的的主主存存空空间间量量。但但是是如如果果分分区区划划分分不不合合适适，则则会会造造成成某某个个作作业业队队列列经经常常为为空空队队列列，使使对对应应分分区区经经常常无无作作业业被被装装入入，反反而而使使分分区区

36、的的利利用用率率不不高高。所所以以采采用用多多个个作作业业队队列列的的固固定定分分区区法法时时，可可结结合合作作业业的的大大小小和和出出现现的频率划分分区，以达到更好的空间利用率。的频率划分分区，以达到更好的空间利用率。机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 可变分区存储管理并不是预先将主存储器中的用户区可变分区存储管理并不是预先将主存储器中的用户区域划分成若干个固定分区，而是在作业要求装入主存时，域划分成若干个固定分区，而是在作业要求装入主存时，根据作业需要的地址空间的大小和当时主存空间的实际根据作业需要的地址空间的大小和当时主存空间的实际使用情况决定是否为该作业

37、分配一个分区。如果有足够使用情况决定是否为该作业分配一个分区。如果有足够的连续空间，则按需要分割一部分空间分区给该作业；的连续空间，则按需要分割一部分空间分区给该作业；否则令其等待主存空间。所以，在可变分区存储管理中，否则令其等待主存空间。所以，在可变分区存储管理中，主存储器中分区的大小是可变的，根据作业的实际需求主存储器中分区的大小是可变的，根据作业的实际需求进行分区的划分；主存中分区的个数是可变的，随着装进行分区的划分；主存中分区的个数是可变的，随着装入主存的作业数量而变化；主存中的空闲分区个数也随入主存的作业数量而变化；主存中的空闲分区个数也随着作业的装入与撤离而发生变化。着作业的装入与

38、撤离而发生变化。图图4 4-11是可变分区存是可变分区存储管理方式的存储空间分配示意图。储管理方式的存储空间分配示意图。操作系统教程课件第28页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 操作系统教程课件第29页图 4-11 可变分区存储分配与回收示意图机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 1空间的分配和去配空间的分配和去配系系统统初初始始时时，把把主主存存中中整整个个用用户户区区看看作作一一个个大大的的空空闲闲分分区区。当当作作业业要要求求装装入入主主存存时时，系系统统根根据据作作业业对对主主存存空空间间的的实实际际需需求求量量进进行行分

39、分配配。图图4-11（a）给给出出了了作作业业被被装装入入时时主主存存空间分配的情况。空间分配的情况。装装入入主主存存储储器器中中的的作作业业执执行行结结束束后后，它它所所占占用用的的分分区区被被收收回回，成成为为一一个个新新的的空空闲闲区区，可可以以用用来来装装入入新新的的作作业业。随随着着作作业业不不断断的的装装入入和和作作业业执执行行完完后后的的撤撤离离，主主存存储储区区被被分分成成若若干干分分区区，其其中中有有的的分分区区被被作作业业占占用用，有有的的分分区区空空闲闲。图图4-11（b）给给出出了了作作业业被被装装入入、执执行行结结束束后后撤撤离离的的主主存存空空间间分分配情况。配情况

40、。机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 1.可变分区数据结构可变分区数据结构采采用用可可变变分分区区存存储储管管理理方方式式管管理理诸诸存存储储空空间间时时，主主存存中中已已占占用用分分区区和和空空闲闲区区的的数数目目和和大大小小都都是是可可变变的的。为为了了实实现现可可变变分分区区存存储储管管理理，系系统统必必须须设设置置相相应应的的数数据据结结构构，用用来来描描述述空空闲闲分分区区和和已已分分配配分分区区的的情情况况，为为系系统统空空间间分分配配提提供供依依据据。常用的数据结构有以下两种形式。常用的数据结构有以下两种形式。 （1）分区表。）分区表。 系系统统设

41、设置置“空空闲闲分分区区表表”和和“已已分分配配分分区区表表”，用用来来描描述述空空闲闲分分区区和和已已分分配配分分区区的的情情况况，为为系系统统空空间间分分配配提提供供依依据据。已已分分配配分分区区表表记记录录已已装装入入的的作作业业在在主主存存空空间间中中占占用用分分区区的的始始址址和和长长度度，用用标标志志位位指指出出占占用用该该分分区区的的作作业业名名。空空闲闲分分区区表表记记录录主主存存中中可可供供分分配配的的空空闲闲分分区区的的始始址址和和长长度度，用用标标志志位位指指出出该分区是未分配的空闲分区。该分区是未分配的空闲分区。操作系统教程课件第31页机械工业出版社4.3.34.3.3

42、可变分区存储管理可变分区存储管理 图图4-12为可变分区存储管理方式的主存分配表。系统为可变分区存储管理方式的主存分配表。系统按一定的规则组织主存分配表，当作业要求装入时，从空按一定的规则组织主存分配表，当作业要求装入时，从空闲分区表查找一个长度大于作业要求的空闲闲分区表查找一个长度大于作业要求的空闲分区。操作系统教程课件第32页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 （2）分区链。）分区链。 为了实现对空闲分区的分配和链接，在每个分区的起始为了实现对空闲分区的分配和链接，在每个分区的起始部分，设置一些用于控制分区分配的信息，以及用于链接前部分，设置一些用于控制分区

43、分配的信息，以及用于链接前一个分区的前向指针；在分区尾部则设置一后向指针，通过一个分区的前向指针；在分区尾部则设置一后向指针，通过前、后向链接指针，可以将所有的空闲分区联结成一个双向前、后向链接指针，可以将所有的空闲分区联结成一个双向链。为了检索的方便，在分区尾部重复设置状态位和分区大链。为了检索的方便，在分区尾部重复设置状态位和分区大小表目。小表目。如图如图4-13所示所示。操作系统教程课件第33页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 2.可变分区分配算法可变分区分配算法将一个作业装入主存，须按照一定的分配算法，从空闲将一个作业装入主存，须按照一定的分配算法，从

44、空闲分区表或空闲分区链中选出一个分区分配给该作业。可变分分区表或空闲分区链中选出一个分区分配给该作业。可变分区存储管理常用的空间分配算法有：区存储管理常用的空间分配算法有：“最先适应最先适应”分配算法、分配算法、“最优适应最优适应”分配算法和分配算法和“最坏适应最坏适应”分配算法。以下以空闲分分配算法。以下以空闲分区表为例说明各种算法。区表为例说明各种算法。操作系统教程课件第34页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 （1）最先适应分配算法）最先适应分配算法最最先先适适应应分分配配算算法法在在主主存存空空间间分分配配时时，总总是是顺顺序序查查找找空空闲闲分分区区表

45、表，选选择择第第一一个个满满足足作作业业地地址址空空间间要要求求的的空空闲闲分分区区进进行行分分割割，一一部部分分分分配配给给作作业业，而而剩剩余余部部分分仍仍为为空空闲闲分分区。区。最最先先适适应应分分配配算算法法实实现现简简单单，但但是是经经过过若若干干次次作作业业的的装装入入与与撤撤离离后后，有有可可能能把把较较大大的的主主存存空空间间分分割割成成若若干干个个小小的的、不不连连续续的的新新空空闲闲分分区区，这这些些空空闲闲分分区区的的长长度度可可能能比比较较小小，不不能能满满足足主主存存再再次次分分配配的的需需要要，从从而而使使主主存存空空间间的的利利用率大大降低，这些空闲分区称为用率大

46、大降低，这些空闲分区称为“碎片碎片”。操作系统教程课件第35页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 （2）最优适应分配算法）最优适应分配算法 最最优优适适应应分分配配算算法法总总是是选选择择一一个个满满足足作作业业地地址址空空间间要要求求的的最最小小空空闲闲分分区区进进行行分分配配，这这样样每每次次分分配配后后总总能能保保留留下下较较大大的分区，使装入大作业时比较容易获得满足。的分区，使装入大作业时比较容易获得满足。 在在实实现现过过程程中中，空空闲闲分分区区按按其其长长度度以以递递增增顺顺序序登登记记在在空空闲闲分分区区表表中中。这这样样，系系统统分分配配时时顺

47、顺序序查查找找空空闲闲分分区区表表，找找到到的的第第一一个个满满足足作作业业空空间间要要求求的的空空闲闲分分区区一一定定是是能能够够满满足足该该作作业要求的所有分区中的最小一个分区。业要求的所有分区中的最小一个分区。采采用用最最优优适适应应分分配配算算法法，每每次次分分配配后后分分割割的的剩剩余余空空间间总总是是最最小小的的，这这样样形形成成的的“碎碎片片”非非常常“零零散散”，往往往往难难以以再再次次分分配使用，从而影响了主存空间的利用率。配使用，从而影响了主存空间的利用率。操作系统教程课件第36页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 （3）最坏适应分配算法）最

48、坏适应分配算法最最坏坏适适应应分分配配算算法法与与最最优优适适应应分分配配算算法法相相反反，总总是是选选择择一一个个满满足足作作业业地地址址空空间间要要求求的的最最大大空空闲闲分分区区进进行行分分割割，按按作作业业需需要要的的空空间间大大小小进进行行分分配配给给作作业业使使用用后后，剩剩余余部部分分的的空空间间不不致致于于太太小小，仍仍然然可可以以供供系系统统再再次次分分配配使使用用。这这种种分分配配算算法法对中小型作业是有利的。对中小型作业是有利的。 实实现现最最坏坏适适应应分分配配算算法法时时，空空闲闲分分区区按按其其长长度度以以递递减减顺顺序序登登记记在在空空闲闲分分区区表表中中。系系统

49、统分分配配时时顺顺序序查查找找空空闲闲分分区区表表，表表中中的的第第一一个个登登记记项项即即对对应应着着当当前前主主存存的的最最大大空空闲闲分分区区。同同样样，当当作作业业归归还还主主存存空空间间时时，则则需需要要按按分分区区的的大大小小按按递递减减顺顺序登记到空闲分区表的适当位置。序登记到空闲分区表的适当位置。操作系统教程课件第37页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 操作系统教程课件第38页图 4-14 可变分区分配算法示例机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 装装入入的的作作业业执执行行结结束束后后，它它所所占占据据的的分分区

50、区将将被被回回收收，回回收收后后的的空空闲闲分分区区登登记记在在空空闲闲分分区区表表中中，用用来来装装入入新新的的作作业业。回回收收空空间间时时应应检检查查是是否否存存在在与与回回收收区区相相邻邻的的空空闲闲分分区区，如如果果有，则将其合并成为一个新的空闲分区进行登记管理。有，则将其合并成为一个新的空闲分区进行登记管理。 一一个个回回收收区区可可能能存存在在上上邻邻空空闲闲分分区区，也也可可能能存存在在下下邻邻空空闲闲分分区区，或或既既存存在在上上邻邻又又存存在在下下邻邻空空闲闲分分区区，或或既既无无上上邻邻又又无无下下邻邻空空闲闲分分区区，如如图图4-15所所示示。假假定定作作业业归归还还的

51、的分分区区始始址为址为S S，长度为，长度为L L。操作系统教程课件第39页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 操作系统教程课件第40页图 4-15 主存回收示意图机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 图图4 4-16给出了合并下邻给出了合并下邻/上邻空闲分区的回收算法流程。上邻空闲分区的回收算法流程。 机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 2 2地址转换和存储保护地址转换和存储保护采采用用可可变变分分区区存存储储管管理理方方式式，一一般般均均采采用用动动态态重重定定位位方方式式装装入入作作业业。为为使

52、使地地址址的的转转换换不不影影响响到到指指令令的的执执行行速速度度，必必须须有有硬硬件件地地址址转转换换机机构构的的支支持持。硬硬件件地地址址转转换换机机构构包包括括两两个个专专用用控控制制寄寄存存器器：基基址址寄寄存存器器和和限限长长寄寄存存器器，以以及及一一些些加加法法、比比较较线线路路等等。基基址址寄寄存存器器用用来来存存放放作作业业所所占占分分区区的起始地址，限长寄存器用来存放作业所占分区长度。的起始地址，限长寄存器用来存放作业所占分区长度。 机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 正在运行的作业所占分区的起始地址和长度被送入基址正在运行的作业所占分区的起始

53、地址和长度被送入基址寄存器和限长寄存器中。执行过程中，处理器每执行一条寄存器和限长寄存器中。执行过程中，处理器每执行一条指令都要将该指令的逻辑地址与限长寄存器中的值进行比指令都要将该指令的逻辑地址与限长寄存器中的值进行比较，当逻辑地址小于限长值时，则把逻辑地址与基址寄存较，当逻辑地址小于限长值时，则把逻辑地址与基址寄存器的值相加就可得到对应的物理地址。当逻辑地址大于限器的值相加就可得到对应的物理地址。当逻辑地址大于限长寄存器中的限长值时，表示欲访问的地址超出了所分配长寄存器中的限长值时，表示欲访问的地址超出了所分配的分区范围，这时形成一个的分区范围，这时形成一个“地址越界地址越界”的程序性中断

54、事件，的程序性中断事件，达到存储保护的目的达到存储保护的目的。图图4-17示出了可变分区存储管理的示出了可变分区存储管理的地址转换示例。地址转换示例。操作系统教程课件第43页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 3 3 移动技术移动技术采采用用可可变变分分区区存存储储管管理理主主存存时时，可可采采用用移移动动技技术术使使分分散散的空闲分区集中起来以容纳新的作业，的空闲分区集中起来以容纳新的作业，如图如图4-18所示所示。机械工业出版社 移移动动技技术术为为作作业业执执行行过过程程中中扩扩充充主主存存空空间间提提供供方方便便，一一道道作作业业在在执执行行中中要要求求

55、增增加加主主存存量量时时，只只要要适适当当移移动动邻邻近近的作业就可增加它所占的分区长度。的作业就可增加它所占的分区长度。移移动动可可以以集集中中分分散散的的空空闲闲分分区区，提提高高主主存存空空间间的的利利用用率率，移移动动也也为为作作业业动动态态扩扩充充主主存存空空间间提提供供了了方方便便。但但是是，采用移动技术时必须注意：采用移动技术时必须注意： （1）移动会增加系统开销。）移动会增加系统开销。（2）移动是有条件的。）移动是有条件的。操作系统教程课件第45页机械工业出版社4.3.34.3.3可变分区存储管理可变分区存储管理 采用移动技术时应该尽量减少移动的作业数和信息量，采用移动技术时应

56、该尽量减少移动的作业数和信息量，以降低系统的开销、提高系统的效率。以降低系统的开销、提高系统的效率。图图4-19给出了两种给出了两种作业装入主存的方式。作业装入主存的方式。操作系统教程课件第46页机械工业出版社4.3.4覆盖与交换技术覆盖与交换技术n覆盖技术和交换技术是在多道环境下用来扩充主存的覆盖技术和交换技术是在多道环境下用来扩充主存的两种方法。这两种技术都是用来解决主存容量不足及有效两种方法。这两种技术都是用来解决主存容量不足及有效利用主存的方法。覆盖技术主要用于早期的操作系统中，利用主存的方法。覆盖技术主要用于早期的操作系统中，而交换技术在现代操作系统中仍有较强的生命力。而交换技术在现

57、代操作系统中仍有较强的生命力。n单一连续存储管理和分区存储管理对作业的大小都有单一连续存储管理和分区存储管理对作业的大小都有严格的限制，当作业要求运行时，系统将作业的全部信息严格的限制，当作业要求运行时，系统将作业的全部信息一次装入主存，并一直驻留在主存直至运行结束。当作业一次装入主存，并一直驻留在主存直至运行结束。当作业的大小大于主存可用空间时，该作业就无法运行，这就限的大小大于主存可用空间时，该作业就无法运行，这就限制了计算机系统上开发较大程序的可能。覆盖和交换技术制了计算机系统上开发较大程序的可能。覆盖和交换技术是解决大作业与小主存矛盾的两种存储管理技术，他们实是解决大作业与小主存矛盾的

58、两种存储管理技术，他们实质上是对主存进行了逻辑扩充。质上是对主存进行了逻辑扩充。操作系统教程课件第47页机械工业出版社4.3.4覆盖与交换技术覆盖与交换技术n覆盖技术的基本思想是一个程序不需要把所有的指令覆盖技术的基本思想是一个程序不需要把所有的指令和数据都装入主存。可以把程序划为若干功能上相对独立和数据都装入主存。可以把程序划为若干功能上相对独立的程序段，让那些不会同时执行的程序段共享一块主存。的程序段，让那些不会同时执行的程序段共享一块主存。这样使用户看起来好像主存扩大了，从而达到了主存扩充这样使用户看起来好像主存扩大了，从而达到了主存扩充的目的。的目的。n将程序的必要部分（常用功能）的代

59、码和数据常驻主将程序的必要部分（常用功能）的代码和数据常驻主存；可选部分（不常用功能）在其他程序模块中实现，平存；可选部分（不常用功能）在其他程序模块中实现，平时存放在外存中（覆盖文件），在需要用到时才装入到主时存放在外存中（覆盖文件），在需要用到时才装入到主存；不存在调用关系的模块不必同时装入到主存，从而可存；不存在调用关系的模块不必同时装入到主存，从而可以相互覆盖以相互覆盖(即不同时用的模块可共用一个分区即不同时用的模块可共用一个分区)。把可以相。把可以相互覆盖的程序段叫做覆盖，可共享的主存区叫做覆盖区。互覆盖的程序段叫做覆盖，可共享的主存区叫做覆盖区。操作系统教程课件第48页机械工业出版

60、社4.3.4覆盖与交换技术覆盖与交换技术操作系统教程课件第49页图4-20 覆盖技术示意图机械工业出版社4.3.4覆盖与交换技术覆盖与交换技术n为了实现覆盖管理，系统必须提供相应的覆盖管理控为了实现覆盖管理，系统必须提供相应的覆盖管理控制程序。当作业装入运行时，由系统根据用户提供的覆盖制程序。当作业装入运行时，由系统根据用户提供的覆盖结构进行覆盖处理。当程序中引用当前尚未装入覆盖区的结构进行覆盖处理。当程序中引用当前尚未装入覆盖区的覆盖中的例程时，则调用覆盖管理控制程序，请求将所需覆盖中的例程时，则调用覆盖管理控制程序，请求将所需的覆盖装入覆盖区中，系统响应请求，并自动将所需覆盖的覆盖装入覆盖

61、区中，系统响应请求，并自动将所需覆盖装入主存覆盖区中。装入主存覆盖区中。n覆盖技术打破了必须将一个作业的全部信息装入主存覆盖技术打破了必须将一个作业的全部信息装入主存后才能运行的限制。在一定程度上解决了小主存运行大作后才能运行的限制。在一定程度上解决了小主存运行大作业的矛盾。但是，采用覆盖技术编程时必须划分程序模块业的矛盾。但是，采用覆盖技术编程时必须划分程序模块和确定程序模块之间的覆盖关系，增加了编程复杂度；从和确定程序模块之间的覆盖关系，增加了编程复杂度；从外存装入覆盖文件，是以时间延长来换取空间节省。外存装入覆盖文件，是以时间延长来换取空间节省。操作系统教程课件第50页机械工业出版社n交

62、换最早用在麻省理工学院的兼容分时系统交换最早用在麻省理工学院的兼容分时系统CTSS中，中，其基本思想是把主存中暂时不能运行的进程或暂时不使其基本思想是把主存中暂时不能运行的进程或暂时不使用的程序和数据换出到外存，以腾出足够的主存空间，用的程序和数据换出到外存，以腾出足够的主存空间，把已具备运行条件的进程或进程所需要的程序和数据换把已具备运行条件的进程或进程所需要的程序和数据换入主存。入主存。n交换技术并不要求程序员做特殊的工作。交换完全交换技术并不要求程序员做特殊的工作。交换完全由操作系统进行，整个过程对进程是透明的。交换的对由操作系统进行，整个过程对进程是透明的。交换的对象可以是整个进程，此

63、时成为象可以是整个进程，此时成为“整体交换整体交换”或或“进程交换进程交换”。图图4-21为作业交换的示意图。为作业交换的示意图。操作系统教程课件第51页4.3.4覆盖与交换技术覆盖与交换技术机械工业出版社4.3.4覆盖与交换技术覆盖与交换技术n实现交换技术需要后援存储器，通常是硬盘，它必须具实现交换技术需要后援存储器，通常是硬盘，它必须具备两个显著的特征：数据传输快，容量足够大。备两个显著的特征：数据传输快，容量足够大。n交换技术主要是在进程或作业之间进行，而覆盖则主要交换技术主要是在进程或作业之间进行，而覆盖则主要是在同一个作业或进程内进行。是在同一个作业或进程内进行。操作系统教程课件第5

64、2页机械工业出版社4.4页式存储管理页式存储管理 连续分配方式要求作业一次性、连续装入在主存空连续分配方式要求作业一次性、连续装入在主存空间，对空间的要求较高，而且可能形成很多间，对空间的要求较高，而且可能形成很多“碎片碎片”，虽然可以通过移动技术将零散的空闲分区汇集成可用的虽然可以通过移动技术将零散的空闲分区汇集成可用的大块空间，但需要增加系统的额外开销。如果采用不连大块空间，但需要增加系统的额外开销。如果采用不连续存储的方式，把逻辑地址连续的作业分散存放到几个续存储的方式，把逻辑地址连续的作业分散存放到几个不连续的主存区域中，并能保证作业的正确执行。这样不连续的主存区域中，并能保证作业的正

65、确执行。这样既可充分利用主存空间，减少主存的碎片，又可避免移既可充分利用主存空间，减少主存的碎片，又可避免移动所带来的额外开销。动所带来的额外开销。操作系统教程课件第53页机械工业出版社4.4.1基本原理基本原理 页页式式存存储储管管理理是是把把主主存存储储器器划划分分成成大大小小相相等等的的若若干干区区域域，每每个个区区域域称称为为一一块块，并并对对它它们们加加以以顺顺序序编编号号，如如0#块块、1#块块等等等等。与与此此对对应应，用用户户程程序序的的逻逻辑辑地地址址空空间间划划分分成成大大小小相相等等的的若若干干页页，同同样样为为它它们们加加以以顺顺序序编编号号，从从0开开始始，如如第第0

66、页、第页、第1页等。页等。页的大小与块的大小相等。页的大小与块的大小相等。分分页页式式存存储储管管理理的的逻逻辑辑地地址址由由两两部部分分组组成成：页页号号和和页页内地址。其格式为：内地址。其格式为：操作系统教程课件第54页页内地址W页号P31 12 11 0机械工业出版社4.4.2存储空间的分配与去配存储空间的分配与去配 分分页页式式存存储储管管理理把把主主存存空空间间划划分分成成若若干干块块，以以块块为为单单位位进进行行主主存存空空间间的的分分配配。由由于于块块的的大大小小是是固固定定的的，系系统统可可以以采采用用一一张张主主存存分分配配表表来来记记录录已已分分配配的的块块、尚尚未未分分配

67、配的的块块以以及及当当前前剩剩余余的的空空闲闲块块总总数数。最最简简单单的的办办法法可可用用一一张张“位位示示图图”来来记记录录主主存存的的分分配配情情况况。例例如如主主存存的的用用户户区区被被划划分分成成512块块，则则可可用用字字长长为为32位位的的16个个字字的的位位示示图图来来构构成成一一张张主主存存分分配配表表，位位示示图图中中的的每每一一位位与与一一个个物物理理块块对对应应，用用0/1表表示示对对应应块块的的占占用用标标志志（空空闲闲/已已占占用用），另另用用一一个个字字节节记记录当前系统的剩余空闲块总数，录当前系统的剩余空闲块总数，如图如图4-22所示所示。操作系统教程课件第55

68、页机械工业出版社4.4.2存储空间的分配与去配存储空间的分配与去配操作系统教程课件第56页 进行主存分配时，首先查看空闲块总数是否能够满足作进行主存分配时，首先查看空闲块总数是否能够满足作业要求，若不能满足，则不进行分配；若能满足，则从位示业要求，若不能满足，则不进行分配；若能满足，则从位示图中找出为图中找出为“0”的位，并且将其占用标志置为的位，并且将其占用标志置为“1”，并从，并从空闲块总数中减去本次占用的块数，按找到的位计算出对应空闲块总数中减去本次占用的块数，按找到的位计算出对应的块号，建立该作业的页表，并把作业装入对应的物理块中。的块号，建立该作业的页表，并把作业装入对应的物理块中。

69、机械工业出版社4.4.2存储空间的分配与去配存储空间的分配与去配 由由于于每每一一块块的的大大小小相相等等，在在位位示示图图中中查查找找到到一一个个为为“0”的的位位后后，根根据据它它所所在在的的字字号号、位位号号，按按如如下下公公式式可可计计算算出出对对应的块号：应的块号：块号字号块号字号字长位号字长位号当当一一个个作作业业执执行行结结束束时时，则则应应该该收收回回作作业业所所占占的的主主存存块块。根根据据归归还还的的块块号号计计算算出出该该块块在在位位示示图图中中对对应应的的位位置置，将将占占用用标标志志修修改改为为“0”，同同时时把把归归还还块块数数加加入入到到空空闲闲块块总总数数中中。

70、假假定归还块的块号为定归还块的块号为i，则在位示图中对应的位置为：，则在位示图中对应的位置为：字号字号i/字长字长，位号位号imod字长字长 其中其中表示对表示对i除以字长后取其整数，而除以字长后取其整数，而mod表示对表示对i除除以字长后取其余数部分。以字长后取其余数部分。操作系统教程课件第57页机械工业出版社4.4.3页表与地址转换页表与地址转换 在在分分页页式式存存储储管管理理系系统统中中，允允许许将将作作业业的的每每一一页页离离散散地地存存储储在在主主存存的的物物理理块块中中，但但系系统统必必须须能能够够保保证证作作业业的的正正确确运运行行，即即能能在在主主存存中中找找到到每每个个页页

71、面面所所对对应应的的物物理理块块。为为此此，系系统统为为每每个个作作业业建建立立了了一一张张页页面面映映像像表表，简简称称页页表表。页页表表实实现现了了从从页页号号到到主主存存块块号号的的地地址址映映像像。作作业业中中的的所所有有页页（0n）依依次次地地在在页页表表中中记记录录了了相相应应页页在在主主存存中中对对应应的的物物理理块块号号，如如图图4-23所示所示。页表的长度由进程或作业拥有的页面数决定。页表的长度由进程或作业拥有的页面数决定。操作系统教程课件第58页机械工业出版社4.4.3页表与地址转换页表与地址转换操作系统教程课件第59页图 4-23 页表示意图机械工业出版社4.4.3页表与

72、地址转换页表与地址转换操作系统教程课件第60页n 页式存储管理采用动态重定位方式装入作业，作业执页式存储管理采用动态重定位方式装入作业，作业执行时通过硬件的地址转换机构实现从用户空间中的逻辑地行时通过硬件的地址转换机构实现从用户空间中的逻辑地址到主存空间中物理地址的转换工作。由于页内地址和物址到主存空间中物理地址的转换工作。由于页内地址和物理块内的地址是一一对应的。因此，地址变换机构的任务，理块内的地址是一一对应的。因此，地址变换机构的任务，实际上是将逻辑地址中的页号，转换成为主存中的物理块实际上是将逻辑地址中的页号，转换成为主存中的物理块号。页表是硬件进行地址转换的依据。号。页表是硬件进行地

73、址转换的依据。机械工业出版社4.4.3页表与地址转换页表与地址转换 调调度度程程序序在在选选择择作作业业后后，将将选选中中作作业业的的页页表表始始址址送送入入硬硬件件设设置置的的页页表表控控制制寄寄存存器器中中。地地址址转转换换时时，只只要要从从页页表表寄寄存存器器中中就就可可找找到到相相应应的的页页表表。当当作作业业执执行行时时，分分页页地地址址变变换换机机构构会会自自动动将将逻逻辑辑地地址址分分为为页页号号和和页页内内地地址址两两部部分分，以以页页号号位位索索引引检检索索页页表表，如如果果页页表表中中无无此此页页号号，则则产产生生一一个个“地地址址错错”的的程程序序性性中中断断事事件件；如

74、如果果页页表表中中有有此此页页号号，则则可可得得到到对对应应的的主主存存块块号号，再再按按逻逻辑辑地地址址中中的的页页内内地地址址计计算算出出欲欲访访问问的的主主存存单单元元的的物物理理地地址址。因因为为块块的大小相等，所以的大小相等，所以物理地址物理地址=块号块号块长页内地址块长页内地址图图4-24给出分页式存储管理的地址变换机构示例给出分页式存储管理的地址变换机构示例。操作系统教程课件第61页机械工业出版社4.4.3页表与地址转换页表与地址转换操作系统教程课件第62页图 4-24 分页系统的地址变换机构示意图机械工业出版社4.4.4快表快表由由于于页页表表是是存存放放在在主主存存储储器器中

75、中的的，这这样样取取一一个个数数据据或或指指令令至至少少需需要要访访问问主主存存两两次次以以上上。第第一一次次是是访访问问主主存存中中的的页页表表，查查找找到到指指定定页页面面所所对对应应的的物物理理块块号号，将将块块号号与与页页内内地地址址拼拼接接，计计算算出出数数据据或或指指令令的的物物理理地地址址。第第二二次次访访问问主主存时，根据第一次得到的物理地址进行数据的存取操作。存时，根据第一次得到的物理地址进行数据的存取操作。 为了提高存取速度，可以设想把页表存放在一组寄存器为了提高存取速度，可以设想把页表存放在一组寄存器中，但寄存器成本太高，数量有限，不可行。通常在地址中，但寄存器成本太高，

76、数量有限，不可行。通常在地址变换机构中增设一个具有并行查找能力的小容量高速缓冲变换机构中增设一个具有并行查找能力的小容量高速缓冲寄存器，又称寄存器，又称“相联寄存器相联寄存器”。利用高速缓冲寄存器存放页。利用高速缓冲寄存器存放页表的一部分，把存放在高速缓冲寄存器中的这部分页表称表的一部分，把存放在高速缓冲寄存器中的这部分页表称“快表快表”。快表中登记了当前执行程序中最常用的页号与主存。快表中登记了当前执行程序中最常用的页号与主存中块号的对应关系，中块号的对应关系，图图4-25给出具有快表的地址变换机构给出具有快表的地址变换机构示例。示例。操作系统教程课件第63页机械工业出版社4.4.4快表快表

77、操作系统教程课件第64页图 4-25 具有快表的地址变换机构示意图机械工业出版社4.4.5页的共享与保护页的共享与保护 采采用用页页式式存存储储管管理理能能方方便便地地实实现现程程序序和和数数据据的的共共享享。在在多多道道程程序序系系统统中中，编编译译程程序序、编编辑辑程程序序、解解释释程程序序、公公共共子子程程序序、公公共共数数据据等等都都是是可可共共享享的的，这这些些共共享享的的信信息息在在主主存存储储器器中中只只需需要要保保留留一一个个副副本本，大大大大提提高高了了主主存存空空间间的的利用率。利用率。 在实现共享时，必须区分数据的共享和程序的共享。实在实现共享时，必须区分数据的共享和程序

78、的共享。实现数据共享时，可允许不同的作业对共享的数据页采用不现数据共享时，可允许不同的作业对共享的数据页采用不同页号，只需要将各自的有关表目指向共享的数据信息块同页号，只需要将各自的有关表目指向共享的数据信息块即可。而实现程序共享时，由于页式存储结构要求逻辑地即可。而实现程序共享时，由于页式存储结构要求逻辑地址空间是连续的，所以在程序运行前它们的页号是确定的。址空间是连续的，所以在程序运行前它们的页号是确定的。操作系统教程课件第65页机械工业出版社4.4.5页的共享与保护页的共享与保护n 图图4-26所示所示给出了两个作业共享一个程序和一个数给出了两个作业共享一个程序和一个数据段的情况。据段的

79、情况。操作系统教程课件第66页机械工业出版社4.5段式存储管理段式存储管理 用用户户编编制制的的程程序序是是由由若若干干段段组组成成的的：一一个个程程序序可可以以由由一一个个主主程程序序、若若干干子子程程序序、符符号号表表、栈栈以以及及数数据据等等若若干干段段组组成成。每每一一段段都都有有独独立立、完完整整的的逻逻辑辑意意义义，每每一一段段程序都可独立编制，且每一段的长度可以不同。程序都可独立编制，且每一段的长度可以不同。段段式式存存储储管管理理支支持持用用户户的的分分段段观观点点，具具有有逻逻辑辑上上的的清晰和完整性，它以段为单位进行存储空间的管理。清晰和完整性，它以段为单位进行存储空间的管

80、理。操作系统教程课件第67页机械工业出版社4.5.1原理原理每每个个作作业业由由若若干干个个相相对对独独立立的的段段组组成成，每每个个段段都都有有一一个个段段名名，为为了了实实现现简简单单，通通常常可可用用段段号号代代替替段段名名，段段号号从从“0”开开始始，每每一一段段的的逻逻辑辑地地址址都都从从“0”开开始始编编址址，段段内内地地址址是是连连续的，而段与段之间的地址是不连续的。续的，而段与段之间的地址是不连续的。其逻辑地址由段号和段内地址两部分所组成其逻辑地址由段号和段内地址两部分所组成：操作系统教程课件第68页段内地址W段号S31 16 15 0机械工业出版社4.5.2空间的分配与去配空

81、间的分配与去配 分分段段式式存存储储管管理理是是在在可可变变分分区区存存储储管管理理方方式式的的基基础础上上发发展展而而来来的的。在在分分段段式式存存储储管管理理方方式式中中，以以段段为为单单位位进进行行主主存存分分配配，每每一一个个段段在在主主存存中中占占有有一一个个连连续续空空间间，但但各各个个段段之之间间可可以以离离散散地地存存放放在在主主存存不不同同的的区区域域中中。为为了了使使程程序序能能正正常常运运行行，即即能能从从主主存存中中正正确确找找出出每每个个段段所所在在的的分分区区位位置置，系系统统为为每每个个进进程程建建立立一一张张段段映映射射表表，简简称称“段段表表”。每每个个段段在

82、在表表中中占占有有一一个个表表项项，记记录录该该段段在在主主存存储储器器中中的的起起始始地地址址和和长长度度，如如图图4-27所示所示。段表实现了从逻辑段到主存空间之间的映射。段表实现了从逻辑段到主存空间之间的映射。操作系统教程课件第69页机械工业出版社4.5.2空间的分配与去配空间的分配与去配操作系统教程课件第70页图 4-27 段的装入示意图机械工业出版社4.5.2空间的分配与去配空间的分配与去配 如如果果在在装装入入某某段段信信息息时时找找不不到到满满足足该该段段地地址址空空间间大大小小的的空空闲闲区区，则则可可采采用用移移动动技技术术合合并并分分散散的的空空闲闲区区，以以利利于于大大作

83、作业的装入。业的装入。当当采采用用分分段段式式存存储储管管理理的的作作业业执执行行结结束束后后，它它所所占占据据的的主主存存空空间间将将被被回回收收，回回收收后后的的主主存存空空间间登登记记在在空空闲闲分分区区表表中中，可可以以用用来来装装入入新新的的作作业业。系系统统在在回回收收空空间间时时同同样样需需要要检检查查是是否否存存在在与与回回收收区区相相邻邻的的空空闲闲分分区区，如如果果有有，则则将将其其合合并并成成为为一个新的空闲分区进行登记管理。一个新的空闲分区进行登记管理。 段表存放在主存储器中，在访问一个数据或指令时至少段表存放在主存储器中，在访问一个数据或指令时至少需要访问主存两次以上

84、。为了提高对段表的存取速度，通常需要访问主存两次以上。为了提高对段表的存取速度，通常增设一个相联寄存器，利用高速缓冲寄存器保存最近常用的增设一个相联寄存器，利用高速缓冲寄存器保存最近常用的段表项。段表项。操作系统教程课件第71页机械工业出版社4.5.3地址转换与存储保护 段段式式存存储储管管理理采采用用动动态态重重定定位位方方式式装装入入作作业业，作作业业执执行行时时通通过过硬硬件件的的地地址址转转换换机机构构实实现现从从逻逻辑辑地地址址到到物物理理地地址址的的转转换换工工作作，段段表表的的表表目目起起到到了了基基址址寄寄存存器器和和限限长长寄寄存存器器的作用，是硬件进行地址转换的依据。的作用

85、，是硬件进行地址转换的依据。 图图4-28给出分段式存储管理的地址变换示例。给出分段式存储管理的地址变换示例。操作系统教程课件第72页机械工业出版社4.5.4段的共享段的共享 由由于于段段是是按按逻逻辑辑意意义义来来划划分分的的，可可以以按按段段名名进进行行访访问问，因因此此分分段段式式存存储储管管理理系系统统的的一一个个突突出出优优点点，是是可可以以方方便便地地实实现现段段的的共共享享，即即允允许许若若干干个个进进程程共共享享一一个个或或多多个个段段。为为实实现现某某段段代代码码的的共共享享，在在分分段段式式存存储储管管理理系系统统中中，各各个个进进程程对对共共享享段段使使用用相相同同的的段

86、段名名，在在各各自自的的段段表表中中填填入入共共享享段段的的起起始始地地址址，并并置置以以适适当当的的读读写写控控制制权权，即即可可做做到到共共享享一一个个逻逻辑辑上上完完整整的的主主存存段段信信息息。例例如如一一个个多多用用户户系系统统，可可同同时时接接纳纳40个个用用户户，他他们们都都需需要要执执行行一一个个文文本本编编辑辑程程序序（TextEditor）。如如果果文文本本编编辑辑程程序序有有160KB的的代代码码和和40KB的的数数据据区区，则则总总共共需需要要8MB的的主主存存空空间间来来支支持持40个个用用户户的的访访问问。如如果果160KB的的代代码码是是可可重重入入的的，则则该该

87、代代码码只只需需要要在在主主存存中中保保留留一一份份文文本本编编辑辑程程序序的的副副本本，此此时时所所需需要要的的主主存存空空间间仅仅为为1760KB（4040+160），只只需需要要在在每每个进程的段表中为文本编辑程序设置一个段表项。个进程的段表中为文本编辑程序设置一个段表项。操作系统教程课件第73页机械工业出版社4.5.4 段的共享操作系统教程课件第74页图 4-29 段的共享示意图机械工业出版社4.5.4 段的共享 在多道程序设计系统中，由于进程的并发执行，一个在多道程序设计系统中，由于进程的并发执行，一个程序段为多个进程共享时，有可能出现多次同时重复执行程序段为多个进程共享时，有可能出

88、现多次同时重复执行该段程序的情况，而该共享程序段的指令和数据在执行过该段程序的情况，而该共享程序段的指令和数据在执行过程中是不能被修改的。此外，共享段也有可能被置换出主程中是不能被修改的。此外，共享段也有可能被置换出主存，显然，一个正在被某个进程使用或即将被某个进程使存，显然，一个正在被某个进程使用或即将被某个进程使用的共享段是不应该置换出主存的，因此可以在段表中设用的共享段是不应该置换出主存的，因此可以在段表中设置共享位来判别该段是否正在被某个进程调用。置共享位来判别该段是否正在被某个进程调用。操作系统教程课件第75页机械工业出版社4.5.5分页和分段存储管理的主要区别分页和分段存储管理的主

89、要区别n分页和分段系统都采用离散分配主存方式，都需要通过分页和分段系统都采用离散分配主存方式，都需要通过地址映射机构来实现地址变换，有许多相似之处。但两者又地址映射机构来实现地址变换，有许多相似之处。但两者又是完全不同的。具体表现如下。是完全不同的。具体表现如下。页是信息的物理单位，是系统管理的需要而不是用户页是信息的物理单位，是系统管理的需要而不是用户的需要；而段则是信息的逻辑单位，它含有一组意义相对完的需要；而段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段是为了更好地满足用户的需要。整的信息，分段是为了更好地满足用户的需要。页的大小固定且由系统决定，因而一个系统只能有一页的大小固

90、定且由系统决定，因而一个系统只能有一种大小的页面；而段的长度却不固定，由用户所编写的程序种大小的页面；而段的长度却不固定，由用户所编写的程序决定，通常由编译程序对源程序进行编译时根据信息的性质决定，通常由编译程序对源程序进行编译时根据信息的性质来划分。来划分。分页式作业的地址空间是一维的，页间的逻辑地址是分页式作业的地址空间是一维的，页间的逻辑地址是连续的；而分段式作业的地址空间则是二维的，段间的逻辑连续的；而分段式作业的地址空间则是二维的，段间的逻辑地址是不连续的。地址是不连续的。操作系统教程课件第76页机械工业出版社4.6段页式存储管理段页式存储管理 段段式式存存储储管管理理支支持持了了用

91、用户户的的观观点点，但但每每段段必必须须占占据据主主存存储储器器的的连连续续区区域域，有有可可能能需需要要采采用用移移动动技技术术汇汇集集主主存存空空间间，为为此此，兼兼用用分分段段和和分分页页的的方方法法，构构成成可可分分页页的的段段式式存存储储管管理理，通通常常被被称称为为是是“段段页页式式存存储储管管理理”。段段页页式式存存储储管管理理兼兼顾顾了了段式在逻辑上的清晰和页式在管理上方便的优点。段式在逻辑上的清晰和页式在管理上方便的优点。用用户户对对作作业业采采用用分分段段组组织织，每每段段独独立立编编程程，在在主主存存空空间间分分配配时时，再再把把每每段段分分成成若若干干个个页页面面，这这

92、样样每每段段不不必必占占据据连连续续的主存空间，可把它按页存放在不连续的主存块中。的主存空间，可把它按页存放在不连续的主存块中。段页式存储管理的逻辑地址格式如下：段页式存储管理的逻辑地址格式如下：操作系统教程课件第77页段号（S）页号（P）页内地址（W）机械工业出版社4.6段页式存储管理段页式存储管理 段页式存储管理为每一个装入主存的作业建立一张段表，段页式存储管理为每一个装入主存的作业建立一张段表，且对每一段建立一张页表。段表的长度由作业分段的个数决定，且对每一段建立一张页表。段表的长度由作业分段的个数决定，段表中的每一个表目指出本段页表的始址和长度。页表的长度段表中的每一个表目指出本段页表

93、的始址和长度。页表的长度则由对应段所划分的页面数所决定，页表中的每一个表目指出则由对应段所划分的页面数所决定，页表中的每一个表目指出本段的逻辑页号与主存物理块号之间的对应关系。段页式存储本段的逻辑页号与主存物理块号之间的对应关系。段页式存储管理中段表、页表之间的关系管理中段表、页表之间的关系如图如图4-30所示所示。操作系统教程课件第78页机械工业出版社4.6段页式存储管理段页式存储管理 执行指令时，地址机构根据逻辑地址中的段号查找段表，执行指令时，地址机构根据逻辑地址中的段号查找段表，得到该段的页表始址，然后根据逻辑地址中的页号查找该页得到该段的页表始址，然后根据逻辑地址中的页号查找该页表，

94、得到对应的主存块号，由主存块号与逻辑地址中的页内表，得到对应的主存块号，由主存块号与逻辑地址中的页内地址形成可访问的物理地址。如果逻辑地址中的段号超出了地址形成可访问的物理地址。如果逻辑地址中的段号超出了段表中的最大段号或者页号超出了该段页表中的最大页号，段表中的最大段号或者页号超出了该段页表中的最大页号，都将形成都将形成“地址越界地址越界”的程序性中断事件。可以看出，由逻辑的程序性中断事件。可以看出，由逻辑地址到物理地址的变换过程中，需要三次访问主存，第一次地址到物理地址的变换过程中，需要三次访问主存，第一次是访问主存中的段表，获得该段对应页表的始址，第二次是是访问主存中的段表，获得该段对应

95、页表的始址，第二次是访问页表，获得指令或数据的物理地址，最后再按物理地址访问页表，获得指令或数据的物理地址，最后再按物理地址存取信息。段页式存储管理的地址转换机构存取信息。段页式存储管理的地址转换机构如图如图4-31所示所示。操作系统教程课件第79页机械工业出版社4.6段页式存储管理段页式存储管理操作系统教程课件第80页图 4-31 段页式存储管理的地址转换机构示意图机械工业出版社4.7虚拟存储管理方式虚拟存储管理方式 前前面面所所介介绍绍的的各各种种存存储储管管理理方方式式具具有有一一个个共共同同的的特特点点，即即作作业业必必须须一一次次性性全全部部装装入入主主存存空空间间后后才才能能运运行

96、行，直直至至作作业业运运行行结结束束后后才才释释放放所所占占有有的的全全部部主主存存资资源源。这这样样就就会会出出现以下情况：现以下情况： （1 1）当当主主存存空空间间不不能能满满足足作作业业地地址址空空间间要要求求时时，作作业业就就不能装入主存，无法运行。不能装入主存，无法运行。 （2 2）当当有有大大量量作作业业要要求求运运行行时时，由由于于主主存存容容量量有有限限，只只能将少数作业装入主存运行，而其他作业留在辅存上等待。能将少数作业装入主存运行，而其他作业留在辅存上等待。 操作系统教程课件第81页机械工业出版社4.7虚拟存储管理方式虚拟存储管理方式 早早在在19681968年年，Den

97、ning.PDenning.P就就曾曾指指出出：程程序序执执行行时时呈呈现现出出局局部部性性特特征征，即即在在一一较较短短的的时时间间内内，程程序序的的执执行行仅仅局局限限于于某某个个部部分分；而而它它所所访访问问的的存存储储空空间间也也局局限限在在某某个个区区域域中中。局局限限性表现在时间局限性和空间局限性两方面。性表现在时间局限性和空间局限性两方面。 （）时时间间局局限限性性：如如果果程程序序中中的的某某条条指指令令一一旦旦执执行行，则则不不久久以以后后该该指指令令可可能能再再次次执执行行；如如果果某某数数据据被被访访问问，则则不不久久以以后后该该数数据据可可能能再再次次被被访访问问。例例

98、如如程程序序中中存存在在着着的的大大量量的的迭代循环、临时变量和子程序调用等迭代循环、临时变量和子程序调用等。 （）空间局限性：一旦程序访问了某个存储单元，在（）空间局限性：一旦程序访问了某个存储单元，在不久以后，其附近的存储单元也将被访问，即程序在一段时不久以后，其附近的存储单元也将被访问，即程序在一段时间内所访问的地址，可能集中在一定的范围之内。例如对数间内所访问的地址，可能集中在一定的范围之内。例如对数组、表或数据堆栈进行操作。组、表或数据堆栈进行操作。机械工业出版社4.7.1虚拟存储器虚拟存储器 基基于于局局部部性性原原理理，可可以以把把作作业业信信息息保保存存在在磁磁盘盘上上，当当作

99、作业业请请求求装装入入时时，只只需需将将当当前前运运行行所所需需要要的的一一部部分分信信息息先先装装入入主主存存，作作业业执执行行过过程程时时，如如果果所所要要访访问问的的信信息息已已调调入入主主存存，则则可可继继续续执执行行；如如果果信信息息尚尚未未装装入入主主存存，再再将将这这些些信信息息调调入入主主存存，使使程程序序继继续续执执行行；如如果果此此时时主主存存已已满满，无无法法再再装装入入新新的的信信息息，则则系系统统将将主主存存中中暂暂时时不不用用的的信信息息置置换换到到磁磁盘盘上上，腾腾出出主主存存空空间间后后，再再将将所所需需要要的的信信息息调调入入主主存存，使使程程序序继继续续执执

100、行行。这这样样，可可使使一一个个大大的的用用户户程程序序得得以以在在比比较较小小的的主主存存空空间间中中运运行行，也也可可以以在在主主存存中中同同时时装装入入更更多多的的作作业业使使它它们们并并发发执执行行。这这不不仅仅使使主主存存空空间间能能充充分分地地被被利利用用，而而且且用用户户编编制制程程序序时时可可以以不不必必考考虑虑主主存存储储器器的的实实际际容容量量，允允许许用用户户的的逻逻辑辑地地址址空空间间大大于于主主存存的的实实际际容容量量。从从用用户户的的角角度度来来看看，好好像像计计算算机机系系统统提提供供了了一一个个容容量量很很大大的的主主存存储储器，我们称它为器，我们称它为“虚拟存

101、储器虚拟存储器”。操作系统教程课件第83页机械工业出版社4.7.1虚拟存储器虚拟存储器虚虚拟拟存存贮贮器器指指一一种种实实际际上上并并不不存存在在的的虚虚假假存存贮贮器器，它它是是系系统统为为了了满满足足应应用用对对存存贮贮器器容容量量的的巨巨大大需需求求而而构构造造的的一一个个非非常常大大的的地地址址空空间间。它它使使用用户户在在编编程程时时无无需需担担心心存存贮贮器器之之不不足足，好像有一个无限大的存贮器供其使用一样。好像有一个无限大的存贮器供其使用一样。虚虚拟拟存存储储器器是是建建立立在在离离散散分分配配的的存存储储管管理理方方式式的的基基础础上上，它它允允许许将将一一个个作作业业分分多

102、多次次调调入入主主存存。虚虚拟拟存存储储器器实实际际上上是是为为了了扩扩大大主主存存容容量量而而采采用用的的一一种种设设计计技技巧巧，虚虚拟拟存存储储器器的的容容量量由由计计算算机机的的地地址址结结构构和和辅辅助助存存储储器器的的容容量量所所决决定定，与与实实际际主主存存储储器器的的容容量量无无关关，其其逻逻辑辑容容量量由由主主存存和和辅辅存存容容量量之之和和决决定定，其其运运行行速速度度接接近近于于主主存存储储器器的的速速度度，而而每每位位的的成成本本却却又又接接近近辅助存储器。辅助存储器。 可见，虚拟存储技术是一种性能非常优越的存储器管理可见，虚拟存储技术是一种性能非常优越的存储器管理技术

103、。技术。操作系统教程课件第84页机械工业出版社4.7.1虚拟存储器虚拟存储器 虚拟存储器具有离散性、多次性、对换性和虚拟性四虚拟存储器具有离散性、多次性、对换性和虚拟性四大主要特征。大主要特征。1、离散性、离散性2、多次性、多次性3、对换性、对换性4、虚拟性、虚拟性操作系统教程课件第85页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 请请求求分分页页式式存存储储管管理理是是在在页页式式存存储储管管理理的的基基础础上上，增增加加请请求求分分页页功功能能和和页页面面置置换换功功能能实实现现的的虚虚拟拟存存储储系系统统。请请求求分分页页式式存存储储管管理理允允许许作作业业只只装装入入

104、部部分分页页面面，就就启启动动运运行行，在在执执行行过过程程中中，如如果果所所要要访访问问的的页页已已调调入入主主存存，则则进进行行地地址址转转换换，得得到到欲欲访访问问的的主主存存物物理理地地址址；如如果果所所要要访访问问的的页页面面不不在在主主存存中中，则则产产生生一一个个“缺缺页页中中断断”，如如果果此此时时主主存存能能容容纳纳新新页页，则则启启动动磁磁盘盘I/OI/O将将其其调调入入主主存存；如如果果主主存存已已满满，则则通通过过页页面面置置换功能将当前所需的页面调入。换功能将当前所需的页面调入。操作系统教程课件第86页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 1.

105、 1. 请求分页式存储的管理请求分页式存储的管理 为为了了实实现现请请求求分分页页和和页页面面置置换换功功能能，系系统统必必须须提提供供必必要要的硬件支持和相应的软件支持。一般需要以下支持：的硬件支持和相应的软件支持。一般需要以下支持： 请求分页的页表机制请求分页的页表机制 缺页中断机构缺页中断机构 地址变换机构地址变换机构 页面置换算法页面置换算法操作系统教程课件第87页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理（1）页表机制）页表机制请请求求分分页页式式存存储储管管理理的的主主要要依依据据就就是是页页表表。由由于于只只是是将将作作业业的的部部分分页页面面调调入入主主存存，

106、其其余余部部分分仍仍存存放放在在辅辅助助存存储储器器上上，因因此此必必须须指指出出哪哪些些页页面面已已在在主主存存，哪哪些些页页面面还还没没有有装装入入。为为此需要将页表增加若干项，修改后的页表格式如下所示：此需要将页表增加若干项，修改后的页表格式如下所示：操作系统教程课件第88页页号物理块号状态位访问字段修改位辅存地址机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 （2）缺页中断机构）缺页中断机构请请求求分分页页式式存存储储管管理理中中，当当所所要要访访问问的的页页面面不不在在主主存存时时，则则由由硬硬件件发发出出一一个个缺缺页页中中断断，操操作作系系统统必必须须处处理理这这个

107、个中中断断，将将所所需需要要的的页页面面调调入入主主存存，图图4-32给给出出缺缺页页中中断断处处理理的的流流程程。在在处处理理缺缺页页中中断断的的过过程程中中，同同样样需需要要保保护护现现场场、分分析析中中断断源源、转转入入中中断断处处理理程程序序进进行行处处理理、恢恢复复现现场场等等步步骤骤，但但缺缺页中断又与一般的中断有着明显的区别，主要表现在：页中断又与一般的中断有着明显的区别，主要表现在：操作系统教程课件第89页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理操作系统教程课件第90页图 4-32 缺页中断处理流程机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理

108、 在在处处理理缺缺页页中中断断的的过过程程中中，同同样样需需要要保保护护现现场场、分分析析中中断断源源、转转入入中中断断处处理理程程序序进进行行处处理理、恢恢复复现现场场等等步步骤骤，但但缺缺页中断又与一般的中断有着明显的区别，主要表现在：页中断又与一般的中断有着明显的区别，主要表现在：1）在在指指令令执执行行期期间间产产生生和和处处理理中中断断信信号号。通通常常，CPU在在一一条条指指令令结结束束后后接接收收中中断断请请求求并并响响应应。而而缺缺页页中中断断则则是是在在指指令令执执行行期期间间，所所要要访访问问的的指指令令或或数数据据不不在在主主存存时时所所产产生生和和处理的。处理的。2）一

109、条指令在执行期间可能）一条指令在执行期间可能产生多次缺页中断。产生多次缺页中断。操作系统教程课件第91页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 3）地址变换机构）地址变换机构 在请求分页式存储管理中，当作业访问某页时，硬件的在请求分页式存储管理中，当作业访问某页时，硬件的地址转换机构首先查找快表，若找到，并且其状态位为地址转换机构首先查找快表，若找到，并且其状态位为“1”，则按指定的物理块号进行地址转换，得到其对应的物理地，则按指定的物理块号进行地址转换，得到其对应的物理地址；若该页的状态位为址；若该页的状态位为“0”，则由硬件发出一个，则由硬件发出一个“缺页中断缺页中断

110、”，按照页表中指出的辅存地址，由操作系统将其调入主存，按照页表中指出的辅存地址，由操作系统将其调入主存，并在页表中填上其分配的物理块号，修改状态位、访问位，并在页表中填上其分配的物理块号，修改状态位、访问位，对于写指令，置修改位为对于写指令，置修改位为“1”，然后按页表中的物理块号和，然后按页表中的物理块号和页内地址形成物理地址，页内地址形成物理地址，图图4-34给出请求分页式存储管理中给出请求分页式存储管理中的地址变换过程。的地址变换过程。 如果在快表中未找到该页的页表项时，则到主存中查找如果在快表中未找到该页的页表项时，则到主存中查找页表，若该页尚未调入主存，系统产生缺页中断，请求操作页表

111、，若该页尚未调入主存，系统产生缺页中断，请求操作系统将该页面调入，同时将此页表项写入快表。系统将该页面调入，同时将此页表项写入快表。操作系统教程课件第92页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理操作系统教程课件第93页图 4-34 请求式分页存储管理地址变换过程机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 2页面置换算法页面置换算法 在在作作业业运运行行过过程程中中，如如果果所所要要访访问问的的页页面面不不在在主主存存中中，需需要要把把他他们们调调入入主主存存，但但主主存存中中已已没没有有空空闲闲空空间间时时，为为了了保保证证作作业业的的运运行行，系系统统

112、必必须须按按一一定定的的算算法法选选择择一一个个已已在在主主存存中中的的页页面面，将将它它暂暂时时调调出出主主存存，让让出出主主存存空空间间，用用来来存存放放所所需需调调入入的的页页面面，这这个个工工作作称称为为“页页面面置置换换”。选选择择换换出出页面的算法称为页面的算法称为“页面置换算法页面置换算法”。 刚刚被被调调出出的的页页面面又又立立即即要要用用，因因而而又又要要把把它它调调入入，而而调调入入不不久久又又被被选选中中调调出出，调调出出不不久久又又被被调调入入，如如此此反反复复，使使调调度度非非常常频频繁繁，以以至至于于大大部部分分时时间间都都花花费费在在来来回回调调度度上上。这这种种

113、现现象象称称为为“抖抖动动”或或称称“颠颠簸簸”。一一个个好好的的置置换换算算法法应应该该尽可能地减少和避免抖动现象的发生。尽可能地减少和避免抖动现象的发生。 操作系统教程课件第94页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 （1 1）最佳置换算法（）最佳置换算法（OPTOPT） 最最佳佳置置换换算算法法选选择择被被淘淘汰汰的的页页面面将将是是以以后后永永远远不不再再使使用用，或或者者是是在在将将来来最最长长时时间间内内不不再再被被访访问问的的页页面面，这这样样，产产生生的的缺缺页页中中断断次次数数将将会会是是最最少少的的。采采用用最最佳佳置置换换算算法法通通常常可可获获得

114、得最最低低的的缺缺页页中中断断率率，但但这这是是一一种种理理想想化化的的算算法法，无法实现。但是这个算法可以作为衡量其它算法的标准。无法实现。但是这个算法可以作为衡量其它算法的标准。操作系统教程课件第95页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理n 假定某进程共有假定某进程共有8 8页，且系统为之分配了三个物理块，页，且系统为之分配了三个物理块，并有以下页面调度序列：并有以下页面调度序列：7 7，0 0，1 1，2 2，0 0，3 3，0 0，4 4，2 2，3 3，0 0，3 3，2 2，1 1，2 2，0 0，1 1，7 7，0 0，1 1n 采用最佳置换算法，只发生了

115、采用最佳置换算法，只发生了9 9次页面置换，缺页中断次页面置换，缺页中断率为率为45%45%。操作系统教程课件第96页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 （2 2）先进先出页面置换算法（）先进先出页面置换算法（FIFOFIFO） 先先进进先先出出页页面面置置换换算算法法认认为为刚刚被被调调入入的的页页面面在在最最近近的的将将来来被被访访问问的的可可能能很很大大，而而在在主主存存中中驻驻留留时时间间最最长长的的页页面面在在最最近近的的将将来来被被访访问问的的可可能能性性最最小小。因因此此，FIFOFIFO算算法法总总是是淘淘汰汰最最先先进进入入主主存存的的页页面面，即即

116、淘淘汰汰在在主主存存中中驻驻留留时间最长的页面。时间最长的页面。 FIFOFIFO算算法法只只需需要要把把装装入入主主存存的的页页面面按按调调入入的的先先后后次次序序链链接接成成一一个个队队列列，并并设设置置一一个个替替换换指指针针，指指针针始始终终指指向向最最先先装装入入主主存存的的页页面面，每每次次页页面面置置换换时时，总总是是选选择择替替换换指针所指示的页面调出。指针所指示的页面调出。操作系统教程课件第97页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理n 图图4-364-36给出了以给出了以OPTOPT算法中的例子采用算法中的例子采用FIFOFIFO算法时保留算法时保留在

117、主存中页面变化的情况。在主存中页面变化的情况。采用采用FIFOFIFO置置换算法一共算法一共发生了生了1515次次页面置面置换，缺，缺页中断率中断率为75%75%，页面淘汰的面淘汰的顺序序为7 7，0 0，1 1，2 2，3 3，0 0，4 4，2 2，3 3，0 0，1 1，2 2。n FIFO算法简单，易实现，但效率不高。操作系统教程课件第98页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理n 先进先出算法存在一种异常现象。一般来说，对于任先进先出算法存在一种异常现象。一般来说，对于任一个作业，系统分配给它的主存物理块数越接近于它所要一个作业，系统分配给它的主存物理块数越接近

118、于它所要求的页面数，则发生缺页中断的次数会越少，如果一个作求的页面数，则发生缺页中断的次数会越少，如果一个作业获得它所要求的全部物理块数，则不会发生缺页中断现业获得它所要求的全部物理块数，则不会发生缺页中断现象。但是，采用象。但是，采用FIFOFIFO算法时，在未给作业分配满足它所要算法时，在未给作业分配满足它所要求的页面时，有时会出现这样的奇怪现象：分配的物理块求的页面时，有时会出现这样的奇怪现象：分配的物理块数增多，而缺页中断次数反而增加。这种现象称之为数增多，而缺页中断次数反而增加。这种现象称之为BeladyBelady现象。现象。操作系统教程课件第99页机械工业出版社4.7.2请求分页

119、式存储管理请求分页式存储管理操作系统教程课件第100页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 （3 3）最近最少用页面置换算法（）最近最少用页面置换算法（LRULRU） 最最近近最最少少用用页页面面置置换换算算法法总总是是选选择择最最近近一一段段时时间间内内最最长长时时间间没没有有被被访访问问过过的的页页面面调调出出。LRULRU的的提提出出基基于于程程序序执执行行的的局局部部性性原原理理，即即认认为为那那些些刚刚被被访访问问的的页页面面，可可能能在在最最近近的的将将来来还还会会经经常常访访问问它它们们，而而那那些些在在较较长长时时间间里里未未被被访访问问的的页页面面，一

120、一般般在在最最近近的的将将来来不不会会再再访访问问。为为了了记记录录页页面面自自上上次次被被访访问问以以来来所所经经过过的的时时间间，需需要要在在页页表表中中增增加加一一个个“引引用用位位”标标志志，在在每每次次被被访访问问后后将将引引用用位位置置零零，重重新新计计时时，这这样样，在在发发生生缺缺页页中中断断需需要要调调入入新新的的页页面面时时，通通过过检检查查页页表表中中各各页页的的引引用用位位，选选择择计计时时最最长长时时间间没没有有被被访访问问过过的的页页面面淘淘汰汰，并并且且把把主主存存中中所所有有页页面面的的引引用用位位全全部部清清零零，重重新新计计时。时。操作系统教程课件第101页

121、机械工业出版社n图图4-39所示为在所示为在OPT算法的例子中采用算法的例子中采用LRU算法时，算法时，保留在主存中页面的变化情况。该进程执行过程中，共产保留在主存中页面的变化情况。该进程执行过程中，共产生了生了12次缺页中断，缺页中断率为次缺页中断，缺页中断率为60%，页面淘汰的顺，页面淘汰的顺序为序为7，1，2，3，0，4，0，3，2。操作系统教程课件第102页4.7.2请求分页式存储管理请求分页式存储管理机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 LRU近似算法（时钟置换算法近似算法（时钟置换算法Clock）是在页表中为）是在页表中为每一页增加一个引用位信息，当该页被访

122、问时，由硬件将每一页增加一个引用位信息，当该页被访问时，由硬件将它的引用位信息置为它的引用位信息置为1，操作系统选择一个时间周期，操作系统选择一个时间周期T，每隔一个周期每隔一个周期T，将页表中所有页面的引用位信息置，将页表中所有页面的引用位信息置0，这，这样，在时间周期样，在时间周期T内，被访问过的页面的引用位为内，被访问过的页面的引用位为1，而没，而没有被访问过的页面的引用位仍为有被访问过的页面的引用位仍为0。当产生缺页中断时，可。当产生缺页中断时，可以从引用位为以从引用位为0的页面中选择一页调出，同时将所有页面的的页面中选择一页调出，同时将所有页面的引用位信息全部重置引用位信息全部重置0

123、。这种近似算法的实现比较简单，但。这种近似算法的实现比较简单，但关键在于时间周期关键在于时间周期T大小的确定。大小的确定。T太大，可能所有的引太大，可能所有的引用位都变成用位都变成1，找不出最近最少使用的页面淘汰；，找不出最近最少使用的页面淘汰；T太小，太小，引用位为引用位为0的页面可能很多，而无法保证所选择的页面是最的页面可能很多，而无法保证所选择的页面是最近最少使用的。近最少使用的。操作系统教程课件第103页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 淘汰一个页面时，如果该页面已被修改过，必须将它淘汰一个页面时，如果该页面已被修改过，必须将它重新写回磁盘；但如果淘汰的是未

124、被修改过的页面，就不需重新写回磁盘；但如果淘汰的是未被修改过的页面，就不需要写盘操作了，这样看来淘汰修改过的页面比淘汰未被修改要写盘操作了，这样看来淘汰修改过的页面比淘汰未被修改过的页面开销要大。如果把页表中的过的页面开销要大。如果把页表中的“引用位引用位”和和“修改位修改位”结结合起来使用可以改进时钟页面替换算法，它们一共组合成四合起来使用可以改进时钟页面替换算法，它们一共组合成四种情况：种情况：（1）最近没有被引用，没有被修改（）最近没有被引用，没有被修改（r=0，m=0）（2）最近被引用，没有被修改（）最近被引用，没有被修改（r=1，m=0）（3）最近没有被引用，但被修改（）最近没有被引

125、用，但被修改（r=0，m=1）（4）最近被引用过，也被修改过（）最近被引用过，也被修改过（r=1，m=1）操作系统教程课件第104页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 改进的时钟页面替换算法就是扫描队列中的所有页面，改进的时钟页面替换算法就是扫描队列中的所有页面，寻找一个既没有被修改且最近又没有被引用过的页面，把这寻找一个既没有被修改且最近又没有被引用过的页面，把这样的页面挑出来作为首选页面淘汰是因为没有被修改过，淘样的页面挑出来作为首选页面淘汰是因为没有被修改过，淘汰时不用把它写回磁盘。如果第一步没找到这样的页面，算汰时不用把它写回磁盘。如果第一步没找到这样的页面，

126、算法再次扫描队列，欲寻找一个被修改过但最近没有被引用过法再次扫描队列，欲寻找一个被修改过但最近没有被引用过的页面；虽然淘汰这种页面需写回磁盘，但依据程序局部性的页面；虽然淘汰这种页面需写回磁盘，但依据程序局部性原理，这类页面一般不会被马上再次使用。如果第二步也失原理，这类页面一般不会被马上再次使用。如果第二步也失败了，则所有页面已被标记为最近未被引用，可进入第三步败了，则所有页面已被标记为最近未被引用，可进入第三步扫描。扫描。Macintosh的虚存管理采用了这种策略，其主要优点的虚存管理采用了这种策略，其主要优点是没有被修改过的页面会被优先选出来，淘汰这种页面时不是没有被修改过的页面会被优先

127、选出来，淘汰这种页面时不必写回磁盘，从而节省时间，但查找一个淘汰页面可能会经必写回磁盘，从而节省时间，但查找一个淘汰页面可能会经过多轮扫描，算法的实现开销较大。过多轮扫描，算法的实现开销较大。操作系统教程课件第105页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 （4 4）最近最不常用页面置换算法（）最近最不常用页面置换算法（LFULFU） 最最近近最最不不常常用用置置换换算算法法总总是是选选择择被被访访问问次次数数最最少少的的页页面面调调出出，即即认认为为在在过过去去的的一一段段时时间间里里被被访访问问次次数数多多的的页页面面可可能能经常需要访问。经常需要访问。 一种简单的实

128、现方法是为每一页设置一个计数器，页面一种简单的实现方法是为每一页设置一个计数器，页面每次被访问后其对应的计数器加每次被访问后其对应的计数器加1 1，每隔一定的时间周期，每隔一定的时间周期T T，将所有计数器全部清零。这样，在发生缺页中断时，选择计将所有计数器全部清零。这样，在发生缺页中断时，选择计数器值最小的对应页面淘汰，显然它是最近最不常用的页面，数器值最小的对应页面淘汰，显然它是最近最不常用的页面，同时把所有计数器清零。这种算法实现比较简单，但代价很同时把所有计数器清零。这种算法实现比较简单，但代价很高，同时有一个关键问题是如何选择一个合适的时间周期高，同时有一个关键问题是如何选择一个合适

129、的时间周期T T。操作系统教程课件第106页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 3缺页中断率分析缺页中断率分析 虚虚拟拟存存储储系系统统解解决决了了有有限限主主存存贮贮器器的的容容量量限限制制问问题题，能能使使更更多多的的作作业业同同时时多多道道运运行行，从从而而提提高高系系统统的的效效率率，但但缺缺页页中中断断处处理理需需要要系系统统的的额额外外开开销销，影影响响系系统统效效率率，因因此此应应尽尽可能减少缺页中断的次数，降低缺页中断率。可能减少缺页中断的次数，降低缺页中断率。 假假定定一一个个作作业业共共有有n n页页，系系统统分分配配给给它它的的主主存存块块是是m

130、 m块块（m m、n n均均为为正正整整数数，且且1mn1mn）。因因此此，该该作作业业最最多多有有m m页页可可同同时时被被装装入入主主存存。如如果果作作业业执执行行中中访访问问页页面面的的总总次次数数为为A A，其其中中有有F F次次访访问问的的页页面面尚尚未未装装入入主主存存，故故产产生生了了F F次次缺缺页页中中断。现定义：断。现定义：f fF/AF/A， 则则f f称为称为“缺页中断率缺页中断率”。操作系统教程课件第107页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 缺缺页页中中断断率率与与缺缺页页中中断断的的次次数数有有关关。因因此此影影响响缺缺页页中中断断率的因

131、素有：率的因素有： （1 1）分配给作业的主存块数）分配给作业的主存块数 系统分配给作业的主存块数多，则同时装入主存的页面系统分配给作业的主存块数多，则同时装入主存的页面数就多，那么缺页中断次数就少，缺页中断率就低，反之，数就多，那么缺页中断次数就少，缺页中断率就低，反之，缺页中断率就高。缺页中断率就高。 图图4-404-40示出了处理器的利用率与多道程序之间的关系。示出了处理器的利用率与多道程序之间的关系。操作系统教程课件第108页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 图图4-414-41所示所示存储容量与缺页中断次数的关系。存储容量与缺页中断次数的关系。 图中可以看

132、出，主存物理块数增加到临界值以后，即使图中可以看出，主存物理块数增加到临界值以后，即使再增加较多的物理块，进程的缺页中断次数也不再明显减少。再增加较多的物理块，进程的缺页中断次数也不再明显减少。大多数程序都有这样一个特定点，在这个特定点以后再增加大多数程序都有这样一个特定点，在这个特定点以后再增加主存容量，缺页中断次数的减少并不明显。主存容量，缺页中断次数的减少并不明显。操作系统教程课件第109页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理n程序在运行时对页面的访问是不均匀的，即往往在程序在运行时对页面的访问是不均匀的，即往往在某段时间内访问仅局限于较少的若干页面，如果能够预某

133、段时间内访问仅局限于较少的若干页面，如果能够预知程序在某段时间间隔内要访问哪些页面，并能将它们知程序在某段时间间隔内要访问哪些页面，并能将它们提前调入主存，将会大大地降低缺页率，从而减少置换提前调入主存，将会大大地降低缺页率，从而减少置换工作，提高工作，提高CPU的利用率。的利用率。n对于给定的访问序列选取定长的时间间隔对于给定的访问序列选取定长的时间间隔( )，称为，称为工作集窗口，落在工作集窗口中的页面集合称为工作集。工作集窗口，落在工作集窗口中的页面集合称为工作集。即工作集是指在某段时间间隔里，进程实际要访问的页即工作集是指在某段时间间隔里，进程实际要访问的页面的集合。把某进程在时间面的

134、集合。把某进程在时间t的工作集记为的工作集记为w(t, ),把变量把变量 称为工作集称为工作集“窗口尺寸窗口尺寸”。操作系统教程课件第110页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理假如有以下页面访问序列，窗口尺寸=9： 26157775162341234443434441327 |-| |-| t1 t2则t1 时刻的工作集 w(t1)=1,2,5,6,7 ；t2 时刻的工作集 w(t2)=3,4操作系统教程课件第111页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理n 在有些操作系统中，如在有些操作系统中，如Windows，虚拟存储管理程序，虚拟存储管理程

135、序为每一个进程分配固定数量的物理块，并且这个数目可以为每一个进程分配固定数量的物理块，并且这个数目可以进行动态的调整。这个数目就是由每个进程的工作集来确进行动态的调整。这个数目就是由每个进程的工作集来确定，并且根据主存的负荷和进程的缺页情况动态地调整其定，并且根据主存的负荷和进程的缺页情况动态地调整其工作集。工作集。n当每个工作集都已达到最小值时，虚存管理程序跟踪进当每个工作集都已达到最小值时，虚存管理程序跟踪进程的缺页数量，根据主存中自由页面数量可以适当增加其程的缺页数量，根据主存中自由页面数量可以适当增加其工作集的大小。工作集的大小。操作系统教程课件第112页机械工业出版社 （2 2）页面

136、的大小）页面的大小 页页面面的的大大小小影影响响页页表表的的长长度度、页页表表的的检检索索时时间间、置置换换页页面面的的时时间间、可可能能的的页页内内零零头头的的大大小小等等，对对缺缺页页中中断断的的次次数数也也有有一一定定的的影影响响。如如果果划划分分的的页页面面大大，一一个个作作业业的的页页面面数数就就少少，页页表表所所占占用用的的主主存存空空间间少少且且查查表表速速度度快快，在在系系统统分分配配相相同同主主存存块块的的情情况况下下，发发生生缺缺页页中中断断的的次次数数减减少少，降降低低了了缺缺页页中中断断率率，但但是是一一次次换换页页需需要要的的时时间间延延长长，可可能能产产生生的的页页

137、内内零零头头所所带带来来的的空空间间浪浪费费较较大大。反反之之，页页面面小小，一一次次换换页页需需要要的的时时间间就就短短，可可能能产产生生的的页页内内零零头头少少，空空间间利利用用率率提提高高，但但是是一一个个作作业业的的页页面面数数多多，页页表表所所占占用用的的主主存存空空间间长长且且查查表表速速度度慢慢，在在系系统统分分配配相相同同主主存存块块的的情情况况下下，发发生生缺缺页页中中断断的的次次数数增增多多，增加了缺页中断率。增加了缺页中断率。 操作系统教程课件第113页4.7.2请求分页式存储管理请求分页式存储管理机械工业出版社 （3 3）程序编制方法）程序编制方法 程程序序编编制制的的

138、方方法法不不同同，对对缺缺页页中中断断的的次次数数也也有有很很大大影影响响。缺缺页页中中断断率率与与程程序序的的局局部部化化程程度度密密切切相相关关。一一般般，希希望望编编制制的的程程序序能能经经常常集集中中在在几几个个页页面面上上进进行行访访问问，以以减减少少缺缺页页中中断断次数，降低缺页中断率。次数，降低缺页中断率。 例例如如，一一个个程程序序要要将将128128128128数数组组置置初初值值“0 0”。现现假假设设分分配配给给该该程程序序的的主主存存块块数数只只有有一一块块，页页面面的的大大小小为为每每页页128128个个字字，数数组组中中每每一一行行元元素素存存放放在在一一页页中中。

139、开开始始第第一一页页已已经经调调入主存。入主存。操作系统教程课件第114页4.7.2请求分页式存储管理请求分页式存储管理机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 若程序如下，则产生（若程序如下，则产生（128*128-1128*128-1）次缺页中断。）次缺页中断。intint A A128128128128; ;for (j=0;j128;j+ )for (j=0;j128;j+ ) for (i=0;i128;i+) for (i=0;i128;i+) A Ai ij j=0; =0; 如果重新编制这个程序：如果重新编制这个程序：intint A A1281281281

140、28; ;for (i=0;i128;i+ )for (i=0;i128;i+ ) for (j=0;j128;j+) for (j=0;j128;j+) A Ai ijj=0; =0; 则总共产生（则总共产生（128-1128-1）次缺页中断。）次缺页中断。操作系统教程课件第115页机械工业出版社4.7.2请求分页式存储管理请求分页式存储管理 （4 4）页面调度算法）页面调度算法 页页面面调调度度算算法法对对缺缺页页中中断断率率的的影影响响也也很很大大，如如果果选选择择不不当当，有有可可能能产产生生抖抖动动现现象象。理理想想的的调调度度算算法法是是当当要要装装入入一一个个新新页页而而必必须须

141、调调出出一一个个页页面面时时，所所选选择择的的调调出出页页应应该该是是以以后后再再也也不不使使用用的的页页或或者者是是距距离离当当前前最最长长时时间间以以后后才才使使用用的的页页。这这样的调度算法能使缺页中断率最低。样的调度算法能使缺页中断率最低。操作系统教程课件第116页机械工业出版社4.7.3请求分段式存储管理 请请求求分分段段式式存存储储管管理理以以段段式式存存储储管管理理为为基基础础，为为用用户户提提供供比比主主存存实实际际容容量量更更大大的的虚虚拟拟空空间间。请请求求分分段段式式存存储储管管理理把把作作业业的的各各个个分分段段信信息息保保留留在在磁磁盘盘上上，当当作作业业被被调调度度

142、进进入入主主存存时时，首首先先把把当当前前需需要要的的一一段段或或几几段段装装入入主主存存，便便可可启启动动执执行行，当当所所要要访访问问的的段段已已在在主主存存，则则将将逻逻辑辑地地址址转转换换成成绝绝对对地地址址；如如果果所所要要访访问问的的段段尚尚未未调调入入主主存存，则则产产生生一一个个“缺缺段段中中断断”，请请求求操操作作系系统统将将所所要要访访问问的的段段调调入入。为为实实现现请请求求分分段段式式存存储储管管理理，需需要要有有一一定定的的硬硬件件支支持持和和相相应应的的软件。软件。 请请求求分分段段式式存存储储管管理理所所需需要要的的硬硬件件支支持持有有段段表表机机制制、缺缺段中断

143、机构，以及地址变换机构等。段中断机构，以及地址变换机构等。操作系统教程课件第117页机械工业出版社4.7.3请求分段式存储管理 1 1段表机制段表机制 在在请请求求分分段段式式存存储储管管理理中中，段段表表是是进进行行段段调调度度的的主主要要依依据据。在在段段表表中中需需要要增增设设段段是是否否在在主主存存，各各段段在在磁磁盘盘上上的的存存储储位位置置，已已在在主主存存的的段段需需要要指指出出该该段段在在主主存存中中的的起起始始地地址址和和占占用用主主存存区区的的长长度度，还还可可设设置置该该段段是是否否被被修修改改，是是否否可可扩扩充充等等标志信息。请求分段式存储管理的段表结构如下：标志信息

144、。请求分段式存储管理的段表结构如下： 操作系统教程课件第118页段名段长段基址存取方式访问字段A修改位M状态位P扩充位辅存始址机械工业出版社4.7.3请求分段式存储管理 2 2缺段中断机构缺段中断机构 在在请请求求分分段段式式存存储储管管理理中中，当当所所要要访访问问的的段段尚尚未未调调入入主主存存时时，则则由由缺缺段段中中断断机机构构产产生生一一个个“缺缺段段中中断断”信信号号，请请求求操操作作系系统统将将所所要要访访问问的的段段调调入入主主存存。操操作作系系统统处处理理缺缺段段中中断的步骤如下：断的步骤如下： （1 1）空间分配：）空间分配： （2 2）修改段表：）修改段表： （3 3）新

145、的段被装入后应让作业重新执行被中断的指令，）新的段被装入后应让作业重新执行被中断的指令，这时就能在主存中找到所要访问的段，可以继续执行下去。这时就能在主存中找到所要访问的段，可以继续执行下去。操作系统教程课件第119页机械工业出版社4.7.3请求分段式存储管理 3 3地址变换机构地址变换机构 请求分段式存储管理方式中的地址变换在分段式存储管请求分段式存储管理方式中的地址变换在分段式存储管理系统的地址变换机构的基础上增加缺段中段请求及处理等理系统的地址变换机构的基础上增加缺段中段请求及处理等形成。形成。图图4-434-43示示出了请求分段式存储管理系统的地址变换过出了请求分段式存储管理系统的地址

146、变换过程。程。 请求分段式存储管理还是以段为单位进行主存空间的分请求分段式存储管理还是以段为单位进行主存空间的分配，整段信息的装入、调出，有时需要主存空间的移动，这配，整段信息的装入、调出，有时需要主存空间的移动，这些都增加了系统的开销。如果按段页式存储管理方式，每个些都增加了系统的开销。如果按段页式存储管理方式，每个作业仍然按逻辑分段，把每一段再分成若干页面，这样，在作业仍然按逻辑分段，把每一段再分成若干页面，这样，在请求式存储管理中，每一段不必占用连续的存储空间，可按请求式存储管理中，每一段不必占用连续的存储空间，可按页存放在不连续的主存块中，甚至当主存块不足时，可以将页存放在不连续的主存

147、块中，甚至当主存块不足时，可以将一段中的部分页面装入主存。这种管理方式称为一段中的部分页面装入主存。这种管理方式称为“请求段页请求段页式存储管理式存储管理”。操作系统教程课件第120页机械工业出版社4.7.3请求分段式存储管理 操作系统教程课件第121页机械工业出版社4.7.3请求分段式存储管理 采采用用请请求求段段页页式式存存储储管管理理，需需要要对对每每一一个个装装入入主主存存的的作作业业建建立立一一张张段段表表，对对每每一一段段建建立立一一张张页页表表，段段表表中中指指出出该该段段对对应应页页表表所所存存放放的的起起始始地地址址及及其其长长度度，页页表表中中应应指指出出该该段段的的每每一

148、一页页在在磁磁盘盘上上的的位位置置以以及及该该页页是是否否在在主主存存，若若在在主主存存，则则填填上上占占用用的的主主存存块块号号。作作业业执执行行时时按按段段号号查查找找段段表表，找找到到相相应应的的页页表表再再根根据据页页号号查查找找页页表表，由由状状态态位位判判定定该该页页是是否否已已在在主主存存，若若在在，则则进进行行地地址址转转换换，否否则则进进行行页页面面调调度。度。 请求段页式存储管理结合了请求分段式虚拟管理和请求请求段页式存储管理结合了请求分段式虚拟管理和请求分页式虚拟管理的优点，但增加了设置表格（段表、页表）分页式虚拟管理的优点，但增加了设置表格（段表、页表）和查表等开销。和

149、查表等开销。操作系统教程课件第122页机械工业出版社本章小结本章小结n存储器是计算机系统的重要组成部分。存储管理对主存中的用户存储器是计算机系统的重要组成部分。存储管理对主存中的用户区进行管理，其目的是尽可能地提高主存空间的利用率，使主存在成区进行管理，其目的是尽可能地提高主存空间的利用率，使主存在成本、速度和规模之间获得较好的权衡。存储管理的基本功能有主存空本、速度和规模之间获得较好的权衡。存储管理的基本功能有主存空间的分配与去配、地址转换、主存空间的共享与保护、主存空间的扩间的分配与去配、地址转换、主存空间的共享与保护、主存空间的扩充。充。n在现代计算机系统中，存储部件采用层次结构来组织，

150、具体可在现代计算机系统中，存储部件采用层次结构来组织，具体可分为寄存器、高速缓存、主存储器、磁盘缓存、磁盘、可移动存储介分为寄存器、高速缓存、主存储器、磁盘缓存、磁盘、可移动存储介质等组成，这样在成本、速度和规模等诸因素中能获得较好的性能价质等组成，这样在成本、速度和规模等诸因素中能获得较好的性能价格比。格比。n多道程序设计系统中，为了方便程序编制，用户程序中使用的多道程序设计系统中，为了方便程序编制，用户程序中使用的地址是逻辑地址，而地址是逻辑地址，而CPU则是按物理地址访问主存，读取指令和数据，则是按物理地址访问主存，读取指令和数据，为了保证程序的正确执行，需要进行地址转换。地址转换又称为

151、重定为了保证程序的正确执行，需要进行地址转换。地址转换又称为重定位，有静态重定位和动态重定位。采用动态重定位的系统支持程序的位，有静态重定位和动态重定位。采用动态重定位的系统支持程序的浮动。浮动。操作系统教程课件第123页机械工业出版社本章小结本章小结n早期单用户、单任务操作系统中主存管理采用单用户连续存储管理方式。早期单用户、单任务操作系统中主存管理采用单用户连续存储管理方式。现代操作系统支持多道程序设计，满足多道程序设计最简单的存储管理技术是现代操作系统支持多道程序设计，满足多道程序设计最简单的存储管理技术是分区管理，有固定分区管理和可变分区管理。固定分区管理采用顺序分配算法分区管理，有固

152、定分区管理和可变分区管理。固定分区管理采用顺序分配算法进行主存空间的分配，采用静态重定位方式将作业装入主存，通过上、下限寄进行主存空间的分配，采用静态重定位方式将作业装入主存，通过上、下限寄存器实现存储保护。可变分区管理的空间分配算法包括：最先适应、最优适应存器实现存储保护。可变分区管理的空间分配算法包括：最先适应、最优适应和最坏适应等算法。回收空间时检查是否存在与回收区相邻的空闲分区，如果和最坏适应等算法。回收空间时检查是否存在与回收区相邻的空闲分区，如果有，则将其合并成为一个新的空闲分区进行登记管理。可变分区管理一般采用有，则将其合并成为一个新的空闲分区进行登记管理。可变分区管理一般采用动

153、态重定位方式将作业装入主存，通过基址寄存器和限长寄存器等硬件实现存动态重定位方式将作业装入主存，通过基址寄存器和限长寄存器等硬件实现存储保护。可变分区管理可以有条件地采用移动技术使分散的空闲区汇集起来容储保护。可变分区管理可以有条件地采用移动技术使分散的空闲区汇集起来容纳新的作业。分区管理中，主存空间不足时，交换技术和覆盖技术可以达到扩纳新的作业。分区管理中，主存空间不足时，交换技术和覆盖技术可以达到扩充主存的目的。分区管理方式要求作业信息一次性连续装入主存，对空间的要充主存的目的。分区管理方式要求作业信息一次性连续装入主存，对空间的要求较高，为了解决这个矛盾，操作系统引入离散存储管理方式。离

154、散存储管理求较高，为了解决这个矛盾，操作系统引入离散存储管理方式。离散存储管理方式主要有页式存储管理、段式存储管理和段页式存储管理。离散存储管理允方式主要有页式存储管理、段式存储管理和段页式存储管理。离散存储管理允许将一个作业信息存储在不相邻的主存空间中，通过操作系统建立页表（或段许将一个作业信息存储在不相邻的主存空间中，通过操作系统建立页表（或段表）数据结构实现逻辑地址空间与物理地址空间的映射，实现地址空间的保护。表）数据结构实现逻辑地址空间与物理地址空间的映射，实现地址空间的保护。操作系统教程课件第124页机械工业出版社本章小结本章小结n虚拟存储器的实现借助于大容量的辅助存储器（如磁盘）存

155、放虚拟存储器的实现借助于大容量的辅助存储器（如磁盘）存放作业信息，操作系统利用作业执行在时间上和空间上的局部性特点作业信息，操作系统利用作业执行在时间上和空间上的局部性特点把当前需要使用的作业信息装入主存，并且利用页表、段表等数据把当前需要使用的作业信息装入主存，并且利用页表、段表等数据结构构造一个用户的虚拟空间。操作系统根据中断（缺页中断、缺结构构造一个用户的虚拟空间。操作系统根据中断（缺页中断、缺段中断）进行处理，选择一种合适的调度算法对主存和辅存中的信段中断）进行处理，选择一种合适的调度算法对主存和辅存中的信息进行调入和调出，尽可能地避免息进行调入和调出，尽可能地避免“抖动抖动”现象的发

156、生。虚拟存储现象的发生。虚拟存储管理有请求式分页存储、请求式分段存储和请求式段页存储。请求管理有请求式分页存储、请求式分段存储和请求式段页存储。请求式分页存储管理的实现需要必要的硬件支持和相应的软件支持，涉式分页存储管理的实现需要必要的硬件支持和相应的软件支持，涉及到请求分页的页表机制；缺页中断机构；地址变换机构；页面置及到请求分页的页表机制；缺页中断机构；地址变换机构；页面置换算法等。其中页面置换算法主要有：最佳置换算法、先进先出置换算法等。其中页面置换算法主要有：最佳置换算法、先进先出置换算法、最近最少用置换算法、换算法、最近最少用置换算法、Clock置换算法和最近最不常用置换置换算法和最近最不常用置换算法等。虚拟存储器的性能与缺页中断率密切相关，系统分配给作算法等。虚拟存储器的性能与缺页中断率密切相关，系统分配给作业的主存物理块数、页面的大小以及程序的编制方法等对缺页中断业的主存物理块数、页面的大小以及程序的编制方法等对缺页中断率都有影响。率都有影响。操作系统教程课件第125页