电子科技大学计算机操作系统―第四章存储管理课件.pptx

1、许家珆4.1 存储管理的基本概念（一）存储管理的基本概念（一）这里只讨论内存管理，外存管理在设备中讨论。这里只讨论内存管理，外存管理在设备中讨论。存储器是价格昂贵，数量不足的资源。存储管存储器是价格昂贵，数量不足的资源。存储管理的效率直接影响到系统的性能，也最能够反映一理的效率直接影响到系统的性能，也最能够反映一个操作系统的特色。因此，存储管理的问题是操作个操作系统的特色。因此，存储管理的问题是操作系统的核心问题。系统的核心问题。存储管理的目的存储管理的目的1.1.为用户使用存储器提供方便。为用户使用存储器提供方便。在逻辑空间编程在逻辑空间编程 提供足够大的存储空间提供足够大的存储空间2.2.

2、充分发挥内存的利用率。充分发挥内存的利用率。许家珆4.1 存储管理的基本概念存储管理的基本概念存储管理的功能存储管理的功能 内存分配内存分配 内存保护内存保护 地址映射地址映射 内存扩充内存扩充 内存分配内存分配 内存保护内存保护 地址映射地址映射 内存扩充内存扩充讨论内容讨论内容装入模块装入模块装入装入内内 存存装入程序链接链接装入装入 链接链接 运行运行编译编译 内存分配内存分配许家珆4.1 存储管理的基本概念存储管理的基本概念 调入策略调入策略 确定装入时机确定装入时机 （预调、请调）（预调、请调）放置策略放置策略 如何分配空闲内存区的原则如何分配空闲内存区的原则（算法、连续、（算法、连

3、续、不连续）不连续）淘汰策略淘汰策略 当使用当使用请调请调策略时，确定淘汰哪些信息，策略时，确定淘汰哪些信息，以腾出内存空间，以便调入需要的信息。以腾出内存空间，以便调入需要的信息。可分为相等和不相等的内存块可分为相等和不相等的内存块内存分配与回收内存分配与回收分配策略分配策略内存划分内存划分内存回收内存回收回收进程所释放的存储空间回收进程所释放的存储空间存储管理的功能存储管理的功能许家珆4.1 存储管理的基本概念存储管理的基本概念 1.地址空间和存储空间地址空间和存储空间 程序经过编译所形成的目标代码，一般使用程序经过编译所形成的目标代码，一般使用相相对地址；对地址；即其首地址为即其首地址为

4、 0 ，其它指令的地址是相，其它指令的地址是相对首地址而定。相对地址又称为对首地址而定。相对地址又称为逻辑地址逻辑地址。该目标代码相对地址的全体称为程序的该目标代码相对地址的全体称为程序的地址空地址空间间，或或逻辑空间。逻辑空间。实际的内存物理地址的集合称为实际的内存物理地址的集合称为物理空间物理空间，或存，或存储空间。储空间。地址映射地址映射存储管理的功能存储管理的功能许家珆4.1 存储管理的基本概念存储管理的基本概念 2、重定位重定位（RelocationRelocation）为了保证程序的执行，操作系统必须将执行过程要为了保证程序的执行，操作系统必须将执行过程要访问的逻辑地址转换为物理地

5、址。这种地址的转换过程访问的逻辑地址转换为物理地址。这种地址的转换过程称为称为重定位重定位或地址或地址映射。映射。地址映射地址映射存储管理的功能存储管理的功能重定位分为重定位分为静态、动态静态、动态两种：两种：静态静态重定位重定位 程序装入过程中一次完成地址程序装入过程中一次完成地址映射。运行过程中，地映射。运行过程中，地址空间不允许改变。址空间不允许改变。优点：软件实现，无需硬件支持。优点：软件实现，无需硬件支持。缺点：分配连续空间，程序不能移动。缺点：分配连续空间，程序不能移动。许家珆4.1 存储管理的基本概念存储管理的基本概念 动态动态重定位重定位 重定位发生在程序执行过程中，在访问指令

6、或数据重定位发生在程序执行过程中，在访问指令或数据时，才进行地址变换。需要硬件地址变换机制实现。时，才进行地址变换。需要硬件地址变换机制实现。5001000VRBR+100011001500LOAD 1，5001 2 3 4 5内存空间内存空间LOAD 1，50001005001 2 3 4 5地址空间地址空间LOAD 1，500许家珆4.1 存储管理的基本概念存储管理的基本概念一。程序的装入和链接一。程序的装入和链接 绝对装入方式绝对装入方式 装入程序按照装入模块中的绝对地址将装入程序按照装入模块中的绝对地址将程序和数据装入内存。程序和数据装入内存。可重定位装入方式可重定位装入方式 装入模块

