9.2 最优算法、先进先出算法和最近最久未使用算法在线视频

好 接下来我们介绍置换算法

首先我们来介绍局部置换算法

也就是说假定给一个进程的

物理页面数是已经确定了

那在这些页面里头呢

我们来进行置换

那第一个要说的置换算法呢

是最优置换算法 最优置换算法呢

它的基本思路是说

我在任何一次缺页的时候

我会去观察

这内存当中存在的各个逻辑页

它在未来什么时间会被访问

那我们要置换的是在未来

最长时间不会被访问的这个页面

那这个思路我们怎么来做呢

它的做法是这样的

缺页的时候我来计算内存当中

每一个逻辑页面的下一次访问时间

假定你能计算出来的话

然后我去看 比较它们的大小

未来最长时间不访问的页面

就是我要被置换的页面

那这个思路很简单

你把内存当中的所有逻辑页面排序

排序的依据是下一次访问的时间

然后最长的那个就是你要置换的

那这种算法呢 它思路很清楚

但是它的特征呢

这是缺页的次数最少的

但是它也有一个致命的问题

就是它没法实现

原因在于我无法预知该逻辑页面

它的下一次访问的时间

到底是在什么时候

在这之前我要等多长时间

实际上如果我知道那个

等的时间有多长的话

那我就把等的时间最长的那个

放到外存里面去 这是最理想的

但是这种做法呢

为什么我们还要在这说

实际上就是因为它可以作为

其它算法性能评测的依据

也就是说你设计了一种置换算法

能跟这个最优置换算法相比

你比它差多少

那你最好是能达到它的状态

你不会比它再好

所以在这用它来

作为评测依据是比较好的

那具体怎么做呢

是说我在模拟器里头运行该程序

假定它的对外界的影响都是固定的

好 那这时候我记录下

它每一个页面的访问的情况

第二次我再来运行的时候

我就得到它的最少的缺页次数了

那另设计一个算法和它比较

你就能知道这个算法的好坏了

这是最优置换算法

那我们在这用一个例子

来说它到底该怎么做

在这里呢 上边是时间的顺序

中间这一行

是请求访问的页面的顺序

这是逻辑页的编号

我们用A B C D来表示

好 这地方呢

是物理内存分配的页面数

那在这我们假定

给它分了四个页面

然后底下我们来记录

它缺页的情况

那我们执行起来会什么样子呢

首先执行第一次请求访问C

那这时候呢没有缺页

第二次也没有 那我都能访问

第三次D也能访问

第四B在这里也有

那我们这些都没问题 正常访问了

等到你访问E的时候就会发现

这时候不在你的物理内存里头了

产生了缺页

那在缺页处理例程里头呢

我们就会引用最优置换算法

最优置换算法就来判断

当时我这几个选哪一个呢

那我们就看在未来的时间里头

它都会在什么时间会被访问到

好 那我们看内存里有A

A会在这地方访问到

好 B是在这 C是9 还有个D是10

这几个比较起来呢

10是离的最远的

那我们在这就把

这个10对应的D给替换掉

那替换完了之后结果

就是把D变成了E

好 那我这个缺页中断处理呢

就处理完了

回来你再来访问

这个就算是成功了

好 继续访问B没有问题

访问A也没有问题

再访问B也没有问题

再访问C也没有问题

好 那这时候说我们再访问D

那这时候呢

这个D又不在这里头了

那这时候怎么办

我们接着说未来会访问

但是这时候已经再往后

它的未来已经结束了

那就你说什么都可以了

所以在这呢

后边你再怎么置换都无所谓了

所以在这 最好的情况

你是缺页两次

那其它的算法你写完之后

就看跟这两个比较

在对于这个特定的序列

谁好谁坏就清楚了

那这是最优置换算法

那它的毛病是在于

我在缺页的时候

我没有办法知道

后边到底是什么样的访问

特别是你比如说我的一个程序

每次处理的时候

它的数据是不一样的

我们前边说

你可以重复两次来用

但是我通常情况下

我们的程序每次执行的时候

它处理的数据都是不一样的

好 这个序列你也是没办法

