9.3 时钟置换算法和最不常用算法在线视频

接下来我们介绍时钟置换算法

和最不常用置换算法

这两个算法呢实际上是对

前面的FIFO和LRU呢做的一些简化

时钟置换算法呢是对这个

LRU考察的是过去一段时间

而现在在这里头呢 它是把

在FIFO完全不考虑过去的访问情况

变成是在这里呢有一定的考虑

但又不像LRU呢那样考虑的那么长

所以这时候呢

在它俩之间做了一个折中

而最不常用算法呢实际上是从

考察过去这个间隔的时间

变成是考察过去的访问次数

时钟置换算法呢

它的基本思路呢很简单

就是对页面的访问情况进行大致的统计

因为我LRU呢统计过于详细过于细致

以至于开销太大 那我只做粗略统计

那所谓的粗略统计呢

它只是统计过去一段时间这个页面

是否被访问过 访问过我留下

没访问过的我就按照进来的先后顺序

或者说它按照现有的顺序来做排序了

那它在这里头 为了做这件事情

它首先对数据结构做了一些改动

页表项里头增加了一个访问位

这个访问位呢用来描述

在过去一段时间里头 是否被访问过

而过去一段时间呢

是靠这个指针来约定的

那这个指针怎么约定过去一段时间呢

它把这些页面组织成一个环形链表

然后这个指针呢

是在环形链表上进行周期性的循环

这也是我们这个时钟这个词的来历

看上去呢像一个钟表

好 那在这里少的时候

它是去看访问过的留下

没访问过的它就按照链表里的顺序

进行顺序的置换了

那这是它的数据结构

它的算法怎么做的呢

是访问页面的时候

那你要在页表项里记录它的访问情况

也就是说访问过 我把相应的访问位置1

没访问的那我就不做处理

好 再有一个呢就是缺页的时候

缺页的时候

它从指针的位置开始顺序查找

查找在上一次扫过

到现在这一次扫描的时候

它是否被访问过

如果没访问过那就是

在过去这段时间里头没有访问

对于这些呢 它就可以对它进行置换

找到第一个作为它的置换

所以这儿呢它也有FIFO的那种思路

好 那这种做法呢

它的特征是在LRU和FIFO之间做折中

那所谓的折中是在于

它对过去的访问情况有考虑

做了统计

所以它不像FIFO完全不考虑

这里的访问情况

然后再有一个呢

它又不像LRU考虑的很详细

FIFO里说 只是说在过去一段时间里头

没有访问的那它就做置换了

这个时候呢如果说你所有都没访问

那它就退化成是FIFO了

那具体说起来呢是这样的

我们怎么来实现呢

装入一个页面的时候

那把它的访问位清0

然后访问的时候呢把访问位置1

那你在执行的过程当中访问了哪些页面

你就把哪些页面的标志位置为1

好 出现缺页的时候我怎么处理呢

出现缺页的时候从当前的指针位置

开始扫描环形链表 检查

如果访问位为0

那这一页呢是我可以置换的

那我直接置换 好

这个指针移到下一个地方就结束了

好 如果说页面是访问过的

那这个时候呢

我就去把它的标志位改成0

也就是说我从现在这个点开始

进行一次新的计时

好 并且把指针移向下一个页面

如果下一个页面仍然是访问过的

继续往后找

一直到找到一个可以置换的页面

找到一个访问位为0的

按照头一条进行置换

那这是呢它的处理的办法

那我们用一个图示来说明这个过程

那这是一个内存当中的物理页面

它把它组织成一个环形

然后在这儿呢加了一个指针

开始的时候指向这儿了

好 如果在这里头我们访问某一个页面

在这儿 它把这访问位置1

好 如果说已经置1的你再访问

那这个1就不动就行了

然后在我发生缺页的时候

那这一页没在这里头那我怎么办呢

就从这指针的位置开始扫描

找访问位为0的 访问位为1的我清0

