专题进阶 · 操作系统算法推荐总顺序 · 第 147 / 148 课

手算环形指针与引用位,理解 Clock 如何用较低维护成本近似最近使用。

先学会这些,再进入本课 FIFO 页面置换 最近最少使用
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 操作系统算法

Clock 算法Clock Algorithm

环形扫描引用位,给最近访问页面第二次机会,以低成本近似使用历史。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

手算环形指针与引用位,理解 Clock 如何用较低维护成本近似最近使用。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

精确维护 LRU 的每次访问次序有成本,能否只记“最近是否访问过”这一位信息?

02一步步得到方法

环形页框加一个引用位

每个页框有引用位 R,命中就把 R 设为1。页框排列成环,指针 hand 指向下一次检查的位置。缺页时从 hand 开始扫描:遇到 R=1 就清零并前进,遇到 R=0 就替换。

这称为第二次机会:曾被访问过的页获得一次跳过,但不是永远保护。新页装入后 R=1,指针移到下一位置。空页框可以直接使用。

它没有保存精确时间顺序

如果所有页的 R 都是1,一次缺页会绕一圈清零,再回到起点进行替换。于是刚被访问过的页也可能被淘汰,因为一个比特不能记录谁比谁更新。

Clock 是对近期访问的近似,具体效果受访问位采样、扫描速度和工作负载影响。操作系统还可能区分脏页、增加多只指针或使用更多代际信息,本课先掌握最基础版本。

把指针移动规则固定下来

本课命中只置位,不移动 hand;扫描 R=1 时前进;替换完成后也前进。若采用另一变体,应同时修改规则与示例,不能混用。

使用 page→槽位 字典做命中定位,避免每次遍历环。演示轨迹保存页框、位和指针,便于看清清零不等于页面已经被淘汰。

03把一个小例子完全算清楚

容量3,引用串 [1,2,3,1,4]。

步骤计算与状态为什么这样做
装入1、2、3页框[1,2,3],R=[1,1,1],hand=0绕完一圈回起点
命中1R仍[1,1,1],hand仍0命中不转动指针
访问4清零一整圈,再替换槽0页框[4,2,3],R=[1,0,0],hand=1

窄屏可左右滑动表格,阅读完整计算与理由。

共4次缺页,尽管刚访问过1,它仍可能在这一轨迹中被淘汰。

04为什么这个方法成立

  1. 命中表与页框始终一一对应,引用位标记自上次清零以来是否访问或装入。
  2. 扫描只清位和前进,直到找到空位或无第二次机会的页,符合策略规则。
  3. 最多绕过所有已置位页后就能找到零位,因此有限页框下每次替换会终止。

05把推导翻译成代码

Python · 可独立运行的教学实现

def clock_pages(references,capacity):
    if capacity<1:
        raise ValueError("positive capacity required")
    frames = [None]*capacity
    bits = [0]*capacity
    positions = {}
    hand,faults = 0,0
    trace = []
    for page in references:
        if page is None:
            raise ValueError("None is reserved for an empty frame")
        if page in positions:
            bits[positions[page]] = 1
        else:
            faults += 1
            while frames[hand] is not None and bits[hand]:
                bits[hand] = 0
                hand = (hand+1)%capacity
            old = frames[hand]
            if old is not None:
                del positions[old]
            frames[hand] = page
            positions[page] = hand
            bits[hand] = 1
            hand = (hand+1)%capacity
        trace.append((frames.copy(),bits.copy(),hand))
    return faults,trace

print(clock_pages([1,2,3,1,4],3))

逐个理解关键决定

bits[positions[page]] = 1
命中只刷新引用位,不改变页所在槽位。
bits[hand] = 0
给予第二次机会后清位,页面仍驻留。
del positions[old]
替换时同步维护命中表,防止旧页仍被误判为命中。

06时间、空间与实现范围

一次缺页最坏扫描 O(capacity),命中字典平均 O(1)。

不存轨迹时,每次清位可计费给此前一次置位,整个序列扫描可作摊还分析;本版保存每步完整轨迹,最坏时间及空间 O(n×capacity)。

07改变条件,检查哪里会出错

Clock 就是精确 LRU

引用位不能恢复完整访问顺序,两者可选择不同牺牲页。

清引用位等于删页

清位只取消第二次机会,真正替换时才移除页面映射。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

所有引用位均为1时,缺页会不会死循环?

需要一点提示

扫描时会把它们清零。

查看解析与答案

不会,最多绕过一圈后就能替换一个零位页。

练习 2 · 边界与辨析

本课命中会移动 hand 吗?

需要一点提示

查看命中分支。

查看解析与答案

不会,只把对应引用位置1。

练习 3 · 变式与迁移

为什么引用位不能区分刚访问和较早访问?

需要一点提示

它只有两种状态。

查看解析与答案

自上次清零后访问一次或多次都只是1,没有保存先后时间。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Arpaci-Dusseau · Operating Systems: Three Easy Pieces

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。