操作系统原理第7章虚拟存储器管理

操作系统原理OperatingSystemPrinciples四川大学计算机学院段磊[e-mail]2014第7章虚拟存储器管理虚拟存储器管理为解决内存扩充问题而提出，其实现思想是将外存作为内存的扩充，作业运行不需要将作业的全部信息放入内存。虚拟存储器的实现基础是内存的分页式或分段式管理，采用的是进程页面或分段在内存与外存之间对换2020/2/24《计算机操作系统》-第7章3/69本章目录7.1虚拟存储器的基本概念7.2请求分页虚拟存储管理7.3页面置换算法7.4页面调度性能7.5请求分段存储管理方式7.6Windows2000/XP系统存储器管理实例2020/2/24《计算机操作系统》-第7章4/69本章目录7.1虚拟存储器的基本概念虚拟存储器的概念虚拟存储器的特征7.2请求分页虚拟存储管理7.3页面置换算法7.4页面调度性能7.5请求分段存储管理方式7.6Windows2000/XP系统存储器管理实例2020/2/24《计算机操作系统》-第7章5/69虚拟存储器的引入常规存储管理的特征：一次性（指全部装入）驻留性（指驻留在内存不换出）局部性原理时间局部性：如循环执行空间局部性：如顺序执行。程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。过程调用将会使程序的执行轨迹变化，但在一段时间内都局限在一定过程的范围内运行。程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内2020/2/24《计算机操作系统》-第7章6/69虚拟存储器的引入常规存储管理的特征：一次性（指全部装入）驻留性（指驻留在内存不换出）局部性原理时间局部性：如循环执行空间局部性：如顺序执行。程序执行时，除了少部分的转移和过程调用指令外，在大多数情况下仍是顺序执行的。过程调用将会使程序的执行轨迹变化，但在一段时间内都局限在一定过程的范围内运行。程序中存在许多循环结构，这些虽然只由少数指令构成，但是它们将多次执行。程序中还包括许多对数据结构的处理，如对数组进行操作，它们往往都局限于很小的范围内。程序或数据访问的特点：顺序性局限性多次性独立性虚拟地址空间内存硬盘存储器管理地址映射调出调入物理地址空间2020/2/24《计算机操作系统》-第7章7/69应用程序部分装入内存访问部分已在内存？启动请求调页（段）功能程序继续执行是否内存已满？是否调入内存执行结束页（段）置换2020/2/24《计算机操作系统》-第7章8/69虚拟存储器具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。实质：以时间换空间，但时间牺牲不大。需要动态重定位虚拟存储器的引入2020/2/24《计算机操作系统》-第7章9/69请求分页系统以页为单位转换需硬件：（1）请求分页的页表机制（2）缺页中断（3）地址变换机构需实现请求分页机制的软件（置换软件等）虚拟存储器的实现方式2020/2/24《计算机操作系统》-第7章10/69请求分段系统以段为单位转换:（1）请求分段的段表结构（2）缺段中断（3）地址变换机构需实现请求分段机制的软件（置换软件等）虚拟存储器的实现方式2020/2/24《计算机操作系统》-第7章11/697.1.2虚拟存储器的特征离散性部分装入多次性局部装入，多次装入对换性虚拟性2020/2/24《计算机操作系统》-第7章12/69本章目录7.1虚拟存储器的基本概念7.2请求分页虚拟存储管理请求分页的硬件支持分页虚拟存储器管理实施中的策略问题7.3页面置换算法7.4页面调度性能7.5请求分段存储管理方式7.6Windows2000/XP系统存储器管理实例2020/2/24《计算机操作系统》-第7章13/697.2.1请求分页中的硬件支持页表机制缺页中断机构地址变换机构2020/2/24《计算机操作系统》-第7章14/69页表机制请求分页中的硬件支持页号物理块号状态位P访问字段A修改位M外存地址状态位P：用于指示该页是否已调入内存，供程序访问时参考。访问字段A：用于记录本页在一段时间内被访问的次数，或记录本页最近已有多长时间未被访问，供选择换出页面时参考。修改位M：表示该页在调入内存后是否被修改过，供置换页面时参考。外存地址：用于指出该页在外存上的地址，通常是物理块号，供调入该页时参考。2020/2/24《计算机操作系统》-第7章15/69缺页中断机构当所要访问的页面不在内存时，产生缺页中断，请求OS将所缺之页调入内存。与其他中断的区别可在指令执行期间产生一条指令在执行期间，可能产生多次缺页中断。（如图7.3）请求分页中的硬件支持2020/2/24《计算机操作系统》-第7章16/69缺页中断处理保留CPU现场从外存中找到缺页内存满否？选择一页换出该页被修改否？将该页写回外存OS命令CPU从外存读缺页启动I/O硬件将一页从外存换入内存修改页表否是是否页表项在快表中？CPU检索快表访问页表否页在内存？修改访问位和修改位形成物理地址地址变换结束否页号＞页表长度?开始程序请求访问一页产生缺页中断请求调页修改快表是越界中断是是地址变换过程增加中断处理2020/2/24《计算机操作系统》-第7章17/697.2.2分页虚拟存储器管理实施中的策略问题最小物理块数保证进程正常运行所需的最小物理块数不同的作业要求不同如：允许间接寻址：则至少要求3个物理块。MovA,[B]2020/2/24《计算机操作系统》-第7章18/69内存分配策略和分配算法固定与可变：指为进程分配的物理块数是固定的还是变化的局部与全局：指因内存不够需要置换时，换出的页面是该进程的页面，还是内存中所有进程的某一页面。2020/2/24《计算机操作系统》-第7章19/69页面分配和置换策略固定分配局部置换缺点：难以确定固定分配的页数.(少：置换率高多：浪费)可变分配全局置换可变分配局部置换根据进程的缺页率进行页面数调整，进程之间相互不会影响。内存分配策略和分配算法2020/2/24《计算机操作系统》-第7章20/69分配算法平均分配算法按比例分配算法考虑优先权的分配算法内存分配策略和分配算法mssbiiniiss12020/2/24《计算机操作系统》-第7章21/69调页策略1.调入时机：预调：（根据空间局部性）目前：成功率≤50％请求调：较费系统开销各有优劣2．从何处调页：对换区：修改过的页被换出时入对换区，快文件区：稍慢对共享页，应判断其是否在内存区。3.页面调入过程2020/2/24《计算机操作系统》-第7章22/69发生缺页中断保护现场分析缺页原因中中中中中中中中中中中中中中查找页表获得该页的物理块内存是否可容纳新页将新页调入内存是否调用页面置换算法选择被淘汰页该页是否修改是否将新页调入内存该页写回磁盘修改页表将页表写入快表地址变换，形成物理地址访问内存页面调入过程2020/2/24《计算机操作系统》-第7章23/69本章目录7.1虚拟存储器的基本概念7.2请求分页虚拟存储管理7.3页面置换算法先进先出（FIFO）页面置换算法最佳（optimal）页面置换算法最近最久未使用（LRU）页面置换算法时钟（clock）置换算法7.4页面调度性能7.5请求分段存储管理方式7.6Windows2000/XP系统存储器管理实例2020/2/24《计算机操作系统》-第7章24/69理想淘汰算法—最佳页面算法（OPT）淘汰以后不再需要的或最远的将来才会用到的页面先进先出页面淘汰算法（FIFO）淘汰在内存中驻留时间最长的页并淘汰最近最久未使用页面淘汰算法（LRU）淘汰最后一次访问时间距离当前时间最长的一页即淘汰没有使用的时间最长的页Clock置换算法－LRU近似算法最不经常使用（LFU）淘汰访问次数最少的页面主要置换算法2020/2/24《计算机操作系统》-第7章25/69举例在一个请求分页系统中，假设一个作业的页面走向为：432143543215当分配给该作业的物理块数M分别是3和4时，请计算不同页面置换算法下，访问过程中所发生的缺页次数和缺页率。2020/2/24《计算机操作系统》-第7章26/69思想：选择的被淘汰页面，将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。效果：通常可保证获得最低的缺页率。评价：由于人们无法预知一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法无法实现可以利用该算法去评价其它算法页面置换算法-OPT2020/2/24《计算机操作系统》-第7章27/69举例采用OPT淘汰算法，当M＝3时512345341234P121110987654321时刻FM4++3+4+2+-34+1+-34+1-341-345+-34+534-53-452+-4+51+-4+5-14由表可以算出缺页中断次数F=7，而缺页率：7／12=58%。2020/2/24《计算机操作系统》-第7章28/69采用OPT淘汰算法，当M＝4时512345341234P121110987654321时刻FM4++3+4+2+34+1+-234+1-2341-2345+-234+5234-523-452-3451+-34+5-134由表可以算出缺页中断次数F=6，而缺页率：6／12=50%。举例2020/2/24《计算机操作系统》-第7章29/69思想：总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。效果：实现简单。评价：与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，该算法并不能保证这些页面不被淘汰。页面置换算法-FIFO2020/2/24《计算机操作系统》-第7章30/69举例如果采用FIFO替换算法，当M＝3时512345341234P121110987654321时刻FM4++3+4+2+34-+1+23-+4+12-+3+41-+5+34-+534-534-2+53-+1+25-+125-由表可以算出缺页中断次数F=9，而缺页率：9／12=75%。2020/2/24《计算机操作系统》-第7章31/69举例采用FIFO替换算法，当M＝4时512345341234P121110987654321时刻FM4++3+4+2+34+1+234-[phone]+123-+4+512-+3+451-+2+345-+1+234-+5+123-+由表可以算出缺页中断次数F=10，而缺页率：10／12=83%。2020/2/24《计算机操作系统》-第7章32/69思想：根据页面调入内存后的使用情况进行决策的。选择最近最久未使用的页面予以淘汰。效果：较好。评价：需要有较多的硬件支持（寄存器、栈）。页面置换算法-LRU2020/2/24《计算机操作系统》-第7章33/69举例当M＝3时，采用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=10／12=83％。2020/2/24《计算机操作系统》-第7章34/69举例当M＝4时，采用LRU替换算法：512345341234P121110987654321时刻FM4++3+4+2+34+1+234-[phone]+341-[phone]+345-+1+234-+5+123-+由表可以算出缺页中断次数F=8，而缺页率：8／12=67%。2020/2/24《计算机操作系统》-第7章35/69结论总结：通过以上缺页次数和缺页率的分析计算，可以看出：对于LRU、OP