完全准确的预测出来的

这是第一种做法

那么第二个做法呢

是先进先出算法

FIFO那它的做法呢

是我们想知道未来的情况 没办法知道

那我们就采用一种最简单的做法

那谁来进来 我按照进来的顺序排

这实际上我们在很多地方

我比较不出谁更好谁更坏的时候

我们就按照先来后到

这是我们在做各种各样算法的时候

一种最基本的做法

那它的依据是说

在内存驻留时间最长的页面进行替换

也就是说我第一个进来

那它的时间是最长的

最后一个进来它的时间是最短的

好 那怎么做呢

那维护一个逻辑页面的链表

按先来后到的顺序 按驻留时间排序

好 在头上的呢 是最长时间的

你置换的时候就从头上选

然后最先进来的呢 放在最后头

那缺页的时候呢

我从链首取相应的页面进行置换

新加的页面呢 放在链尾里头

那这种做法呢 它的麻烦是什么呢

是性能比较差

好处是我比较好实现

性能比较差怎么说呢

就是因为它只是按照

你进内存的先后顺序再排序

有可能你会出现这样一种情况

我刚把一个页面拿出去

它是在这里待的最长时间的

好 你马上就会去用它

如果说我们出现这种极端的情况

那这时候呢 它的缺页率就会很高了

好 甚至于会出现这种情况

这种FIFO算法

它可能会出现什么呢

我分配它N个页面的时候它缺页M次

我把它N+1之后

可能那个通常情况下

我们理解一个算法

我分配的物理页面越多

它的缺页次数应该更少 但这时候呢

它有可能缺页次数不但不减少

反而会增加

这是我们后边说到的Belady的现象

这个时候呢

实际上从另一个角度上说明

这个算法它是有缺陷的

好 通常情况下呢 这种算法呢

我们不会直接把它

作为一个独立的算法来用

它会把它揉到别的算法里来用

所以我们在这还会继续去说它

那我们也通过一个示例来说明

FIFO的执行过程

假定我这个进程分配了四个页面

然后我维护一个链表

然后在这依据它访问的顺序

我来判断

那这是我们刚才那个例子

我们接着分配给它四个页面

看看在FIFO算法里头

它会缺页多少次 那在前边呢

这地方先访问这四个页面没问题

它肯定都在 这个你用哪个算法呢

它的效果都是一样的

好 开始不一样的地方是在这

我在访问E的时候呢 它产生了缺页

在最优算法里头

我们是依据后来做判断的

现在我得不到这个了

我根据什么 我根据它进出的顺序

在这我假定它进内存的顺序

是按照A B C进来的

那这样的话很容易

我就知道我要用A来做替换

替换完了把A换成了E

好 然后后边再访问的时候

B在里头访问得到没问题

A这时候又缺页了

这时候缺页怎么办呢

我又要进行替换

替换我选的内存当中的页面

选哪一个呢

选这里头时间最长的

A进来之后 E实际上是排在最后的

那这时候呢

我把B替换了 B替换成A

然后这个时候呢 再下一个

我又访问了B 正好不错

我刚拿出去就访问它了

再访问B的时候

这时候我有A E C D这几个

按照先后顺序是C D E A

好 那我们这个时候呢说我们换C

好 把C换了

然后到这来了之后呢

再下一次访问C 它又出现缺页

那么这时候呢 我们看 这内存有哪

D E A B是这个顺序

那这时候我们换D

换完之后是这样一个结果

然后我再换 再下一步

那这个地方的时候呢

我们看到这时候D被换出去了

这里头E A B C 那这时候要换的是E

那到这我们这个访问序列执行完毕

我们看缺页几次

1 2 3 4 5 5次

和我们最优算法的两次

比较起来它多了

那你说你在这里头构造的这个例子

正好是极端情况

你刚把哪一个拿出去

你下边就要访问哪一个

那当然会是这样 那这时候是说

是不是我任何一个算法

都可能构造出一个极端的例子

你的性能会很差 那实际上这个呢

从理论上我们是可以证明

最优算法它的这种特征是最好的

好 这是FIFO算法

那这种算法呢 它实际上过于简单

