1、操作系统原理操作系统原理Operating System Principles四川大学计算机学院段 磊2014第第7章章 虚拟存储器管理虚拟存储器管理n 虚拟存储器管理为解决内存扩充问题而提出，其实现思想是将外存作为内存的扩充，作业运行不需要将作业的全部信息放入内存。n 虚拟存储器的实现基础是内存的分页式或分段式管理，采用的是进程页面或分段在内存与外存之间对换2022-6-23计算机操作系统- 第7章3/69本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理 n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/X
2、P系统存储器管理实例 2022-6-23计算机操作系统- 第7章4/69本章目录n7.1 虚拟存储器的基本概念 n虚拟存储器的概念 n虚拟存储器的特征 n7.2 请求分页虚拟存储管理 n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 2022-6-23计算机操作系统- 第7章5/69虚拟存储器的引入n常规存储管理的特征：n一次性（指全部装入）n驻留性（指驻留在内存不换出）n局部性原理n时间局部性：如循环执行n空间局部性：如顺序执行。n程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的
3、。n过程调用将会使程序的执行轨迹变化，但在一段时间内都局限在一定过程的范围内运行。n程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。n程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内2022-6-23计算机操作系统- 第7章6/69虚拟存储器的引入n常规存储管理的特征：n一次性（指全部装入）n驻留性（指驻留在内存不换出）n局部性原理n时间局部性：如循环执行n空间局部性：如顺序执行。n程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。n过程调用将会使程序的执行轨迹变化，但在一段时间内都局限在一定过程的范围内运行。n程
4、序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。n程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。2022-6-23计算机操作系统- 第7章7/692022-6-23计算机操作系统- 第7章8/69n虚拟存储器n具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。n实质：以时间换空间，但时间牺牲不大。n需要动态重定位虚拟存储器的引入2022-6-23计算机操作系统- 第7章9/69n请求分页系统n以页为单位转换n需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构n需实现请求分页机制的软件（置换软件等）虚拟存
5、储器的实现方式2022-6-23计算机操作系统- 第7章10/69n请求分段系统n以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构n需实现请求分段机制的软件（置换软件等）虚拟存储器的实现方式2022-6-23计算机操作系统- 第7章11/697.1.2 虚拟存储器的特征n离散性n部分装入n多次性n局部装入，多次装入n对换性n虚拟性2022-6-23计算机操作系统- 第7章12/69本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n请求分页的硬件支持n分页虚拟存储器管理实施中的策略问题 n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段
6、存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 2022-6-23计算机操作系统- 第7章13/697.2.1 请求分页中的硬件支持n页表机制n缺页中断机构n地址变换机构2022-6-23计算机操作系统- 第7章14/69n页表机制请求分页中的硬件支持页号 物理块号状态位P访问字段A修改位M外存地址状态位P： 用于指示该页是否已调入内存，供程序访问时参考。访问字段A： 用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。修改位M： 表示该页在调入内存后是否被修改过，供置换页面时参考。外存地址： 用于指出该页在外存上的地址，通
7、常是物理块号，供调入该页时参考。2022-6-23计算机操作系统- 第7章15/69n缺页中断机构n当所要访问的页面不在内存时，产生缺页中断，请求OS将所缺之页调入内存。n与其他中断的区别n可在指令执行期间产生n一条指令在执行期间，可能产生多次缺页中断。（如图7.3）请求分页中的硬件支持2022-6-23计算机操作系统- 第7章16/69地地址址变变换换过过程程增加增加中断处理中断处理2022-6-23计算机操作系统- 第7章17/697.2.2 分页虚拟存储器管理实施中的策略问题 n最小物理块数n保证进程正常运行所需的最小物理块数n不同的作业要求不同n如：允许间接寻址：则至少要求3个物理块。
8、Mov A, B 2022-6-23计算机操作系统- 第7章18/69内存分配策略和分配算法固定与可变： 指为进程分配的物理块数是固定的还是变化的局部与全局： 指因内存不够需要置换时，换出的页面是该进程的页面，还是内存中所有进程的某一页面。2022-6-23计算机操作系统- 第7章19/69n页面分配和置换策略n固定分配局部置换n缺点：难以确定固定分配的页数.(少：置换率高 多：浪费)n可变分配全局置换n可变分配局部置换n根据进程的缺页率进行页面数调整，进程之间相互不会影响。内存分配策略和分配算法2022-6-23计算机操作系统- 第7章20/69n分配算法n平均分配算法n按比例分配算法n考虑
9、优先权的分配算法内存分配策略和分配算法mssbiiniiss12022-6-23计算机操作系统- 第7章21/69调页策略 n1.调入时机：n预调：（根据空间局部性）n目前：成功率50n请求调：较费系统开销n各有优劣n2从何处调页：n对换区：修改过的页被换出时入对换区， 快n文件区：稍慢n对共享页，应判断其是否在内存区。n3.页面调入过程2022-6-23计算机操作系统- 第7章22/69页页面面调调入入过过程程2022-6-23计算机操作系统- 第7章23/69本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n7.3 页面置换算法 n先进先出（FIFO）页面置换算法 n
10、最佳（optimal）页面置换算法 n最近最久未使用（LRU）页面置换算法 n时钟（clock）置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 2022-6-23计算机操作系统- 第7章24/69n理想淘汰算法最佳页面算法（OPT）n淘汰以后不再需要的或最远的将来才会用到的页面n先进先出页面淘汰算法（FIFO）n淘汰在内存中驻留时间最长的页并淘汰n最近最久未使用页面淘汰算法（LRU）n淘汰最后一次访问时间距离当前时间最长的一页n即淘汰没有使用的时间最长的页nClock置换算法LRU近似算法n最不经常使用（LFU）n淘汰
11、访问次数最少的页面主要置换算法2022-6-23计算机操作系统- 第7章25/69举例n在一个请求分页系统中，假设一个作业的页面走向为： 4 3 2 1 4 3 5 4 3 2 1 5n当分配给该作业的物理块数M分别是3和4时，请计算不同页面置换算法下，访问过程中所发生的缺页次数和缺页率。2022-6-23计算机操作系统- 第7章26/69n思想：n选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。n效果：n通常可保证获得最低的缺页率。n评价：n由于人们无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法无法实现n可以利用该算
12、法去评价其它算法页面置换算法-OPT2022-6-23计算机操作系统- 第7章27/69举例n采用OPT淘汰算法，当M3时 512345341234P121110987654321时刻FM4+3+4+2+-34+1+-34+1-341-345+-34+534-53-452+-4+51+-4+5-14由表可以算出缺页中断次数由表可以算出缺页中断次数F=7，而缺页率：，而缺页率：712=58%。2022-6-23计算机操作系统- 第7章28/69n采用OPT淘汰算法，当M4时512345341234P121110987654321时刻FM4+3+4+2+34+1+-234+1-2341-2345+
13、-234+5234-523-452-3451+-34+5-134由表可以算出缺页中断次数由表可以算出缺页中断次数F=6，而缺页率：，而缺页率：612=50%。举例2022-6-23计算机操作系统- 第7章29/69n思想：n总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。n效果：n实现简单。n评价：n与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，该算法并不能保证这些页面不被淘汰。 页面置换算法-FIFO2022-6-23计算机操作系统- 第7章30/69举例n如果采用FIFO替换算法，当M3时 512345341234P121110987654321时刻
14、FM4+3+4+2+34-+1+23-+4+12-+3+41-+5+34-+534-534-2+53-+1+25-+125-由表可以算出缺页中断次数由表可以算出缺页中断次数F=9，而缺页率：，而缺页率：912=75%。2022-6-23计算机操作系统- 第7章31/69举例n采用FIFO替换算法，当M4时 512345341234P121110987654321时刻FM4+3+4+2+34+1+234-+1234-1234-5+123-+4+512-+3+451-+2+345-+1+234-+5+123-+由表可以算出缺页中断次数由表可以算出缺页中断次数F=10，而缺页率：，而缺页率：1012
15、=83%。2022-6-23计算机操作系统- 第7章32/69n思想：n根据页面调入内存后的使用情况进行决策的。选择最近最久未使用的页面予以淘汰。n效果：n较好。n评价：n需要有较多的硬件支持（寄存器、栈）。页面置换算法-LRU2022-6-23计算机操作系统- 第7章33/69举例n当M3时，采用LRU替换算法： 512345341234P121110987654321时刻FM4+3+4+2+34-+1+23-+4+12-+3+41-+5+34-+453-345-2+34-+1+23-+5+12-+算出缺页中断次数算出缺页中断次数F=10，缺页率，缺页率f =1012=83。2022-6-2
16、3计算机操作系统- 第7章34/69举例n当M4时，采用LRU替换算法： 512345341234P121110987654321时刻FM4+3+4+2+34+1+234-+4123-3412-5+341-+4531-3451-2+345-+1+234-+5+123-+由表可以算出缺页中断次数由表可以算出缺页中断次数F=8，而缺页率：，而缺页率：812=67%。2022-6-23计算机操作系统- 第7章35/69结论总结：n 通过以上缺页次数和缺页率的分析计算，可以看出：n对于LRU、OPT算法，增加物理块数，不会增加缺页次数。n对于FIFO算法，增加物理块数，不一定能减少缺页次数。nOPT算
17、法仅是一种理论算法，不作为实用算法，仅用于算法的比较和评价。2022-6-23计算机操作系统- 第7章36/69结论讨论：n 计算缺页次数和缺页率时，要注意初始时刻所有物理块为空。n 调入页面时，不需要页面替换，但是需要引起缺页中断。 2022-6-23计算机操作系统- 第7章37/69页面置换算法-Clock/NRUn思想：n为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。n当某页被访问时，其访问位被置1。n置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查
18、下一个页面。n当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。2022-6-23计算机操作系统- 第7章38/69页面置换算法-Clock/NRU2022-6-23计算机操作系统- 第7章39/69页面置换算法-Clock/NRU该算法只有一位访问位，只能用它表示该页是否已经使该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该用过，而置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法算法称为最近未用算法NRU (Not Recently Used)。 2022-6-23计算机操作系统- 第7章40/69页
19、面置换算法-改进型Clockn思想：n考虑页面的使用情况外，还须再增加一个因素，即置换代价。n选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。n由访问位A和修改位M可以组合成四种类型的页面： 2022-6-23计算机操作系统- 第7章41/69页面置换算法-改进型Clockn思想：n考虑页面的使用情况外，还须再增加一个因素，即置换代价。n选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。n由访问位A和修改位M可以组合成四种类型的页面： 1 1类类(A=0(A=0，M=0)M=0
20、)：表示该页最近既未被访问，又未被修：表示该页最近既未被访问，又未被修改，是最佳淘汰页。改，是最佳淘汰页。2 2类类(A=0(A=0，M=1)M=1)：表示该页最近未被访问，但已被修改，：表示该页最近未被访问，但已被修改，并不是很好的淘汰页。并不是很好的淘汰页。3 3类类(A=1(A=1，M=0)M=0)：表示该页最近已被访问，但未被修改，：表示该页最近已被访问，但未被修改，该页有可能再被访问。该页有可能再被访问。4 4类类(A=1(A=1，M=1)M=1)：表示该页最近已被访问且被修改，该：表示该页最近已被访问且被修改，该页可能再被访问。页可能再被访问。 2022-6-23计算机操作系统-
21、第7章42/69页面置换算法-改进型Clockn实施步骤：第一步：第一步：从指针所指示的当前位置开始，扫描循环队列，寻找从指针所指示的当前位置开始，扫描循环队列，寻找A=0A=0且且M=0M=0的第一类页面，将所遇到的第一个页面作为所选中的淘的第一类页面，将所遇到的第一个页面作为所选中的淘汰页。在第一次扫描期间不改变访问位汰页。在第一次扫描期间不改变访问位A A。 第二步：第二步：如果第一步失败，即查找一周后未遇到第一类页面，则开始如果第一步失败，即查找一周后未遇到第一类页面，则开始第二轮扫描，寻找第二轮扫描，寻找A=0A=0且且M=1M=1的第二类页面，将所遇到的第一的第二类页面，将所遇到的
22、第一个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过个这类页面作为淘汰页。在第二轮扫描期间，将所有扫描过的页面的访问位都置的页面的访问位都置0 0。第三步：第三步：如果第二步也失败，亦即未找到第二类页面，则将指针返回如果第二步也失败，亦即未找到第二类页面，则将指针返回到开始的位置，并将所有的访问位复到开始的位置，并将所有的访问位复0 0。然后重复第一步，。然后重复第一步，如果仍失败，必要时再重复第二步，此时就一定能找到被淘如果仍失败，必要时再重复第二步，此时就一定能找到被淘汰的页。汰的页。评价：评价：该算法与简单该算法与简单ClockClock算法比较，可减少磁盘的算法比较，可减少磁盘的I
23、/OI/O操作次数。操作次数。但为了找到一个可置换的页，可能须经过几轮扫描。换言之，但为了找到一个可置换的页，可能须经过几轮扫描。换言之，实现该算法本身的开销将有所增加。实现该算法本身的开销将有所增加。 2022-6-23计算机操作系统- 第7章43/69页面置换算法-LFU（最少使用）n思想：n为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。n选择在最近时期使用最少的页面作为淘汰页。2022-6-23计算机操作系统- 第7章44/69页面置换算法-页面缓冲n引入n其他算法需要硬件支持，例如：LRU、Clock等；n置换一个已修改的页比置换未修改页的开销要大。n思想：n采用
24、了可变分配和局部置换方式，置换算法为FIFO。n将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入已修改页面的链表中。n评价：n可改善分页系统的性能，又可采用一种较简单的置换策略2022-6-23计算机操作系统- 第7章45/69本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n7.3 页面置换算法 n7.4 页面调度性能n页面调度对系统性能的影响分析 n工作集模型 n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 2022-6-23计算机操作系统- 第7章46/69n影响缺页次数的因
25、素n分配给进程的物理块数n页本身的大小n程序的编制方法n页淘汰算法n颠簸/抖动n定义n原因讨论2022-6-23计算机操作系统- 第7章47/69n影响缺页次数的因素n分配给进程的物理块数n页本身的大小n程序的编制方法n页淘汰算法n颠簸/抖动n定义n原因讨论在虚存中，页面在内存与外存在虚存中，页面在内存与外存之间频繁调度，以至于调度页之间频繁调度，以至于调度页面所需时间比进程实际运行的面所需时间比进程实际运行的时间还多，此时系统效率急剧时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这下降，甚至导致系统崩溃。这种现象称为种现象称为颠簸或抖动颠簸或抖动 页面淘汰算法不合理页面淘汰算法不合理 分
26、配给进程的物理页面数太少分配给进程的物理页面数太少2022-6-23计算机操作系统- 第7章48/69学习与问题：页面调度中哪些因素会对系统性页面调度中哪些因素会对系统性能产生影响？能产生影响？试分析缺页率对系统性能的影响试分析缺页率对系统性能的影响试分析页面大小对系统性能的影响试分析页面大小对系统性能的影响6 65 54 43 3试分析对换空间对系统性能的影响试分析对换空间对系统性能的影响工作集模型的目的与原理工作集模型的目的与原理2 22022-6-23计算机操作系统- 第7章49/69本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n7.3 页面置换算法 n7.4
27、页面调度性能n7.5 请求分段存储管理方式 n请求分段的实现n段页式虚拟存储器管理的实现 n7.6 Windows 2000/XP系统存储器管理实例 2022-6-23计算机操作系统- 第7章50/69请求分段中的硬件支持n段表机制n缺段中断机构n地址变换机构2022-6-23计算机操作系统- 第7章51/69请求分段中的硬件支持n段表机制段名 段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址存取方式： 用于标识本分段的存取属性是只执行、只读，还是允许读/写访问字段A： 用于记录本段在一段时间内被访问的次数，或记录本段最近已有多长时间未被访问，供选择换出分段时参考。修改位M： 表示
28、该段在调入内存后是否被修改过，供置换分段时参考。存在位P： 指示本段是否已调入内存，供程序访问时参考。增补位： 这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。外存始址： 指示本段在外存中的起始地址，即起始盘块号。2022-6-23计算机操作系统- 第7章52/69请求分段中的硬件支持n缺段中断机构n与缺页中断机构类似n但由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。n同时由于段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂。 2022-6-23计算机操作系统- 第7章53/69请求分段中的硬件支持2
29、022-6-23计算机操作系统- 第7章54/69请求分段中的硬件支持n地址变换机构2022-6-23计算机操作系统- 第7章55/69段的共享与保护n共享段表n共享进程计数Countn存取控制字段n段号2022-6-23计算机操作系统- 第7章56/69段的共享与保护n共享段的分配与回收n分段保护：n越界检查n存取控制检查n环保护机构1.1.一个程序可以访问驻留在相同一个程序可以访问驻留在相同环或较低特权环中的数据。环或较低特权环中的数据。2.2.一个程序可以调用驻留在相同一个程序可以调用驻留在相同环或较高特权环中的服务。环或较高特权环中的服务。2022-6-23计算机操作系统- 第7章57
30、/69段的共享与保护2022-6-23计算机操作系统- 第7章58/69例题1n内存分配一页，初始时矩阵数据均不在内存；页面大小为128个整数；矩阵A128128按行存放。以下两个程序执行时分别会产生多少次缺页中断？程序编制方法1：for j:=1 to 128 for i:=1 to 128 Ai,j:=0;程序编制方法2：for i:=1 to 128 for j:=1 to 128 Ai,j:=0;2022-6-23计算机操作系统- 第7章59/69例题1：答案程序编制方法1：for j:=1 to 128 for i:=1 to 128 Ai,j:=0;程序编制方法2：for i:=1
31、 to 128 for j:=1 to 128 Ai,j:=0;参考7.4.1中“4.编制程序对缺页率的影响”2022-6-23计算机操作系统- 第7章60/69例题2n某程序在内存中分配3块内存，初始为空，访问页走向如下，用FIFO和LRU算法分别计算缺页次数。 2，3，2，1，5，2，4，5，3，2，5，22022-6-23计算机操作系统- 第7章61/69例题2：答案-FIFO FIFO 2 3 2 1 5 2 4 5 3 2 5 2n 页1 2 3 3 1 5 2 4 4 3 3 5 2n 页2 2 2 3 1 5 2 2 4 4 3 5n 页3 2 3 1 5 5 2 2 4 3 x
32、 x x x x x x x xn 共缺页中断9次2022-6-23计算机操作系统- 第7章62/69例题2：答案-LRU LRU 2 3 2 1 5 2 4 5 3 2 5 2n页1 2 3 2 1 5 2 4 5 3 2 5 2n页2 2 3 2 1 5 2 4 5 3 2 5n页3 3 2 1 5 2 4 5 3 3 x x x x x x x n共缺页中断7次2022-6-23计算机操作系统- 第7章63/69例题3n在分页存储管理系统中，有一作业大小为4页，页长为2K，页表如下，试借助地址变换图（即要求画出地址变换图）求出逻辑地址4635所对应的物理地址。 页号块号051327362
33、022-6-23计算机操作系统- 第7章64/69例题3：答案31637250块号页号01000011011000100100001101100111页表首址页表首址+0 010物理地址为：物理地址为：14875148752022-6-23计算机操作系统- 第7章65/69作业n练习习题1、2、3（见后）n作业通过发送电子邮件附件形式提交到助教老师邮箱：n赵 静 n作业文件名命名要求：nOS_学号_姓名_n.doc （n为当章节序号）n如一个合法文件名：nOS_95002_张三_7.doc2022-6-23计算机操作系统- 第7章66/69习题1n某系统采用请求分页管理内存, 采用LRU页面置
34、换算法. 作业的页面走向为： 4、3、2、1、5、3、0、4、3、2、0、5 内存块M=4, 试计算运行时的缺页率。n某系统采用请求分页管理内存, 采用LRU页面置换算法. 作业A的页面走向为: 4、3、1、3、2、4、2、3、5、2、6、3 内存块M=3，试分析运行时的缺页率。2022-6-23计算机操作系统- 第7章67/69习题2n如图所示，现有作业A须申请40K内存，写出选用以下各分配策略时，作业A的首地址和末地址，图中阴影为占用区。A. 最先适应法 B. 最佳适应法C. 最差适应法D. 单一连续分配2022-6-23计算机操作系统- 第7章68/69习题3n现有一请求分页的虚拟存储器 , 内存最多容纳 4 个页面 , 对于下面的引用串 : 1,2,3,4,5,3,4,1,6,7,8,7,8,9,7,8,9,5,4,5,4,2 分别采用 FIFO, LRU, OPT 页面替换算法 , 各将产生多少次缺页中断 ? 2022-6-23计算机操作系统- 第7章69/69Any Question?Thank you !
