第4部分存储管理

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

1、第第4 4章章 存储管理存储管理第4部分存储管理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第第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内存空间（或物理空间）内内存存是是由由若若干干个个存存储储单单元元组组成成的的，每每个个存存储储单单元元有有一一个个编编号号，这这种种编编号号可可唯唯一一标标识识一一个个存存储储单单元元，称为内存地址（或物理地址）。称为内存地址（或物理地址）。下一页下一页第第4 4章章 存储管理存储管理2逻辑空间源源程程序序经

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

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

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

9、图图4.4界限寄存器的两种存储保护方式界限寄存器的两种存储保护方式返回本节返回本节第第4 4章章 存储管理存储管理4.1.4虚拟存储器虚拟存储器对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理对内存进行逻辑上的扩充，现在普遍采用虚拟存储管理技术。技术。虚拟存储技术的基本思想是把有限的内存空间与大容量虚拟存储技术的基本思想是把有限的内存空间与大容量的外存统一管理起来，构成一个远大于实际内存的、虚的外存统一管理起来，构成一个远大于实际内存的、虚拟的存储器。此时，外存是作为内存的直接延伸，用户拟的存储器。此时，外存是作为内存的直接延伸，用户并不会感觉到内、外存的区别，即把两级存储器当作一并不会感觉到

10、内、外存的区别，即把两级存储器当作一级存储器来看待。一个作业运行时，其全部信息装入虚级存储器来看待。一个作业运行时，其全部信息装入虚存，实际上可能只有当前运行的必需一部分信息存入内存，实际上可能只有当前运行的必需一部分信息存入内存，其他则存于外存，当所访问的信息不在内存时，系存，其他则存于外存，当所访问的信息不在内存时，系统自动将其从外存调入内存。统自动将其从外存调入内存。返回本节返回本节第第4 4章章 存储管理存储管理4.2实存管理实存管理4.2.1固定分区存储管理固定分区存储管理 4.2.2可变式分区存储管理可变式分区存储管理4.2.3纯分页存储管理纯分页存储管理 返回本章首页返回本章首页

11、第第4 4章章 存储管理存储管理4.2.1固定分区存储管理固定分区存储管理固固定定分分区区存存储储管管理理是是实实现现多多道道程程序序设设计计的的最最简简单单的的一一种种存存储储管管理理技技术术。其其基基本本思思想想是是，在在作作业业未未进进入入内内存存之之前前，就就由由操操作作员员或或操操作作系系统统把把内内存存可可用用空空间间划划分分成成若若干干个个固固定定大大小小的的存存储储区区，除除操操作作系系统统占占用用一一个个区区域域外外，其其余余区区域域为为系系统统中中多多个个用用户户共共享享，因因为为在在系系统统运运行行期期间间，分分区区大大小小、数数目目都不变，所以固定式分区也称为静态分区。

12、都不变，所以固定式分区也称为静态分区。第第4 4章章 存储管理存储管理图图4.5固定式分区内存分配示意图（固定式分区内存分配示意图（a）和（）和（b）固定式分区说明表固定式分区说明表返回本节返回本节第第4 4章章 存储管理存储管理4.2.2可变式分区存储管理可变式分区存储管理1空闲分区的组织形式空闲分区的组织形式 2内存的分配与回收内存的分配与回收 3常用的分配算法常用的分配算法 4可变式分区的地址重定位可变式分区的地址重定位 下一页下一页第第4 4章章 存储管理存储管理图图4.6可变式分区内存使用情况示意图可变式分区内存使用情况示意图下一页下一页第第4 4章章 存储管理存储管理1空闲分区的组

13、织形式空闲分区的组织形式空闲分区链表的组织是这样的：在每个空闲分区空闲分区链表的组织是这样的：在每个空闲分区的起始部分开辟出一个单元，存放一个链表指针的起始部分开辟出一个单元，存放一个链表指针和该分区的大小，链表指针指向下一个空闲分区。和该分区的大小，链表指针指向下一个空闲分区。系统中用一个固定单元作为空闲分区链表的链表系统中用一个固定单元作为空闲分区链表的链表头指针，指向第一块空闲分区首地址，最后一块头指针，指向第一块空闲分区首地址，最后一块空闲分区的链表指针存放链尾标志。如图空闲分区的链表指针存放链尾标志。如图4.7（a）所示）所示。下一页下一页第第4 4章章 存储管理存储管理2内存的分配

