我在谈论的是C语言中实现LRU内存页面替换算法,不是Java或C++。
根据操作系统课程notes:
好的,那么我们该如何实现LRU呢?想法1):用时间戳标记我们接触到的所有内容。 每当我们需要驱逐一个页面时,我们选择最老的页面(=最近最少使用)。结果发现,这个简单的想法并不好。为什么?因为对于每个内存加载,我们都必须读取时钟的内容并执行内存存储!所以很明显,保持时间戳会使计算机至少变慢一倍。I
内存加载和存储操作应该非常快。 真的有必要摆脱这些微小的操作吗?
在内存替换的情况下,从磁盘加载页面的开销应该比内存操作更重要。我们为什么要关心内存存储和加载呢?
如果笔记中所说不正确,那么使用时间戳实现LRU的真正问题是什么?
编辑:
随着我深入挖掘,我能想到的原因如下。当页面命中时会发生这些存储和加载内存的操作。在这种情况下,我们不是从磁盘上加载页面,所以比较无效。由于命中率预计非常高,因此更新与LRU相关的数据结构应该非常频繁。这就是为什么我们关心在更新过程中重复执行的操作,例如:内存加载和存储。
但仍然不确定进行内存加载和存储的开销有多大。应该有一些相应的测量数据。有人能指导我吗?谢谢!