《虚拟存储器管理四川大学课件》由会员分享，可在线阅读，更多相关《虚拟存储器管理四川大学课件（69页珍藏版）》请在金锄头文库上搜索。
1、操作系统原理操作系统原理Operating System Principles四川大学计算机学院段 磊2014第第7章章 虚拟存储器管理虚拟存储器管理n 虚拟存储器管理为解决内存扩充问题而提出，其实现思想是将外存作为内存的扩充，作业运行不需要将作业的全部信息放入内存。n 虚拟存储器的实现基础是内存的分页式或分段式管理，采用的是进程页面或分段在内存与外存之间对换本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理 n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 8/2/20243计算机操作
2、系统- 第7章本章目录n7.1 虚拟存储器的基本概念 n虚拟存储器的概念 n虚拟存储器的特征 n7.2 请求分页虚拟存储管理 n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 8/2/20244计算机操作系统- 第7章虚拟存储器的引入n常规存储管理的特征：n一次性（指全部装入）n驻留性（指驻留在内存不换出）n局部性原理n时间局部性：如循环执行n空间局部性：如顺序执行。n程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。n过程调用将会使程序的执行轨迹变化，但在一段时间内都局限在一定过
3、程的范围内运行。n程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。n程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内8/2/20245计算机操作系统- 第7章虚拟存储器的引入n常规存储管理的特征：n一次性（指全部装入）n驻留性（指驻留在内存不换出）n局部性原理n时间局部性：如循环执行n空间局部性：如顺序执行。n程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。n过程调用将会使程序的执行轨迹变化，但在一段时间内都局限在一定过程的范围内运行。n程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。n程序
4、中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。程序或数据访问的特点：程序或数据访问的特点：程序或数据访问的特点：程序或数据访问的特点： 顺序性顺序性顺序性顺序性 局限性局限性局限性局限性 多次性多次性多次性多次性 独立性独立性独立性独立性8/2/20246计算机操作系统- 第7章8/2/20247计算机操作系统- 第7章n虚拟存储器n具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。n实质：以时间换空间，但时间牺牲不大。n需要动态重定位虚拟存储器的引入8/2/20248计算机操作系统- 第7章n请求分页系统n以页为单位转换n需硬件：（1）请
5、求分页的页表机制（2）缺页中断（3）地址变换机构n需实现请求分页机制的软件（置换软件等）虚拟存储器的实现方式8/2/20249计算机操作系统- 第7章n请求分段系统n以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构n需实现请求分段机制的软件（置换软件等）虚拟存储器的实现方式8/2/202410计算机操作系统- 第7章7.1.2 虚拟存储器的特征n离散性n部分装入n多次性n局部装入，多次装入n对换性n虚拟性8/2/202411计算机操作系统- 第7章本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n请求分页的硬件支持n分页虚拟存储器管理实施中的策略问
6、题 n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 8/2/202412计算机操作系统- 第7章7.2.1 请求分页中的硬件支持n页表机制n缺页中断机构n地址变换机构8/2/202413计算机操作系统- 第7章n页表机制请求分页中的硬件支持页号 物理块号状态位P访问字段A修改位M外存地址状态位P： 用于指示该页是否已调入内存，供程序访问时参考。访问字段A： 用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。修改位M： 表示该页在调入内存后是否被修改过，供置换页
7、面时参考。外存地址： 用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。8/2/202414计算机操作系统- 第7章n缺页中断机构n当所要访问的页面不在内存时，产生缺页中断，请求OS将所缺之页调入内存。n与其他中断的区别n可在指令执行期间产生n一条指令在执行期间，可能产生多次缺页中断。（如图7.3）请求分页中的硬件支持8/2/202415计算机操作系统- 第7章地地址址变变换换过过程程增加增加中断处理中断处理8/2/202416计算机操作系统- 第7章7.2.2 分页虚拟存储器管理实施中的策略问题 n最小物理块数n保证进程正常运行所需的最小物理块数n不同的作业要求不同n如：允许间接
8、寻址：则至少要求3个物理块。Mov A, B 8/2/202417计算机操作系统- 第7章内存分配策略和分配算法固定与可变： 指为进程分配的物理块数是固定的还是变化的局部与全局： 指因内存不够需要置换时，换出的页面是该进程的页面，还是内存中所有进程的某一页面。8/2/202418计算机操作系统- 第7章n页面分配和置换策略n固定分配局部置换n缺点：难以确定固定分配的页数.(少：置换率高 多：浪费)n可变分配全局置换n可变分配局部置换n根据进程的缺页率进行页面数调整，进程之间相互不会影响。内存分配策略和分配算法8/2/202419计算机操作系统- 第7章n分配算法n平均分配算法n按比例分配算法n
9、考虑优先权的分配算法内存分配策略和分配算法8/2/202420计算机操作系统- 第7章调页策略 n1.调入时机：n预调：（根据空间局部性）n目前：成功率50n请求调：较费系统开销n各有优劣n2从何处调页：n对换区：修改过的页被换出时入对换区， 快n文件区：稍慢n对共享页，应判断其是否在内存区。n3.页面调入过程8/2/202421计算机操作系统- 第7章页页面面调调入入过过程程8/2/202422计算机操作系统- 第7章本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n7.3 页面置换算法 n先进先出（FIFO）页面置换算法 n最佳（optimal）页面置换算法 n最近最
10、久未使用（LRU）页面置换算法 n时钟（clock）置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 8/2/202423计算机操作系统- 第7章n理想淘汰算法最佳页面算法（OPT）n淘汰以后不再需要的或最远的将来才会用到的页面n先进先出页面淘汰算法（FIFO）n淘汰在内存中驻留时间最长的页并淘汰n最近最久未使用页面淘汰算法（LRU）n淘汰最后一次访问时间距离当前时间最长的一页n即淘汰没有使用的时间最长的页nClock置换算法LRU近似算法n最不经常使用（LFU）n淘汰访问次数最少的页面主要置换算法8/2/202424计
11、算机操作系统- 第7章举例n在一个请求分页系统中，假设一个作业的页面走向为： 4 3 2 1 4 3 5 4 3 2 1 5n当分配给该作业的物理块数M分别是3和4时，请计算不同页面置换算法下，访问过程中所发生的缺页次数和缺页率。8/2/202425计算机操作系统- 第7章n思想：n选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。n效果：n通常可保证获得最低的缺页率。n评价：n由于人们无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法无法实现n可以利用该算法去评价其它算法页面置换算法-OPT8/2/202426计算机操作系
12、统- 第7章举例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%。8/2/202427计算机操作系统- 第7章n采用OPT淘汰算法，当M4时512345341234P121110987654321时刻FM4+3+4+2+34+1+-234+1-2341-2345+-234+5234-523-452-3451+-34+5-134由表可以算出缺页中断
13、次数由表可以算出缺页中断次数F=6，而缺页率：，而缺页率：612=50%。举例8/2/202428计算机操作系统- 第7章n思想：n总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。n效果：n实现简单。n评价：n与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，该算法并不能保证这些页面不被淘汰。 页面置换算法-FIFO8/2/202429计算机操作系统- 第7章举例n如果采用FIFO替换算法，当M3时 512345341234P121110987654321时刻FM4+3+4+2+34-+1+23-+4+12-+3+41-+5+34-+534-534-2+53
14、-+1+25-+125-由表可以算出缺页中断次数由表可以算出缺页中断次数F=9，而缺页率：，而缺页率：912=75%。8/2/202430计算机操作系统- 第7章举例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=83%。8/2/202431计算机操作系统- 第7章n思想：n根据页面调入内存后的使用情况进行决策的。选择
15、最近最久未使用的页面予以淘汰。n效果：n较好。n评价：n需要有较多的硬件支持（寄存器、栈）。页面置换算法-LRU8/2/202432计算机操作系统- 第7章举例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。8/2/202433计算机操作系统- 第7章举例n当M4时，采用LRU替换算法： 512345341234P121110987654321时
16、刻FM4+3+4+2+34+1+234-+4123-3412-5+341-+4531-3451-2+345-+1+234-+5+123-+由表可以算出缺页中断次数由表可以算出缺页中断次数F=8，而缺页率：，而缺页率：812=67%。8/2/202434计算机操作系统- 第7章结论总结：n 通过以上缺页次数和缺页率的分析计算，可以看出：n对于LRU、OPT算法，增加物理块数，不会增加缺页次数。n对于FIFO算法，增加物理块数，不一定能减少缺页次数。nOPT算法仅是一种理论算法，不作为实用算法，仅用于算法的比较和评价。8/2/202435计算机操作系统- 第7章结论讨论：n 计算缺页次数和缺页率时
17、，要注意初始时刻所有物理块为空。n 调入页面时，不需要页面替换，但是需要引起缺页中断。 8/2/202436计算机操作系统- 第7章页面置换算法-Clock/NRUn思想：n为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。n当某页被访问时，其访问位被置1。n置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。n当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。8/2/202437计算机操作系统- 第7章页面置换算法-C
18、lock/NRU8/2/202438计算机操作系统- 第7章页面置换算法-Clock/NRU该算法只有一位访问位，只能用它表示该页是否已经使该算法只有一位访问位，只能用它表示该页是否已经使用过，而置换时是将未使用过的页面换出去，故又把该用过，而置换时是将未使用过的页面换出去，故又把该算法称为最近未用算法算法称为最近未用算法NRU (Not Recently Used)。 8/2/202439计算机操作系统- 第7章页面置换算法-改进型Clockn思想：n考虑页面的使用情况外，还须再增加一个因素，即置换代价。n选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页
19、面作为首选淘汰的页面。n由访问位A和修改位M可以组合成四种类型的页面： 8/2/202440计算机操作系统- 第7章页面置换算法-改进型Clockn思想：n考虑页面的使用情况外，还须再增加一个因素，即置换代价。n选择页面换出时，既要是未使用过的页面，又要是未被修改过的页面。把同时满足这两个条件的页面作为首选淘汰的页面。n由访问位A和修改位M可以组合成四种类型的页面： 1 1类类(A=0(A=0，M=0)M=0)：表表示示该该页页最最近近既既未未被被访访问问，又又未未被被修修改，是最佳淘汰页。改，是最佳淘汰页。2 2类类(A=0(A=0，M=1)M=1)：表表示示该该页页最最近近未未被被访访问问
20、，但但已已被被修修改改，并不是很好的淘汰页。并不是很好的淘汰页。3 3类类(A=1(A=1，M=0)M=0)：表表示示该该页页最最近近已已被被访访问问，但但未未被被修修改改，该页有可能再被访问。该页有可能再被访问。4 4类类(A=1(A=1，M=1)M=1)：表示该页最近已被访问且被修改，该表示该页最近已被访问且被修改，该页可能再被访问。页可能再被访问。 8/2/202441计算机操作系统- 第7章页面置换算法-改进型Clockn实施步骤：第一步：第一步：从从指指针针所所指指示示的的当当前前位位置置开开始始，扫扫描描循循环环队队列列，寻寻找找A=0A=0且且M=0M=0的的第第一一类类页页面面
21、，将将所所遇遇到到的的第第一一个个页页面面作作为为所所选选中中的的淘淘汰页。在第一次扫描期间不改变访问位汰页。在第一次扫描期间不改变访问位A A。 第二步：第二步：如如果果第第一一步步失失败败，即即查查找找一一周周后后未未遇遇到到第第一一类类页页面面，则则开开始始第第二二轮轮扫扫描描，寻寻找找A=0A=0且且M=1M=1的的第第二二类类页页面面，将将所所遇遇到到的的第第一一个个这这类类页页面面作作为为淘淘汰汰页页。在在第第二二轮轮扫扫描描期期间间，将将所所有有扫扫描描过过的页面的访问位都置的页面的访问位都置0 0。第三步：第三步：如如果果第第二二步步也也失失败败，亦亦即即未未找找到到第第二二类
22、类页页面面，则则将将指指针针返返回回到到开开始始的的位位置置，并并将将所所有有的的访访问问位位复复0 0。然然后后重重复复第第一一步步，如如果果仍仍失失败败，必必要要时时再再重重复复第第二二步步，此此时时就就一一定定能能找找到到被被淘淘汰的页。汰的页。评价：评价：该该算算法法与与简简单单ClockClock算算法法比比较较，可可减减少少磁磁盘盘的的I/OI/O操操作作次次数数。但但为为了了找找到到一一个个可可置置换换的的页页，可可能能须须经经过过几几轮轮扫扫描描。换换言言之之，实现该算法本身的开销将有所增加。实现该算法本身的开销将有所增加。 8/2/202442计算机操作系统- 第7章页面置换
23、算法-LFU（最少使用）n思想：n为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率。n选择在最近时期使用最少的页面作为淘汰页。8/2/202443计算机操作系统- 第7章页面置换算法-页面缓冲n引入n其他算法需要硬件支持，例如：LRU、Clock等；n置换一个已修改的页比置换未修改页的开销要大。n思想：n采用了可变分配和局部置换方式，置换算法为FIFO。n将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入已修改页面的链表中。n评价：n可改善分页系统的性能，又可采用一种较简单的置换策略8/2/202444计算机操作系统- 第7章本章
24、目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n7.3 页面置换算法 n7.4 页面调度性能n页面调度对系统性能的影响分析 n工作集模型 n7.5 请求分段存储管理方式 n7.6 Windows 2000/XP系统存储器管理实例 8/2/202445计算机操作系统- 第7章n影响缺页次数的因素n分配给进程的物理块数n页本身的大小n程序的编制方法n页淘汰算法n颠簸/抖动n定义n原因讨论8/2/202446计算机操作系统- 第7章n影响缺页次数的因素n分配给进程的物理块数n页本身的大小n程序的编制方法n页淘汰算法n颠簸/抖动n定义n原因讨论在虚存中，页面在内存与外存在虚存中，页
25、面在内存与外存之间频繁调度，以至于调度页之间频繁调度，以至于调度页面所需时间比进程实际运行的面所需时间比进程实际运行的时间还多，此时系统效率急剧时间还多，此时系统效率急剧下降，甚至导致系统崩溃。这下降，甚至导致系统崩溃。这种现象称为种现象称为颠簸或抖动颠簸或抖动 页面淘汰算法不合理页面淘汰算法不合理 分配给进程的物理页面数太少分配给进程的物理页面数太少8/2/202447计算机操作系统- 第7章学习与问题：页面调度中哪些因素会对系统性页面调度中哪些因素会对系统性能产生影响？能产生影响？试分析缺页率对系统性能的影响试分析缺页率对系统性能的影响试分析页面大小对系统性能的影响试分析页面大小对系统性能
26、的影响6 65 54 43 3试分析对换空间对系统性能的影响试分析对换空间对系统性能的影响工作集模型的目的与原理工作集模型的目的与原理2 28/2/202448计算机操作系统- 第7章本章目录n7.1 虚拟存储器的基本概念 n7.2 请求分页虚拟存储管理n7.3 页面置换算法 n7.4 页面调度性能n7.5 请求分段存储管理方式 n请求分段的实现n段页式虚拟存储器管理的实现 n7.6 Windows 2000/XP系统存储器管理实例 8/2/202449计算机操作系统- 第7章请求分段中的硬件支持n段表机制n缺段中断机构n地址变换机构8/2/202450计算机操作系统- 第7章请求分段中的硬件
27、支持n段表机制段名 段长段的基址存取方式访问字段A修改位M存在位P增补位外存始址存取方式： 用于标识本分段的存取属性是只执行、只读，还是允许读/写访问字段A： 用于记录本段在一段时间内被访问的次数，或记录本段最近已有多长时间未被访问，供选择换出分段时参考。修改位M： 表示该段在调入内存后是否被修改过，供置换分段时参考。存在位P： 指示本段是否已调入内存，供程序访问时参考。增补位： 这是请求分段式管理中所特有的字段，用于表示本段在运行过程中是否做过动态增长。外存始址： 指示本段在外存中的起始地址，即起始盘块号。8/2/202451计算机操作系统- 第7章请求分段中的硬件支持n缺段中断机构n与缺页
28、中断机构类似n但由于分段是信息的逻辑单位，因而不可能出现一条指令被分割在两个分段中和一组信息被分割在两个分段中的情况。n同时由于段不是定长的，这使对缺段中断的处理要比对缺页中断的处理复杂。 8/2/202452计算机操作系统- 第7章请求分段中的硬件支持8/2/202453计算机操作系统- 第7章请求分段中的硬件支持n地址变换机构8/2/202454计算机操作系统- 第7章段的共享与保护n共享段表n共享进程计数Countn存取控制字段n段号8/2/202455计算机操作系统- 第7章段的共享与保护n共享段的分配与回收n分段保护：n越界检查n存取控制检查n环保护机构1.1.一个程序可以访问驻留在
29、相同一个程序可以访问驻留在相同环或较低特权环中的数据。环或较低特权环中的数据。2.2.一个程序可以调用驻留在相同一个程序可以调用驻留在相同环或较高特权环中的服务。环或较高特权环中的服务。8/2/202456计算机操作系统- 第7章段的共享与保护8/2/202457计算机操作系统- 第7章例题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
30、128 Ai,j:=0;8/2/202458计算机操作系统- 第7章例题1：答案程序编制方法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;128128128128128128参考7.4.1中“4.编制程序对缺页率的影响”8/2/202459计算机操作系统- 第7章例题2n某程序在内存中分配3块内存，初始为空，访问页走向如下，用FIFO和LRU算法分别计算缺页次数。 2，3，2，1，5，2，4，5，3，2，5，28/2/202460计算机操作系统- 第7章例题2：
31、答案-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 x x x x x x x xn 共缺页中断9次8/2/202461计算机操作系统- 第7章例题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次8/2/2
32、02462计算机操作系统- 第7章例题3n在分页存储管理系统中，有一作业大小为4页，页长为2K，页表如下，试借助地址变换图（即要求画出地址变换图）求出逻辑地址4635所对应的物理地址。 页号块号051327368/2/202463计算机操作系统- 第7章例题3：答案31637250块号页号01000011011000100100001101100111页表首址表首址+0 010物理地址为：物理地址为：14875148758/2/202464计算机操作系统- 第7章作业n练习习题1、2、3（见后）n作业通过发送电子邮件附件形式提交到助教老师邮箱：n赵 静 n作业文件名命名要求：nOS_学号_姓名
33、_n.doc （n为当章节序号）n如一个合法文件名：nOS_95002_张三_7.doc8/2/202465计算机操作系统- 第7章习题1n某系统采用请求分页管理内存, 采用LRU页面置换算法. 作业的页面走向为： 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，试分析运行时的缺页率。8/2/202466计算机操作系统- 第7章习题2n如图所示，现有作业A须申请40K内存，写出选用以下各分配策略时，作业A的首地址和末地址，图中阴影为占用区。A. 最先适应法 B. 最佳适应法C. 最差适应法D. 单一连续分配8/2/202467计算机操作系统- 第7章习题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 页面替换算法 , 各将产生多少次缺页中断 ? 8/2/202468计算机操作系统- 第7章Any Question?Thank you !8/2/202469计算机操作系统- 第7章
