3.9.3Cache替换算法

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6

文章目录

一、引子

这个小结我们要学习的是 cache 的替换算法。

1有待解决的问题

在之前的小结中我们留下了这样的 3 个问题。
image.png

上一个小结我们解决了第一个问题而第二个问题就是我们的 cache 是很小的主存是很大的。

但是每一次被访问的主存块一定会被立即掉入 cache 当中这就意味着 cache 很容易被装满。当 cache 装满之后我们应该怎么办

这就是替换算法要解决的问题。

2地址映射方式

我们要结合上一小节学习的这些地址映射方式来进行考虑。
image.png

①第一种全相联映射

这种映射方式意味着每一个主存块有可能会被放到 cache 的任何一个位置所以如果采用这种映射方式就意味着只有整个 cache 全部被装满之后我们才需要在整个 cache 当中选择一个 cache 块把它进行替换。

②第二种直接映射方式

对于任何一个主存块我们只能把它放到一个指定的特定的位置。这就意味着如果这个位置原来已经有数据了我们直接把原来的这份数据给替换掉、淘汰掉就可以了。

所以如果采用直接映射方式其实我们不需要考虑替换算法到底要替换哪一块这样的问题我们毫无选择只能放到固定的位置。

③第三种组相联映射

每一个主存块会被放到指定分组当中的任何一个位置。所以如果采用这种方式就意味着只有内存块它所属的 cache 分组整个组都被装满之后我们才需要选择到底要替换哪一块。

所以替换算法只会被用到全相联映射还有组相联映射这两种方式。直接映射的时候不需要考虑替换算法。


这个小节的讲解中我们会以全相联映射为例学习 4 种替换算法。
image.png

第一种是随机算法第二种先进先出第三种近期最少使用第四种叫最近不经常使用。

同学们也需要注意各种算法的英文缩写。

二、随机算法

1过程

首先来看第一种随机算法
image.png
顾名思义就是如果 cache 满了我们随机选择一块进行替换非常的free。
image.png

来看这样一个例子假设有一个系统当中它的 cache 块总共有 4 个初始的时候所有的 cache 块都是空的采用全相邻联映射方式。
image.png

接下来我们访问的主存块编号分别是这样的一个序列也就是先访问 1 号主存块再访问 2 号、 3 号、 4 号再访问 1 号、 2 号以此类推。

总共 4 个Cache块并且刚开始所有的块都是空的。

所以我们刚开始访问 1、2、3、4 这几个主存块的时候需要把这些主存块依次调入到 cache 当中。

把1 号主存块放到 0 号 cache 这个位置 把2 号主存块放到 1 号 cache 这个位置。接下来 3 号和 4 号主存块也是类似把它放到 cache 的相应位置。
image.png

刚开始访问的这几个主存块都是没有命中的。每访问一个主存块就需要把这一块的数据从主存调入到cache。

由于前边的这 4 次访问 cache 一直都没被装满所以我们不需要进行 cache 替换算法。


继续往后。

接下我们要访问的是 1 号主存块由于此时 1 号主存块已经存放在 cache 当中所以这一次的访问是可以命中的。
image.png

接下来 2 号也是一样也可以命中。

再接下来 5 号由于此时 4 个 cache 块当中存放的主存块分别是 1234 号 5 号主存块此时没有被调入cache。

而我们之前说过**每访问到一个主存块就一定需要把主存块立即调入 cache **。

所以此时我们就需要根据 cache 块的替换算法来决定要替换哪一块。

根据随机算法的规则可以随便选择一个块进行替换。

比如我们把 3 号主存块给换出去换入 5 号主存块没有任何规律我们随便选的一个位置。
image.png

接下来 1 号和 2 号的访问都可以命中。
image.png

再接下来访问到 3 号块此时 3 号主存块没有放到 cache 当中。所以同样的我们随机选择一个块进行替换。假如我们把 4 号主存块换出去把 3 号主存块换到它原先存放的位置也就是 3 号cache行这个地方。
image.png

接下来又需要访问 4 号主存块我们随机挑一个把 1 号主存块给换出去把 4 号换进来。

接下来访问 5 号储存块 5 号此时是在 cache 当中的所以可以直接命中不需要发生替换。
image.png

