计算机操作系统（第二版）课件：虚拟存储系统

一.虚拟存储器的基本概念

虚拟存储系统局部性特征？什么是虚拟存储器？具有请求调入功能和置换功能，能够利用外存空间从逻辑上扩充内存容量的一种存储器系统。特征多次性置换性虚拟性与前面学习过的传统存储管理方式比较，虚拟存储器有哪些不同的特征呢？说说你对局部性特征的理解？第0页第1页第2页第0页第1页第2页第3页第4页第5页第6页二.请求分页存储管理方式4.6虚拟存储系统只装入部分页面1.扩充页表功能：页号物理块号状态位P访问字段A修改位M外存地址状态位P：用于指示该页是否已调入内存访问字段A：记录本页在一段时间内被访问的情况修改位M：该页在调入内存后是否被修改过外存地址：指示该页在外存上的地址0：不在内存1：在内存0：未被修改1：已被修改4.6虚拟存储系统二.请求分页存储管理方式哪个小组来分析下这些字段的含义？什么时候会检查这些字段的值？案例：Win2000中的页表项二.请求分页存储管理方式2.缺页中断处理:所要访问的页不在内存时，便引发一次缺页中断

启动要处理的指令给出虚地址

得到页号该页在主存?有空闲块?

缺页中断执行完该指令

准备执行下条指令选一页淘汰

从外存读入所需的页

调整存储分配表和页表

重新启动被中断的指令

调整存储分配表和页表要重写入?该页写入外存YNNY硬件实现软件实现YN二.请求分页存储管理方式普通中断的处理过程是怎样的？普通中断与缺页中断有什么不同呢?执行指令的过程中发生和处理的需要修改页表项哪些信息？分析缺页中断处理过程？本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、说明虚拟存储器的基本概念，分析与常规存储管理方式相比较的特点2、分析说明虚拟存储系统中，页表的字段设置及用途3、分析说明缺页中断处理过程前期知识回顾4.3页式存储管理方式思考题：某请求分页系统中，若其指令系统指令长16位，每个操作数的地址码长6位，操作码4位，每个操作数16位，则执行一条双操作数指令，则最多可能发生几次缺页中断？二.请求分页存储管理方式（1）固定分配局部置换（2）可变分配全局置换（3）可变分配局部置换3.内存分配与页面置换策略4.地址映射过程缺页中断处理需要修改页表哪些信息？其实这里要先访问快表哪个小组来分析地址映射过程？若某进程访问内存时产生缺页，则下列选项中，操作系统可能执行的操作有（）置换页面装入缺页处理越界错误分配内存ABCD提交多选题10分5.页面置换算法选择淘汰页面的策略缺页中断率假定程序p共有n页，系统分配m块，有1≤m≤n；

若程序p在运行中：成功的访问次数为s，不成功的访问次数为f；缺页中断率：f′=f/(s+f)f′=f(r，m，p)；