14、与回收内存的分配与回收当当某某一一个个用用户户作作业业完完成成释释放放所所占占分分区区时时，系系统统应应进进行行回回收收。在在可可变变式式分分区区中中，应应该该检检查查回回收收区区与与内内存存中中前前后后空空闲闲区区是是否否相相邻邻，若若相相邻邻，则则应应进进行行合合并并，形形成成一一个个较较大大的的空空闲闲区区，并并对对相相应应的的链链表表指指针针进进行行修修改改；若若不不相相邻邻，应应将将空空闲闲区区插插入入到到空空闲区链表的适当位置。闲区链表的适当位置。下一页下一页第第4 4章章 存储管理存储管理图图4.7首次适应算法的空闲分区链表组织形式首次适应算法的空闲分区链表组织形式下一页下一页第

15、第4 4章章 存储管理存储管理3常用的分配算法常用的分配算法（1）首次适应算法）首次适应算法（2）最佳适应算法）最佳适应算法（3）最差适应算法）最差适应算法 下一页下一页第第4 4章章 存储管理存储管理图图4.8最佳适应算法的空闲分区链表组织形式最佳适应算法的空闲分区链表组织形式下一页下一页第第4 4章章 存储管理存储管理图图4.9最差适应算法的空闲分区链表组织形式最差适应算法的空闲分区链表组织形式下一页下一页第第4 4章章 存储管理存储管理图图4.10内存使用情况内存使用情况下一页下一页第第4 4章章 存储管理存储管理图图4.11用三种适应算法处理同一作业序列用三种适应算法处理同一作业序列下

16、一页下一页第第4 4章章 存储管理存储管理4可变式分区的地址重定位可变式分区的地址重定位可可变变式式分分区区的的地地址址重重定定位位可可采采用用静静态态重重定定位位，也也可可采采用用动动态态重重定定位位。如如采采用用静静态态重重定定位位，因因用用户户作作业业进进入入内内存存后后，程程序序的的逻逻辑辑地地址址实实现现了了重重定定位位，不不能能在在内内存存中中再再进进行行移移动动，经经过过一一段段时时间间的的运运行行，内内存存中中不不能能再再分分配配利利用用的的小小碎碎片片会会越越来来越越多多。有有时时可可能能会会出出现现这这种种情情况况，即即当当一一个个作作业业申申请请一一定定数数量量的的内内存

17、存时时，虽虽然然此此时时空空闲闲区区的的总总和和大大于于新新作作业业的的内内存存要要求求，但但却却没没有有单单个个的的空空闲闲区区足足以以装下该作业。装下该作业。采用动态重定位的可变式分区管理技术，在执行内存分采用动态重定位的可变式分区管理技术，在执行内存分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配时，如无足够大空闲块，应考虑实现紧凑操作。其分配算法如图配算法如图4.12所示所示。下一页下一页第第4 4章章 存储管理存储管理图图4.12采用动态重定位的可变式分区分配算法采用动态重定位的可变式分区分配算法返回本节返回本节第第4 4章章 存储管理存储管理4.2.3纯分页存储管理纯分页存储管

18、理1纯分页存储管理中存储块的分配与回收纯分页存储管理中存储块的分配与回收 2纯分页存储管理的地址重定位问题纯分页存储管理的地址重定位问题3联想存储器联想存储器 4存储保护存储保护 下一页下一页第第4 4章章 存储管理存储管理1纯分页存储管理中存储块的分配与回收纯分页存储管理中存储块的分配与回收通通常常有有两两种种记记录录空空闲闲存存储储块块的的方方法法：位位图图法法和和链表法。链表法。（a）存储块使用情况 （b）存储块使用情况的位图表示图图4-13存储块的位图管理法存储块的位图管理法第第4 4章章 存储管理存储管理2纯分页存储管理的地址重定位问题纯分页存储管理的地址重定位问题纯分页存储管理中的

