第4部分存储管理

《第4部分存储管理》由会员分享，可在线阅读，更多相关《第4部分存储管理（72页珍藏版）》请在装配图网上搜索。

1、第第4 4章章 存储管理存储管理第第4 4章章 存储管理存储管理 本章学习目标本章学习目标 4.1 4.1 存储管理的功能存储管理的功能 4.2 4.2 实存管理实存管理 4.3 4.3 虚拟存储器管理虚拟存储器管理 4.4 4.4 碎片与抖动问题碎片与抖动问题 开开 始始第第4 4章章 存储管理存储管理本章学习目标本章学习目标 本章首先介绍了存储管理的研究对象和目的，明本章首先介绍了存储管理的研究对象和目的，明确了存储管理的基本功能和有关的基本概念；然确了存储管理的基本功能和有关的基本概念；然后从实存和虚存两个角度，分别介绍了常用的几后从实存和虚存两个角度，分别介绍了常用的几种存储管理方案；

2、最后对各种存储管理方案存在种存储管理方案；最后对各种存储管理方案存在的问题，主要是碎片和抖动问题进行了总结。的问题，主要是碎片和抖动问题进行了总结。 返回本章首页返回本章首页第第4 4章章 存储管理存储管理本章的主要内容如下：本章的主要内容如下：(1)存储管理的目的和四大基本功能。存储管理的目的和四大基本功能。 (2)实存管理中讲述了固定分区存储管理、可变式实存管理中讲述了固定分区存储管理、可变式分区存储管理、纯分页存储管理三种存储管理方分区存储管理、纯分页存储管理三种存储管理方案的实现原理案的实现原理(3)虚存管理以请求式分页存储管理为重点虚存管理以请求式分页存储管理为重点 (4)总结各种存

3、储管理方案中存在的碎片和抖动问总结各种存储管理方案中存在的碎片和抖动问题及解决方法题及解决方法下一页下一页第第4 4章章 存储管理存储管理图图4.1 多级存储器体系示意图多级存储器体系示意图第第4 4章章 存储管理存储管理4.1 存储管理的功能存储管理的功能 4.1.1 内存的分配与回收内存的分配与回收 4.1.2 地址重定位地址重定位4.1.3 存储保护存储保护 4.1.4 虚拟存储器虚拟存储器 返回本章首页返回本章首页第第4 4章章 存储管理存储管理4.1.1 内存的分配与回收内存的分配与回收 内存分配按分配时机的不同，可分为两种方式。内存分配按分配时机的不同，可分为两种方式。（1）静态存

4、储分配：指内存分配是在作业运行之前各目）静态存储分配：指内存分配是在作业运行之前各目标模块连接后，把整个作业一次性全部装入内存，并在标模块连接后，把整个作业一次性全部装入内存，并在作业的整个运行过程中，不允许作业再申请其他内存，作业的整个运行过程中，不允许作业再申请其他内存，或在内存中移动位置。也就是说，内存分配是在作业运或在内存中移动位置。也就是说，内存分配是在作业运行前一次性完成的。行前一次性完成的。（2）动态存储分配：作业要求的基本内存空间是在目标）动态存储分配：作业要求的基本内存空间是在目标模块装入内存时分配的，但在作业运行过程中，允许作模块装入内存时分配的，但在作业运行过程中，允许作

5、业申请附加的内存空间，或是在内存中移动，即分配工业申请附加的内存空间，或是在内存中移动，即分配工作可以在作业运行前及运行过程中逐步完成。作可以在作业运行前及运行过程中逐步完成。返回本节返回本节第第4 4章章 存储管理存储管理4.1.2 地址重定位地址重定位 1内存空间（或物理空间）内存空间（或物理空间）2逻辑空间逻辑空间3地址重定位地址重定位下一页下一页第第4 4章章 存储管理存储管理1内存空间（或物理空间）内存是由若干个存储单元组成的，每个存储单元内存是由若干个存储单元组成的，每个存储单元有一个编号，这种编号可唯一标识一个存储单元，有一个编号，这种编号可唯一标识一个存储单元，称为内存地址（或

