使用时间戳实现LRU算法：内存的存储和加载代价有多大？

Question

5

我在谈论的是C语言中实现LRU内存页面替换算法，不是Java或C++。

根据操作系统课程notes：

好的，那么我们该如何实现LRU呢？想法1）：用时间戳标记我们接触到的所有内容。每当我们需要驱逐一个页面时，我们选择最老的页面（=最近最少使用）。结果发现，这个简单的想法并不好。为什么？因为对于每个内存加载，我们都必须读取时钟的内容并执行内存存储！所以很明显，保持时间戳会使计算机至少变慢一倍。I

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

在内存替换的情况下，从磁盘加载页面的开销应该比内存操作更重要。我们为什么要关心内存存储和加载呢？

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

编辑：

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

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

但仍然不确定进行内存加载和存储的开销有多大。应该有一些相应的测量数据。有人能指导我吗？谢谢！

- Junji Zhi

这是一个单线程数据结构吗？如果不是，那么来自多个核心的存储到同一个缓存行可能会非常昂贵，并防止扩展。另外，这个数据结构有多大？对 L1 缓存命中的存储很便宜。在不同 NUMA 节点上缓存写操作的存储非常昂贵。 - usr

我们在谈论内存页面置换算法。它位于内存和磁盘之间，而不是L1/L2和内存之间。为什么我们要关心L1/L2呢？ - Junji Zhi

问这个有什么意义呢？你关心性能吗？看起来是的。因此，缓存行为非常相关。 - usr

你说得对。我表达得不太清楚。谢谢！ - Junji Zhi

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Craig S. Anderson · Accepted Answer

内存的读写操作可能非常快，但在大多数实际情况下，内存子系统比CPU的执行引擎要慢得多-有时还要慢得多。

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

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

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

简而言之- LRU非常昂贵。