这就是随机算法

2分析

这种算法毫无规律我们并没有考虑到什么程序的局部性之类的这些因素所以这种算法它实际的运行效果会很不稳定 cache 的命中率可能会很低。
image.png

三、先进先出算法

1过程

接下来看第二个先进先出算法。
image.png

顾名思义就是我们会优先把最先被调入 cache 的块给它替换出去。


还是用刚才那个例子。

刚开始访问 1、2、3、4 这几个主存块的时候由于 cache 初始是空的所以我们只需要把这些主存块分别调入到 cache 的相应位置就可以。
image.png

接下来访问 1 和2这两个显然是可以命中了。

再接下来访问 5 号主存块。 5 号主存块此时并没有在 cache 当中。

根据先进先出的规则此时我们放在 cache 里的这些主存块最先被调入的应该是 1 号主存块所以我们会优先淘汰 1 号主存块然后把 5 号主存块放到 cache 0 位置。
image.png

接下来我们又要访问 1 号。 1 号刚才被我们淘汰了现在又需要把 1 号调入cache。

此时我们放在 cache 里的这几个块当中最先被调入的应该是 2 号 cache 块。所以我们会淘汰 2 号放入 1 号。
image.png

淘汰 2 号之后紧接着又访问 2 号。类似的原理在剩下的这几个主存块当中最先被调入的应该是 3 号块所以淘汰 3 号放入 2 号。
image.png

接下来访问 3 号。应该淘汰 4 号掉入 3 号。
image.png

再接下来访问 4 号储存块。剩下的这些块当中最先被调入的应该是 5 号。所以淘汰5放入4。
image.png

接下来又访问5此时剩余的最先被调入的应该是 1 号所以换出 1 调入5。
image.png

这就是先进先出算法很好理解并且用硬件实现也很简单。

2分析

刚开始 cache 的所有行都是空的我们可以按照行号递增的次序 0123 这样的次序来依次放入最初始的几个内存块。接下来我们只需要按照 0123、0123 这样的次序来替换各个块就可以了。

因为按照刚才这种策略我们最先放入的就是 0 位置所以我们最先应该淘汰的也是 0 位置。 0 这个位置被替换之后接下来最先调入的应该就是处于 1 位置对吧所以接下来还需要替换的话我们替换11替换之后再往后想要替换就替换 2 就可以了。

所以先进先出算法用硬件实现起来也会很简单只需要轮流的替换各个 cache 行就可以。

但是先进先出也没有考虑到局部性原理因此 cache 的命中率也会很低。

最先被调入 cache 的块也有可能在之后会被频繁地访问到。

这个应该不难理解比如大家写的 c 语言程序很有可能在刚开始的时候就调用到了 print f 这个函数这个函数你是最开始就使用到的这并不意味着再往后这个函数你就用不到了对吧

所以我们把最先调入 cache 的给淘汰这种处理策略是不科学的。因此先进先出这种替换算法实际的运行效果也不太理想。

另外刚才我们分析到后面这个部分的时候大家会发现我们出现了这样的一个有意思的现象就是在这个地方我们换出了1换入了5 1 刚被换出紧接着又访问了1所以我们不得不换出2然后再换入1。而 2 刚被换出接下来又访问到了2所以就出现了这种频繁的换入换出的现象。
image.png

这种现象被称为抖动现象刚被换出的块很快又被访问所以紧接着又会被调入。

四、近期最少使用

1过程

第三个算法叫近期最少使用英文缩写叫LRU
image.png

这个算法的思想是这样的我们会为每一个 cache 块 cache 行设置一个计数器用于记录 cache 块里面存放的主存块已经多久没有被访问过了。

当我们需要替换的时候我们会选择计数器最大的一个 cache 块把它替换出去。

计数器最大是不是就意味着这个块是最久没有被访问过的。

还是用刚才那个例子体会一下。
image.png

1.手算

首先跟大家介绍一个手算做题的方法。

我们先不考虑机器是如何执行的。总共有 4 个 cache 块刚开始都是空的。

第一个被访问的主存块块号是1我们可以把它放到 0 位置。第二个是2我们可以把 2 号主存块放到 1 这个位置。3、4也是类似的。
image.png

访问了前 4 个主存块之后 cache 里的情况就是上图这个样子 。

