操作系统课件(3.4 虚拟存储管理机制)

1、徐小龙/WindowsLinuxMac OSOpenStackAndroidLinux虚拟存储管理机制本讲内容1. 程序访问局部性原理2. 虚拟存储器基本原理3. 分页式虚拟存储管理4. 典型的页面置换算法5. 分段式虚拟存储管理程序访问局部性原理基本思想基本思想1P.Denning研究了程序执行时的局部性原理一段时间内程序的执行呈现出高度局部性程序访问局部性原理两个局部性两个局部性 2某条指令被执行或某个数据结构被访问，则近期该指令可能再次执行，该数据结构可能再次被访问若某个存储单元被访问，则其附近的存储单元也可能被访问，一段时间内访问可能集中在一定范围内虚拟存储管理机制本讲内容1. 程序访

2、问局部性原理2. 虚拟存储器基本原理3. 分页式虚拟存储管理4. 典型的页面置换算法5. 分段式虚拟存储管理虚拟存储空间虚拟存储空间1虚拟存储器基本原理虚拟存储器是由操作系统提供的假想存储器，它不是实际内存，而是系统对物理内存的逻辑扩充。程序、数据、堆栈可以超过内存的大小，系统把当前使用的部分保留在内存，而把其它部分保存在辅存上，需要时在内存和辅存之间动态交换虚拟存储空间受限于系统地址结构、内存大小及可用的辅存容量虚拟存储系统虚拟存储系统2虚拟存储器基本原理虚拟地址空间处理器虚地址存储管理部件实地址主存辅存物理地址空间虚拟存储管理机制本讲内容1. 程序访问局部性原理2. 虚拟存储器基本原理3.

3、 分页式虚拟存储管理4. 典型的页面置换算法5. 分段式虚拟存储管理分页式虚拟存储管理基本原理基本原理1进程运行前，不装入全部页面，而是装入一个或数个页面根据进程运行的需要，动态装入其它页面内存空间已满，又需要装入新页面时，则淘汰内存部分页面，装入新的页面分页式虚拟存储管理关键问题关键问题2系统如何获知进程当前所需页面不在内存中发现缺页时，如何把所缺页面调入内存需要淘汰页面时，根据什么策略选择淘汰页面分页式虚拟存储管理页表扩充页表扩充3页号和页框号其作用与分页存储管理相同中断位指示页面是否在内存中，若不在内存，则产生缺页中断访问位记录该页是否被访问或者访问次数修改位指示页面在调入内存后是否被修

4、改过辅存地址指出该页在辅存上的地址虚拟存储管理机制本讲内容1. 程序访问局部性原理2. 虚拟存储器基本原理3. 分页式虚拟存储管理4. 典型的页面置换算法5. 分段式虚拟存储管理典型的页面置换算法性能指标性能指标1进程P在运行中成功的内存访问次数为S，不成功的访问次数为F，则缺页中断率为：R=F/(S+F)页面置换算法分配进程页框数页框本身大小程序的编制方法典型的页面置换算法理想理想页面置换算法页面置换算法2调入新的一页面而必须淘汰一个旧页时，淘汰页是以后不再访问或最长时间以后再访问的页面可作为衡量各种实用页面置换算法的标准典型的页面置换算法理想理想页面置换算法页面置换算法2系统为进程P在内存

5、中分配三个页框页面访问序列为4，3，2，1，4，3，5，4，3，2，1，5 OPT 4 3 2 1 4 3 5 4 3 2 1 5页框1 4 2页框2 3 1页框3 2 1 5 x x x x x x x 缺页7次典型的页面置换算法FIFO页面置换算法页面置换算法3选择内存中驻留时间最长的页面并淘汰之部分程序总体按线性顺序来访问物理空间优点: 直观，实现简单缺点: 与进程实际运行的规律不相适应，性能较差，可能出现分配页框数增加、缺页次数反而增加的异常现象典型的页面置换算法FIFO页面置换算法页面置换算法3系统为进程P在内存中分配三个页框页面访问序列为4，3，2，1，4，3，5，4，3，2，1，

6、5 FIFO 4 3 2 1 4 3 5 4 3 2 1 页框1 4 1 5页框2 3 4 2 页框3 2 3 1 x x x x x x x x x 缺页中断9次典型的页面置换算法最近最少用页面置换算法最近最少用页面置换算法4淘汰的页面是在最近较久未被访问或访问次数最少的页面基于程序局部性原理，刚被访问过的页面，马上再被访问的概率将会较高典型的页面置换算法最近最少用页面置换算法最近最少用页面置换算法4设置一个队列，存放当前在主存中的页号页面访问后，需要从队列中把该页调整到队列尾队列尾总指向最近访问的页，队列头就是最近最少用的页面缺页中断时，总淘汰队列头所指示的页面典型的页面置换算法最近最少用

7、页面置换算法最近最少用页面置换算法4系统为进程P在内存中分配三个页框页面访问序列为4，3，2，1，4，3，5，4，3，2，1，5 LRU 4 3 2 1 4 3 5 4 3 2 1 5页框1 4 1 5 2页框2 3 4 1 页框3 2 3 5 x x x x x x x x x x缺页中断10次典型的页面置换算法时钟页面时钟页面置换算法置换算法5一个页面首次装入主存，“访问位”置1主存中的任何页面被访问时，“访问位”置1Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use

8、=1Page33Use=1Page222Use=0下一个帧指针n012345678第1页框典型的页面置换算法时钟页面时钟页面置换算法置换算法5淘汰页面时，从指针当前指向的页面开始扫描循环队列遇到的“访问位”是1的页面的“访问位”清0，跳过这个页面把所遇到的“访问位”是0的页面置换掉，指针推进一步Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一个帧指针n012345678第1页框典型的页面置换算法时钟页面时钟页面置换算法置换算法5如果遇到的所有页面的“访问位”为1，指针就会绕整个循环队列一圈把 碰 到 的 所 有 页 面 的“访问位”清0指针回到起始位置，并淘汰掉这一页，指针推进一步Page9 use=1Page19Use=1Page1Use=0Page45Use=1Page191Use=1Page556Use=0Page13Use=0Page67Use=1Page33Use=1Page222Use=0下一个帧指针n012345678第1页框虚拟存储管理机制本讲内容1. 程序访问局部性原理2. 虚拟存储器基本原理3. 分页式虚拟存储管理4. 典型的页