7、装入模块为相对地址（逻辑地址），为相对地址（逻辑地址），装入程序按照装入程序按照当前内存使用的情况，将当前内存使用的情况，将装入模块装入内存装入模块装入内存的某个物理地址。但是装入后不允许移动。的某个物理地址。但是装入后不允许移动。重定位重定位将逻辑地址转换为物理地址的过程将逻辑地址转换为物理地址的过程，也称为地，也称为地址变换或地址映射。址变换或地址映射。由于地址变换是在装入时一次完成的，又称为由于地址变换是在装入时一次完成的，又称为静态重定位静态重定位。1 1。程序的装入方式。程序的装入方式 动态运行时装入方式动态运行时装入方式 将装入模块装入内存后，运行时才进行地址变换，又将装入模块装入

8、内存后，运行时才进行地址变换，又称为动态重定位。称为动态重定位。许家珆4.1 存储管理的基本概念存储管理的基本概念 静态静态链接链接 事先将所需目标模块链接生成一个完整的事先将所需目标模块链接生成一个完整的装入模块（装入模块（.exe）运行时直接装入内存。运行时直接装入内存。动态动态链接链接 装入时装入时链接链接 边装入时边链接。即装入一个目标模块后，再将它所调用边装入时边链接。即装入一个目标模块后，再将它所调用的外部模块装入，可存放在内存的任何地方，并修改目标模的外部模块装入，可存放在内存的任何地方，并修改目标模块中的相对地址。块中的相对地址。运行时运行时链接链接 延迟到运行时，才将当前被调

9、用的目标模块装入延迟到运行时，才将当前被调用的目标模块装入,并链接。并链接。链接链接由由链接程序将目标模块及其所需的库函数，装配链接程序将目标模块及其所需的库函数，装配 链接生成链接生成装入模块的过程装入模块的过程。2.2.程序的程序的链接链接许家珆4.1 存储管理的基本概念存储管理的基本概念 实存方案实存方案 分区分配管理分区分配管理 分页管理分页管理 分段管理分段管理 虚存虚存方案方案 请求式分页管理请求式分页管理 请求式分段管理请求式分段管理 段页式管理段页式管理二。存储管理的机制二。存储管理的机制内存分配策略内存分配策略地址映射机制地址映射机制内存保护机制内存保护机制虚拟存储机制虚拟存

10、储机制许家珆4.2 4.2 分区存储管理分区存储管理一。固定一。固定分区（分区（Fixed PartitionsFixed Partitions）将内存固定划分为相等或不等的区域，称为分区，分区将内存固定划分为相等或不等的区域，称为分区，分区一旦划定，在执行过程中分区长度和个数将不再变化。建立一旦划定，在执行过程中分区长度和个数将不再变化。建立内存分配表内存分配表记录分区分配的情况。记录分区分配的情况。简单、可靠，但产生简单、可靠，但产生分区分区“内零头内零头”。内存利用效低。内存利用效低。分区存储管理的基本思想：分区存储管理的基本思想：将内存划分为若干分区，对用户作业进行连续分配。将内存划分

11、为若干分区，对用户作业进行连续分配。分区号分区号大小大小（K）始址始址（K）状态状态1234153050100304575125已分配已分配已分配已分配已分配已分配未分配未分配操作系统操作系统进程进程A（6K）进程进程B（25K）进程进程C（36K）0304575125内零头内零头1234许家珆4.2 4.2 分区存储管理分区存储管理二、可变二、可变分区分区（Variable PartitionsVariable Partitions）1.1.数据结构数据结构 。已分配分区表。已分配分区表 。未分配分区表。未分配分区表 通常表项由存储控制块通常表项由存储控制块MCB（区号、长度、始址（区号、长

12、度、始址等）描述。等）描述。并按照某种次序构成并按照某种次序构成链结构链结构。许家珆2.2.分区分区分配算法分配算法 首次适应算法首次适应算法FFFF（First FitFirst Fit）未分配分区按照地址从小到大排列。分配时顺序查找，未分配分区按照地址从小到大排列。分配时顺序查找，选择第一个满足要求的分区进行分配。选择第一个满足要求的分区进行分配。循环循环首次适应算法首次适应算法RFFRFF 分配时从上次已分配分配时从上次已分配分区分区的下一空闲的下一空闲分区开始查找。分区开始查找。查找到查找到链尾后，又从链首开始链尾后，又从链首开始查找。查找。最佳最佳适应算法适应算法BFBF（Best