r：置换算法；m：系统分配的块数；p：程序特征二.请求分页存储管理方式5.页面置换算法（1）先进先出页面置换算法FIFO（2）最佳置换算法OPT（3）最近最久未使用置换算法LRU（4）最近最少使用置换算法LFU（5）时钟置换算法CLOCK（讲授）（6）改进的CLOCK算法（7）页缓冲思想二.请求分页存储管理方式基本概念、实现思路、性能优缺点总是先淘汰那些最先进入系统，即驻留主存时间最长的页。例1：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，刚开始没有一个页面装入内存，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。用FIFO计算缺页次数和缺页率。缺页次数：9，缺页率：(9/12)*100%=75%特点：实现简单与进程实际的运行不相适应5.页面置换算法二.请求分页存储管理方式基本概念？如何实现？（1）先进先出页面置换算法（FIFO）性能优缺点？例2：在一个请求分页系统中，假如一个作业的页面走向为1，2，3，4，1，2，5，1，2，3，4，5,当分给该作业的物理块数M分别为3和4时，请用FIFO计算缺页次数和缺页率，并比较所得的结果。5.页面置换算法（1）先进先出页面置换算法（FIFO）物理块数为3：缺页次数为9物理块数为4：缺页次数为10这种异常现象称为Belady现象。结果分别是多少？5.页面置换算法（2）最佳置换算法（OPT）选择以后永远不会被访问的页面或将来最长时间内不会被访问的页面淘汰出去。基本概念？如何实现？在一个请求分页系统中，假定系统分给一个作业的物理块数为3，刚开始没有一个页面装入内存，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。使用OPT置换算法，则缺页次数是（）。5678ABCD提交单选题10分缺页中断32532532+532534534+534532+532+13232+32+21252354251232页面走向OPT算法：缺页次数：6，缺页率：6/12特点：理论上，性能最佳；实际上，无法实现；通常用该算法来评价其他算法的优劣。（3）最近最久未使用置换算法（LRU）选择在最近一段时间内最长时间未被使用（访问）的页面淘汰出去。5.页面置换算法缺页中断32253253+253+453452+452152+152+13232+32+21252354251232页面走向缺页次数：7缺页率：7/12特点：性能较好，但精确实现较困难（3）最近最久未使用置换算法（LRU）5.页面置换算法LRU算法的实现用引用位考察页面的使用情况；当访问页面时，将引用位置1，并记时；当要淘汰一页时，选择时间最长的一页淘汰。硬件方法：采用移位寄存器软件方法：采用页号栈极偶尔的情况下，性能会很差假设一个进程顺序访问N+1个页面后再循环地访问这些页面，若进程分配到的内存块数为N块。如：顺序访问1,2,3,4,5,6,7，再循环访问它们，进程分配到的内存块为6个块，缺页情况如何？如果让你来设计，你会怎么实现以便快速找到淘汰页面？使用页号栈实现LRU算法（3）最近最久未使用置换算法（LRU）5.页面置换算法缺页中断252354251232页面走向23223123512251425542354235523253+++++++缺页次数：7，缺页率：7/12你能使用链表来实现这个特殊的栈结构吗？本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、分析说明最佳页面置换算法的基本概念、性能特点？2、分析说明LRU页面置换算法的基本概念、性能特点？如何实现LRU算法？前期知识回顾4.6虚拟存储系统选择过去一段时间里访问次数最少的页面进行淘汰。

思考：如何实现该算法？（5）最近最少使用置换算法（LFU）5.页面置换算法

①简单的clock置换算法：每页设置一位访问位。当某页被访问了，则访问位置“1”。内存中的所有页链接成一个循环队列；再设置一个起始查询指针置换算法：循环检查各页面的使用情况:若访问位为“0”，选择该页淘汰；若访问位为“1”，复位访问位为“0”；查询指针前进一步。又称为“最近未使用”置换算法（NRU）（4）Clock置换算法（引导讲授）5.页面置换算法CLOCK算法流程描述：

入口检查查询指针指向的页面移动指针指向下一个页面

访问位为0?选择该页淘汰，记录该页的页号、块号移动查询指针指向下一个页面返回置访问位为0YN很关键简单的clock置换算法：1210访问位页号块号1311101216131514115150121603041730202181040000000案例：Linux的双表针clock置换算法12101311101216131514115150121603040731202181040000例：在一个请求分页系统中，假定系统分给一个作业的物理块数为3，刚开始没有一个页面装入内存，并且此作业的页面走向为2，3，2，1，5，2，4，5，3，2，5，2。采用Clock置换算法，则缺页次数是（）。6789ABCD提交单选题10分②改进型Clock置换算法：考虑置换代价访问位A、修改位M，共同表示一个页面的状态页面的四种状态：

00：(A=0;M=0)最近未被访问也未被修改

01：(A=0;M=1)最近未被访问但已被修改

10：(A=1;M=0)最近已被访问但未被修改

11：(A=1;M=1)最近已被访问且被修改（4）Clock置换算法5.页面置换算法当用A、M两位来表示页面状态时，内存中的页面可以分为几种状态的页面？②改进型Clock置换算法：三轮扫描：第一轮：查找A=0,M=0页面，未找到，下一步；第二轮：查找A=0,M=1页面，A位复位为“0”，未找到，下一步；第三轮：把所有A置为“0”，重复第一轮，必要时再重复第二轮。（4）Clock置换算法5.页面置换算法哪个小组来说说如何查找淘汰页面？5.页面置换算法可变分配局部置换策略，FIFO页面置换算法给淘汰页面再一次驻留内存的机会空闲页面链表：已修改页面链表：空闲内存块空白内存块或未修改淘汰页所在内存块已修改淘汰页所在内存块淘汰页未被修改已被修改（6）页面缓冲置换算法本次课前学习中不理解的问题、希望老师重点讲解的内容有哪些？用弹幕给出1、分析说明最佳页面置换算法的基本概念、性能特点？2、分析说明LRU页面置换算法的基本概念、性能特点？如何实现LRU算法？3、分析说明clock页面置换算法查找淘汰页面的过程？4、分析说明页面缓冲置换算法的基本思想？前期知识回顾4.6虚拟存储系统案例：Windows2000空闲块链表（1）零初始化链表；（2）空闲链表；（3）后备链表：未修改淘汰页；（4）修改链表：已修改淘汰页修改页面写回器零页线程

