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 | 绕完一圈回起点 |
| 命中1 | R仍[1,1,1],hand仍0 | 命中不转动指针 |
| 访问4 | 清零一整圈,再替换槽0 | 页框[4,2,3],R=[1,0,0],hand=1 |
窄屏可左右滑动表格,阅读完整计算与理由。
共4次缺页,尽管刚访问过1,它仍可能在这一轨迹中被淘汰。
04为什么这个方法成立
- 命中表与页框始终一一对应,引用位标记自上次清零以来是否访问或装入。
- 扫描只清位和前进,直到找到空位或无第二次机会的页,符合策略规则。
- 最多绕过所有已置位页后就能找到零位,因此有限页框下每次替换会终止。
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时,缺页会不会死循环?
需要一点提示
扫描时会把它们清零。
查看解析与答案
不会,最多绕过一圈后就能替换一个零位页。
本课命中会移动 hand 吗?
需要一点提示
查看命中分支。
查看解析与答案
不会,只把对应引用位置1。
为什么引用位不能区分刚访问和较早访问?
需要一点提示
它只有两种状态。
查看解析与答案
自上次清零后访问一次或多次都只是1,没有保存先后时间。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Arpaci-Dusseau · Operating Systems: Three Easy Pieces