13、FitBest Fit）按照空闲区大小升序排列，按照空闲区大小升序排列，分配时顺序查找，选择第分配时顺序查找，选择第一个满足要求的最小分区进行分配。一个满足要求的最小分区进行分配。最坏最坏适应算法适应算法WFWF（Worst FitWorst Fit）未分配分区按照大小从大到小排列。分配时顺序选择未分配分区按照大小从大到小排列。分配时顺序选择当前最大区。当前最大区。许家珆分配算法分配算法小结 名名 称称 未分配区组织未分配区组织 策策 略略 优优 点点 缺缺 点点首次适应算法首次适应算法循环循环首次适应算法首次适应算法最佳最佳适应算法适应算法最坏最坏适应算法适应算法 名名 称称 未分配区组织未

14、分配区组织 策策 略略 优优 点点 缺缺 点点首次适应算法首次适应算法循环循环首次适应算法首次适应算法最佳最佳适应算法适应算法最坏最坏适应算法适应算法许家珆 4.2 4.2 分区存储管理分区存储管理（三）（三）3 3。分区的分配与回收操作。分区的分配与回收操作将分区分配给请求者将分区分配给请求者修改数据结构修改数据结构p110许家珆4.2 4.2 分区存储管理分区存储管理（四）（四）3 3。分区的分配与回收操作。分区的分配与回收操作（P143 P143 图图5-105-10）回收回收F1回收区回收区F1回收区回收区F2回收区回收区F1内存内存回收的三种情况回收的三种情况许家珆4.2 4.2 分

15、区存储管理分区存储管理（四）（四）3 3。分区的分配与回收操作。分区的分配与回收操作顺序检索可用资源表直到找到表目：顺序检索可用资源表直到找到表目：m.addrsaa 或 m.size=0P143许家珆4.2 4.2 分区存储管理分区存储管理（五）（五）三。动态三。动态重定位重定位分区分配分区分配 1.1.紧凑技术紧凑技术 也称为也称为“拼凑拼凑”技术，用于解决可变分区中产生的技术，用于解决可变分区中产生的“外零外零头头”，即移动某些已分配分区，使，即移动某些已分配分区，使“外零头外零头”合并为一个大的合并为一个大的连续空闲区。连续空闲区。（P111 P111 图图4-8)4-8)2 2。分配

16、算法。分配算法请求分配请求分配顺序查找顺序查找空闲空闲分区表分区表有可用有可用分区分区动态分配动态分配修改数据结构修改数据结构Y空闲区总空闲区总和和 需求需求 N紧凑紧凑修改数据结构修改数据结构Y返返回回N 显然，可变显然，可变分区分配克服了内零头，提高了内存的利率，但分区分配克服了内零头，提高了内存的利率，但产生了外零头。使小碎片得不到利用。产生了外零头。使小碎片得不到利用。返回返回分区号分区号及首地址及首地址许家珆思 考 题 1 1、说明重定位分区分配方式的地址转换机制？如何实现分区存储保护？2、为什么要引入对换技术？如何实现进程的对换？许家珆4.3 4.3 分页存储管理分页存储管理（一）

17、（一）离散式内存分配离散式内存分配 允许一个进程分配在不相连接的内存允许一个进程分配在不相连接的内存 区域中，以利于提高存储效率。区域中，以利于提高存储效率。一。一。分页存储管理的基本思想分页存储管理的基本思想 将地址空间划分为大小相等的将地址空间划分为大小相等的页面页面，将内存空间也划分，将内存空间也划分为大小相等的为大小相等的物理块物理块，一个作业的所有页面，一个作业的所有页面一次装入一次装入，但，但可不连续存放可不连续存放。1 1、分页地址结构分页地址结构 页号页号 P P 位移量位移量 W3112 110内存连续分配的问题内存连续分配的问题 ：产生内零头或者外零头。产生内零头或者外零头

18、。采用紧凑技术增加额外开销。采用紧凑技术增加额外开销。页面大小通常为页面大小通常为2的整数次幂（的整数次幂（512字节字节4K）。）。许家珆 4.3 4.3 分页存储管理分页存储管理（二）（二）页表页表PTPT（Page TablePage Table）页号页号 P P 位移量位移量 W逻辑地址逻辑地址LA 页框号页框号 位移量位移量 物理地址物理地址2 2、内存分配、内存分配 将地址空间连续划分为大小相等的将地址空间连续划分为大小相等的页面页面，将内存空间，将内存空间也划分为大小相等的也划分为大小相等的物理块物理块（页框），一个作业的所有页（页框），一个作业的所有页面一次装入，但可不连续存放

19、面一次装入，但可不连续存放。仅存在很少的页内零头。仅存在很少的页内零头。为每个进程建立一张页表，每页占据一个表项，页表通常为每个进程建立一张页表，每页占据一个表项，页表通常放在内存中。放在内存中。页号页号页框号（页框号（块号）块号）存取控制存取控制01.m:35.许家珆 4.3 4.3 分页存储管理分页存储管理（三）（三）二。二。地址地址映射机制映射机制是通过是通过“页表页表”来实现来实现地址地址映射的。映射的。页页 号号 块块 号号 存取控制存取控制页描述子+如果页号如果页号页表页表长度，则中断，长度，则中断，否则继续否则继续.如果访问非法，如果访问非法，则中断，否则则中断，否则继续。继续。

