Linux内核中使用哪些页面替换算法进行OS文件缓存？

Question

Linux 将未使用的内存部分用于文件缓存，并在需要时清理空间。

我的问题是它如何选择受害者页面进行替换？有多种算法（LRU、FIFO、LFU和随机替换）

我想知道 1) Linux 内核中使用哪些页面替换算法来进行 OS 文件缓存？

2) 如果可能的话，我想知道它在 Linux 内核中是如何随着时间的推移而演变的。我假设考虑到趋势的“合理”变化，它的算法和实现可能会随着时间的推移而改变。我怎样才能找到那些？我需要阅读内核源代码吗？

Answer 1

Linux 内存管理（“MM”）似乎有点神秘且难以追踪。

Linux 文献在内存管理的上下文中大量提到了 LRU（最近最少使用）。我没有注意到提到的任何其他术语。

我在无与伦比的 LWN.net 上的这篇文章中找到了一个有趣的介绍（前四段）。它解释了如何在实践中为虚拟内存实现基本的 LRU。阅读。

真正的 LFU（最不常用）替换对于虚拟内存来说并不实用。内核无法计算页面的每次读取，何时mmap()用于访问文件缓存页面 - 例如，这是大多数程序在内存中加载的方式。性能开销会太高。

为了超越这个简单的概念，这里有一个围绕 Linux 2.6.28-32 版的设计大纲：

http://linux-mm.org/PageReplacementDesign

它建议 Clock-PRO 用于文件页面。上面有一张原始纸。LWN.net 上有一篇关于 Clock-PRO的旧描述，同样包含了一些实际的实现细节。显然，Clock-PRO“试图超越 LRU 方法”，其变体“在大多数系统中使用”。它似乎更重视频率。

Linux-mm 有另一个设计文档，用于在 Linux 中实现 Clock-PRO。这个没有说它被合并了；它是在 LWN 关于它的文章之前几个月写的。 http://linux-mm.org/ClockProApproximation

最近的描述是 Linux 只是“使用了Clock-PRO 的一些想法”，实际上是“许多不同算法的混合体，并进行了许多修改以捕捉极端情况和各种优化”。

以上引用由Adrian McMenamin回答了一个问题。McMenamin 继续在 2011 年完成了一个MSc 项目，测试基于“工作集模型”对 Linux 页面替换的修改。它包括对 Linux 页面替换的简要说明。“LRU 的变体”被命名为“用于数据库管理的 2Q [双队列] 方法”，提供了许多参考资料，并且有一个图表说明了两个队列之间的移动和其他状态转换。他还将 Linux 描述为使用 CLOCK-PRO 的部分实现。

我希望 LRU 概念，而不是你提到的其他可能性，是从一开始就建立的。最显着的变化是引入了基于 Clock-PRO 的功能，即在频率上增加了一些权重。

2013 年，Linux 获得了“基于抖动检测的文件缓存大小调整”。这可能也与问题有关。