6、物理地址）。称为内存地址（或物理地址）。下一页下一页第第4 4章章 存储管理存储管理2逻辑空间源程序经过汇编或编译后，形成目标程序，每个源程序经过汇编或编译后，形成目标程序，每个目标程序都是以目标程序都是以0为基址顺序进行编址的，原来为基址顺序进行编址的，原来用符号名访问的单元用具体的数据用符号名访问的单元用具体的数据单元号取单元号取代。这样生成的目标程序占据一定的地址空间，代。这样生成的目标程序占据一定的地址空间，称为作业的逻辑地址空间，简称逻辑空间。在逻称为作业的逻辑地址空间，简称逻辑空间。在逻辑空间中每条指令的地址和指令中要访问的操作辑空间中每条指令的地址和指令中要访问的操作数地址统称为

7、逻辑地址。数地址统称为逻辑地址。下一页下一页第第4 4章章 存储管理存储管理图图4.2 作业的名空间、逻辑地址空间和装入后的物理空间作业的名空间、逻辑地址空间和装入后的物理空间下一页下一页第第4 4章章 存储管理存储管理3地址重定位(1)静态地址重定位静态地址重定位静态地址重定位是在程序执行之前由操作系统的静态地址重定位是在程序执行之前由操作系统的重定位装入程序完成的。重定位装入程序完成的。 (2)动态地址重定位动态地址重定位 动态地址重定位是在程序执行期间进行的。动态地址重定位是在程序执行期间进行的。 下一页下一页第第4 4章章 存储管理存储管理（b）采用动态重定位时内存空间及地址重定位示意

8、图 （a）采用静态重定位后的内存空间 图图4.3 静态地址重定位和动态地址重定位示意图静态地址重定位和动态地址重定位示意图返回本节返回本节第第4 4章章 存储管理存储管理4.1.3 存储保护存储保护 （1）上、下界存储保护：上、下界保护是一种）上、下界存储保护：上、下界保护是一种简单的存储保护技术。系统可为每个作业设置一简单的存储保护技术。系统可为每个作业设置一对上、下界寄存器，分别用来存放当前运行作业对上、下界寄存器，分别用来存放当前运行作业在内存空间的上、下边界地址，用它们来限制用在内存空间的上、下边界地址，用它们来限制用户程序的活动范围。户程序的活动范围。 （2）基址）基址限长存储保护：

9、上、下界保护的一限长存储保护：上、下界保护的一个变种是采用基址个变种是采用基址限长存储保护。限长存储保护。 第第4 4章章 存储管理存储管理图图4.4 界限寄存器的两种存储保护方式界限寄存器的两种存储保护方式返回本节返回本节第第4 4章章 存储管理存储管理4.1.4 虚拟存储器虚拟存储器 对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。技术。 虚拟存储技术的基本思想是把有限的内存空间与大容量虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储

10、器。此时，外存是作为内存的直接延伸，用户拟的存储器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一并不会感觉到内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，实际上可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。统自动将其从外存调入内存。 返回本节返回本节第第4 4章章 存储管理存储管理4.2 实存管理实存管理

11、4.2.1 固定分区存储管理固定分区存储管理 4.2.2 可变式分区存储管理可变式分区存储管理4.2.3 纯分页存储管理纯分页存储管理 返回本章首页返回本章首页第第4 4章章 存储管理存储管理4.2.1 固定分区存储管理固定分区存储管理 固定分区存储管理是实现多道程序设计的最简单固定分区存储管理是实现多道程序设计的最简单的一种存储管理技术。其基本思想是，在作业未的一种存储管理技术。其基本思想是，在作业未进入内存之前，就由操作员或操作系统把内存可进入内存之前，就由操作员或操作系统把内存可用空间划分成若干个固定大小的存储区，除操作用空间划分成若干个固定大小的存储区，除操作系统占用一个区域外，其余区

12、域为系统中多个用系统占用一个区域外，其余区域为系统中多个用户共享，因为在系统运行期间，分区大小、数目户共享，因为在系统运行期间，分区大小、数目都不变，所以固定式分区也称为静态分区。都不变，所以固定式分区也称为静态分区。第第4 4章章 存储管理存储管理图图4.5 固定式分区内存分配示意图（固定式分区内存分配示意图（a）和（）和（b）固定式分区说明表固定式分区说明表返回本节返回本节第第4 4章章 存储管理存储管理4.2.2 可变式分区存储管理可变式分区存储管理 1空闲分区的组织形式空闲分区的组织形式 2内存的分配与回收内存的分配与回收 3常用的分配算法常用的分配算法 4可变式分区的地址重定位可变式