20、页页 号号 位移量位移量虚拟地址虚拟地址 LA 块块 号号 位移量位移量物理地址物理地址页表始址页表始址 长度长度页表寄存器页表寄存器PTR页页 表表 块号块号 存取控制存取控制页描述子页描述子页页 号号 0 1 .块块 号号位移量位移量许家珆 4.3 4.3 分页存储管理分页存储管理（四）（四）由于页表存放在内存，每存取一个数据，由于页表存放在内存，每存取一个数据，CPU 要访要访两次内存，几乎降低了一半的计算速度，为了加快地址两次内存，几乎降低了一半的计算速度，为了加快地址变换的速度，在地址变换机构中建立一个变换的速度，在地址变换机构中建立一个高速缓冲存储高速缓冲存储器器，也称为，也称为联

21、想存储器联想存储器(Associative MemoryAssociative Memory)或或快表快表。2 2。具有快表的。具有快表的地址变换机构地址变换机构三。分页系统中的超高速缓存（三。分页系统中的超高速缓存（Cache MemoryCache Memory）在在CacheCache中，存放现行进程的页表副本，即记录现行进程中，存放现行进程的页表副本，即记录现行进程中最常用的页描述子。中最常用的页描述子。页表表目是在访问内存的过程中按需要动态装入快表的，页表表目是在访问内存的过程中按需要动态装入快表的，当进程切换时，快表被清零。当进程切换时，快表被清零。P153 P153 图图5-18

22、 5-18 描述了具有快表的描述了具有快表的地址变换过程。地址变换过程。1 1。为什么要设置快表为什么要设置快表许家珆 4.3 4.3 分页存储管理分页存储管理（五）（五）在缓存中查找页在缓存中查找页 描述子，找到了描述子，找到了 则提取。则提取。快表的命中率可高达快表的命中率可高达80%90%80%90%。利用页描述子和位利用页描述子和位移量计算物理地址移量计算物理地址2在缓存中未找到，在缓存中未找到，从页表中读取，并从页表中读取，并存入缓存。存入缓存。利用页描述子和位利用页描述子和位移量计算物理地址移量计算物理地址页号页号 位移量位移量虚拟地址虚拟地址具有超高速缓冲存储器的地址变换过程具有

23、超高速缓冲存储器的地址变换过程275382。超高速缓存超高速缓存页表页表01234.首先访问高速缓首先访问高速缓存，确定需要的页描存，确定需要的页描述子是否在其中，如述子是否在其中，如果没有发现，再访问果没有发现，再访问存储器中的页表。同存储器中的页表。同时将从页表中读出的时将从页表中读出的页描述子更新高速缓页描述子更新高速缓存中旧的页描述子。存中旧的页描述子。许家珆 4.3 4.3 分页存储管理分页存储管理（六）（六）1 1、什么是什么是“页表页表”？它具有什么样的结构？其表？它具有什么样的结构？其表 项项 一般包括哪些字段？一般包括哪些字段？2 2、如何通过如何通过页表实现逻辑地址到物理地

24、址的转换？页表实现逻辑地址到物理地址的转换？画出地址转换的流程图。画出地址转换的流程图。3 3、分页存储管理采用什么存储保护措施？分页存储管理采用什么存储保护措施？4 4、画出具有快表的地址转换过程的流程图。画出具有快表的地址转换过程的流程图。问问 题题 许家珆 4.3 4.3 分页存储管理分页存储管理（七）（七）四。多级页表四。多级页表 设置多级页表是为了解决逻辑空间过大，所造成的页表设置多级页表是为了解决逻辑空间过大，所造成的页表过大，占有太大的连续内存空间的过大，占有太大的连续内存空间的 问题。问题。1 1。二级页表。二级页表 页表内再分页，分为外层页表和内层页表。页表内再分页，分为外层

25、页表和内层页表。逻辑地址结构：逻辑地址结构：外层页号外层页号 P1 P1内层页号内层页号 P2 P2页内地址页内地址 d d 31 22 21 12 11 0具有具有二级页表的地址变换机构：二级页表的地址变换机构：问题：问题：1.分别画出二级页表的页描述子的结构，你认为它们分别画出二级页表的页描述子的结构，你认为它们 应该存放在哪里？如何存放？应该存放在哪里？如何存放？2.画出二级页表地址转换机制的流程图。画出二级页表地址转换机制的流程图。许家珆 4.4 4.4 分段存储管理分段存储管理（一）（一）一、一、分段存储管理的基本思想分段存储管理的基本思想1 1、什么是分段、什么是分段 页是信息的物

