使用时间戳实现 LRU：内存存储和加载的成本有多高？

Question

我说的是用 C 实现的 LRU 内存页面替换算法，而不是用 Java 或 C++ 实现。

根据操作系统课程笔记：

好的，那么我们如何实际实现 LRU 呢？想法1）：用时间戳标记我们接触过的一切。每当我们需要驱逐页面时，我们都会选择最旧的页面（=最近最少使用）。事实证明，这个简单的想法并不那么好。为什么？因为对于每个内存加载，我们都必须读取时钟的内容并执行内存存储！因此很明显，保留时间戳将使计算机速度至少慢一倍。我

内存加载和存储操作应该非常快。真的有必要摆脱这些微小的操作吗？

在内存替换的情况下，从磁盘加载页面的开销应该比内存操作大很多。为什么要真正关心内存存储和加载？

如果注释所说的不正确，那么使用时间戳实现 LRU 的真正问题是什么？

编辑：

当我深入挖掘时，我能想到的原因如下。这些内存存储和加载操作在页面命中时发生。在这种情况下，我们没有从磁盘加载页面，因此比较无效。

由于预计命中率会非常高，因此更新与LRU相关的数据结构应该非常频繁。这就是为什么我们关心更新过程中重复的操作，例如内存加载和存储。

但我仍然无法相信内存加载和存储的开销有多大。周围应该有一些测量值。有人可以指点我吗？谢谢！

Answer 1

内存加载和存储操作可能非常快，但在大多数实际情况下，内存子系统比 CPU 的执行引擎慢（有时慢得多）。

内存访问时间的粗略数字：

• L1 缓存命中：2-4 个 CPU 周期
• L2 缓存命中：10-20 个 CPU 周期
• L3 缓存命中：50 个 CPU 周期
• 主存访问：100-200 个 CPU 周期

因此，加载和存储会花费实时时间。使用 LRU，每次常规内存访问也会产生内存存储操作的成本。仅此一项就使 CPU 的内存访问次数增加了一倍。在大多数情况下，这会减慢程序的执行速度。此外，在页面驱逐时，需要读取所有时间戳。这会很慢。

此外，不断读取和存储时间戳意味着它们将占用 L1 或 L2 缓存中的空间。这些缓存中的空间是有限的，因此其他访问的缓存未命中率可能会更高，这将花费更多时间。

简而言之 - LRU 相当昂贵。