3.4 虚拟存储管理机制
- 程序访问局部性原理
- 虚拟存储器基本原理
- 分页式虚拟存储管理
- 经典的页面置换算法
- 分段式虚拟存储管理
一、程序访问局部性原理
一段时间内程序的执行呈现高度的局部性
主要包括两个方面:
时间局部性:
某条指令被执行或者某个数据结构被访问,则近期该指令可能再次被执行,该数据结构可能再次被访问;(概率很高)
空间局部性:
若某个存储单元被访问,则其附近的存储单元也可能被访问,一段时间内访问可能集中在一定的范围之内;
二、虚拟存储器基本原理
虚拟存储空间:
虚拟存储器是由操作系统提供的遐想存储器,它不是实际的内存,而是系统对于物理内存的逻辑扩充;
程序、数据、堆栈可以超过内存的大小,系统把当前使用的部分保留在内存,而把其他部分保存在辅存上,需要时在内存和辅存之间动态交换;
虚拟存储空间受限于系统地址结构、内存大小以及可用的辅存容量;
虚拟存储系统:
CPU 拿到的是虚拟地址空间的虚拟逻辑地址(虚地址),虚地址会被交给存储管理部件(MMU)转换成实地址。
实地址由主存和辅存联合组成。
三、分页式虚拟存储管理
(1)基本原理:
进程在运行前,不需要装入全部页面,而是装入一个或者多个页面。
(根据程序局部性原理,当前用到得可能就是一个或者多个页面,没必要将进程所有的逻辑页面都装入内存)
如果要用到不在内存中的其他页面,只需要动态的装入其他页面即可;
如果内存空间已满,但又需要装入新的页面时,则要淘汰内存中的部分页面,装入新的页面;(页面的置换)
(2)关键问题:
系统如何获知进程当前需要的页面在不在内存中;
当发现缺页时,系统如何把所缺的页面调入内存;
需要淘汰页面时,根据什么策略选择淘汰页面;(不同的策略将会极大影响系统性能)
(3)页表扩充
分页式虚拟存储管理是由分页式存储管理演变而来的,在原来的基础上,比较重要的是对于原来页表的扩充;
原来的页表主要包括页号和页框的对应关系;
虚拟存储管理的页表增加了中断位、辅存地址、访问位、修改位等信息;
页号和页框号:作用同分页存储管理相同;
中断位: 指示页面是否在内存中,若不在内存,则产生缺页中断;
访问位: 记录该页在内存中是否被访问过,或者被访问的次数;
修改位: 指示出页面在被调入内存中是否被修改过;(如果该页面未来将被淘汰,是否要将内存中更改过的内容持久化到硬盘上)
辅存地址: 指出该页在辅存上的地址;
四、经典的页面置换算法
页面置换算法非常影响分页虚拟存储管理的性能,衡量算法优劣的一个重要的指标就是缺页中断率;
(1)性能指标
进程$P$在运行中成功的内存访问次数为$S$,不成功的访问次数为$F$,则缺页中断率为:$ R = F / (S + F) $
缺页中断率应该是越低越好,越低就表示该进程要访问的大部分页面都能够在内存中找到,这样在程序的执行过程中不需要过多的和辅存打交道。因为和内存相比,CPU对辅存的访问太慢了。
决定缺页中断率的因素有:
- 分配进程的页框数
- 页框本身的大小
- 程序的编制方法
- 页面置换算法
这里主要讨论页面置换算法对缺页中断率的影响;
(2)算法1:理想页面置换算法(最佳页面置换算法)
当内存已经内存已经放满,调入新的一个页面而必须淘汰一个旧页面时,淘汰的页面是以后不再访问或者最长时间以后再访问的页面;
例如:
当前进程P在内存中分配有三个页框;
页面访问的序列为:$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 | |||||||||
是否缺页 | √ | √ | √ | √ | × | × | √ | × | × | √ | √ | × |
一共缺页7次
该算法是最理想的算法,因为系统无法预测未来哪一个页面不再被访问或者最长时间以后再被访问,因此无法做到;
但是该算法可以作为衡量各种实用页面置换算法的标准;
(3)FIFO页面置换算法(先进先出)
当每次需要淘汰页面时,选择内存中驻留最长的页面。因为部分程序总体是按照线性的顺序来访问物理空间,先进的页面有较大概率以后不会再访问;
优点:直观、实现简单
缺点:与进程实际运行规律不相适应(程序中可能出现很多的跳转),可能会出现分配页框数增加,缺页次数反而增加的异常现象
还是以上述题目为例来演示FIFO算法:
OPT | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
页框1 | 4 | 1 | 5 | |||||||||
页框2 | 3 | 4 | 2 | |||||||||
页框3 | 2 | 3 | 1 | |||||||||
是否缺页 | √ | √ | √ | √ | √ | √ | √ | × | × | √ | √ | × |
共缺页9次。
这次的页面置换出现了一种情况,某一页面刚被淘汰出内存,随即又需要被调入内存,这种情况被称为颠簸现象;
(4)最近最少用页面置换算法
该算法淘汰的页面是在较久未被访问或者访问次数最少的页面。
因为基于程序局部性原理,刚被访问过的页面,马上被访问的概率较高。
算法实现:
-
设置一个队列,存放当前在主存中的页号
-
页面访问后,需要从队列中把该页调整到队列尾
-
队列尾总指向最近访问的页,队列头就是最近最少用的页面
-
缺页中断时,总淘汰队列头所指示的页面
还是以上述题目为例来演示该算法:
OPT | 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 | |||||||||
是否缺页 | √ | √ | √ | √ | √ | √ | √ | × | × | √ | √ | √ |
共缺页中断10次。
(5)时钟页面置换算法
时钟页面置换算法是最近最少用页面算法的一种实现方式。
步骤:
-
首先将所有的逻辑页面放入一个循环队列中
-
当一个页面首次装入主存,其“访问位”置为1;
-
主存中的任何页面被访问时,“访问位”置1;
-
淘汰页面时,从指针当前指向的页面开始扫描循环队列;
-
遇到的“访问位”是1的页面的“访问位”清0,跳过这个页面;
-
把所遇到的“访问位”是0的页面置换掉,指针推进一步;
-
如果遇到的所有页面的访问位”为1,指针就会绕整个循环队列一圈把碰到的所有页面的“访问位”清0;
-
指针回到起始位置,并淘汰掉这一页,指针推进一步;
五、分段式虚拟存储管理 (思想同分页虚拟存储类似)
分段式虚拟存储系统把所有分段的副本都存放在辅助存储器中;
进程被调度投入运行时,把当前需要的一段或几段装入主存;
在执行过程中,访问到不在主存的段时再动态装入;
厉害厉害
热乎~
嘿嘿(º﹃º )
加油啊学长!!!!!!!!!!!!!!!!!!!
加油加油