13、分区的地址重定位 下一页下一页第第4 4章章 存储管理存储管理图图4.6 可变式分区内存使用情况示意图可变式分区内存使用情况示意图下一页下一页第第4 4章章 存储管理存储管理1空闲分区的组织形式空闲分区的组织形式 空闲分区链表的组织是这样的：在每个空闲分区空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块头指

14、针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。如图空闲分区的链表指针存放链尾标志。如图4.7（a）所示所示 。下一页下一页第第4 4章章 存储管理存储管理2内存的分配与回收内存的分配与回收 当某一个用户作业完成释放所占分区时，系统应当某一个用户作业完成释放所占分区时，系统应进行回收。在可变式分区中，应该检查回收区与进行回收。在可变式分区中，应该检查回收区与内存中前后空闲区是否相邻，若相邻，则应进行内存中前后空闲区是否相邻，若相邻，则应进行合并，形成一个较大的空闲区，并对相应的链表合并，形成一个较大的空闲区，并对相应的链表指针进行修改；若不相邻，应将空闲区插入到空指针进行

15、修改；若不相邻，应将空闲区插入到空闲区链表的适当位置。闲区链表的适当位置。 下一页下一页第第4 4章章 存储管理存储管理图图4.7 首次适应算法的空闲分区链表组织形式首次适应算法的空闲分区链表组织形式下一页下一页第第4 4章章 存储管理存储管理3常用的分配算法常用的分配算法 （1）首次适应算法）首次适应算法 （2）最佳适应算法）最佳适应算法 （3）最差适应算法）最差适应算法 下一页下一页第第4 4章章 存储管理存储管理图图4.8 最佳适应算法的空闲分区链表组织形式最佳适应算法的空闲分区链表组织形式下一页下一页第第4 4章章 存储管理存储管理图图4.9 最差适应算法的空闲分区链表组织形式最差适应

16、算法的空闲分区链表组织形式下一页下一页第第4 4章章 存储管理存储管理图图4.10 内存使用情况内存使用情况 下一页下一页第第4 4章章 存储管理存储管理图图4.11 用三种适应算法处理同一作业序列用三种适应算法处理同一作业序列下一页下一页第第4 4章章 存储管理存储管理4可变式分区的地址重定位可变式分区的地址重定位 可变式分区的地址重定位可采用静态重定位，也可采用可变式分区的地址重定位可采用静态重定位，也可采用动态重定位。如采用静态重定位，因用户作业进入内存动态重定位。如采用静态重定位，因用户作业进入内存后，程序的逻辑地址实现了重定位，不能在内存中再进后，程序的逻辑地址实现了重定位，不能在内

17、存中再进行移动，经过一段时间的运行，内存中不能再分配利用行移动，经过一段时间的运行，内存中不能再分配利用的小碎片会越来越多。有时可能会出现这种情况，即当的小碎片会越来越多。有时可能会出现这种情况，即当一个作业申请一定数量的内存时，虽然此时空闲区的总一个作业申请一定数量的内存时，虽然此时空闲区的总和大于新作业的内存要求，但却没有单个的空闲区足以和大于新作业的内存要求，但却没有单个的空闲区足以装下该作业。装下该作业。采用动态重定位的可变式分区管理技术，在执行内存分采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配时，如无足够大空闲块，应考虑实现紧凑操

18、作。其分配算法如图配算法如图4.12所示所示 。 下一页下一页第第4 4章章 存储管理存储管理图图4.12 采用动态重定位的可变式分区分配算法采用动态重定位的可变式分区分配算法返回本节返回本节第第4 4章章 存储管理存储管理4.2.3 纯分页存储管理纯分页存储管理 1纯分页存储管理中存储块的分配与回收纯分页存储管理中存储块的分配与回收 2纯分页存储管理的地址重定位问题纯分页存储管理的地址重定位问题3联想存储器联想存储器 4存储保护存储保护 下一页下一页第第4 4章章 存储管理存储管理1纯分页存储管理中存储块的分配与回收纯分页存储管理中存储块的分配与回收 通 常 有 两通 常 有 两种 记 录