19、地址重定位是非常重要的，纯分页存储管理中的地址重定位是非常重要的，要使不连续的、分散的用户程序能正常运行，须要使不连续的、分散的用户程序能正常运行，须采用动态地址重定位。此时，可采用重定位寄存采用动态地址重定位。此时，可采用重定位寄存器方式，如分页太多，则重定位寄存器用得太多。器方式，如分页太多，则重定位寄存器用得太多。通常可在内存中为每个作业开辟一块特定区域，通常可在内存中为每个作业开辟一块特定区域，建立起作业的逻辑页与存储块之间的对应表格关建立起作业的逻辑页与存储块之间的对应表格关系，这种表常称为页面映象表，简称页表。系，这种表常称为页面映象表，简称页表。下一页下一页第第4 4章章 存储管

20、理存储管理图图4.14纯分页存储管理示意图纯分页存储管理示意图下一页下一页第第4 4章章 存储管理存储管理3联想存储器联想存储器从从上上面面介介绍绍的的地地址址变变换换过过程程可可以以看看出出：如如果果把把页页表表全全部部放放在在内内存存，那那么么存存取取一一个个数数据据时时，至至少少要要访访问问二二次次内内存存。一一次次是是访访问问页页表表，形形成成实实际际内内存存地地址址；另另一一次次是是根根据据形形成成的的内内存存地地址址存存取取数数据据。显显然然，这这比比通通常常执执行行指指令令的的速速度要慢得多，使计算机的运行速度几乎降低一半。度要慢得多，使计算机的运行速度几乎降低一半。应应用用联联

21、想想存存储储器器和和页页表表相相结结合合的的方方式式，可可有有效效地地提提高高系系统动态地址转换的速度，是一种行之有效的方法。统动态地址转换的速度，是一种行之有效的方法。下一页下一页第第4 4章章 存储管理存储管理图图4.15纯分页存储管理地址重定位实现过程纯分页存储管理地址重定位实现过程下一页下一页第第4 4章章 存储管理存储管理图图4.16采用快表和页表相结合的分页地址变换过程示意图采用快表和页表相结合的分页地址变换过程示意图下一页下一页第第4 4章章 存储管理存储管理4存储保护存储保护四四种种保保护护方方式式：禁禁止止做做任任何何操操作作，只只能能执执行行，只只能能读读，能能读读/写写，

22、当当要要访访问问某某页页时时，先先判判断断该页的存取控制和存储保护信息是否允许。该页的存取控制和存储保护信息是否允许。添加了存取控制信息的页表表目如下图所示：添加了存取控制信息的页表表目如下图所示：返回本节返回本节第第4 4章章 存储管理存储管理4.3虚拟存储器管理虚拟存储器管理4.3.1虚拟存储器的概念虚拟存储器的概念 4.3.2请求式分页存储管理与动态地址重定位请求式分页存储管理与动态地址重定位 4.3.3现代计算机系统改进的动态地址重定位现代计算机系统改进的动态地址重定位 4.3.4页面置换算法页面置换算法 4.3.5请求式分页存储管理性能分析举例请求式分页存储管理性能分析举例 4.3.

23、6请求式分段存储管理请求式分段存储管理 返回本章首页返回本章首页第第4 4章章 存储管理存储管理4.3.1虚拟存储器的概念虚拟存储器的概念（1）程序中往往会有一些彼此互斥的部分。）程序中往往会有一些彼此互斥的部分。（2）在一个完整的程序中，会有一些诸如出错处理这样）在一个完整的程序中，会有一些诸如出错处理这样的子程序，在作业正常运行情况下不会执行这些程序，的子程序，在作业正常运行情况下不会执行这些程序，没有必要把它们调入内存。没有必要把它们调入内存。基于程序局部性原理和上述情况，就没有必要把一个作基于程序局部性原理和上述情况，就没有必要把一个作业一次性全部装入内存再开始运行。而是可以把程序当业