接下来 1 和2它们已经在 cache 当中所以可以命中。
image.png

再接下来要访问5此时就必须把其中的某一个主存块给替换出去。

根据算法的规则我们要替换的是最久没有被访问过的一个主存块。

我们可以从 5 位置从这个位置开始往前看。 2 最近被访问过1 最近被访问过。 4 最近被访问过。所以此时 cache 里边这几个主存块最久没有被访问过的应该是3号块。
image.png

所以在这个时候我们可以淘汰3调入5其他的几个保持不变。
image.png

再接下来 1 和 2 也可以命中然后又要访问到 3 号主存块 3 号没有在 cache 当中。和之前的处理方法类似我们从2号这个位置往前看 2、1、5 是最近被访问过的所以最久没有被访问过的应该是4号块。
image.png

所以我们淘汰4号换入3号其他的几个保持不变。
image.png

这就是我们做题的时候可以采取的一个方法。

当需要替换一个 cache 块的时候从当前访问的主存块号位置开始往前看一下哪些主存块是最近被访问过的。

从后往前看最后一个出现的主存块号应该是需要替换的主存块后续的两个就不再展开。这是我们做题的时候可以采取的一个比较快的方法。

2.硬件角度

接下来我们再来看一下用硬件站在机器的角度它是如何实现近期最少使用算法的。

上一小节中我们说过每一个 cache 行需要有一个标记用来记录 cache 行里边所存储的主存块号另外还需要增加一个有效位。除了这些信息之外如果要使用LRU 这种算法我们还必须给每一个 cache 行添加这样的一个属性就是计数器

刚开始所有的 cache 行都是空的计数器也会被全部置为0。
image.png

计数器的变化规则是这样的。

如果我们访问某一个主存块号在 cache 里边没有命中此时如果还有空闲的 cache 行我们就会把主存块装入到一个空闲的行里边同时把这个 cache 行所对应的计数器置为0其余的非空闲的 cache 行计数器会全部加1。

来看一下什么意思。

<1> 刚开始我们访问的是 1 号主存块此时没有命中并且还依然有空闲的 cache 行所以我们会把 1 号储存块放到 cache 0 这个位置把 cache 行所对应的计数器设置为0其余的非空闲行需要把计数器全部加1。
image.png

在这个时刻其他这些 cache 行都是空闲的所以它们的计数器我们不需要管不需要加1。

<2> 接下来访问 2 号主存块我们可以把它调入到 cache 1 这个位置并且把它的计数器设为0同时把其它的非空闲 cache 行所对应的计数器加1。
image.png

此时 cache 0 的计数器变为了1。

注意理解计数器的逻辑它想要反映的是 cache 块已经多久没有被访问了

<3> 接下来是 3 号主存块我们把它放到 cache 2 这个位置计数器设为0同时其他的这些非空闲Cache行计数器加1。
image.png

<4>再接下来访问 4 号也是类似的其他的这些计数器都会加1。
image.png

<5> 接下来要访问的是 1 号主存块。

显然1号主存块此时已经在 cache 当中是可以命中的。

当我们命中之后我们会把所命中的 cache 行它的计数器清零。同时计数器的值比它更低的其它的那些计数器我们会把它加1其余不变。
image.png

总之我们此时访问了 0 号 cache 块它的计数器应该从 3 变为0计数器的值比 3 更小的这些cache行它的计数器的值都要加 1。2 变 3、1 变 2、0 变1。

所以这种方式可以保证我们最近访问过的主存块它的计数器的值肯定是最小的可以恢复成0。

越久没有被访问过的cache行它的计数器的值会不断加1就会变得越来越大。

<6> 接下来要访问的是 2 号主存块显然也是可以命中的。

和之前的处理方式一样我们会把当前访问的 cache 行把它计数器的值清零另外其他计数器的值都加1。
image.png

<7> 接下来要访问的是 5 号主存块此时 cache 没有命中。

我们必须选择替换某一个 cache 块。按照这个算法的规则我们会替换掉计数器的值最大的一个 cache 块也就是 2 号它的计数器是3这个cache 块当中存放的是 3 号主存块。

所以最后我们把 3 号主存块替换掉 将5 号主存块放到这个位置。
image.png

