接下来我们讨论
全局置换算法当中的缺页率算法
那缺页率算法呢
实际上它是依据缺页之间的间隔
来调整我哪些页面放到内存里头
哪些页面被置换
在具体说明缺页率算法之前
我们需要对缺页率
给出一个准确的定义
通常情况下我们理解的缺页率
是缺页的次数和访存次数之间的
一个比值 这个比值实际上
在我们缺页率算法里用的时候
它比较不好把握 那我们更多的
会用缺页平均时间间隔的倒数
这个来作为我们缺页率
也就是说两次缺页之间
它有个间隔 这个间隔可能长可能短
那我们在这取它的平均值
然后给倒数作为它缺页率
好 那缺页率受哪些因素的影响呢
影响缺页率的因素有这样一些
我用的置换算法
然后我给进程分配的物理页面数
这个页面的大小
以及与我在实现我程序的时候
我所用的方法
比如说像前边说的 我的局部性
跟我的实验方法有关系一样的
这几个因素里头
我们目前能控制的是置换算法
我们希望通过置换算法的选择
来影响这个缺页率
具体的做法是这样的
说我们的缺页率会随着分配给
进程的物理页面数的增加而降低
物理页面数越少 缺页率会越高
那我们的缺页率算法的思路
是什么样子呢
是说我通过调节常驻集的大小
这个调节过程当中呢
会使得缺页率有变化
我去观测它这个变化
让它的缺页率保持在一定的范围里头
那具体说起来怎么保持呢
如果说缺页率过高 那这时候呢
明显是我的分配给它的
物理页面数比较少
好 那在这我就增加它的物理页面数
使得这条线能够回到下边来
好 然后还有一种情况呢
是说我往里加 那不会越加越多吗
那缺页率会低
低到一定程度之后
我的并发度就会降低
然后我的CPU的利用效率也会下降
好 那这时候我会增加第二条
缺页率过低的时候 我减少常驻集
这时候呢把一些页面给置换出去
那这样的话我的缺页率
就会回到一个合理的范围里头
那这是我们在这里
缺页率置换算法它的基本思路
那它如何来实现呢 它是这样来做的
访存的时候我们去设置引用标志位
这和我们前边的
局部置换算法是一样的
然后不同的地方是在于
出现缺页的时候的处理
出现缺页的时候
我就计算上一次缺页的时间
和当前这个时间
也就是这一次缺页的时间
它们之间的间隔
根据这个间隔的大小的不同
我来做不同的处理
这个大小的不同实际上就是对应着
我们刚才说到的
缺页率置换算法里头的上界和下界
好 在这里头我们有一个常量T
如果说这两个间隔是大于T的
也就是说这一段时间隔的比较长
这表示什么意思
这表示我这里头缺页比较少
那对于这种情况我就会把
在这一段时间没有引用的这些页面
我就把它置换出去
这样的话我就是减少常驻集的大小
就相当于缺页率比较低
然后我把这些不用的页面
我就把它置换出去
这样我可以
把它用到更有意义的地方
另一种情况是小
如果说这个缺页的间隔
小于这个时间T 那这时候我认为
这个缺页率是比较高的 那这时候呢
我增加它的常驻集的大小
所谓增加怎么办呢
就是把你缺失的那一页
放到常驻集里头 那这样一来的话
我们就实现了我们这里所说的
缺页率置换算法
那具体说起来呢
我们还是通过一个实例
来给出它到底是如何工作的
在这假定这个窗口是2
这和我们刚才说的
工作集里的那个窗口 然后我们在
每次访问存储单元的时候
相当于正常访问的时候
你就直接访问做标记
缺页的时候我们来看它怎么处理
那首先第一次出现缺页
那这第一次没有以前了
那这时候直接往里加
然后接着往下访问
C不出现缺页 正常访问 你做修改
访问D也是一样的
在访问B的时候出现了缺页
那这个时候呢 时间间隔是3
大于我们的2
那这时候我们说大于2的话
我就需要把在这一段时间里头
没有访问过的页面把它剔除出去
那这时候我们看
在这里头没有访问过的
这2里头访问的是哪
C和D 只把C和D留下
那这时候它就变成是
加上你刚才缺的这页B
就变成这个样子了
剩下的A和E就被置换出去了
在访问C的时候是正常的
在访问E的时候又出现缺页
那这个时候这个间隔是2
那小于等于我们刚才这个值
我直接加上 再访问C是正常的
然后再访问E也是正常的
再访问A的时候 它又出现缺页了
那这个缺页的时候呢 我们再来看
在这里头我要把哪些留下
我在这一段时间里头访问过的
这里头就相当于是C E A这三种
这是目前这种情况
那实际上在这里头呢
再来访问D又缺页
这两个间隔比较小
我直接把它加进来 那到这个地方呢
我们缺页率算法就算是说清楚了
那实际上我们看到
在这个执行的过程当中
进程驻留在内存里面的
页面数是有变化的
那这就是我们的常驻集的大小
在缺页率置换算法里
它会自动做调节
你比如说在这段时间里头
我是有四个页面
那分配给它的物理页面数就是四
然后在这一段时间里头呢
它是只有三个
在这一段时间里呢 又是四个
那到这变成三个
这样的话每一个进程
它的物理页面数是在
整个运行过程当中动态调节的
某种角度上来讲
我们这个算法就是在逼近
我们刚才前边说的工作集
那个变化的那条曲线
我们希望它尽可能的接近
同时我又把这开销降下去
那这时候缺页率算法
和前边的工作集算法的区别在哪
区别在于原来你去看
我淘汰哪一个的时候
我是在每一次访问的时候
来做这件事情
那这个开销太大了 现在怎么办呢
在中间你访问的时候
只要间隔足够大
那这时候我就认为这是需要加进去的
只是间隔大到一定程度之后
我才认为那里头有你不用的
我把它淘汰一次
这样的话我就把置换这件事情
放到缺页中断里头来完成
这和我们局部置换算法又一致了
这时候它的开销也就降下来了
好 这是我们说到的缺页率置换算法