Clock页替换与回收资格

形式陈述

Clock在有限驻留页框上维护环、手指位置h和访问位A。OS-16中一次成功用户访问把对应页的A置1。为选一个可回收页，手指依环前进：遇到被pin或不可回收页就跳过；对可回收且A=1者，清A并给第二次机会；遇到可回收且A=0者选作受害者，并把h推进到后一槽。

本文算法选择后并不立即覆盖旧数据。内核还须阻止新的旧映射访问、完成TLB失效、确认无pin；若最新内容未在backing保存，先安排写出并确认需要的完成条件，才能把帧交给新页。干净文件页已有可重新读取的内容，通常可直接丢弃；脏匿名页若无可用换出位置，不能仅因A=0而丢弃。

为给手算唯一结果，主示例在选择扫描期间冻结用户访问，所有槽都可回收。真实并发下硬件可能重新置A，扫描可能需要重试；清PTE访问位后怎样保证以后访问重新记录，还须遵守ISA与TLB规则。

直觉

精确LRU需要知道每次访问后的完整顺序。Clock只问“上次手指经过之后有没有用过”：A=1买来一次机会，清零后若下一圈仍未用就可淘汰。因此它是近期使用的粗略证据，不是精确时间戳。

访问位与dirty位回答两件事。最近读过很多次的页可能完全干净；很久没访问的页可能仍保存唯一一份尚未写出的修改。只看近期使用能挑候选，却不能证明丢弃内容安全。

例子与边界

三槽初始装a,b,c，A均1，h指槽0。请求d缺页：先清a、b、c的A，绕回槽0见a的A=0，选a；装d后A[d]=1，h=1。此时状态为d(1),b(0),c(0)。

随后读b命中，只置A[b]=1，h仍为1。请求e缺页：清b的A并前进，c的A=0，故淘汰c，装e，h=0。最终为d(1),b(0),e(1)。这两次替换扫描分别检查4槽和2槽，共6次检查；不能把“平均看起来很快”写成每次只检查一槽。

若c是脏页，第二次选择并未让其旧字节消失。OS-16先把c标记回写中，冻结相应旧映射并保存到规定backing，确认后才复用槽2。若写出失败，这个替换请求失败或改选其他页，不能报告e已成功驻留。

a、b都在手指上次经过后被读过，A均1，但a可能只在很早读过一次，b刚刚读过。Clock可能因环次序先淘汰b；它没有足够信息恢复精确LRU。改变初始手指也可改变受害者，因此题目必须给出h。

若所有页都被pin，本实现扫描一圈后报告“当前无合格受害者”，由上层等待、回收别处或返回内存不足。无限循环指针不会创造空闲页，反而可能让驱动完成得不到运行机会。

推论与应用

在扫描期间不再置A、所有k页都可回收的限定下，最坏检查k+1次就选到受害者：至多先清掉一整圈的1，再见一个0。允许并发持续访问或pin时，这个界不成立，应分别设置扫描预算与等待策略。

Paging问题已研究单位页、忽略脏写回的在线替换及LRU竞争界；本页新增的是低成本访问证据和回收资格协议。不能把LRU的k竞争证明直接转贴给Clock，也不能把OS中的页故障全部当成“缓存已满所以需替换”：首次零页分配可能有空闲帧，权限故障根本不该装入新页。

性能账单至少区分缺页数、扫描次数、脏页写出数和等待时间。两个策略缺页数相同，若一个频繁逐出脏页或扫描pin页，其实际工作仍可能不同。工作集持续大于可用帧时，单纯改变Clock指针很难消除频繁换入换出的抖动。

参考资料

Remzi与Andrea Arpaci-Dusseau，OSTEP: Beyond Physical Memory—Policies，第22章，Clock/引用位与脏页的策略作用。本文冻结扫描和三槽序列为自定实验。
Peter J. Denning, “The Working Set Model for Program Behavior”， Communications of the ACM 11(5), 1968, pp.323–333，工作集与抖动的经典问题背景。