那接下来我们说

我是不是可以把这种简单的算法和

不可实现的算法之间

做某种程度的折中呢

这是第一种折中的办法

最近最久未使用算法 LRU

那它的做法是什么呢

我们刚才考察未来的引用情况

这事我没有办法考察得到

那怎么办 我们去考察过去

选择最长时间没有被引用的

也就是说我们原始考察当前时间点

往后最远被访问到的

我把它置换出去 那现在呢

我是过去的情况我是可以统计的

我在当前这个时间点

看过去在内存当中

这些页面的访问情况

离的最远的那个

最长时间没有被引用的

我把它置换掉 这是可能的

这种做法的依据是什么呢

这种做法的依据是在于

我们通常情况下认为

在过去一段时间经常访问的页面

那在未来也会经常访问

在过去一段时间很少访问的

在未来也很少访问

基于这样一种假测

我们依据过去来预测未来

好 那这是它的思路 它怎么做呢

缺页的时候我去看在内存当中的

每一个逻辑页面

它的上一次的访问时间

那这个时间我是可以计算出来的

计算出来之后

上一次访问到当前这个时间

最长的那一个那就是最远的

那一次被访问者

我把那个页面置换出去

好 这样做法之后呢

它有什么特征呢

它是最优算法的一种近似

但是这种算法仍然足够复杂

以至于我们在这里要实施的话

是不太可能的

好 那这次说我们在这里头说的LRU

我们也通过一个实例来看

刚才这个序列它的执行情况

那在这呢

前边的几个正常情况下都没问题

C A D B 这访问完了

然后下一个E出现缺页

那这时候呢 我们要去考察

过去一段时间这几个的引用情况

那我们看A在哪访问 第二个

B呢 是第四个

C呢 是第一个 D呢是第三个

这个顺序和我们的最优算法很相像

区别在哪

区别在于最优算法是往后考察

最近最久未使用算法是往前考察

然后得出它上一次访问的时间

然后我选其中最小的那个

这里头是C 好 我替换C

好 替换完的结果呢是这样的

好 然后再继续往下走

B访问在里头 A访问在里头

B访问还在里头 C访问的时候

那这时候又出现缺页了

那这时候我们说我们又需要

按刚才一样的做法去考察

在内存当中的A B E D这几个

它的上一次访问时间

那怎么考察呢

我们看这是A上一次访问时间是7

B上一次访问时间是8

然后E上一次访问时间是5

然后还有一个D上一次访问时间是3

那这时候比较下的结果呢

这个D是最早的 我们把D替换掉

替换成我这里的C

替换完的结果呢 是这样的

好 然后这时候说

我接下来执行下一个 那这时候呢

访问到的D正好是刚被替换出去的

你又要出现缺页

那这时候按照我们最优置换算法

因为最后一个没有未来了

给哪个都一样 实际上也是这样的

但是在最近最久未使用算法里头呢

我们就需要去看

过去一段时间它的情况

当然我们知道这种考察呢

实际上对未来的执行是没有意义的

从这个角度来说呢

这个LRU 在最优算法的

近似的过程当中

它也有不准确的地方

所以它是个近似

好 我们看这时候呢

A是7 B是8 E是5

那唯一变化的就是这个C

那它是9 这几个我选择下来呢

这个E是最早的一个 我把它替换

那这是替换之后的结果

那我们看到在这里头呢

它的缺页次数是三次

和我们前边说到的

先进先出算法要好很多

和最优算法比较它又多一次

那这是最近最久未使用算法

那我们看到 实际上它处理呢

是比较复杂的 在缺页的时候

我要把所有内存的页面

全部去统计一遍 那这个统计呢

有可能你是在缺页的时候

你再来做这个统计

你已经统计不出来了

所以这个统计呢

应该是落实到你每一次访问的时候

你才有可能统计得出来

好 那这个呢

我们就说到下一个它的实现办法

第一种实现办法呢

是我构造一个页面的链表

那在这个链表里头呢

它的排列顺序是按照

最近一次访问的时间来排序的

然后是链表的首结点

是最近被访问过的

