为什么最近最少使用算法在页面文件方面比FIFO更好？
5个回答
12
如果你指的是将内存页面卸载到磁盘，那么如果你的进程经常访问一个页面，即使这是你访问的第一个页面，你也不希望它被分页到磁盘上。另一方面，如果你几天没有访问一个内存页面，那么你不太可能在近期内访问它。
如果这不是你的意思，请编辑你的问题并提供更多细节。
如果这不是你的意思，请编辑你的问题并提供更多细节。
- Jon Skeet
4
没有单一的缓存算法可以始终表现良好，因为这需要对未来有完美的了解。(如果你知道在哪里获取它...) LRU在VM缓存设计中的占主导地位是测量系统行为的漫长历史的结果。在实际工作负载下，LRU在很大程度上表现得非常好。然而，很容易构造一个参考字符串，使FIFO在LRU之上具有优越的性能。
考虑对一个比可分页实际内存大得多的大地址空间进行线性扫描。LRU基于“最近访问过的内容很可能会再次访问”，但是线性扫描完全违反了这个假设。这就是为什么一些操作系统允许程序向内核建议其引用行为的原因——一个例子是经典LISP解释器所代表的“标记和清除”垃圾收集。 (也是更现代的GCs如“分代”工作的主要驱动力。)
另一个例子是某个古老的宏处理器(STAGE2)中的符号表。二叉树从根节点开始搜索每个符号，并且字符串评估是在堆栈上完成的。结果发现，通过“固定”符号树的根页面和堆栈底部页面来减少可用页面帧数，可以大大改善页面故障率。缓存非常小，而且它翻滚不停，总是推出两个最常引用的页面，因为缓存比对这些页面的间隔更小。所以小的缓存效果更好，但只是因为从缓存中窃取的这两个页面帧被明智地使用了。
所有这些的结论是，LRU是标准答案，因为在不是极度超载的系统(VM多次实际内存可用)上，它通常对实际工作负载表现得非常好，并且这得到了多年仔细测量的支持。然而，你肯定可以找到替代行为优越的情况。这就是为什么测量真实系统很重要的原因。
考虑对一个比可分页实际内存大得多的大地址空间进行线性扫描。LRU基于“最近访问过的内容很可能会再次访问”，但是线性扫描完全违反了这个假设。这就是为什么一些操作系统允许程序向内核建议其引用行为的原因——一个例子是经典LISP解释器所代表的“标记和清除”垃圾收集。 (也是更现代的GCs如“分代”工作的主要驱动力。)
另一个例子是某个古老的宏处理器(STAGE2)中的符号表。二叉树从根节点开始搜索每个符号，并且字符串评估是在堆栈上完成的。结果发现，通过“固定”符号树的根页面和堆栈底部页面来减少可用页面帧数，可以大大改善页面故障率。缓存非常小，而且它翻滚不停，总是推出两个最常引用的页面，因为缓存比对这些页面的间隔更小。所以小的缓存效果更好，但只是因为从缓存中窃取的这两个页面帧被明智地使用了。
所有这些的结论是，LRU是标准答案，因为在不是极度超载的系统(VM多次实际内存可用)上，它通常对实际工作负载表现得非常好，并且这得到了多年仔细测量的支持。然而，你肯定可以找到替代行为优越的情况。这就是为什么测量真实系统很重要的原因。
- Mike
2
实际上，在线性扫描中，LRU 和 FIFO 将是相同的（非常糟糕）。你可以构造一种访问模式，其中 FIFO 比 LRU 更好，但这相当牵强。 - Chris Dodd
1@ChrisDodd 你能描述一个FIFO比LRU表现更好的例子吗？ - CuriousCoder
2
将RAM视为缓存。为了成为一个有效的缓存，它需要将最有可能被请求的项目保留在内存中。
LRU将最近使用的项目保留在内存中。FIFO将最近添加的项目保留在内存中。通常来说，LRU更有效率，因为通常会添加一次并且永远不再使用的内存项，以及经常添加和使用的项。LRU更有可能将经常使用的项目保留在内存中。
LRU将最近使用的项目保留在内存中。FIFO将最近添加的项目保留在内存中。通常来说，LRU更有效率，因为通常会添加一次并且永远不再使用的内存项，以及经常添加和使用的项。LRU更有可能将经常使用的项目保留在内存中。
- BlueRaja - Danny Pflughoeft
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接