26、理单位，段（页是信息的物理单位，段（segmentssegments）是信息的逻辑单位，）是信息的逻辑单位，在逻辑上是一组整体的信息，每个段都是从在逻辑上是一组整体的信息，每个段都是从0 0开始相对编址的。开始相对编址的。2、为什么引入为什么引入分段存储管理分段存储管理 方便用户编程和实现共享方便用户编程和实现共享 便于实现动态链接便于实现动态链接 许家珆 4.4 4.4 分段存储管理分段存储管理（二）（二）3 3、分段地址、分段地址 在分段存储管理系统中，对所有地址空间的访问均要求两在分段存储管理系统中，对所有地址空间的访问均要求两个成分：（个成分：（1）段名；）段名；（2）段内地址。）段内

27、地址。例如：例如：CALL X|转移到子程序的入口点转移到子程序的入口点Y。LOAD1，A|将数组将数组A A 的的D D单元的值读入寄存器单元的值读入寄存器1 1。STORE1 B|将将寄存器寄存器1 1的内容存入分段的内容存入分段B B的的C C 单元中。单元中。这些符号程序经汇编和装配后，指令和数据的单元地址由这些符号程序经汇编和装配后，指令和数据的单元地址由两部分构成，一是表示段名的段号两部分构成，一是表示段名的段号S；一是位移量；一是位移量W，即段内，即段内地址。所以在分段系统中的地址结构有如下形式：地址。所以在分段系统中的地址结构有如下形式：一旦段号和段内位移量字段的长度确定后，一

28、个地址空间一旦段号和段内位移量字段的长度确定后，一个地址空间中允许的最多段数及段的长度也就限定了。中允许的最多段数及段的长度也就限定了。段号段号S 段内位移量段内位移量W31 16 15 0 许家珆 4.4 4.4 分段存储管理分段存储管理（三）（三）分段分段地址变换由段表实现，在作业被调入时，为其地址变换由段表实现，在作业被调入时，为其建立一张段表建立一张段表ST（Segment Table）。）。由此可见：由此可见：二、二、分段分段地址变换地址变换 所谓分段管理，就是管理由若干分段组成的作业，所谓分段管理，就是管理由若干分段组成的作业，且按分段来进行存储分配。实现分段管理的关键在于，且按分

29、段来进行存储分配。实现分段管理的关键在于，如何保证分段（二维）地址空间中的一个作业在线性如何保证分段（二维）地址空间中的一个作业在线性（一维）的存储空间中正确运行。（一维）的存储空间中正确运行。许家珆 4.4 4.4 分段存储管理分段存储管理（四）（四）利用段表实现地址映射利用段表实现地址映射许家珆 4.4 4.4 分段存储管理分段存储管理（五）（五）段号段号 段长段长 主存地址主存地址110K23+10340 段表始址段表始址 段表长度段表长度分段分段地址变换过程地址变换过程许家珆 4.4 4.4 分段存储管理分段存储管理（六）（六）三、分段存储保护三、分段存储保护在进行地址转换时，将段号与

30、段表寄存器中的段表长在进行地址转换时，将段号与段表寄存器中的段表长度进行比较，判断是否产生越界中断。度进行比较，判断是否产生越界中断。在进行存储访问时，将段地址的位移量与表目中段长在进行存储访问时，将段地址的位移量与表目中段长进行比较，如果超过段长，便发出越界中断信号。进行比较，如果超过段长，便发出越界中断信号。在段表的表目中，建立在段表的表目中，建立“存取控制存取控制”项进行段保护。项进行段保护。对非共享段，主要用于检查程序错误。对共享段尤其重要，对非共享段，主要用于检查程序错误。对共享段尤其重要，如对共享的纯过程，要求禁止修改。如对共享的纯过程，要求禁止修改。有哪些存储保护措施？有哪些存储

31、保护措施？许家珆 4.5 4.5 段页式存储管理段页式存储管理（一）（一）段页式段页式存储管理的基本思想存储管理的基本思想利用分段向用户提供二维的编程空间，利用分页来管理利用分段向用户提供二维的编程空间，利用分页来管理内存空间，以提高内存的利用率。内存空间，以提高内存的利用率。即对作业的地址空间分段，段内再分页。即对作业的地址空间分段，段内再分页。例如：例如：只有只有“内零头内零头”将分页管理和分段管理的优点集中起来进行存储管理。将分页管理和分段管理的优点集中起来进行存储管理。0 4k 8k12k15k16k一段一段0 0页页1 1页页2 2页页3 3页页三段三段 0 4k 8k10k12k0

