玻尔百科在计算世界中，物理内存是一种有限而宝贵的资源。每个操作系统都面临一个持续而关键的挑战：当内存已满时，应该驱逐哪个页面来为新页面腾出空间？做出正确的选择对系统性能至关重要，而错误的选择则会导致系统因争相检索刚被丢弃的数据而变慢。这一困境推动了对理想页面置换策略的探索，但理论上完美的算法无法实现，而其最接近的实用替代方案——最近最少使用 (LRU)——又成本过高。这种知识上的差距呼唤一种“足够好”的解决方案——一种既巧妙又高效的方案。
本文探讨了解决此问题最优雅且应用最广泛的方案之一：CLOCK 算法。我们首先将在 原理与机制 部分剖析其核心操作原理，理解它如何使用一个简单的“引用位”来近似 LRU，以及这个基本机制如何被改进以获得更高的智能。随后，在 应用与跨学科关联 部分，我们将看到该算法的实际应用，审视它如何适应和应对由现代硬件、复杂的操作系统特性以及要求苛刻的云计算环境所带来的复杂动态挑战。
要理解 CLOCK 算法，我们必须首先回顾每个现代计算机核心处的一个基本问题：内存是有限的。当计算机物理内存耗尽时，它必须选择一个“牺牲者”——一个要驱逐并发送到二级存储（如 SSD）的内存页面，以便为新页面腾出空间。但谁应该成为牺牲者？这个选择至关重要。一个糟糕的选择意味着我们可能马上又需要被驱逐的页面，从而引发缓慢的缺页中断来检索它。一个好的选择则意味着我们驱逐了一个在很长一段时间内都不会再需要的页面，从而保持系统平稳运行。
理想的、完美的选择是驱逐在未来最远的时间点才会被需要的页面。这被称为最优页面置换算法 (OPT)。它很优美，很完美，但在真实系统中完全无法实现。为什么？因为它需要预知能力——操作系统需要知道未来所有内存访问的序列。
既然我们无法预测未来，我们就转向次优选择：回顾过去。引用局部性原理告诉我们，程序倾向于重用它们最近使用过的数据和指令。这启发了一个强大的启发式方法：如果一个页面长时间未被使用，它可能很快也不会被再次使用。这就催生了最近最少使用 (LRU) 算法，该算法总是驱逐最长时间未被访问的页面。
LRU 是 OPT 的一个极佳近似，但它自身也有一个实际问题：成本高昂。要实现真正的 LRU，操作系统需要为每一次对每个页面的内存访问记录一个时间戳。这将需要专门且昂贵的硬件，并会显著拖慢系统。因此，我们的追求不是完美，而是对 LRU 的一种巧妙、高效的近似。这正是 CLOCK 算法登场的舞台。
想象一下，内存中所有的物理页框像钟面一样排列成一个圆圈。一个“指针”指向其中一个页框。这就是 CLOCK 算法的精髓。每个页面没有完整的时间戳，只有一个与之关联的内存位：引用位（或访问位）。
硬件会帮助我们，在页面被访问（读取或写入）时自动将此位设置为 1。操作系统的页面置换算法，即时钟指针，随后使用这个位来做决策。当发生缺页中断需要一个牺牲者时，时钟指针开始扫过这些页框：
1，意味着该页面最近被使用过。算法给它第二次机会。它将引用位翻转为 0，然后将时钟指针推进到下一个页框。0，意味着自从上次指针扫过它之后，该页面就没有被使用过。这个页面就是我们的牺牲者。它被选中进行驱逐，新页面被放入其位置（其引用位初始化为 1），并且指针向前推进。这个简单的机制是对 LRU 的一个出色近似。一个引用位为 0 的页面不一定是整个系统中绝对最久未被使用的页面，但我们知道关于它的一件重要事情：它至少在时钟指针完整扫描一圈的过程中没有被访问过。引用位就像一个粗略的、只有一位的时间戳。1 表示“在最近的过去被使用过”，而 0 表示“在最近的过去没有被使用过”，其中“最近”的定义与时钟指针的速度相关。硬件设置位、软件清除位的这种简单而优雅的协作，构成了应用最广泛的页面置换策略之一的核心。从中断到驱逐的整个过程可以通过逐步模拟来计算页面换入、换出和回写的次数，从而为其操作流程提供一幅具体的图景。
时钟指针到底需要做多少工作才能找到一个牺牲者？答案取决于工作负载。如果内存中大多数页面都在被活跃使用，它们的引用位几乎总是 1。时钟指针将不得不扫过许多页框，清除它们的位，然后才能找到一个 0。相反，如果许多页面处于空闲状态，牺牲者几乎会立即被找到。
时钟指针必须扫描的页框数量直接取决于内存压力。如果我们假设任何给定页面的引用位以概率 被设置为 1，那么寻找一个牺牲页面（位为 0）的过程就像一系列试验。时钟指针必须扫描的期望页框数 的一个良好近似由几何分布的公式给出：
这个公式优雅地表明，如果 接近 0（大多数页面空闲）， 接近 1——牺牲者会立刻被找到。相反，如果 接近 1（大多数页面活跃），期望扫描次数会变得非常大。在最坏的情况下，内存中所有 个页面的引用位都被设置为 1，指针必须完整地转一圈，清除所有 个位，然后在检查下一个页框时找到一个牺牲者，总共需要扫描 次。
这个概率 不仅仅是一个魔法数字；它源于页面被使用的频率（其访问率 ）和时钟指针扫描的速度（其旋转率 ）之间的相互作用。一个页面获得第二次机会——即当指针到达时其位为 1——的概率，正是在扫描间隔内它至少被访问一次的概率。对于随机访问模式，这可以被证明是 。这一洞见使我们能够调整时钟指针的速度：我们可以调整 以匹配工作负载的特性，确保时钟维持的“近时性”窗口能根据系统的实际内存需求进行优化。在实践中，许多系统发现标准 CLOCK 算法的“懒惰”清除策略在避免持续清除所有位的高开销和保持平均扫描长度在可接受的低水平之间取得了很好的平衡。
基本的 CLOCK 算法是健壮且高效的，但我们可以通过提供更多信息使其变得更智能。这就是我们将简单机制改进为更复杂东西的起点。
并非所有的驱逐都是平等的。如果一个页面从磁盘加载后被修改过（即它是“脏”的），驱逐它就需要一个缓慢的回写操作来保存更改。如果它没有被修改过（即它是“干净”的），我们就可以直接丢弃它。硬件再次通过一个修改位（或脏位, ）来帮助我们，它会在对页面进行任何写入操作时将该位设置为 1。
增强型 CLOCK 算法利用了这个额外的位。它根据元组（引用位，修改位），即 ，将页面分为四类：
该算法现在进行两轮扫描。在第一轮中，它寻找类别 (0, 0) 的页面，同时仍然清除它遇到的任何类别 (1, x) 页面的引用位。如果未能找到类别 (0, 0) 的牺牲者，它会进行第二轮扫描，这次寻找类别 (0, 1) 的页面。这确保了在其他条件相同的情况下，它总是倾向于选择成本低的驱逐而不是成本高的驱逐，从而通过最小化磁盘写入来显著提高性能。
有时，即使是脏位也不能说明全部情况。考虑一个写时复制 (COW) 页面——例如，在 [fork()](/sciencepedia/feynman/keyword/fork()|lang=zh-CN|style=Feynman) 系统调用后复制的内存页面。最初，这个页面被标记为干净的。然而，它是一个匿名页面，意味着它在磁盘上没有后备文件。如果我们需要驱逐它，我们必须将它写入交换文件，这是一个昂贵的操作，尽管硬件脏位是 0。
这在硬件告诉我们的信息和真实成本之间造成了“语义鸿沟”。一个聪明的操作系统可以弥合这个鸿沟。它可能会为这类匿名页面预先设置脏位，实际上是向 CLOCK 算法“撒谎”，以防止它做出一个看似合乎逻辑但实则糟糕的选择。这是一个绝佳的例子，说明了真实世界的系统必须如何用更高层次的软件智能来增强简单的硬件机制，以实现稳健的性能。
如果一个程序的访问模式恰好被设计用来攻破 CLOCK 算法怎么办？想象一个程序在一个拥有 个页框的系统中循环访问 个页面。当指针扫过一圈清除了所有引用位时，程序循环正好又回来重新引用了所有页面，将它们的位重新设置为 1。指针被迫在每次缺页中断时都进行一次完整的、无用的旋转。这种振荡行为是一种已知的病态。
解决方法和问题本身一样优雅：一个双指针时钟。一个额外的“清除指针”在“牺牲者指针”之前扫描。清除指针的唯一工作就是将引用位设置为 0。牺牲者指针跟在后面。如果一个页面的位在两个指针经过的间隙内被重新引用并设置回 1，牺牲者指针就会放过它。这个宽限期有助于区分那些真正频繁使用的页面和那些恰好属于恶意循环一部分的页面，从而抑制振荡。
最后，我们可以进一步推进对 LRU 的近似。单个引用位的记忆非常短暂。通过为每个页面增加一个小的老化计数器，我们可以获得更精细的近时性感知。每次一个页面获得第二次机会时，我们可以增加它的计数器。当需要一个牺牲者时，我们选择计数器最低的那个。这个简单的修改让我们从一个简单的时钟变成了一个精密的计时器，缩小了 CLOCK 的效率与 LRU 的准确性之间的差距，展示了算法设计中优美而持续的改进路径。
在理解了 CLOCK 算法优雅的机制后，我们可能会倾向于认为它是一台完美的、已完成的机器。我们给它上好发条，它就能自行运转。但是，科学或工程中一个基本思想的真正美妙之处，并不在于它在无菌的、理论真空中的表现，而在于它在真实世界中的行为——一个充满混乱、相互作用的部分、意想不到的约束和层层复杂性的世界。正是在这个动态的、真实世界的交响乐中，简单的 CLOCK 算法才真正显示出它的力量，不是作为一件独奏乐器，而是作为一位反应灵敏、适应性强的指挥家。
让我们踏上一段旅程，去观察 CLOCK 算法的实际运作，去欣赏它解决的微妙问题以及它在计算机科学领域建立的深刻联系。
想象一下，你是一个大型系统的管理员，你只有一个旋钮可以控制时钟指针的“速度”。你应该把它设置在哪里？如果你调得太快，指针会飞速扫过内存，以至于在 CPU 有机会再次使用活动页面之前就清除了它们的引用位。指针转回来，发现引用位是零，错误地驱逐了一个即将被使用的页面。这会导致一场缺页中断的风暴，即所谓的颠簸（thrashing）现象，此时系统把所有时间都花在交换页面上，而不是做有用的工作。
另一方面，如果你把旋钮调得太慢，时钟指针移动得就非常迟缓。当一个进程完成一项任务并转向另一项任务时——切换其页面的“工作集”——旧任务的陈旧页面会在内存中停留太长时间。移动缓慢的指针需要很长时间才能找到它们，并为新任务回收它们的页框。同样，结果也是一连串的缺页中断，因为新的工作集难以在内存中找到立足点。
显然，存在一个“金发姑娘”区域。最佳速度是一种微妙的平衡：足够快以便及时回收旧的、未使用的页面，但又足够慢以便给最近使用的页面一个公平的机会在指针转回来之前再次被引用。这种调优不是一次性的设置；它是一个动态的挑战，将抽象的算法与系统性能调优这个非常现实的问题联系起来。该算法不仅仅是一条规则；它是一件需要演奏的乐器。
我们的计算机不仅仅是一个 CPU 和内存。它通过 I/O 设备（如网卡和磁盘驱动器）不断地与外部世界对话。这些对话引入了新的规则。例如，一个当前正用于直接内存访问 (DMA) 操作的页面——比如从网卡接收数据——是不能被驱逐的。它被“钉”在内存中。如果时钟指针偶然遇到这样一个页面，它必须简单地跳过，不问任何问题。这意味着指针可能需要走得更远，检查更多的页框，才能找到一个合适的牺牲者。被钉住的页面的存在给算法带来了一种可变的“阻力”，这个成本可以根据被临时禁用的内存比例来建模和预测。
这种与硬件的对话揭示了一个更微妙、更深刻的观点。CLOCK 算法的目的是近似 CPU 工作负载的 LRU。它旨在将 CPU 可能很快需要的页面保留在内存中。但是，当一个 DMA 设备写入内存中的缓冲区时会发生什么？这个访问不涉及 CPU。如果我们天真地允许这个 DMA 访问设置页面的引用位，我们就引入了一种“虚假近时性”。系统可能会认为一个网络缓冲区是“热”的且被频繁使用，而实际上，CPU 从未接触过它。这可能导致算法保护这些 I/O 缓冲区，而牺牲了包含 CPU 迫切需要的实际应用程序代码或数据的页面。
真正优雅的解决方案是认识到并非所有的“引用”都是平等的。操作系统可以被设计成区分 CPU 引用和 DMA 引用。它可以将硬件引用位专门用于 CPU 活动，并使用一个单独的软件标志或钉住机制来处理 DMA 的安全要求。通过这样做，操作系统确保 CLOCK 算法接收到一个干净的信号，一个忠实代表 CPU 局部性并使其能够做出智能决策的信号。这不仅仅是一个技术调整；这是对算法目的的深刻洞察，以及为了匹配其目标而筛选其输入的重要性。
随着操作系统变得越来越复杂，我们简单的 CLOCK 算法面临的挑战也越来越大。考虑内存内压缩。为了节省空间，操作系统可能会取一个旧页面，将其压缩，并保存在一个特殊的内存池中，而不是将其写入磁盘。解压它比从磁盘读取要快得多。但是 CLOCK 算法如何处理这种情况呢？一个被压缩的页面没有以硬件可以设置其引用位的方式进行映射。
这是否意味着它永远得不到第二次机会？当然不是！在这里，软件在硬件力所不及之处介入。操作系统可以将触发解压的缺页中断行为本身视为一个强大的引用信号。当一个程序试图访问一个压缩页面时，操作系统捕获中断，为该页面设置一个软件引用位，然后解压它。通过这种方式，该页面被理所当然地给予了“第二次机会”，将这种现代的内存节省技术无缝地集成到经典算法的逻辑中。
但交互也可能导致意想不到的后果。许多系统使用预取技术，即操作系统试图预测程序很快会需要哪些页面，并提前将它们加载到内存中。这通常是一个巨大的性能提升。然而，当一个预取页面被加载时，它对 CLOCK 算法来说看起来是“被引用”的。这可能导致这样一种情况：时钟指针扫过内存，发现大量的页面——包括真正被使用的和仅仅是预取的——它们的引用位都被设置了。这种对引用位的“污染”迫使指针做更多的工作，清除每个页面的位，并可能需要多次旋转才能找到一个牺牲者。指针必须扫描的期望页框数增加了，这是一个本来有益的优化所带来的微妙成本。
CLOCK 算法在任何地方都没有比在虚拟化和多租户系统的世界里面临更复杂的环境了，而这正是现代云计算的支柱。想象一下，一台物理机器上运行着数十个虚拟机 (VM) 或应用程序，它们都共享由一个单一的、全局的 CLOCK 算法管理的同一个内存池。
在这里，出现了一个新的、至关重要的维度：公平性。考虑两个租户。租户 A 是“突发性的”，在短时间内以极高的强度访问其页面。租户 B 是“平稳的”，以较慢、更规律的速度访问其页面。由于租户 A 的页面在其突发期间被如此频繁地引用，当全局时钟指针扫过时，它们的引用位几乎总是 1。租户 B 的页面被访问的频率较低，在之前的扫描中被清除引用位后，更有可能被发现引用位为 0。结果呢？全局 CLOCK 算法以其机械般的简单性，会不成比例地驱逐平稳租户的页面，为突发租户腾出空间。贪婪的租户饿死了温和的租户。
这是一个深刻的问题，一个关于进程间“社会正义”的问题。解决方案需要对算法进行演进。我们可以强制执行硬性配额，给每个租户自己的私有内存池。或者，我们可以让算法本身变得更智能。“老化”或“双指针时钟”方案需要更持续的使用证据，而不仅仅是单次的最近接触，来保护一个页面。这些调整恢复了公平性，确保一个租户的行为不会不公平地惩罚另一个租户。
随着现代虚拟机监控程序（hypervisor）使用的复杂技巧，复杂性进一步加深。内核同页合并 (KSM) 是一种技术，它能找到来自不同虚拟机的相同内存页，并将它们合并为单个物理副本以节省空间。现在，一个物理页框有了多个虚拟身份。我们如何判断这个共享页面是否“最近被使用”？唯一合乎逻辑的方法是合成一个引用位：如果任何共享它的虚拟机访问了它们的副本，那么该物理页面就被认为是已被引用的。Hypervisor 必须聚合来自其所有用户的引用信号，并在给予第二次机会时清除它们所有页表中的位。
最后，考虑一下嵌套分页的令人眩晕的现实，其中硬件支持两级转换：一级用于客户虚拟机（从其虚拟地址到其“物理”地址），另一级用于 hypervisor（从客户机的“物理”地址到主机的真实物理地址）。这里我们可以有两个 CLOCK 算法同时运行：一个在客户机内部，管理自己的内存；另一个在 hypervisor 中，管理底层的物理页框。两者是独立的，但又相互影响。Hypervisor 可能认为一个页面是“冷的”（嵌套引用位为 0），而客户机知道它是“热的”（客户机引用位为 1）。如果 hypervisor 驱逐了该页面，客户机就会遭受性能损失。最终的适应方案是让 hypervisor 成为一个元观察者：它可以周期性地、安全地窥探客户机的页表，读取其引用位，并利用该信息做出更智能的驱逐决策。这避免了因客户机无法控制的事情而惩罚它，这是抽象层之间合作的一个绝佳范例。
从一个简单的旋钮到多租户公平性和嵌套现实的复杂舞蹈，CLOCK 算法的旅程证明了一个简单、优雅思想的力量。它告诉我们，在计算中，如同在自然界一样，最稳健的机制不是最僵化的，而是最具适应性的。