19、空种 记 录 空闲 存 储 块闲 存 储 块的 方 法 ：的 方 法 ：位 图 法 和位 图 法 和链表法。链表法。（a）存储块使用情况 （b）存储块使用情况的位图表示图图4-13 存储块的位图管理法存储块的位图管理法第第4 4章章 存储管理存储管理2纯分页存储管理的地址重定位问题纯分页存储管理的地址重定位问题 纯分页存储管理中的地址重定位是非常重要的，纯分页存储管理中的地址重定位是非常重要的，要使不连续的、分散的用户程序能正常运行，须要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器

20、用得太多。器方式，如分页太多，则重定位寄存器用得太多。通常可在内存中为每个作业开辟一块特定区域，通常可在内存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映象表，简称页表。系，这种表常称为页面映象表，简称页表。 下一页下一页第第4 4章章 存储管理存储管理图图4.14 纯分页存储管理示意图纯分页存储管理示意图下一页下一页第第4 4章章 存储管理存储管理3联想存储器联想存储器 从上面介绍的地址变换过程可以看出：如果把页表全部从上面介绍的地址变换过程可以看出：如果把页表全部放在内存，那么存取一个数据时，至少要访

21、问二次内存。放在内存，那么存取一个数据时，至少要访问二次内存。一次是访问页表，形成实际内存地址；另一次是根据形一次是访问页表，形成实际内存地址；另一次是根据形成的内存地址存取数据。显然，这比通常执行指令的速成的内存地址存取数据。显然，这比通常执行指令的速度要慢得多，使计算机的运行速度几乎降低一半。度要慢得多，使计算机的运行速度几乎降低一半。应用联想存储器和页表相结合的方式，可有效地提高系应用联想存储器和页表相结合的方式，可有效地提高系统动态地址转换的速度，是一种行之有效的方法。统动态地址转换的速度，是一种行之有效的方法。下一页下一页第第4 4章章 存储管理存储管理图图4.15 纯分页存储管理地

22、址重定位实现过程纯分页存储管理地址重定位实现过程下一页下一页第第4 4章章 存储管理存储管理图图4.16 采用快表和页表相结合的分页地址变换过程示意图采用快表和页表相结合的分页地址变换过程示意图下一页下一页第第4 4章章 存储管理存储管理4存储保护存储保护 四种保护方式：四种保护方式：禁止做任何操作，禁止做任何操作，只能执行，只能执行，只能读，只能读，能读能读/写，当要访问某页时，先判断写，当要访问某页时，先判断该页的存取控制和存储保护信息是否允许。该页的存取控制和存储保护信息是否允许。添加了存取控制信息的页表表目如下图所示：添加了存取控制信息的页表表目如下图所示： 返回本节返回本节第第4 4

23、章章 存储管理存储管理4.3 虚拟存储器管理虚拟存储器管理 4.3.1 虚拟存储器的概念虚拟存储器的概念 4.3.2 请求式分页存储管理与动态地址重定位请求式分页存储管理与动态地址重定位 4.3.3 现代计算机系统改进的动态地址重定位现代计算机系统改进的动态地址重定位 4.3.4 页面置换算法页面置换算法 4.3.5 请求式分页存储管理性能分析举例请求式分页存储管理性能分析举例 4.3.6 请求式分段存储管理请求式分段存储管理 返回本章首页返回本章首页第第4 4章章 存储管理存储管理4.3.1 虚拟存储器的概念虚拟存储器的概念 （1）程序中往往会有一些彼此互斥的部分。）程序中往往会有一些彼此互

24、斥的部分。 （2）在一个完整的程序中，会有一些诸如出错处理这样）在一个完整的程序中，会有一些诸如出错处理这样的子程序，在作业正常运行情况下不会执行这些程序，的子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。没有必要把它们调入内存。基于程序局部性原理和上述情况，就没有必要把一个作基于程序局部性原理和上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当业一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存临时调入，由

