计算机操作系统课件：第5章存储器管理03-虚拟存储器

1、第五章 存储管理(三)- 虚拟存储器知识回顾与展开在上一节课中我们主要介绍了：1 分页式存储管理方式2 分段式存储管理方式3 段页式存储管理方式以上方法的共同缺点：都要求将一个作业全部装入内存后方能运行。解决方法：虚拟存储技术 1 局部性原理 2 虚拟存储器的基本原理 3 请求分页系统 4 页面调度策略本节课的主要内容局部性原理： 指在一较短的时间内，程序的执行仅局限于某个部分；程序所访问的存储空间也局限于某个特定的区域。1.局部性原理1.局部性原理可表现为两方面 时间局限性： 一条指令的一次执行和下次执行，一个数据的 一次访问和下次访问都集中在一个较短时期内。如循环、子程序、累计变量等。 空

2、间局限性： 若某一存储单元被访问，那么与该存储单元相邻的单元可能也会很快被访问。基于局部性原理，在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。虚拟存储器：是指仅把程序的一部分装入内存便可运行程序的存储器系统，该系统具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。其容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度，而成本接近于外存。2. 虚拟存储器的基本原理虚拟存储技术实现思想： 在程序执行过程中，如果需执行的指令或访 问的数据尚未在内存（称为缺页或缺段）， 则程序利用操作系统所提供的请求调页（段） 功

3、能，将他们调入内存，然后继续执行程序。 如果此时内存已满，须利用操作系统的页 （段）的置换功能，将内存中暂时不用的页或 段调出保存在外存上，从而腾出空间存放将要 装入的程序以及将要调入的页或段。目的：提高内存利用率。虚拟存储器的特征多次性 指一个程序被分成多次调入内存运行。多次性是虚拟存储器最重要的特征，任何其它的存储管理方式都不具有这一特征。因此，我们也可以认为虚拟存储器是具有多次性特征的存储器系统。 对换性 指允许在程序的运行过程中进行换进、换出，换进和换出能有效地提高内存利用率。 虚拟性 指能够从逻辑上扩充内存容量，使用户所看到的内存容量远大于实际内存容量。这是虚拟存储器所表现出来的最重

4、要的特征，也是实现虚拟存储器的最重要的目标。 虚拟存储器的实现方法 分页虚拟存储管理方式 分段虚拟存储管理方式虚拟存储器的实现建立在离散分配的存储器管理方式的基础上。分页虚拟存储管理方式系统需要解决下面两个问题：当发现缺页时，如何把所缺页面调入内存。当内存中没有空闲的物理块时，为了要接受一个新页，需要把老的一页淘汰出去，根据什么策略选择欲淘汰的页面。注： 缺页中断：当CPU要访问进程的某个页面不在内存中，称这种现象为缺页中断。 虚拟存储器系统通常定义三种策略来规定如何（何时）以及怎样进行页面调度。 调页策略 内存分配及置换策略 页面置换算法页面调度策略 虚拟存储器的调入策略决定采用什么样的方式

5、将所缺页面由外存调入到内存之中。两种常用调页策略：1.页面调入策略 请求调页 预调页1.请求调页 只调入发生缺页时所需的页面。2.预调页 发生缺页时，一次调入该页及相邻的几页。 如调入页以后很少被访问，造成浪费。1.页面调入策略 如果缺页中断发生时内存已满，“置换策略”用于确定必须从内存中移出哪个虚页面，以便为新的页面腾出空位。 在请求分页系统中，可采取两种内存分配策略，即:固定分配和可变分配策略。 在进行置换时，也可采取两种策略，即: 全局置换和局部置换策略。2.内存分配及置换策略 1) 固定分配局部置换 (Fixed Allocation, Local Replacement) 2) 可变

6、分配全局置换 (Variable Allocation, Global Replacement) 3) 可变分配局部置换 (Variable Allocation, Local Replacemen）2.内存分配及置换策略 1) 固定分配局部置换 为每一进程分配固定物理块数的内存空间， 在整个运行期间都不再改变。如进程发生缺页，只能从该进程在内存中的 自己的N个页面中选出一页换出，然后再调 入所缺页面。 2.内存分配及置换策略 2) 可变分配全局置换 先为系统中每个进程分配一定数量的 物理块，OS本身保持一个空闲物理块队列。 若进程发生缺页，则系统从空闲物理块队列中，取出一物理块分配给该进程，