链表的尾结点是最久未使用的页面

好 然后在这里访问页面的时候呢

每一次访问

我都把访问到的那个页面

把它从这个队列链表里摘出来

放到它的链表首部

然后缺页的时候怎么办呢

缺页的时候我从最后一个

来作为我选的这个缺页

不像我们刚才给的那个表里头

我是到每次缺页的时候

再把那些重新计算一遍

而把这件事情落实到平时当中

每一次访问的时候来做这件事情

但是这样做呢

实际上你每一次访问的时候

它的开销是很大的

好 再一种做法呢

是说我做成一个活动的页面栈

思路都是一样的

只是实现的手段有一些区别

那访问的时候我把这个页号呢

压到栈点

同时压完之后我要把栈内相同

也就是说 以前访问到的

同一个页面的 过去的情况

我就把它去掉了

把这个结点从这里抽出来

实际上这还是维护了

跟前边一样的一个栈

只是它做法是压进去之后

把相同的页号抽出来

那这时候我的链表的维护变少了

但实际上这时候呢

你压进去一个之后

你要把整个这个队列呢

完全的搜索一遍 去掉重复的

实际上这个工作量仍然是很大的

好 缺页的时候呢

我从这个栈底的页面

把它作为我被置换的页面

好 那这时候呢

说LRU算法它最大的问题是开销大

那我们下边需要解决的就是

我如何能让这件事情开销变的小

我们先来看一下它到底

都有些什么样的开销

那我们用栈的方式来实现

我们的最近最久未使用算法

看实施的过程是个啥样子

那我们前边说

在最近最久未使用算法里头

前面那个示例的时候

我在访问的时候没有做任何事情

现在我们把那个统计的事情

放到你访问的时候来做

那就会变成什么样子呢

首先访问第一个页面

那这时候我维护这个栈

这里头只有一个元素

好 我访问第二个页面的时候

我就把这个页面作为压下一格

在上边加上你刚才访问的这个页面

那这就是这个栈里就有两个了

访问第三步的时候 我再复制一遍

然后把新访问的这个页面放到栈顶

再访问B 第四次的时候再压栈

这时候是刚开始没有缺页的情况

缺页的时候访问E的时候

它出现缺页 缺页的时候怎么办呢

我们从这里头这个栈里头

把最底下的那一个E

这个C拿出来 把它置换掉

然后把它换成E

这个栈就是把底下那个取掉

在顶上加一个

实际上这个C在哪呢 在这个地方

换完之后这个结果

就把这个E换到C那去

好 这是第一次

那实际上我们在前边做些什么

在这里维护这个栈

是你平时访问的时候的开销

好 正经到这缺页的时候

我只需要从这里取出一个

在栈顶再加一个

那开销比我们前边做的时候呢

已经要省事很多了

好 再是访问B 那这时候呢

从这里抽出来 把它放到栈顶

这是你平常访问的时候需要的开销

然后再访问A的时候呢

那抽出来 把它放到栈顶

那这是从最底下抽出来的

所以移动的区域就会比较长

然后再访问B的时候呢 一样的

这时候抽出一个来放到栈顶

好 再访问C的时候又出现缺页了

那这时候怎么办

把这D拽到最底下 把它置换出去

然后把C放到D的位置

那这是置换完的结果

把C放出去

好 然后再来 这地方呢

到下一步再访问D的时候又缺页

好 把这个E挪出去

把这个D放到栈顶

那这就变成这样了

好 置换完的结果

跟我们上一个呢 是完全一样的

但是这时候呢

我们跟前边的做法有什么区别

前边的做法我到缺页的时候挨个去查

现在我在每次的访问的时候呢

做一些记录

缺页的时候我只需要看一下

这个数据结构我就可以换了

那这种做法呢

我们看到平时的这个开销是很大的

特别是在这个地方

你要把这个栈整个捋一遍 移一遍

然后把最底下的那个挪到最上边来

这个时候的开销确实是很大

好 那接下来呢

我们还会再进一步的去讨论

我怎么把这个算法做进一步的近似

使得它访问的特征不是太差

但是它的开销呢

会大幅度的减少