25、操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。这样的计算机系统好像为用户提之间信息的动态调度。这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。虚拟存储器。 返回本节返回本节第第4 4章章 存储管理存储管理4.3.2 请求式分页存储管理与动态地址重定位请求式分页存储管理与动态地址重定位 请求式分页存储管理与纯分页存储管理在内存块的分配请求式分页存储管理与纯分页存储管理在内存块的分配与回收，存储保护某方面都十分相似，不同之处在于地与回收，存储保护某方面都十分相似，不同之处在于地址重定位问题。在请求式分

26、页存储管理的地址重定位时，址重定位问题。在请求式分页存储管理的地址重定位时，可能会出现所需页面不在主存的情况，此时，系统必须可能会出现所需页面不在主存的情况，此时，系统必须解决以下两个问题：解决以下两个问题：（1）当程序要访问的某页不在内存时，如何发现这种缺）当程序要访问的某页不在内存时，如何发现这种缺页情况？发现后应如何处理？页情况？发现后应如何处理？（2）当需要把外存上的某个页面调入内存时，此时内存）当需要把外存上的某个页面调入内存时，此时内存中没有空闲块应怎么办？中没有空闲块应怎么办？下一页下一页第第4 4章章 存储管理存储管理如图如图4.17所示是请求式分页存储管理的存储映像所示是请求

27、式分页存储管理的存储映像 下一页下一页第第4 4章章 存储管理存储管理为了帮助操作系统对要置换出内存的页面进行选为了帮助操作系统对要置换出内存的页面进行选择，在页表中还可以增加一个引用位，以反映该择，在页表中还可以增加一个引用位，以反映该页最近的使用情况。页最近的使用情况。一般来说，一个页表的表目通常可包括如下的数一般来说，一个页表的表目通常可包括如下的数据内容：据内容：下一页下一页第第4 4章章 存储管理存储管理请求式分页存储管理中的地址重定位和缺页中断处请求式分页存储管理中的地址重定位和缺页中断处理过程如图理过程如图4.18所示。所示。返回本节返回本节第第4 4章章 存储管理存储管理4.3

28、.3 现代计算机系统改进的动态地址重定位现代计算机系统改进的动态地址重定位 （1）如何合理地组织管理相当大的页表？）如何合理地组织管理相当大的页表？在在Windows NT中，为解决第一个问题，对页表本身进行了改中，为解决第一个问题，对页表本身进行了改进，将庞大的页表本身也采取分页措施，采用了两级页表结构。进，将庞大的页表本身也采取分页措施，采用了两级页表结构。即把页表本身按固定大小分成一个个小页表，每个小页表由即把页表本身按固定大小分成一个个小页表，每个小页表由210=1024个页表表目构成，每个表目占个页表表目构成，每个表目占4字节，所以每个小页字节，所以每个小页表刚好占一个页面（页面大小

29、为表刚好占一个页面（页面大小为212=4kb）。一共有）。一共有210=1k个个小页表。为了对这小页表。为了对这1k个小页表进行管理和索引查找，设置了个小页表进行管理和索引查找，设置了一个页表目录，也称之为顶级页表或一级页表，该页目录包含一个页表目录，也称之为顶级页表或一级页表，该页目录包含有有1k个表目项，分别指出每个次级小页表所在的物理块号和个表目项，分别指出每个次级小页表所在的物理块号和其他有关状态信息。这样，每个作业有一个页目录（一级页其他有关状态信息。这样，每个作业有一个页目录（一级页表），它的每个表目指向一个二级页表。页目录本身也刚好是表），它的每个表目指向一个二级页表。页目录本身

30、也刚好是一个页面大小（一个页面大小（210=1k，每个表目，每个表目4个字节）。个字节）。下一页下一页第第4 4章章 存储管理存储管理图图4.19 Windows NT两级页表地址变换示意图两级页表地址变换示意图下一页下一页第第4 4章章 存储管理存储管理（2）面对大的页表，地址的映射怎样才能比较）面对大的页表，地址的映射怎样才能比较快地实现？快地实现？ （1）使用快表：即利用前面我们已介绍的高速）使用快表：即利用前面我们已介绍的高速缓冲存储器来存放经常使用的页表表目，以提高缓冲存储器来存放经常使用的页表表目，以提高页表的查询速度。页表的查询速度。（2）使用高速缓冲存储器：在微处理器和主存）使

