基于LRU算法的缓存内存计算

Question

假设我有4个缓存内存块，在以下访问内存块的序列上使用LRU (最近使用最少的)替换算法:1 2 3 4 5 5 5 4 1 5 2 3：

1   2   3   4   5   2   5   4   1   5   2   3

1   1   1   1   5   5   5   5   5   5   5   5
    2   2   2   2   2   2   2   2   2   2   2
        3   3   3   3   3   3   1   1   1   1
            4   4   4   4   4   4   4   4   3

最后，缓存内存将包含以下内存块："5 2 1 3“。

但正确的结果是"1 5 2 3“

请告诉我我在这里做错了什么！

编辑：

老实说，我正在做一次运动，除了这里，我什么地方都得不到帮助，而且可能是我误解了这个问题，所以这是最初的问题：

​

​

Answer 1

所以我对LRU的模拟是错的吗？老实说我还是不明白！

模拟在第5列中出错，您可以将最新数据添加到最老的位置。

以下是更正：

            1   2   3   3   3   2   2   4   1  <-- Oldest accesses
        1   2   3   4   4   2   5   4   1   5
    1   2   3   4   5   2   5   4   1   5   2
1   2   3   4   5   2   5   4   1   5   2   3  <-- Newest accesses

• 注意，最新的行总是等于您的输入序列。
• 其他元素一次只老化一行，除非它们被带着新的通道带到前面。

Answer 2

在一个简单的缓存中，顺序并不重要。LRU算法非常简单，不需要运行整个仿真程序。只需看一下序列中的最后4个数字：

... 1 5 2 3

Answer 3

根据亚伯拉罕·西尔伯沙茨操作系统概念，第8版，第9章，图9.15。CPU中缓存的顺序并不重要。重要的是缓存错误率或页面错误率。

然而，在这个问题中，询问的是CPU中的缓存顺序，而不是缓存中的顺序。雷蒙德·赫廷格的方法会给你正确的答案。

不幸的是，良好的CPU设计不会以这种方式工作。因为，每个缓存块都必须使用每个输入的新数据刷新。这就挫败了使用缓存的目的！