一、引子
这个小结我们要学习的是 cache 的替换算法。
（1）有待解决的问题
在之前的小结中，我们留下了这样的 3 个问题。
上一个小结我们解决了第一个问题，而第二个问题就是，我们的 cache 是很小的，主存是很大的。
但是每一次被访问的主存块一定会被立即掉入 cache 当中，这就意味着 cache 很容易被装满。当 cache 装满之后，我们应该怎么办？
这就是替换算法要解决的问题。
（2）地址映射方式
我们要结合上一小节学习的这些地址映射方式来进行考虑。 
①第一种全相联映射。
这种映射方式意味着每一个主存块有可能会被放到 cache 的任何一个位置，所以如果采用这种映射方式，就意味着只有整个 cache 全部被装满之后，我们才需要在整个 cache 当中选择一个 cache 块，把它进行替换。
②第二种直接映射方式。
对于任何一个主存块，我们只能把它放到一个指定的特定的位置。这就意味着，如果这个位置原来已经有数据了，我们直接把原来的这份数据给替换掉、淘汰掉就可以了。
所以，如果采用直接映射方式，其实我们不需要考虑替换算法到底要替换哪一块这样的问题，我们毫无选择，只能放到固定的位置。
③第三种组相联映射。
每一个主存块会被放到指定分组当中的任何一个位置。所以如果采用这种方式，就意味着只有内存块它所属的 cache 分组整个组都被装满之后，我们才需要选择到底要替换哪一块。
所以替换算法只会被用到全相联映射，还有组相联映射这两种方式。直接映射的时候不需要考虑替换算法。
这个小节的讲解中，我们会以全相联映射为例，学习 4 种替换算法。
第一种是随机算法，第二种先进先出，第三种近期最少使用，第四种叫最近不经常使用。
同学们也需要注意各种算法的英文缩写。
二、随机算法
（1）过程
首先来看第一种随机算法。
顾名思义就是如果 cache 满了，我们随机选择一块进行替换，非常的free。
来看这样一个例子，假设有一个系统当中，它的 cache 块总共有 4 个，初始的时候所有的 cache 块都是空的，采用全相邻联映射方式。 
接下来我们访问的主存块编号分别是这样的一个序列，也就是先访问 1 号主存块，再访问 2 号、 3 号、 4 号，再访问 1 号、 2 号，以此类推。
总共 4 个Cache块，并且刚开始所有的块都是空的。
所以我们刚开始访问 1、2、3、4 这几个主存块的时候，需要把这些主存块依次调入到 cache 当中。
把1 号主存块放到 0 号 cache 这个位置， 把2 号主存块放到 1 号 cache 这个位置。接下来 3 号和 4 号主存块也是类似，把它放到 cache 的相应位置。
刚开始访问的这几个主存块，都是没有命中的。每访问一个主存块，就需要把这一块的数据从主存调入到cache。
由于前边的这 4 次访问， cache 一直都没被装满，所以我们不需要进行 cache 替换算法。
继续往后。
接下我们要访问的是 1 号主存块，由于此时 1 号主存块已经存放在 cache 当中，所以这一次的访问是可以命中的。
接下来 2 号也是一样，也可以命中。
再接下来 5 号，由于此时 4 个 cache 块当中存放的主存块分别是 1234 号， 5 号主存块此时没有被调入cache。
而我们之前说过，每访问到一个主存块，就一定需要把主存块立即调入 cache 。
所以此时我们就需要根据 cache 块的替换算法来决定要替换哪一块。
根据随机算法的规则，可以随便选择一个块进行替换。
比如我们把 3 号主存块给换出去，换入 5 号主存块，没有任何规律，我们随便选的一个位置。
接下来 1 号和 2 号的访问都可以命中。
再接下来访问到 3 号块，此时 3 号主存块没有放到 cache 当中。所以同样的，我们随机选择一个块进行替换。假如我们把 4 号主存块换出去，把 3 号主存块换到它原先存放的位置，也就是 3 号cache行这个地方。
接下来又需要访问 4 号主存块，我们随机挑一个，把 1 号主存块给换出去，把 4 号换进来。
接下来访问 5 号储存块， 5 号此时是在 cache 当中的，所以可以直接命中，不需要发生替换。
这就是随机算法。
（2）分析
这种算法毫无规律，我们并没有考虑到什么程序的局部性之类的这些因素，所以这种算法它实际的运行效果会很不稳定， cache 的命中率可能会很低。 
三、先进先出算法
（1）过程
接下来看第二个先进先出算法。
顾名思义，就是我们会优先把最先被调入 cache 的块给它替换出去。
还是用刚才那个例子。
刚开始访问 1、2、3、4 这几个主存块的时候，由于 cache 初始是空的，所以我们只需要把这些主存块分别调入到 cache 的相应位置就可以。 
接下来访问 1 和2，这两个显然是可以命中了。
再接下来访问 5 号主存块。 5 号主存块此时并没有在 cache 当中。
根据先进先出的规则，此时我们放在 cache 里的这些主存块，最先被调入的应该是 1 号主存块，所以我们会优先淘汰 1 号主存块，然后把 5 号主存块放到 cache 0 位置。
接下来我们又要访问 1 号。 1 号刚才被我们淘汰了，现在又需要把 1 号调入cache。
此时我们放在 cache 里的这几个块当中，最先被调入的应该是 2 号 cache 块。所以我们会淘汰 2 号，放入 1 号。
淘汰 2 号之后，紧接着又访问 2 号。类似的原理，在剩下的这几个主存块当中，最先被调入的应该是 3 号块，所以淘汰 3 号，放入 2 号。
接下来访问 3 号。应该淘汰 4 号，掉入 3 号。
再接下来访问 4 号储存块。剩下的这些块当中，最先被调入的应该是 5 号。所以淘汰5，放入4。
接下来又访问5，此时剩余的最先被调入的应该是 1 号，所以换出 1 调入5。
这就是先进先出算法，很好理解，并且用硬件实现也很简单。
（2）分析
刚开始 cache 的所有行都是空的，我们可以按照行号递增的次序 0123 这样的次序来依次放入最初始的几个内存块。接下来我们只需要按照 0123、0123 这样的次序来替换各个块就可以了。
因为按照刚才这种策略，我们最先放入的就是 0 位置，所以我们最先应该淘汰的也是 0 位置。 0 这个位置被替换之后，接下来最先调入的应该就是处于 1 位置对吧？所以接下来还需要替换的话，我们替换1，1替换之后再往后想要替换，就替换 2 就可以了。
所以先进先出算法，用硬件实现起来也会很简单，只需要轮流的替换各个 cache 行就可以。
但是先进先出也没有考虑到局部性原理，因此 cache 的命中率也会很低。
最先被调入 cache 的块，也有可能在之后会被频繁地访问到。
这个应该不难理解，比如大家写的 c 语言程序，很有可能在刚开始的时候就调用到了 print f 这个函数，这个函数你是最开始就使用到的，这并不意味着再往后这个函数你就用不到了，对吧？
所以我们把最先调入 cache 的给淘汰，这种处理策略是不科学的。因此先进先出这种替换算法实际的运行效果也不太理想。
另外，刚才我们分析到后面这个部分的时候，大家会发现我们出现了这样的一个有意思的现象，就是在这个地方，我们换出了1，换入了5， 1 刚被换出，紧接着又访问了1，所以我们不得不换出2，然后再换入1。而 2 刚被换出，接下来又访问到了2，所以就出现了这种频繁的换入换出的现象。
这种现象被称为抖动现象，刚被换出的块，很快又被访问，所以紧接着又会被调入。
四、近期最少使用
（1）过程
第三个算法叫近期最少使用，英文缩写叫LRU。
这个算法的思想是这样的，我们会为每一个 cache 块（ cache 行）设置一个计数器，用于记录 cache 块里面存放的主存块已经多久没有被访问过了。
当我们需要替换的时候，我们会选择计数器最大的一个 cache 块把它替换出去。
计数器最大是不是就意味着这个块是最久没有被访问过的。
还是用刚才那个例子体会一下。 
1.手算
首先跟大家介绍一个手算做题的方法。
我们先不考虑机器是如何执行的。总共有 4 个 cache 块，刚开始都是空的。
第一个被访问的主存块，块号是1，我们可以把它放到 0 位置。第二个是2，我们可以把 2 号主存块放到 1 这个位置。3、4也是类似的。
访问了前 4 个主存块之后， cache 里的情况就是上图这个样子 。
接下来 1 和2，它们已经在 cache 当中，所以可以命中。
再接下来要访问5，此时就必须把其中的某一个主存块给替换出去。
根据算法的规则，我们要替换的是最久没有被访问过的一个主存块。
我们可以从 5 位置，从这个位置开始往前看。 2 最近被访问过，1 最近被访问过。 4 最近被访问过。所以此时 cache 里边这几个主存块最久没有被访问过的应该是3号块。
所以在这个时候我们可以淘汰3，调入5，其他的几个保持不变。
再接下来 1 和 2 也可以命中，然后又要访问到 3 号主存块， 3 号没有在 cache 当中。和之前的处理方法类似，我们从2号这个位置往前看， 2、1、5 是最近被访问过的，所以最久没有被访问过的应该是4号块。
所以我们淘汰4号，换入3号，其他的几个保持不变。
这就是我们做题的时候可以采取的一个方法。
当需要替换一个 cache 块的时候，从当前访问的主存块号位置开始，往前看一下哪些主存块是最近被访问过的。
从后往前看，最后一个出现的主存块号，应该是需要替换的主存块，后续的两个就不再展开。这是我们做题的时候可以采取的一个比较快的方法。
2.硬件角度
接下来我们再来看一下，用硬件，站在机器的角度，它是如何实现近期最少使用算法的。
上一小节中我们说过，每一个 cache 行需要有一个标记，用来记录 cache 行里边所存储的主存块号，另外还需要增加一个有效位。除了这些信息之外，如果要使用LRU 这种算法，我们还必须给每一个 cache 行添加这样的一个属性，就是计数器。
刚开始所有的 cache 行都是空的，计数器也会被全部置为0。 
计数器的变化规则是这样的。
如果我们访问某一个主存块号在 cache 里边没有命中，此时如果还有空闲的 cache 行，我们就会把主存块装入到一个空闲的行里边，同时把这个 cache 行所对应的计数器置为0，其余的非空闲的 cache 行计数器会全部加1。
来看一下什么意思。
<1> 刚开始我们访问的是 1 号主存块，此时没有命中，并且还依然有空闲的 cache 行，所以我们会把 1 号储存块放到 cache 0 这个位置，把 cache 行所对应的计数器设置为0，其余的非空闲行需要把计数器全部加1。
在这个时刻，其他这些 cache 行都是空闲的，所以它们的计数器我们不需要管，不需要加1。
<2> 接下来访问 2 号主存块，我们可以把它调入到 cache 1 这个位置，并且把它的计数器设为0，同时把其它的非空闲 cache 行所对应的计数器加1。
此时 cache 0 的计数器变为了1。
注意理解计数器的逻辑，它想要反映的是 cache 块已经多久没有被访问了。
<3> 接下来是 3 号主存块，我们把它放到 cache 2 这个位置，计数器设为0，同时其他的这些非空闲Cache行计数器加1。
<4>再接下来访问 4 号也是类似的，其他的这些计数器都会加1。
<5> 接下来要访问的是 1 号主存块。
显然，1号主存块此时已经在 cache 当中，是可以命中的。
当我们命中之后，我们会把所命中的 cache 行它的计数器清零。同时，计数器的值比它更低的其它的那些计数器，我们会把它加1，其余不变。
总之，我们此时访问了 0 号 cache 块，它的计数器应该从 3 变为0，计数器的值比 3 更小的这些cache行它的计数器的值都要加 1。2 变 3、1 变 2、0 变1。
所以这种方式可以保证我们最近访问过的主存块，它的计数器的值肯定是最小的，可以恢复成0。
越久没有被访问过的cache行它的计数器的值会不断加1，就会变得越来越大。
<6> 接下来要访问的是 2 号主存块，显然也是可以命中的。
和之前的处理方式一样，我们会把当前访问的 cache 行把它计数器的值清零，另外其他计数器的值都加1。
<7> 接下来要访问的是 5 号主存块，此时 cache 没有命中。
我们必须选择替换某一个 cache 块。按照这个算法的规则，我们会替换掉计数器的值最大的一个 cache 块，也就是 2 号，它的计数器是3，这个cache 块当中存放的是 3 号主存块。
所以最后我们把 3 号主存块替换掉， 将5 号主存块放到这个位置。
同时把计数器的值清零，其余的计数器的值全部加1。
<8>接下来要访问的是1，此时 1 是可以命中的。
因此我们会把 1 号主存块所存放的 cache 行它的计数器给清零。 另外，比这个计数器的值更小的那些计数器的值，我们需要加1。
也就是我们只需要把比 2 更小的 1 和 0 这两个计数器的值加1，而比 2 更大的计数器3的值，我们不需要加1。
思考一下，我们把 2 变为了 0，1 和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让它保持不变。
<10> 接下来要访问的是3，此时 cache 没有命中，并且已经没有空闲的 cache 行了。
所以我们会选择计数器的值最大的 cache 块进行淘汰，把 4 号主存块淘汰出去，把 3 号主存块换进来。
另外还需要修改计数器的值为0，其余的这些计数器都需要加1。
<11> 再往后访问 4 ，没有命中。
我们同样需要把计数器最大的给它替换掉，就变成这个样子。
<12> 接下来访问 5 也是类似的，没有命中。
我们把计数器最大的这一个给它替换掉，其余的这些计数器都需要加1。
这就是LRU算法。
（2）分析
我们模拟机器的执行比我们手算要麻烦一些，但是机器对计数器进行这样的处理是有好处的。
刚才我们说过，采用这样的策略，可以保证所有的这些计数器的值只有可能出现0、1、2、3，这也就意味着，当我们的 cache 块的总数只有 2 的 n 次方这么多块的时候，我们就只需要 n 个比特位来作为计数器就可以。
比如这个例子当中，我们只有 4 个 cache 块，我们就只需要 2 比特的信息来表示计数器就可以， 2 比特刚好可以表示 0123 这几种数字。
所以这样的策略就保证了当我们用硬件实现替换算法的时候，硬件电路的设计可以变得更简单，我们只需要增加两个比特的冗余信息就可以。
很显然，这个算法它其实是考虑到了局部性原理的。
因为基于时间局部性，可以知道，我们近期访问过的主存块，在不久的将来也很有可能会被再次访问。所以这种算法的思想就是每一次会淘汰最久没有访问过的主存块。这种策略是合理的，遵循的局部性原理。
所以这个算法在实际当中运行效果会很优秀， cache 的命中率很高。
这就是LRU算法，虽然这个算法很优秀，但是如果我们频繁访问到的主存块的数量要比 cache 行的数量要更大，我们也有可能会发生抖动现象。
比如我们按 12345、12345 这样的顺序来访问各个主存块，此时被我们频繁访问到的主存块总共有 5 块，而 cache 行的数量只有4。
大家可以自己模拟一下。如果是这样的访问序列，即便是采用LRU算法，依然会发生抖动现象，这就不再展开。
五、最不经常使用算法
（1）过程
接下来我们看小结的最后一种算法，最不经常使用算法，叫 LFU。
f 指的是频率frequently，和 LRU算法类似，我们也需要给每个 cache 块 （cache 行)设置一个计数器，只不过它这儿的计数器是用于记录每一个 cache 块到目前为止被访问过了多少次。
当我们需要替换某一个块的时候，我们会选择计数器最小的，也就是被访问次数最少的一个进行替换。
还是用刚才的例子来看一下。
刚开始我们需要把计数器都设为0。
计数器的变化规则是这样的。
当我们调入一个新的块时候，这个块所对应的计数器会置为0，之后这个块每被访问一次，计数器的值就会加1。
<1> 所以刚开始我们访问1234，只需要把这几个主存块分别的调入到 cache 的相应位置。
由于第一次被调入的时候，计数器的值都是置为0，所以计数器此时是 4 个0。
<2> 接下来要访问 1，1 号主存块命中，我们就可以让它计数器的值加1。
再接下来访问 2，2 号主存块命中，与它所对应的 cache 行，计数器也会加1。 
<3> 接下来访问5，没有命中。
此时就需要替换一个块。按照算法的规则，我们会替换掉计数器最小的一行。
不过现在大家会发现，我们 2 和 3 这两行的计数器的值都是最小的，都是0，到底替换哪一块？
通常来说可以有这样的两种处理策略。
①第一种策略就是按照行号，也就是按照cache行号递增的次序来判断它们的优先级。
比如我可以选择优先淘汰 cache 行号更小的，这是第一种策略。
②第二种策略，也可以按照先进先出的规则来给他们进行排序。
对于这个例子来说， 2 和 3 这两个 cache 行，它里边存入的主存块，应该是 2 号 cache 行的最先被调入的。
所以按照先进先出的规则，我们会优先淘汰 2 号 cache 块里边存放的内容。
所以我们把 3 号主存块给淘汰掉，相应的位置换入 5 号。
<4> 再接下来， 1 和 2 又再次会被访问，这两次访问都可以命中，所以我们需要把 1 和 2 所对应的这两个计数器都加 1 。
<5> 再往后访问到3，此时又需要运行一次替换算法。
同样的，Cache2和Cache3它们的计数器都是最小的，我们可以选择按照行号递增的次序来给它们进行一个优先级的排序。
我们会选择淘汰行号更小的 cache 块，所以我们把 5 换出 ，把 3 换入。
<6> 接下来 4 号，可以命中。
与 4 号相对应的 cache 行，它的计数器加1。
<7> 最后要访问 5 号。
这个时候计数器最小的 cache 行只有一个。所以毫无疑问，我们需要淘汰的是 3 这个主存块，然后换入 5 号。
这就是 LFU算法。
（2）分析
显然，采用这种算法，这个计数器的值有可能是 0到1一个很大的数。
所以如果要用硬件实现每个 cache 行所对应的计数器，就需要用比较长的几个二进制比特位来表示。
另一个方面，LFU这种算法看起来好像很科学，这个计数器相当于我们对每一个 cache 块被访问的次数进行了一个总体的统计，对吧？看起来好像很科学。
总体来看，被访问次数越多的我们就越有可能把它留住。
但事实上，考虑到时间局部性原理，我们不难想到，曾经经常会被访问的主存块，在未来其实不一定会被用到。
比如大家使用微信视频聊天的时候，和视频聊天相关的那些块的数据，显然在一段时间内经常会被访问。这就意味着，与这些块相对应的计数器，在你使用视频聊天的这段时间内会一直增加，加到一个很大的值。之后你不再需要视频聊天了。
但是，由于这些块的计数器已经变得很大了，所以接下来这些块在 cache 当中的数据副本很有可能在长时间内不会被淘汰。
因此这种算法实际运行效果其实也不好。它并没有遵循局部性原理。
所谓局部性，其实只需要考虑到最近的一小个局部，而不需要像这个算法这样有可能会记录下整个全局的一个访问的频率。
所以这个算法看起来科学，但实际上它的 cache 命中率可能也不高。
六、总结回顾
这个小节当中，我们学习了 4 种 cache 替换算法。
因为 cache 的存储容量很小，而主存的存储容量很大，所以我们不得不考虑到当 cache 存满了之后，我们需要替换哪些数据这样的问题。
随机算法和先进先出很好理解。
稍微复杂一点的是近期最少使用这个算法，但是这个算法的实际运行效果，就是 cache 的命中率在这几个算法当中是最优秀的。所以我们考试最经常考察的也还是这个算法。
不过我们手动做题的时候，大多数情况下我们也不需要写出计数器的值怎么变化，大家可以用我们刚才提到的更快的那种方法来快速地做题。大家也需要理解这种算法计数器它的一个工作原理。
以上就是小节的全部内容。
