algorithm - 为什么 LRU 比 FIFO 好？

Question

为什么最近最少使用的页面文件比 FIFO 更好？

Answer 1

如果您的意思是将内存页面卸载到磁盘 - 如果您的进程经常访问一个页面，那么您真的不希望它被分页到磁盘，即使它是您访问的第一个页面。另一方面，如果您已经好几天没有访问内存页面，那么您不太可能在不久的将来这样做。

如果这不是您的意思，请编辑您的问题以提供更多详细信息。

Answer 2

没有一种单一的缓存算法会一直做得很好，因为这需要对未来有完全的了解。（如果你知道从哪里得到它……） LRU 在 VM 缓存设计中的主导地位是长期测量系统行为的结果。给定实际工作负载，LRU 在很大一部分时间里都能很好地工作。但是，构造一个引用字符串并不难，FIFO 的性能优于 LRU。

考虑对比可用的可分页实内存大得多的大地址空间进行线性扫描。LRU 是基于“你最近触摸过的东西很可能会再次触摸”的假设，但是线性扫描完全违反了这个假设。这就是为什么一些操作系统允许程序就它们的引用行为向内核提供建议的原因——一个例子是经典 LISP 解释器所代表的“标记和清除”垃圾收集。（并且是“世代”等更现代的 GC 工作的主要驱动力。）

另一个例子是某个古董宏处理器（STAGE2）中的符号表。从根开始搜索二叉树以查找每个符号，并且在堆栈上进行字符串评估。事实证明，通过“向下连接”符号树的根页面和堆栈的底部页面来减少可用的页框可以极大地提高页面错误率。缓存很小，而且搅动得很厉害，总是推出两个最常被引用的页面，因为缓存小于这些页面的相互引用距离。所以一个小的缓存效果更好，但这只是因为从缓存中窃取的那两个页面框架被明智地使用了。

所有这一切的结果是，LRU 是标准答案，因为它通常非常适合系统上的实际工作负载，这些工作负载并没有严重超载（VM 是可用实际内存的许多倍），并且经过多年的仔细测量支持。但是，您当然可以找到替代行为更好的情况。这就是为什么测量真实系统很重要的原因。

Answer 3

将 RAM 视为缓存。为了成为有效的缓存，它需要将最有可能被请求的项目保存在内存中。

LRU 将最近使用的东西保存在内存中。FIFO 保留最近添加的内容。LRU一般来说效率更高，因为一般有内存项被添加一次就不再使用，也有一些项被频繁添加和使用。LRU 更有可能将经常使用的项目保留在内存中。

Answer 4

根据访问模式，FIFO 有时可以击败 LRU。自适应替换缓存是混合的，它根据实际使用模式调整其策略。

Answer 5

根据参考的时间局部性，最近访问过的内存更有可能很快再次被访问。