32、 0页页1 1页页2 2页页二段二段 0 4k 8k0 0页页1 1页页许家珆 4.5 4.5 段页式存储管理段页式存储管理（二）（二）段页式段页式存储管理的基本思想存储管理的基本思想 段页式地址变换段页式地址变换 由段表和页表实现。由段表和页表实现。通常，分段由程序员完成，分页由系统自动完成。通常，分段由程序员完成，分页由系统自动完成。段页式地址结构段页式地址结构 实际上是一种三维地址，由实际上是一种三维地址，由（S，W ）（S，P，W）段号段号S和段内相对地址和段内相对地址W W 其中：其中：S：段号；：段号；P：页号；：页号；W：页内位移量。：页内位移量。S P W许家珆 例：有一页式系

33、统，其页表存放在主存中：例：有一页式系统，其页表存放在主存中：如果对主存的一次存取需要如果对主存的一次存取需要1.5 1.5 s,s,试问实现一次页面访试问实现一次页面访问的存取时间是多少问的存取时间是多少?如果系统具有快表如果系统具有快表,平均命中率为平均命中率为85%,当页表项在快表中当页表项在快表中时时,其查找时间忽略为其查找时间忽略为0,试问此时的存取时间是多少试问此时的存取时间是多少?答：若页表存放在主存中，则要实现一次页面访问需两次访问答：若页表存放在主存中，则要实现一次页面访问需两次访问主存：一次是访问页表，确定所存取页面的物理地址（称为定主存：一次是访问页表，确定所存取页面的物

34、理地址（称为定位）。第二次才根据该地址存取页面数据。位）。第二次才根据该地址存取页面数据。页表在主存的存取访问时间页表在主存的存取访问时间 =1.5 =1.5*2=3(s)2=3(s)增加快表后的存取访问时间增加快表后的存取访问时间 =0.85 =0.85*1.5+(1-0.85)1.5+(1-0.85)*2 2*1.5=1.725(s)1.5=1.725(s)许家珆小小 结结比较几种实存管理方案的异同，并说明其特点。比较几种实存管理方案的异同，并说明其特点。内存分配内存分配 地址变换机制地址变换机制 存储保护和共享存储保护和共享 优点优点 缺点缺点分区存储分区存储分页存储分页存储分段存储分段

35、存储段页存储段页存储许家珆 虚拟存储技术，有效地解决了上述问题。虚拟存储技术，有效地解决了上述问题。实存管理方案存在以下主要问题：实存管理方案存在以下主要问题：1 1、要求作业一次装入，造成内存资源的浪费。、要求作业一次装入，造成内存资源的浪费。2 2、用户编程的地址空间（逻辑空间）不能超过实际的内、用户编程的地址空间（逻辑空间）不能超过实际的内存空间。无法运行很大的应用程序。存空间。无法运行很大的应用程序。尤其是对多道程序系统，以上问题更加突出。尤其是对多道程序系统，以上问题更加突出。许家珆注意：注意：虚拟存储管理的各种方案，建立在相应的虚拟存储管理的各种方案，建立在相应的实存方实存方案基础

36、上。案基础上。虚拟存储方案：虚拟存储方案：请求分页式请求分页式 请求分段式请求分段式 请求段页式请求段页式 部分装入部分装入 作业在开始运行前，只装入部分，其余的作业在开始运行前，只装入部分，其余的 存放在外存，需要时再装入。存放在外存，需要时再装入。部分交换部分交换 当需要部分作业调入内存，而内存空间不当需要部分作业调入内存，而内存空间不 足时，需要将进程部分信息交换到外存，足时，需要将进程部分信息交换到外存，以腾出内存空间。以腾出内存空间。许家珆 地址变换地址变换 请求调页（段）方式下的地址转换机制。请求调页（段）方式下的地址转换机制。请调策略请调策略 是指作业的某页面（段）何时装入内存。

37、是指作业的某页面（段）何时装入内存。分为：请求式调入、预先调入两种。分为：请求式调入、预先调入两种。分配策略分配策略 调入的页面（段）放在何处，如何进行调入的页面（段）放在何处，如何进行 内存分配。内存分配。淘汰策略淘汰策略 也称为置换策略，按照某种算法选择淘也称为置换策略，按照某种算法选择淘 汰的页面（段）。汰的页面（段）。需要解决的问题需要解决的问题许家珆1 1、请求分页系统中的页表、请求分页系统中的页表 页描述子：页描述子：页面访问位页面访问位 A A 0 页面不在内存页面不在内存1 1 页面在内存页面在内存0 页面未被访问页面未被访问1 1 页面已被访问页面已被访问0 页面未被修改页面

38、未被修改1 1 页面已被修改页面已被修改判断缺页中断判断缺页中断影响页影响页面面置换策略置换策略是否重写外存是否重写外存 页面存在位页面存在位 P P 页面修改位页面修改位 M M 页号页号块号块号 存取控制存取控制 请求式分页存储管理是在分页式实存方案的基础上，进请求式分页存储管理是在分页式实存方案的基础上，进行行部分装入部分装入 和和部分交换部分交换 。许家珆地址变换过程地址变换过程请求访问一页请求访问一页页号页号 页表长页表长越界中断越界中断表项在快表中表项在快表中CPU检索快表检索快表访问页表访问页表页在内存页在内存YNYNY修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理