7、直到空闲物理块用完时才会从内存中选中一页调出，该页可能为系统中任意一个进程的页。 2.内存分配及置换策略 3) 可变分配局部置换 为每个进程分配一定数目的物理块数。如进程发生缺页，从该进程的页面中 换出一页，不影响其他进程运行。如频繁发生缺页，系统再为该进程分配若干物理块，降低进程的缺页率。 2.内存分配及置换策略 ) 最佳算法 （ OPT，Optimal ）) 最近最久未使用算法 （ LRU，Least Recently Used ）) 先进先出算法（ FIFO ）) 简单时钟算法 （ Clock ）) 改进型Clock算法3.页面置换算法-页面淘汰算法 1).最佳置换算法(OPT)-向后看

8、 是由Belady于1966年提出的一种理论上的算法，不能被实现，做性能评价依据。 选择置换“未来不再使用的”或“在离当前最远位置上出现的”页面。采用最佳置换算法，通常可保证获得最低的缺页率。 3.页面置换算法 例：假定系统为某进程分配了三个物理块，一作业要依次访问如下页面：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。请采用OPT页面置换算法，求出在访问过程中发生缺页中断的次数及缺页率（缺页次数总访问次数 * 100% ）。1).最佳置换算法(OPT,Optimal)3.页面置换算法 （提示：进程运行时， 先将7，0，1三个页面装入内存。进程要访问页面2时，

9、将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7淘汰。）（新装入的页号放在表格中被淘汰页的位置，状态保持未列出。）3.页面置换算法 N=3页面访问的次序初始70120304230321201701NULL72777NULL4NULL3缺页次1).最佳算法(OPT)-向后看（新装入的页号放在表格中被淘汰页的位置）3.页面置换算法 缺页率为9/20*100%=45%2).先进先出算法 (FIFO) 选择置换装入最早的页面。可通过链表来表示各页的装入时间先后。性能较差。较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出。并且有Belady现象。3.页面置换算法 Bela

10、dy现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的内存物理块数增多，缺页率反而提高的异常现象。Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是矛盾的，即被置换的页面并不是进程不会访问的。2).先进先出算法 (FIFO) 3.页面置换算法 例1：假定系统为某进程分配了三个物理块,一个作业要依次访问如下页面：，0，。请采用FIFO页面置换算法，求出在访问过程中发生缺页中断的次数及缺页率。（缺页率缺页次数总访问次数 * 100%） 2).先进先出算法 (FIFO) 3.页面置换算法 Belady异常N=3页面访问的次序初始01230140

11、1234最新NULL2301444233NULL11230111422最早NULL000123000144缺页9次2).先进先出算法 (FIFO) 3.页面置换算法 缺页率为9/12*100%=75%N=4页面访问的次序初始012301401234最新NULL333401234NULL2222340123NULL11111234012最老NULL000000123401缺页10次Belady异常2).先进先出算法 (FIFO) 3.页面置换算法 缺页率为10/12*100%=83%3).最近最久未使用算法(LRU) 选择置换内存中最久未使用的页面。性能接近最佳算法。需记录页面使用时间的先后关系

12、，所以硬件开销比较大。以下硬件机构帮助实现：）特殊栈）为每一页面设置移位寄存器3.页面置换算法 栈：把被访问的页面移到栈顶，栈底的 页面就是最久未使用的页面。用栈保存当前使用页面时栈的变化情况 LRU置换算法的硬件支持 3.页面置换算法 2).最近最久未使用算法(LRU) 例：假定系统为某进程分配了三个物理块，一作业要依次访问如下页面：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1。请采用LRU页面置换算法，求出在访问过程中发生缺页中断的次数及缺页率（缺页次数总访问次数 * 100% ）。3.页面置换算法 N=3页面访问的次序初始7012030423032120

13、1701NULL120304230322070NULL0012030423032120170NULL77701223042203312017缺页次3).最近最久未使用算法(LRU)（注：新装入的页号放在表格中被淘汰页的位置）3.页面置换算法 缺页率为12/20*100%=60%练习题1在一个分页虚拟存储管理系统中，进程P共有5页。页面访问序列为：3，2，1，0，3，2，4，3，2，1，0，4时，试采用FIFO和LRU置换算法，计算当分配给该进程的物理块数分别为3和4时，求访问过程中发生的缺页中断次数和缺页率。练习题页面321032432104块11032444100块222103222411块3333210333244缺页缺页中断次数为9，缺页率为 9/12*100%= 75% 。分配给该进程的物理块数为3时：先进先出算法 (FIFO) 缺页中断次数为10，缺页率为10/12*100%= 83%。页面321032432104块1000432104块21111043210块322222104321块4333333210432缺页分配给该进程的物理块数为4时：练习题分配给该进程的物理块数为4时：先进先出算法 (FIFO) 练习题页面321032432104块11032432104块222103243210块33332