24、一次性全部装入内存再开始运行。而是可以把程序当前执行所涉及的信息放入内存中，其余部分可根据需要前执行所涉及的信息放入内存中，其余部分可根据需要临时调入，由操作系统和硬件相配合来完成主存和辅存临时调入，由操作系统和硬件相配合来完成主存和辅存之间信息的动态调度。这样的计算机系统好像为用户提之间信息的动态调度。这样的计算机系统好像为用户提供了一个存储容量比实际主存大得多的存储器，就称为供了一个存储容量比实际主存大得多的存储器，就称为虚拟存储器。虚拟存储器。返回本节返回本节第第4 4章章 存储管理存储管理4.3.2请求式分页存储管理与动态地址重定位请求式分页存储管理与动态地址重定位请请求求式式分分页页

25、存存储储管管理理与与纯纯分分页页存存储储管管理理在在内内存存块块的的分分配配与与回回收收，存存储储保保护护某某方方面面都都十十分分相相似似，不不同同之之处处在在于于地地址址重重定定位位问问题题。在在请请求求式式分分页页存存储储管管理理的的地地址址重重定定位位时时，可可能能会会出出现现所所需需页页面面不不在在主主存存的的情情况况，此此时时，系系统统必必须须解决以下两个问题：解决以下两个问题：（1）当当程程序序要要访访问问的的某某页页不不在在内内存存时时，如如何何发发现现这这种种缺缺页情况？发现后应如何处理？页情况？发现后应如何处理？（2）当当需需要要把把外外存存上上的的某某个个页页面面调调入入内

26、内存存时时，此此时时内内存存中没有空闲块应怎么办？中没有空闲块应怎么办？下一页下一页第第4 4章章 存储管理存储管理如图如图4.17所示是请求式分页存储管理的存储映像所示是请求式分页存储管理的存储映像下一页下一页第第4 4章章 存储管理存储管理为为了了帮帮助助操操作作系系统统对对要要置置换换出出内内存存的的页页面面进进行行选选择择，在在页页表表中中还还可可以以增增加加一一个个引引用用位位，以以反反映映该该页最近的使用情况。页最近的使用情况。一一般般来来说说，一一个个页页表表的的表表目目通通常常可可包包括括如如下下的的数数据内容：据内容：下一页下一页第第4 4章章 存储管理存储管理请求式分页存储

27、管理中的地址重定位和缺页中断处请求式分页存储管理中的地址重定位和缺页中断处理过程如图理过程如图4.18所示。所示。返回本节返回本节第第4 4章章 存储管理存储管理4.3.3现代计算机系统改进的动态地址重定位现代计算机系统改进的动态地址重定位（1）如何合理地组织管理相当大的页表？）如何合理地组织管理相当大的页表？在在WindowsNT中中，为为解解决决第第一一个个问问题题，对对页页表表本本身身进进行行了了改改进进，将将庞庞大大的的页页表表本本身身也也采采取取分分页页措措施施，采采用用了了两两级级页页表表结结构构。即即把把页页表表本本身身按按固固定定大大小小分分成成一一个个个个小小页页表表，每每个

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

29、页目目录录（一一级级页页表表），它它的的每每个个表表目目指指向向一一个个二二级级页页表表。页页目目录录本本身身也也刚刚好好是是一一个个页页面面大小（大小（210=1k，每个表目，每个表目4个字节）。个字节）。下一页下一页第第4 4章章 存储管理存储管理图图4.19WindowsNT两级页表地址变换示意图两级页表地址变换示意图下一页下一页第第4 4章章 存储管理存储管理（2）面对大的页表，地址的映射怎样才能比较）面对大的页表，地址的映射怎样才能比较快地实现？快地实现？（1）使使用用快快表表：即即利利用用前前面面我我们们已已介介绍绍的的高高速速缓缓冲冲存存储储器器来来存存放放经经常常使使用用的的页

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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