algorithm - LRU 算法什么时候会 100% 未命中？

Question

我知道这两种让 LRU 算法错过 100% 的方法。

1. 循环访问略大于缓存大小的数据集。

2. 对不经常访问的数据集的任意突发访问，通过替换更频繁使用的条目来污染缓存。

红色表示缓存未命中。

但它有另一种方式“访问具有不同访问频率的块”。

我不知道如何用一个例子来描述它。

Answer 1

LRU 可能会考虑我们访问数据的频率，例如：

Data   1    1    2    2    3    4
Cache1 1(1) 1(2) 1(2) 1(2) 1(2) 1(2)
Cache2           2(1) 2(2) 2(2) 2(2)
Cache3                     3(1) 4(1)

这是在圆括号中的计数器，每次缓存命中相应块时计数器都会增加。因此，由于我们在开始时访问了块 1 和 2 两次，因此块 3 被从缓存中逐出，尽管它比块 1 和 2 使用得更晚。

所以“对具有不同访问频率的块的访问”基本上可能如下所示：

Data   1    1    2    2    3    4    3    4
Cache1 1(1) 1(2) 1(2) 1(2) 1(2) 1(2) 1(2) 1(2)
Cache2           2(1) 2(2) 2(2) 2(2) 2(2) 2(2)
Cache3                     3(1) 4(1) 3(1) 4(1)

所以尽管我们只使用了 3 和 4，LRU 仍然更喜欢保持 1 和 2 更频繁地使用。

另一个示例可能就像您之前的示例一样：我们应该只访问一次块，因此计数器永远不会增加，即：

Data   1    2    3    4    1    2    3
Cache1 1(1) 1(1) 1(1) 4(1) 4(1) 4(1) 3(1)
Cache2      2(1) 2(1) 2(1) 1(1) 1(1) 1(1)
Cache3           3(1) 3(1) 3(1) 2(1) 2(1)

希望这能回答你的问题。