39、地址形成物理地址N缺页中断缺页中断许家珆2 2、缺页中断、缺页中断 进程在执行过程中，进程在执行过程中，需要请求某个（某些）需要请求某个（某些）页面，但其对应页描述页面，但其对应页描述子中子中P P 位为位为0 0，即页面，即页面不在内存中，产生缺页不在内存中，产生缺页中断，又称缺页故障。中断，又称缺页故障。缺页中断处理过程如图缺页中断处理过程如图 应该进一步讨论：应该进一步讨论：。页面页面淘汰策略淘汰策略。页面页面交换策略交换策略缺页中断缺页中断保留保留 CPU现场现场外存中找到所需页面外存中找到所需页面有空页框吗有空页框吗N选择淘汰的页面选择淘汰的页面该页修改过该页修改过Y把该页写回外存把

40、该页写回外存装入新的一页装入新的一页更新页表、快表更新页表、快表YN许家珆地址变换过程地址变换过程请求访问一页请求访问一页页号页号 页表长页表长越界中断越界中断表项在快表中表项在快表中CPU检索快表检索快表访问页表访问页表页在内存页在内存YNYNY修改快表修改快表修改访问位和修改位修改访问位和修改位形成物理地址形成物理地址N缺页中断处理缺页中断处理缺页中断缺页中断保留保留 CPU现场现场外存中找到所需页面外存中找到所需页面有空页框吗有空页框吗N选择淘汰的页面选择淘汰的页面该页修改过该页修改过Y把该页写回外存把该页写回外存装入新的一页装入新的一页更新页表、快表更新页表、快表YN11许家珆 为了制

41、定切实可行的策略，有效地管理虚拟存储系统，为了制定切实可行的策略，有效地管理虚拟存储系统，OS面临以下三个问题：面临以下三个问题：提取问题提取问题（Fetch Problem):Fetch Problem):作业的每个页面什么时作业的每个页面什么时 侯装入主存？侯装入主存？放置问题放置问题（Placement ProblemPlacement Problem）：在可用的页框中，）：在可用的页框中，页面存于何处？页面存于何处？置换问题置换问题（Replacement ProblemReplacement Problem）：当需要为调入的）：当需要为调入的 新页面腾出内存空间时，应该选择哪些交换到

42、外存去？新页面腾出内存空间时，应该选择哪些交换到外存去？其他要考虑的问题：外存中页面的存储分配，在多道其他要考虑的问题：外存中页面的存储分配，在多道程序系统中调度作业时，如何保证每个就绪作业拥有一定程序系统中调度作业时，如何保证每个就绪作业拥有一定数量的页框，这个数量以多少为宜。数量的页框，这个数量以多少为宜。许家珆 1 1、调入时机、调入时机 预调预调 根据预测，事先调入页面。根据预测，事先调入页面。请调请调 运行过程中，产生缺页故障时调入。运行过程中，产生缺页故障时调入。VMS VMS中采用群页式调页策略，是上述两种调页策略相结合。中采用群页式调页策略，是上述两种调页策略相结合。在外存中划

43、分特定区域，称为页面交换文件，用于存放在外存中划分特定区域，称为页面交换文件，用于存放换入、换出的页面。交换文件的内容有三种情况：换入、换出的页面。交换文件的内容有三种情况：进程运行前，将其所有页面调入交换区，从交换区调页。进程运行前，将其所有页面调入交换区，从交换区调页。将已修改的调出页面放在交换区，不允许修改的文件放在将已修改的调出页面放在交换区，不允许修改的文件放在文件区，调页时，按能否修改分别从交换区或文件区调。文件区，调页时，按能否修改分别从交换区或文件区调。运行后被调出的页面放在交换区，未运行过的页面放在文运行后被调出的页面放在交换区，未运行过的页面放在文件区。件区。2、页面交换区

44、、页面交换区3 3、页面调入过程、页面调入过程 （详见缺页中断处理）（详见缺页中断处理）许家珆 为每个进程分配固定数目的物理块，运行期间不能改变，为每个进程分配固定数目的物理块，运行期间不能改变，置换时置换时,只能淘汰该进程在内存的页面（局部置换）。只能淘汰该进程在内存的页面（局部置换）。先为每个进程分配一定数目的内存块，如先为每个进程分配一定数目的内存块，如VMS中为中为200块，在运行过程中可以改变。块，在运行过程中可以改变。OS OS中设置一个公共的空闲块队列，当产生缺页故障时，将中设置一个公共的空闲块队列，当产生缺页故障时，将空闲块分配给调入的页面（全局置换）。空闲块分配给调入的页面（