在某请求分页管理系统中，一个作业共5页，作业执行时依次访问如下页面：1，4，3，1，2，5，1，4，2，1，4，5，若分配给该作业的主存块数为4，刚开始没有一个页面在内存，若分别采用LRU和Clock页面置换算法，则缺页中断次数分别是（）。6，76，87，77，8ABCD提交单选题10分（1）缺页率对有效访问时间的影响：设缺页率为P，则有效访问时间为：=(1-P)*内存访问时间+P*缺页中断处理时间缺页中断处理时间保存和恢复现场信息所需时间读入缺页所需时间（可能置换）更新页表和快表所需时间重新执行访存指令时间。6.请求分页存储管理的性能分析二.请求分页存储管理方式如果不缺页，那么访问一次内存包含哪些时间？如果缺页，访问时间又包含哪些？例：（2009年统考真题）某请求分页管理系统中，页面大小为4KB，一次内存的访问时间为100纳秒（ns），一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为100毫秒（已含更新TLB和页表的时间），进程的驻留集大小固定为2个页框，采用FIFO法置换页面。假设1）TLB初始为空；2）地址转换时，先访问TLB，若TLB未命中时再访问页表（忽略TLB更新时间）；3）有效位为0表示页面不在内存中。请问：（1）该系统中，一次访存的时间下限和上限各是多少？给出计算过程。（2）假设快表命中时一定不缺页，若快表命中率为90%，缺页率为10%，则一次内存访问的有效时间是多少？6.请求分页存储管理的性能分析（1）缺页率对有效访问时间的影响：大家计算一下，用弹幕给出答案解答：

（1）访存的下限就是访存的最短时间=一次快表（命中）+一次内存访问（数据）=10ns+100ns=110ns访存的上限就是访存的最长时间=一次快表（不命中）+一次访存（页表）+一次缺页+一次快表（命中）+一次访存（数据）=10ns+100ns+100ms+10ns+100ns=100000.22us（2）快表未命中，但不缺页时的内存访问是：210ns有效访问时间：=90%*110ns+10%（210ns*90%+100000.22us*10%）6.请求分页存储管理的性能分析（1）缺页率对有效访问时间的影响：（2）抖动（颠簸）的基本概念：在主存和辅存之间频繁的页面置换现像

原因：全局置换策略；置换算法选择不当抖动的预防：①采取局部置换策略；②引入工作集概念：进程在某段时间段Δ里实际要访问的页面集合Δ称为工作集“窗口尺寸”（WindowsSize）。③挂起若干进程，降低多道程序度。6.请求分页存储管理的性能分析二.请求分页存储管理方式哪个小组来分析下有哪些预防办法？32.针对某虚拟存储系统，进行了CPU利用率和页面交换磁盘的利用率的检测，发现有四种情况：（1）CPU利用率低，磁盘利用率高；（2）CPU利用率高，磁盘利用率低；（3）CPU利用率低，磁盘利用率低；（4）CPU利用率高，磁盘利用率高。

请你分析一下，分析上述4种不同情况，回答：

（1）系统可能发生了什么事情？

（2）当CPU利用率低的时候，如果增加进程并发数能提高CPU利用率吗？

（3）虚拟存储器是否起到作用了？课堂练习：教材P209：32题哪个小组来分析一下？小组讨论：8分钟在虚拟分页系统中，对系统性能影响较大的因素主要有两点：页面调入策略和页面置换算法。页面调入策略主要考虑两方面的事情：一是什么时候调入页面，二是从哪里调入页面。请你设计一种页面调入策略，