那这个时候呢应该是找到这儿

我们看 好 这儿清0 这儿清0

然后到这儿清0 这地方清0

找到这个地方它停下来

好 这个页面呢

是我们可以用来做置换的

把它置换成新的页面

这个缺页中断呢就算处理完了

再次缺页的时候 它继续往后扫

到这儿又找着一个再做替换

它就周而复始的

那这样的话我们就可以使程序

在正常情况下可以访问

缺页的时候我可以找到一页替换

然后继续执行

那这是时钟置换算法的大致的过程

那我们下面用一个更详细的表格

来说明它处理的情况

这是我们前面例子里

说到的一个访问序列

然后我也给它分配了四个页面

但在这里呢我页表项里头

我记录了一下它的访问的情况

好 那在这里起始的时候

它们都没有访问过

那访问第一个页面

那这时候在内存里头访问的是c

好 那这时候c的访问位是置1的

好 再往后走 这回访问的是a

那这个地方呢访问位置1

再访问 下一步访问d

这里d呢它置1 好 再访问b

那到这上头b置1 再往下走

访问e的时候那这里没有了

那这个时候会出现缺页

缺页的时候呢 那我缺页的处理是什么

那个指针 这个蓝颜色

表示当前指针所在的位置

好 那从这儿开始扫描

是1的改成0

好 找到下一个 再是1 再继续改成0

再是1再改成0

全是1改了一圈之后

回到最顶上它发现了一个不是1的

那这时候我把它替换成我的缺页这个

OK 这样的话我把它改成1

改完之后的结果呢

在这儿 a被替换成e了

好 那这个时候呢

我这个缺页中断就算处理完了

好 再往下继续执行 访问b

这个时候呢又改成1 再访问a

那这个时候呢a不在里头又发生缺页

缺页的时候我就要从这里继续找

当前在这个b的位置

这个b是1改成0

那下一个就可以了 这时候

它处理是先改0到这儿

这是找到的一项改成1

OK把c换成了a

那处理完的结果呢在这儿

c换成a

好 那这时候呢执行到这儿继续往下走

访问b b在里头

把它的0改成1就行了

好 再访问c那它又会出现缺页

缺页之后呢

在这个页表项里头进行扫描

这个地方正好它就是0

所以这项直接可以替换

替换完了之后的结果呢在这儿

好 它换成c

那到这儿之后把这儿换成c

好 我们在这里呢继续往下走

这时候看到

往d的时候这里仍然没有

它还会再出现缺页

那这个缺页呢我会再继续找

这又是一圈全是1

全部改成0又回到这儿

第二步 第三步 第四步 回到这儿

那应该是把e是我可以选择的

把e换成d 这是换完之后的结果

好 到这个地方呢

我们就把这个时钟置换算法的

基本流程说完了

那在这里头呢

我们考虑到的仅仅是它访问的情况

如果说你访问的那一页

你是被修改过的

那么这时候呢它缺页中断的处理时间

就会是当前这个时间的至少是2倍

你需要把原来的内容写出去

再把新的内容读进来

那这个过程呢

在缺页中断这段时间太长

那我们需要对它做改进

那这个地方就是改进的时钟算法

它的基本思路呢是说对有修改的地方

这些缺页的开销呢我把它减小

它怎么减小呢 就是如果你有修改

那我这时候跳过这一页我不做置换

那在系统里呢它会定期的

把这些修改过的呢写到外存里头去

那在这儿呢

我们这个细节不再仔细讨论

好 它的做法是什么呢

在页表项里头加上一个修改位

然后在你做访问的时候进行修改

那我们前面说有一个访问位

是你在访问的时候它被置1

那这里头又加了一个修改位

那这时候我在访问的时候

就有两位来做状态的变化

你是读那只是改访问位

修改位还是0

如果说你是写 那这两位同时改

好 缺页的时候呢

我仍然是跟原来一样去找