同时把计数器的值清零其余的计数器的值全部加1。
image.png

<8>接下来要访问的是1此时 1 是可以命中的。

因此我们会把 1 号主存块所存放的 cache 行它的计数器给清零。 另外比这个计数器的值更小的那些计数器的值我们需要加1。

也就是我们只需要把比 2 更小的 1 和 0 这两个计数器的值加1而比 2 更大的计数器3的值我们不需要加1。
image.png

思考一下我们把 2 变为了 01 和0分别加了1。

我们当然也可以把 3 同样也进行一个加1变成4。但是把 3 变为 4 其实毫无意义。让它的值保留原本的 3 也可以达到同样的效果。

因为我们设置计数器的目的其实是想通过计数器的值的大小来判断我们应该替换哪一个主存块。

我们想要选择的是计数器的值最大的一个 cache 块会把它给替换掉。 3这个值本来就已经是最大的所以我们再让 3 继续加1其实是没有意义的。

这种处理策略的好处就是当我们只有 4 个 cache 行的时候我们的 4 个计数器的值肯定是0、1、2、3。只有可能出现这几种情况不可能出现4这种情况。所以注意体会这个细节。

<9> 接下来访问 2 号主存块 2 号也可以命中。

我们会把 2 号块所对应的计数器把它变为0同时把计数器更小的这些值让它加1计数器更大的3让它保持不变。
image.png

<10> 接下来要访问的是3此时 cache 没有命中并且已经没有空闲的 cache 行了。

所以我们会选择计数器的值最大的 cache 块进行淘汰把 4 号主存块淘汰出去把 3 号主存块换进来。
image.png

另外还需要修改计数器的值为0其余的这些计数器都需要加1。

<11> 再往后访问 4 没有命中。

我们同样需要把计数器最大的给它替换掉就变成这个样子。
image.png

<12> 接下来访问 5 也是类似的没有命中。

我们把计数器最大的这一个给它替换掉其余的这些计数器都需要加1。
image.png

这就是LRU算法

2分析

我们模拟机器的执行比我们手算要麻烦一些但是机器对计数器进行这样的处理是有好处的。

刚才我们说过采用这样的策略可以保证所有的这些计数器的值只有可能出现0、1、2、3这也就意味着当我们的 cache 块的总数只有 2 的 n 次方这么多块的时候我们就只需要 n 个比特位来作为计数器就可以。
image.png

比如这个例子当中我们只有 4 个 cache 块我们就只需要 2 比特的信息来表示计数器就可以 2 比特刚好可以表示 0123 这几种数字。

所以这样的策略就保证了当我们用硬件实现替换算法的时候硬件电路的设计可以变得更简单我们只需要增加两个比特的冗余信息就可以。
image.png

很显然这个算法它其实是考虑到了局部性原理的。

因为基于时间局部性可以知道我们近期访问过的主存块在不久的将来也很有可能会被再次访问。所以这种算法的思想就是每一次会淘汰最久没有访问过的主存块。这种策略是合理的遵循的局部性原理。

所以这个算法在实际当中运行效果会很优秀 cache 的命中率很高。


这就是LRU算法虽然这个算法很优秀但是如果我们频繁访问到的主存块的数量要比 cache 行的数量要更大我们也有可能会发生抖动现象

比如我们按 12345、12345 这样的顺序来访问各个主存块此时被我们频繁访问到的主存块总共有 5 块而 cache 行的数量只有4。

大家可以自己模拟一下。如果是这样的访问序列即便是采用LRU算法依然会发生抖动现象这就不再展开。

五、最不经常使用算法

1过程

接下来我们看小结的最后一种算法最不经常使用算法叫** LFU**。
image.png

f 指的是频率frequently和 LRU算法类似我们也需要给每个 cache 块 cache 行)设置一个计数器只不过它这儿的计数器是用于记录每一个 cache 块到目前为止被访问过了多少次。

当我们需要替换某一个块的时候我们会选择计数器最小的也就是被访问次数最少的一个进行替换。


还是用刚才的例子来看一下。

刚开始我们需要把计数器都设为0。
image.png

计数器的变化规则是这样的。

当我们调入一个新的块时候这个块所对应的计数器会置为0之后这个块每被访问一次计数器的值就会加1。