31、用高速缓冲存储器：在微处理器和主存之间设置之间设置32kb或或64kb的高速缓冲存储器，大部分的高速缓冲存储器，大部分的指令和数据取自高速缓存（命中率为的指令和数据取自高速缓存（命中率为98%），），所以存取数据和指令速度相当高，达到与处理器所以存取数据和指令速度相当高，达到与处理器速度完全相匹配。速度完全相匹配。返回本节返回本节第第4 4章章 存储管理存储管理4.3.4 页面置换算法页面置换算法 1最优算法（最优算法（OPT算法）算法）2先进先出算法（先进先出算法（FIFO算法）算法）3最久未使用页面置换算法（最久未使用页面置换算法（LRU算法）算法）4LRU近似算法近似算法下一页下一页第第

32、4 4章章 存储管理存储管理1最优算法（最优算法（OPT算法算法）最理想的页面置换算法是：从内存中移出以后不最理想的页面置换算法是：从内存中移出以后不再使用的页面；如无这样的页面，则选择以后最再使用的页面；如无这样的页面，则选择以后最长时间内不需要访问的页。这就是最优算法的思长时间内不需要访问的页。这就是最优算法的思想。想。这种算法本身不是一种实际的方法，因为页面访这种算法本身不是一种实际的方法，因为页面访问的顺序是很难预知的。但是，可把它作为一种问的顺序是很难预知的。但是，可把它作为一种评价标准，比较其他实用方法的优劣，所以，最评价标准，比较其他实用方法的优劣，所以，最优算法只具有理论上的意

33、义。优算法只具有理论上的意义。下一页下一页第第4 4章章 存储管理存储管理2先进先出算法（先进先出算法（FIFO算法）算法）这种算法的基本思想是：总是先淘汰那些驻留在这种算法的基本思想是：总是先淘汰那些驻留在内存时间最长的页面，即先进入内存的页面先被内存时间最长的页面，即先进入内存的页面先被置换掉。理由是：最先进入内存的页面不再被访置换掉。理由是：最先进入内存的页面不再被访问的可能性最大。问的可能性最大。 下一页下一页第第4 4章章 存储管理存储管理图图4.20 先进先出算法存储分块表构造先进先出算法存储分块表构造下一页下一页第第4 4章章 存储管理存储管理3最久未使用页面置换算法（最久未使用

34、页面置换算法（LRU算法）算法）这种算法的基本思想是，如果某一页被访问了，那么它这种算法的基本思想是，如果某一页被访问了，那么它很可能马上又被访问；反之，如果某一页很长时间没有很可能马上又被访问；反之，如果某一页很长时间没有被访问，那么最近也不太可能会被访问。这种算法考虑被访问，那么最近也不太可能会被访问。这种算法考虑了程序设计的局部性原理。其实质是，当需要置换一页了程序设计的局部性原理。其实质是，当需要置换一页时，选择在最近一段时间最久未使用的页面予以淘汰。时，选择在最近一段时间最久未使用的页面予以淘汰。实现这种算法可通过周期性地对实现这种算法可通过周期性地对“引用位引用位”进行检查，进行检

35、查，并利用它来记录一页面自上次被访问以来所经历的时间并利用它来记录一页面自上次被访问以来所经历的时间t，淘汰时选择淘汰时选择t最大的页面。最大的页面。 下一页下一页第第4 4章章 存储管理存储管理4LRU近似算法近似算法这种算法，只要在存储分块表（或页表）中设一个这种算法，只要在存储分块表（或页表）中设一个“引引用位用位”，当存储分块表中的某一页被访问时，该位由硬，当存储分块表中的某一页被访问时，该位由硬件自动置件自动置1，并由页面管理软件周期性把所有引用位置，并由页面管理软件周期性把所有引用位置0。这样，在一个时间周期这样，在一个时间周期T内，某些被访问过的页面其引用内，某些被访问过的页面其

