我们接下来介绍
局部置换算法它的一些特征
那么在这里头呢
我们前边已经介绍了
五种局部置换算法
这五种局部置换算法呢
各有各的优缺点
那么它们之间都有一些什么样的特征
到底它们之间是一个什么样的关系呢
我们在这用一部分时间做讨论
第一个是Belady现象
说的是随着分配给进程的
物理页面的增加
它的缺页率会少吗
好 后边这个呢
实际上是对几种算法之间它们的比较
每一种算法呢
它都会在一定的情况下
和另一种算法体现出某种相似性
Belady现象
这里说的是说我们给每一个进程
分配一定数目的物理页面
那如果说它缺页次数比较多
那这时候我会需要增加给它的页面数
那增加完了之后
这时候我们按照通常的理解
它的缺页应该降低
但实际上如果你的算法不好
比如说像我们这里的FIFO
在某些情况下 你增加页面之后
它的缺页次数反而会增加
这种现象就叫Belady
那产生这种现象的原因是什么呢
原因是这样的
我们置换算法 你置换的话
是标记它的某种特征
然后依据这种特征对它进行置换
那我们标记的这种特征
和进程的内存访问的这种特征
它是不一致的
那也就是说每个进程
是不是会有自己的访问特征呢
你比如说我有一个排序程序
那它的访问特征和另外一个
我一个word的编辑程序 那这两种呢
它的内存访问特征
肯定是完全不一样的
好 正是由于这种原因
我们置换算法对它的预测呢
和进程实际情况会不一致
好 那这种预测不合理
那就有可能出现这种情况
那这时候是说
是我所有的算法都这样吗
这是我们需要考虑的 那我们在这呢
还是先从FIFO说起
我们刚才说FIFO是有Belady现象的
我可以找到一个实例
说你用FIFO算法
那分配给它页数少的时候
它会出现一个缺页次数
分配增加之后
缺页次数反而增加的这种情况
那我们具体来看一下这个实例
那在这里头呢 这个地方是个FIFO
然后这是访问的序列
然后我们在这呢 访问缺页状态
在这跟我们前边的约定
稍微有点不一样
比如说我们在这里
第一次访问我就认为它是缺页
为啥会这样呢
原因在于我们在前边
统计局部置换算法的时候
刚开始我的那一段我是不算的
但是在这呢
因为我分配给它三个物理页面
下一次我分配给它四个
如果这段不算的话
这两个的比较性会不一样
好 所以我们在这起头的这几个都算
好 那这个是前三次我刚起头的时候
那这个呢 怎么着都是一样的
什么算法都是这样
好 第四个 那这时候呢 加进来
你的前三个是不在这的
它会产生缺页 再往下一个
这一个也不在 它还会是缺页
然后还会是缺页
然后到这5这也还会是缺页
好 那到1这个地方呢
没问题了 这个1在里头
好 那这个时候呢
它没有命中 然后2命中
然后3缺页 4缺页 5缺页
那这时候呢 总共有多少次呢
总共是在这 缺页是9次
我只有三次命中的
那我们在这呢 这是个示例
好 那我们再这呢 我们再看
我分配给它4页的时候
还是同样一个序列
它的缺页次数会增加吗
好 由于我们刚才说你分出的三次
那前边这四次是肯定一样的
好 那在这里头说
你分配4页肯定比刚才好
那从第一个来讲 这肯定是好
因为刚才那个1拿出去了
你就有缺页了
好 这1没拿出去是不是好了呢
1没拿出去 这确实是命中了
但是这两次都是成功的
好 接下来的日子就不好过了
接下来之后5缺页 你把它拿出去
好 然后在这呢 再来1
你又把它拿出去
然后2 又是缺页 3 4 5
你会发现 在这个顺序当中
我这访问的总共就五个
你到了4页之后 还是有缺页
到什么情况下不会缺页呢
你把这五个全放在这 就肯定不会了
那现在就是说对于4页的这种情况
那到这实际上你可以基本上可以看到
你刚才把哪一个拿出去之后
我就要访问哪一个
1 2 3 4 5 正好对着的
那你说在任何一种情况下
是不是你给出一个序列来之后
我就可以针对着你拿出的情况
构造出这个序列来呢
这是我们在这里头
那你说这么来的话
我可以构造出来的话
我是不是任何一个算法
都能做到这样呢
这是我们在这里需要讨论的
好 从这呢 给出一个实例
就是这个序列分3页和分4页
它的情况是缺页增加的
所以它是存在Belady现象的
那如果说你在这里呢
你证明它有 那我举出一个例子来就行了
但是如果你想证明它没有
你把所有的全枚举一遍吗
这是不可能的 好 那在这呢
我们说LRU它是没有Belady现象的
那在这呢 也给出了一个实例
说我这是分配三页 缺页十次
然后我在这呢 再给它分配四页
那数一遍之后呢
它缺页八次 那这个没有
那我仅靠这一个例子
我是没有办法说明这一条的
那有证明吗
好 实际上在这里呢
我们是可以有证明的
说只要是你类似于
我们前面那个栈的这种做法
那从底下往上抽的话
那这些算法呢
它肯定都是没有Belady现象的
这是我们说的 那再问一句
我们的时钟和改进的时钟
这两种折中之后有Belady现象吗
LRU没有Belady现象
和关于时钟和改进的时钟算法的
Belady现象
到底是个什么结论
留给大家课后去思考
这个在相关的参考书里
可以找到它的证明
那接下来我们说LRU FIFO和时钟
这三种算法它们之间的比较
那实际上我们在前边已经说过了
这两个是两个极端
除了那个最优算法LRU是最好的实现
然后FIFO是我们在这里给出来比较差的
那这时候呢 它们有什么相关性呢
实际上任何一个置换算法
那它在做的时候呢
都会有一个排序
这个排序是什么样的
这对于你有至关重要的影响
这两者的区别在于
LRU是因为是以最近一次访问的时间
前边的访问的时间来做排序
而FIFO是以加载的时候
装入的时间为顺序来排序
这是它排序的 它们俩之间的区别
那仅从这个时间点上来说呢
好像这个事比较好弄
第二个是它的这个在执行的过程当中
它是否要动态的调整
那这时候FIFO的这个顺序进来的时候
这个因素在后边就再也不会变了
所以它没有调整 所以它的开销就小
而LRU每一次访问
我都要去维护我那个栈的顺序
所以它的开销是很大的
那这样一来的话
就相当于我们说这两种算法是开销大
它的性能好 这个开销少 它有问题
然后说这两种算法它在一定情况下
是可以相互转换的
LRU它可以退化成FIFO
在什么情况下呢 是这样的
如果说你访问的页面是第一次
也就只访问一次 然后就不再访问了
对于这种情况这两个算法
你在里用LRU是没有意义的
原因在于它只用一次
你用第一次的时候
没有任何的历史你可以借鉴
所以它俩是一样的
而这时候它的顺序
也是跟你加载的顺序是一样的
所以这两个排序是一样的
好 在这 这是一个实际的例子
那你说这个例子是你构造出来的
有几个页面
我就顺序的访问比它多一个
这样的话对于FIFO
你就肯定是不行的了
那在我们实际用到的程序里
有啥样的是这种情况的
这种情况也是存在的
比如说我们在看视频
视频信息的输出的时候
你在读入相关的信息 那这个信息呢
通常情况下我们播视频的时候
它是从头到尾播一遍
你很少有翻来覆去在那听的这种情况
好 正是由于这种原因
所以我们这种只放一遍的
这种情况也是有的
如果说在你的系统当中
这种情况很常见
你就有必要针对这个
别把这个缓存的事做的很复杂
这是LRU和FIFO之间的一些关系
那这时候说LRU的性能好
但是开销大 FIFO的开销小
但是会有Belady 然后说Clock
时钟算法实际上是它们俩之间的折中
怎么做折中呢 我们看一下
在这里访问页面的时候
我们前面说一个需要调整顺序
一个不调整顺序
那调整顺序的开销大
那不调整顺序这个呢
我就啥事也没做
那这个做法呢不好
我们在这里取一个折中
就是访问的时候 我会做标记
比如说哪些页面访问过
那这是比FIFO做的复杂的事
那由于这件事情有硬件参与
改页表里的页表项
这件事情相对来说比较方便
好 然后我不去调整它的顺序
那这样的话
我调整顺序的开销就没了
然后说在这里头呢
那我要想得到LRU的一些特征
我怎么办呢 我缺页的时候
那缺页的时候我们的时钟算法会去扫描
实际上这个扫描你可以理解为
它这里对这个顺序做了一定的调整
实际上它怎么调整呢
就是你扫描的过程当中
有一些点它是直接蹦过的
访问过的它是直接蹦过去了
好 这种直接蹦过你可以理解为
是把它的顺序是做了某种形式的调整
好 那这样一来的话
说时钟算法它和LRU是什么样的呢
对于刚才说的没有访问过的页面
这Clock算法 你LRU也已经退化成FIFO了
你Clock也和它是一样的所以你可以说
Clock和LRU是性能一样的好
实际上它和FIFO
它们三个是一样的
因为我没有任何可以借用的信息了
好 那在什么情况下
它比FIFO做的好呢
对于被访问过的页面
Clock就比LRU要做的差
但是比FIFO做的好
因为在这里Clock它只记录了
我是否访问过 访问过的我留下
而对于LRU不但是访问过的
我要做记录
并且访问的顺序我还要做记录
所以这样的话
它的记录的信息比Clock要多
这是我们对这三种算法
它们之间的一个比较
到这个地方为止
我们就把局部置换算法呢
全部讲完了 在这里头说
这些主要的区别是在于
我在这个固定页面的情况下
我怎么来调整我要置换的
这个页面到底是谁 我对它做排序
我以什么样的指标来排序
这种排序的情况下
它们的开销是什么样的
好 在开销我不可以接受的情况下
我如何对它去做折中和简化