<1> 所以刚开始我们访问1234只需要把这几个主存块分别的调入到 cache 的相应位置。
image.png

由于第一次被调入的时候计数器的值都是置为0所以计数器此时是 4 个0。

<2> 接下来要访问 11 号主存块命中我们就可以让它计数器的值加1。

再接下来访问 22 号主存块命中与它所对应的 cache 行计数器也会加1。
image.png

<3> 接下来访问5没有命中。

此时就需要替换一个块。按照算法的规则我们会替换掉计数器最小的一行。

不过现在大家会发现我们 2 和 3 这两行的计数器的值都是最小的都是0到底替换哪一块

通常来说可以有这样的两种处理策略。

①第一种策略就是按照行号也就是按照cache行号递增的次序来判断它们的优先级。

比如我可以选择优先淘汰 cache 行号更小的这是第一种策略。

②第二种策略也可以按照先进先出的规则来给他们进行排序。

对于这个例子来说 2 和 3 这两个 cache 行它里边存入的主存块应该是 2 号 cache 行的最先被调入的。
image.png

所以按照先进先出的规则我们会优先淘汰 2 号 cache 块里边存放的内容。

所以我们把 3 号主存块给淘汰掉相应的位置换入 5 号。
image.png

<4> 再接下来 1 和 2 又再次会被访问这两次访问都可以命中所以我们需要把 1 和 2 所对应的这两个计数器都加 1 。
image.png

<5> 再往后访问到3此时又需要运行一次替换算法。

同样的Cache2和Cache3它们的计数器都是最小的我们可以选择按照行号递增的次序来给它们进行一个优先级的排序。

我们会选择淘汰行号更小的 cache 块所以我们把 5 换出 把 3 换入。
image.png

<6> 接下来 4 号可以命中。

与 4 号相对应的 cache 行它的计数器加1。
image.png

<7> 最后要访问 5 号。

这个时候计数器最小的 cache 行只有一个。所以毫无疑问我们需要淘汰的是 3 这个主存块然后换入 5 号。
image.png

这就是 LFU算法

2分析

显然采用这种算法这个计数器的值有可能是 0到1一个很大的数。

所以如果要用硬件实现每个 cache 行所对应的计数器就需要用比较长的几个二进制比特位来表示。

另一个方面LFU这种算法看起来好像很科学这个计数器相当于我们对每一个 cache 块被访问的次数进行了一个总体的统计对吧看起来好像很科学。

总体来看被访问次数越多的我们就越有可能把它留住。

但事实上考虑到时间局部性原理我们不难想到曾经经常会被访问的主存块在未来其实不一定会被用到。

比如大家使用微信视频聊天的时候和视频聊天相关的那些块的数据显然在一段时间内经常会被访问。这就意味着与这些块相对应的计数器在你使用视频聊天的这段时间内会一直增加加到一个很大的值。之后你不再需要视频聊天了。

但是由于这些块的计数器已经变得很大了所以接下来这些块在 cache 当中的数据副本很有可能在长时间内不会被淘汰。

因此这种算法实际运行效果其实也不好。它并没有遵循局部性原理。

所谓局部性其实只需要考虑到最近的一小个局部而不需要像这个算法这样有可能会记录下整个全局的一个访问的频率。

所以这个算法看起来科学但实际上它的 cache 命中率可能也不高。

六、总结回顾

这个小节当中我们学习了 4 种 cache 替换算法。
image.png

因为 cache 的存储容量很小而主存的存储容量很大所以我们不得不考虑到当 cache 存满了之后我们需要替换哪些数据这样的问题。

随机算法和先进先出很好理解。

稍微复杂一点的是近期最少使用这个算法但是这个算法的实际运行效果就是 cache 的命中率在这几个算法当中是最优秀的。所以我们考试最经常考察的也还是这个算法。

不过我们手动做题的时候大多数情况下我们也不需要写出计数器的值怎么变化大家可以用我们刚才提到的更快的那种方法来快速地做题。大家也需要理解这种算法计数器它的一个工作原理。

以上就是小节的全部内容。

阿里云国内75折 回扣 微信号:monov8
阿里云国际,腾讯云国际,低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号:monov8 飞机:@monov6