但这时候找的过程当中呢

修改过的页面它是直接跳过的

那具体说起来是这样的

这是它指针扫描的时候

它改状态位的方法

如果两个都是0

那这时候呢肯定是前一轮里头

它没有访问过 那这时候我可以替换

好 剩下的三种情况访问位为0

修改位为1

那这时候也就相当于

我这里前一轮转过的时候

修改过的地方你还没写出去

那这时候我把它清0

好 通常情况在这个过程里

会启动往外存里写

好 同时继续往下走

那这两个情况呢

访问位1 修改位为0

那这时候呢 我把它改成0

如果访问位两个都是1

我把第一个改成1

第二个继续留着

那就会出现上面

这个地方的这种情况

好 在这儿也有一个示意图来说

我们看在这儿多加了一位修改位

那这个时候在那个指针扫描的时候

会是什么样的呢

把1改成0 两个1

好 这找到一个

这是我们可以替换的 两个都是0

好 我把它改成我要的页面

如果说在下一次再出现缺页的时候

我从这儿继续往下找

两个1的改过来

那在这儿找到一个

好 那我把它做替换

好 那这样的话就是改进的时钟算法

在这个算法里头呢

它在缺页中断的时候

对于修改过的页面

它的处理呢速度会比原来快

那你说在这里头 它快到底在哪呢

一个是延迟之后

后续有可能的改动的页面

写出它可能会被合并和延时

好 这个地方也是把刚才

加了改进的时钟算法它的执行过程

那跟刚才的时钟算法不一样的地方

这地方加了两个标志位了

那处理的过程也是在前面类似的

这是对c的访问是只读的

好 那这个地方只是改成10

对a的访问是写的

好 那这时候把0改成11了

好 然后再是d那是改成10

然后再是b 那是改成11

再到e的时候它产生缺页了

这时候我要去找一个页面

可以来做替换的

那怎么找呢 那做循环

11的改成01

10的改成00

那改一圈之后回来应该是找到c

我们看一下它执行过程

11改成10 11改成10

10改成00 10改成00

好 这个地方01改成00

好 最后找到这个地方

那这一项是替换成1

替换完的结果呢 是这儿

好 那接下来再往下走

那我们访问到这个地方是b

我把b的标志改了

在这个地方注意一下

我这个地方加了两个星号

实际上就相当于我在改标志的时候

实际上这相应的内容

并没有写到外存里头去

需要系统里另外的部分呢

来对这种情况做处理

要不然的话这两者就不一样了

好 继续往后走

a是写00改成11

再有b再访问 这已经改过来了

所以这时候页表项里内容没有做变化

好 然后再是c

这时候又产生缺页

看到结果是什么

这地方直接d 这地方是00

我直接可以替换d

OK 替换完的结果就是在这儿换成c

好 上边的指这儿

实际上刚替换完之后

接下来它又访问d 还是产生缺页

那这时候会找到哪儿呢

这地方不是 这地方不是

改过一圈之后回过身来会在b这个地方

01 00 00 00好再倒过来这改成00

好 这时候找到b 替换

那这是我们刚才说的时钟算法

和改进的时钟算法

那改进的地方就是对于写操作的页面

它的置换会有一个稍微不一样的处理

那接下来我们说最不常用算法

这个算法也是对LRU的一种简化

它所谓的简化呢就是它统计的依据

不再是我们刚才说的时间

时钟算法里修改或者是没修改的01状态

它是在这里加了次数

所以在这种情况下

它的统计开销相对来说就会大一些

那看一下它的具体怎么做的呢

它是在这里每一个页面

加一个访问计数

我们刚才说的访问位呢

某种程度上来讲

你也可以认为它是一个计数

只是说这个计数

它计的范围是比较小的

只有0 1两种状态

而我可以设置一个多位的计数

这时候多位计数的话那它就会加1

加1的操作会复杂

但这时候呢我可以统计的更精确

