缓存块替换策略 #
缓存块替换策略需要达到的一个目标是：被替换出的数据块应该是将来最晚会被访问的块。然而，对将来即将发生的事情是没有办法预测的，因为处理器并不知道程序将来会访问哪个地址。因此，现在的缓存替换策略都采用了最近最少使用算法（Least Recently Used ，LRU）或者是类似 LRU 的算法。
LRU 的原理很简单，比如程序要顺序访问 B1 、B2、B3、B4、B5 这几个地址块，并且这几个缓存块都映射到缓存的同一个组，同时我们假设缓存采用 4 路组组相连映射，那么当访问 B5 时，B1 就需要被替换出来。要实现这一点，有很多种方式，其中最简单也最容易实现的是利用位矩阵来实现。
首先，我们定义一个行、列都与缓存路数相同的矩阵。当访问某个路对应的缓存块时，先将该路对应的行置为 1，然后再将该路对应的列置为 0。最终结果体现为，缓存块访问时间的先后顺序，由矩阵行中 1 的个数决定，最近最常访问缓存块对应行 1 的个数最多。
假设现在一个四路相连的缓存组包含数据块 B1、B2、B3、B4, 数据块的访问顺序为 B2、B3、B1、B4，那么 LRU 矩阵在每次访问后的变化如下图所示：
你会发现，最终 B2 对应行的 1 的个数最少，所以 B2 将会被优先替换。