36、引用位为位为1，而未被访问过的页面其引用位为，而未被访问过的页面其引用位为0。因此，可根。因此，可根据引用位的状态来判别各页面最近的使用情况。当需要据引用位的状态来判别各页面最近的使用情况。当需要置换一页面时，选择其引用位为置换一页面时，选择其引用位为0的页，如图的页，如图4.21所示的所示的算法算法 。图图4.22是这种近似算法的一个例子。是这种近似算法的一个例子。 下一页下一页第第4 4章章 存储管理存储管理图图4.21 LRU近似算法近似算法 下一页下一页第第4 4章章 存储管理存储管理图图4.22 LRU近似算法举例近似算法举例返回本节返回本节第第4 4章章 存储管理存储管理4.3.5

37、 请求式分页存储管理性能分析举例请求式分页存储管理性能分析举例 1程序设计的质量程序设计的质量2页面的大小页面的大小3分配的内存块数分配的内存块数4页面置换算法性能页面置换算法性能下一页下一页第第4 4章章 存储管理存储管理【例【例1】主存块数】主存块数m=3，置换算法采用，置换算法采用FIFO算法，缺页中算法，缺页中断次数及缺页率如图断次数及缺页率如图4.23所示。所示。在图在图4.23中中，P行表示页面走向，行表示页面走向，M行表示在主存中的页行表示在主存中的页面号，其中带有面号，其中带有+的表示新调入页面，在的表示新调入页面，在M行的各列按调行的各列按调入的顺序排列，带有圆圈的数字表示下

38、一时刻将被淘汰入的顺序排列，带有圆圈的数字表示下一时刻将被淘汰页面，页面，F行表示是否引起缺页中断，带行表示是否引起缺页中断，带号的表示引起缺号的表示引起缺页中断。从图页中断。从图4.23可以看出，缺页中断页数为可以看出，缺页中断页数为9次，缺页次，缺页率率f=9/12=75%。下一页下一页第第4 4章章 存储管理存储管理图图4.23 FIFO算法性能分析（算法性能分析（m=3）下一页下一页第第4 4章章 存储管理存储管理【例【例2】设】设m=4，仍采用，仍采用FIFO算法，缺页中断次算法，缺页中断次数及缺页率如图数及缺页率如图4.24所示。可以算出，在分配给所示。可以算出，在分配给该作业的内

39、存块数增加到该作业的内存块数增加到4时，缺页中断由图时，缺页中断由图4.23的的9次反而增加到了次反而增加到了10次，缺页率由次，缺页率由75%增加增加到到10/12=83%，这就是，这就是FIFO算法的一种异常现象。算法的一种异常现象。随着分配的主存块数的增加，缺页中断次数不但随着分配的主存块数的增加，缺页中断次数不但没有降低，反而增加了。这与该算法定全不考虑没有降低，反而增加了。这与该算法定全不考虑程序的动态特征有关。程序的动态特征有关。下一页下一页第第4 4章章 存储管理存储管理图图4.24 FIFO算法性能分析（算法性能分析（m=4）下一页下一页第第4 4章章 存储管理存储管理【例【例

40、3】设】设m=3，采用，采用LRU算法，缺页中断次数算法，缺页中断次数及缺页率如图及缺页率如图4.25所示。所示。图图4.25 LRU算法性能分析（算法性能分析（m=3）下一页下一页第第4 4章章 存储管理存储管理【例例4】设设m=4，其余同例，其余同例3，则缺页中断次数及，则缺页中断次数及缺页率如图缺页率如图4.26所示。所示。 图图4.26 LRU算法性能分析（算法性能分析（m=4）返回本节返回本节第第4 4章章 存储管理存储管理4.3.6 请求式分段存储管理请求式分段存储管理 为了能实现虚拟存储，段式逻辑地址空间中的程序段在为了能实现虚拟存储，段式逻辑地址空间中的程序段在运行时并不全部装