好 缺页的时候呢

我置换那个计数最小的那一页

那也就是说

过去一段时间你访问最少的

我认为它是这个需要置换的

当然这时候也有可能有这种情况

就是一个页刚拿进来没访问几次

又把它置换出去

这是它存在的一个麻烦

它的问题是开销大 并且呢

计数值还没长的很大的时候

可能频繁的是这些页面

刚拿进来又拿出去

所以它的做法呢

后续有一个改进就是对这个

已经计了数的这些值比较大的

它会定期做衰减右移

那这样的话它计数值会变小

用这种办法来做

实际上这个LRU和LFU之间区别在哪

LRU考察的是过去的未访问的时间

这地方考察的是访问的次数

这两者到底有啥区别呢

因为这个统计时间我要去维护那个栈

统计次数相对来说好弄点

我们也还是通过一个具体的例子来说

这是我们刚才那个例子

但是跟刚才那个不太一样的

我们如果按原来那个序列的话

它就太短了

以至于LFU不足以显示它算法的特征

那么在这儿呢给上边加了一个数值

表示我多少次访问

也就说原来我这一次访问的话是一次

那我在这儿呢 统计了

在这里访问过的它是有多少次

好 我们在这里头呢

这是实际分的四个页面

假定初始的时候它的访问次数是这样

那我们看执行的过程当中会是啥样的

好 首先在访问的时候

我要去修改每一个的计数

比如说在这里头原来有6次

那我在这一段时间里头呢

它访问了7次

好 那这样的话

我就会把这个值6加7 13在这儿

再往下走访问的时候a这里头有

计数加上相应的值那这是加1

好 在访问d的时候也是一样

这地方2加14 16

再访问b再继续往上加变成10了

再访问e的时候这里没有了

那就会产生缺页 那缺页怎么办

我去找我当前这些计数里最小的那个

那是a 好 我把a替换成e

那并且这时候

替换完之后你访问多次

那计数加这里头

继续往下到b这个地方又继续往上加

那就会发现存在里头

如果时间越长的话 这数会越加越大

你加的越大你日后

再被置换出去的机率也就会变小

好 如果说你这时候访问的特征

从一个区域变到另一个区域

那么前一个区域里多次访问的页面

有可能会保留很长的时间

好 然后再访问a

那这时候前面没有了 缺页

好 这时候找你最小的是哪个

b把它换掉

那这时候呢它的访问次数清0之后

先换出来把它当前访问次数加上

好 再往下一步呢 又访问b

那这时候又没有了

好 它又要有缺页

在这里找 哪一个c

它只有13次 好 最小的置换掉

那这个地方就换成20次了

这是我这里b的情况

好 再过来访问c

那又是缺页 这里最小的是啥

是16 把16置换掉

那这时候有一个问题是说

你这里写的数 好像你要想置换别的

你这个数只能越写越大

如果说你刚开始几次基本上会换一个

好 那这时候说 再访问d的时候

这里最小的是什么 18 e

换掉之后

这是执行到这个时候的状态的结果

那到这儿呢 我们可以看到这个

时钟算法和最不常用算法

这两个算法呢

都是对LRU的某种程度的简化

那简化之后呢 这个开销会小

但是它统计的精度也会下降

那这时候实际上我们在这里

做这个置换算法的时候

就是需要在这种

近似的程度和它的准确性之间做折中

必须是简化到足够的程度

以便于我们在每一次调指令的时候

都有很多的存储访问

都能在很快的时间里头来实现

或者我用硬件

可以很方便简单地来实现

那像这种情况 LFU就比较难实现了

那为什么我们还在这儿会讨论呢

实际上这个存储的访问呢

它不仅仅是有CPU到内存

也有我读硬盘的这种存储访问的情况

这时候呢它时间长一些

像这些算法呢

在那个地方就相对来说就可以用了

好 那这是我们说的

时钟算法和LFU最不常用算法的情况