45、全局置换）。产生缺页故障时，只能将该进程的内存页面换出。如果缺产生缺页故障时，只能将该进程的内存页面换出。如果缺页率高，可为进程增加内存块，对缺页率低的进程则可减少页率高，可为进程增加内存块，对缺页率低的进程则可减少内存块内存块（局部置换（局部置换)。平均分配平均分配 按进程大小比例分配按进程大小比例分配 按优先权分配按优先权分配许家珆页面置换算法也称淘汰算法，是分页式虚拟存储的核心问页面置换算法也称淘汰算法，是分页式虚拟存储的核心问题，直接影响到存储管理的性能。题，直接影响到存储管理的性能。常见的算法有：常见的算法有：一、最佳一、最佳置换算法（置换算法（OptimalOptimal）理论算法

46、，所选择的淘汰页面，是永不访问的或在未来最理论算法，所选择的淘汰页面，是永不访问的或在未来最长时间内不再被访问的页面。长时间内不再被访问的页面。二二、FIFO算法算法是一种最简单的淘汰算法，首先淘汰在内存中驻留时间最是一种最简单的淘汰算法，首先淘汰在内存中驻留时间最长的页面。（例：长的页面。（例：P134 P134 图图4-264-26）算法依据是：作业按页号依次装入算法依据是：作业按页号依次装入 ，一般相邻页面间逻，一般相邻页面间逻辑关系最密切，故最早调入的页面不被使用的可能性比最近调辑关系最密切，故最早调入的页面不被使用的可能性比最近调入的页面大。入的页面大。优点：易实现。优点：易实现。缺

47、点：驻留时间长的页面往往是经常访问的。还可能出现缺点：驻留时间长的页面往往是经常访问的。还可能出现“异常现象异常现象”。许家珆三、三、LRU（Least Recently Used）算法算法 即即最近最久不使用页面最近最久不使用页面的淘汰算法。的淘汰算法。算法依据算法依据：一个已在内存的页面如在本次缺页中断前的近：一个已在内存的页面如在本次缺页中断前的近一段时间内，未被使用的时间最长，推测其最近的将来，一段时间内，未被使用的时间最长，推测其最近的将来，它也不会被使用。它也不会被使用。需要硬件支持：移位寄存器或堆栈。以寄存器为例：需要硬件支持：移位寄存器或堆栈。以寄存器为例：优点：性能比优点：性

48、能比FIFO FIFO 法好法好 。缺点：实现困难缺点：实现困难,要对要对“页面访问位页面访问位”作周期性检查（硬件支作周期性检查（硬件支 持），故常用近似算法。持），故常用近似算法。R实页实页R7 R6 R5 R4 R3 R2 R1 R0 1 1 0 1 0 0 0 0 0 2 0 0 0 0 1 0 0 0 3 1 0 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0 1 0 1 0 1 0 0 0 0 2 1 0 0 0 1 0 0 0 3 0 1 0 0 0 0 0 0 4 0 1 0 0 0 0 0 0 1 1 0 1 0 1 0 0 0 2 0 1 0 0 0 1 0 0

49、 3 0 1 0 0 0 0 0 0 4 0 0 1 0 1 0 0 0 1 0 1 0 1 0 0 0 0 2 1 0 1 0 0 0 1 0 3 0 1 0 1 1 0 0 1 4 0 0 1 0 1 0 1 0许家珆 四、四、LFU（Least Frequently Used）算法算法 最不常使用页面淘汰算法，最不常使用页面淘汰算法，LRU的的近似算法。近似算法。首先淘汰到当前时间为止，首先淘汰到当前时间为止，被访问次数最少的页面被访问次数最少的页面。只要在页表中增加一个访问计数器即可。该页被访问只要在页表中增加一个访问计数器即可。该页被访问时计数器加时计数器加 1 1。缺页中断时，淘汰

50、计数器值最小的页。缺页中断时，淘汰计数器值最小的页面。面。淘汰后，对计数器清零。淘汰后，对计数器清零。实际上，由于存储器访问速度较高，通常使用移实际上，由于存储器访问速度较高，通常使用移位寄存器实现。位寄存器实现。许家珆 五、五、Clock算法（算法（NRC算法）算法）是一种低开销的是一种低开销的 LRU近近 似算法。似算法。1 1、简单的、简单的Clock算法算法 为每页面设置一个访问位为每页面设置一个访问位A A，将所有页面链成循环链。将所有页面链成循环链。2 2、改进的、改进的Clock算法算法淘汰页面既考虑是否使用过，还考虑是否修改过。首先淘汰页面既考虑是否使用过，还考虑是否修改过。首