41、入内存，而是如同请求式分页存储管运行时并不全部装入内存，而是如同请求式分页存储管理，首先调入一个或若干个程序段运行，在运行过程中理，首先调入一个或若干个程序段运行，在运行过程中调用到哪段时，就根据该段长度在内存分配一个连续的调用到哪段时，就根据该段长度在内存分配一个连续的分区给它使用。若内存中没有足够大的空闲分区，则考分区给它使用。若内存中没有足够大的空闲分区，则考虑进行段的紧凑或将某段或某些段淘汰出去。相应于请虑进行段的紧凑或将某段或某些段淘汰出去。相应于请求式分页存储管理，这种存储管理技术称为请求式分段求式分页存储管理，这种存储管理技术称为请求式分段存储管理。存储管理。下一页下一页第第4

42、4章章 存储管理存储管理图图4.27 分段的逻辑地址空间分段的逻辑地址空间下一页下一页第第4 4章章 存储管理存储管理请求式分段存储管理的地址变换请求式分段存储管理的地址变换 1程序的逻辑地址结构程序的逻辑地址结构 2段表段表 3请求式分段动态地址变换过程请求式分段动态地址变换过程 4请求式分段存储管理的优、缺点请求式分段存储管理的优、缺点 下一页下一页第第4 4章章 存储管理存储管理1程序的逻辑地址结构程序的逻辑地址结构 请求式分段存储管理的逻辑地址结构由段号请求式分段存储管理的逻辑地址结构由段号s和和段内位移量段内位移量d组成，如下图所示。组成，如下图所示。下一页下一页第第4 4章章 存储

43、管理存储管理2段表段表 类似于请求式分页存储管理的页表，为了实现动类似于请求式分页存储管理的页表，为了实现动态地址变换和存储保护，系统要为每一个作业建态地址变换和存储保护，系统要为每一个作业建立一张段表。段表中的每一个表目对应着作业地立一张段表。段表中的每一个表目对应着作业地址空间的一个程序段，其一般格式为：址空间的一个程序段，其一般格式为： 下一页下一页第第4 4章章 存储管理存储管理3请求式分段动态地址变换过程请求式分段动态地址变换过程 图图4.28 请求式分段动态地址请求式分段动态地址 下一页下一页第第4 4章章 存储管理存储管理请求式分段存储管理的地址变换请求式分段存储管理的地址变换

44、（1）可提供大容量的虚存）可提供大容量的虚存 （2）允许动态增加段的长度）允许动态增加段的长度 （3）便于段的动态链接）便于段的动态链接 （4）便于实现程序段的共享）便于实现程序段的共享 （5）便于实现存储保护）便于实现存储保护 返回本节返回本节第第4 4章章 存储管理存储管理4.4 碎片与抖动问题碎片与抖动问题 1、碎片问题、碎片问题 解决碎片问题的比较好的方法是采用分页技术，解决碎片问题的比较好的方法是采用分页技术，在纯分页存储管理系统中，因存储区划分成固定在纯分页存储管理系统中，因存储区划分成固定大小的块，而用户作业也划分成与块相等的若干大小的块，而用户作业也划分成与块相等的若干页，每个

45、作业调入内存时，除最后一个页面可能页，每个作业调入内存时，除最后一个页面可能有页内碎片出现外，其余页不存在碎片问题，一有页内碎片出现外，其余页不存在碎片问题，一般来说，平均每个作业可能有半页的内碎片。般来说，平均每个作业可能有半页的内碎片。返回本章首页返回本章首页第第4 4章章 存储管理存储管理2、抖动现象、抖动现象 避免抖动现象最根本的方法是控制多道程序的道避免抖动现象最根本的方法是控制多道程序的道数，使得每个用户作业都有足够的内存空间可供数，使得每个用户作业都有足够的内存空间可供使用。但作业的个数又不能太少，否则，会影响使用。但作业的个数又不能太少，否则，会影响处理机的利用率。最好是使处理机利用率较高，处理机的利用率。最好是使处理机利用率较高，又不致于使系统发生抖动，这是一个很难解决的又不致于使系统发生抖动，这是一个很难解决的问题，牵扯到程序的局部性问题，并需借助于工问题，牵扯到程序的局部性问题，并需借助于工作集模型。作集模型。返回本节返回本节第第4 4章章 存储管理存储管理THANK YOU VERY MUCH THANK YOU VERY MUCH ！本章到此结束，本章到此结束，谢谢您的光临！谢谢您的光临！返回本章首页返回本章首页结束放映结束放映