页面置换

程序访问不驻留页且物理帧已满时，页面置换策略决定逐出哪个驻留页。FIFO 选最早载入者，LRU 选最久未用者，Clock 用每帧一个引用位近似最近使用信息。

三者区别在维护什么记录：FIFO 载入时记时间，命中不改；LRU 每次使用都更新时间；Clock 命中置位，时钟指针扫描时清位。选择受害页要花工作，维护信息也要花工作，选得差还会增加后续缺页。本课默认 FIFO 比另两种多两次存储读入。

页面置换如何工作

先检查请求页是否驻留。命中就直接使用；未命中则缺页。本课假设缺页要从存储读入整页：有空闲帧便填入，否则选择受害帧。真实系统还可能处理无需存储读取的次缺页，这里专注驻留与置换。

• FIFO 保存 arrived，表示载入的访问编号，选最小值。命中不更新时间。
• LRU 保存 last_used，每次访问刷新，选最小值。
• Clock 保存 R。命中将 R 置 1。指针沿环扫描：遇 1 给第二次机会，清成 0 后继续；遇已有的 0 则选中。选择阶段停在受害帧，安装新页后前进到下一帧，下次从该处继续，不从 F0 重来。

FIFO 不使用命中带来的新信息；LRU 用它维护完整最近顺序，精确维护每次内存引用的成本较高。硬件访问位给 Clock 类近似提供较低成本的信息：它只知道自上次清除后是否被访问，不能精确排序。

逐步演示

默认三帧、FIFO、十二次访问：0 1 2 · 0 1 3 · 0 1 4 · 0 1 2。P0、P1 是反复使用的热点，中间插入其他页。

1. 第 1–3 次访问 P0、P1、P2，均首次缺页，分别进入 F0、F1、F2，标签为 arrived @1、@2、@3。有空帧，不需选择受害页。
2. 第 4、5 次命中 P0、P1，不读存储。FIFO 的标签仍是 @1、@2；近期命中未被写进决策记录。
3. 第 6 次访问 P3，帧满，比较 @1、@2、@3，选最小 @1，逐出刚在第 4 次使用的 P0。P3 进 F0，标签 @6，累计第四次缺页。干净旧副本可丢弃，无需额外回写。
4. 第 7 次又要 P0。比较 @6、@2、@3，逐出另一个热点 P1，P0 进 F1，@7，第五次缺页。
5. 第 8 次要 P1，逐出 P2（@3），P1 进 F2，@8，第六次缺页。三个连续请求都缺页。
6. 第 9 次要 P4，逐出 @6 的 P3，第七次缺页，F0 标签变 @9。
7. 第 10、11 次 P0、P1 仍驻留，命中，标签保留 @7、@8。
8. 第 12 次要 P2，比较 @9、@7、@8，再次逐出 P0，第八次缺页。

最终 FIFO 八次缺页、四次命中。结束对比同输入同三帧：FIFO=8、LRU=6、Clock=6。首次置换时 FIFO 选 P0（arrived @1），LRU 选 P2（last used @3），Clock 也选 P2（R=0）：三个规则、两个不同受害页。

同输入下的 LRU 与 Clock

LRU 前三次首次缺页相同。第 4、5 次命中会把 P0、P1 标签改为 @4、@5。第 6 次需要 P3 时，@4、@5、@3 中最旧为 P2，两个热点得以保留。第 7、8 次于是命中；第 9 次逐出 P3，第 12 次逐出 P4，合计六次缺页。

以引用的每次约一百万周期为比例，少两次意味着约两百万存储服务周期；页面置换画布实际统计缺页数，不模拟设备时序。

Clock 在默认轨迹的相同六次访问缺页，也逐出 P2、P3、P4。因为本课载入页 R=0，P0、P1 后来命中才置 1，扫描会给它们第二次机会并清位，选仍为 0 的冷页。这条历史上一个位已足够作出和 LRU 一样的选择，不表示两者对所有输入等价。

Clock's full sweep 让全部 R=1。指针清完整个环，再回起点，选该帧。此预设中它与 FIFO 选同页；一般全一状态只能说明扫描回原指针，不能总说该页就是全局最早载入者。近似记录无法区分所有同样被引用的页。

增加内存为何可能增加缺页

Bélády: 3 frames 用 FIFO 处理 0 1 2 3 · 0 1 4 · 0 1 2 3 4，缺页九次。Bélády: 4 frames 保持序列与策略，只多一帧，却缺页十次。这是 Bélády 异常。

LRU 具有栈性质：从空状态处理同一历史，k 帧驻留集合包含于 k+1 帧集合。因此增加容量不会让同一访问由命中变缺页，缺页数不增。FIFO 没有这种集合嵌套，新增帧改变淘汰顺序，可能逐出小容量下反而保留的页。

把同一预设切成 LRU，异常消失。第二个结束图比较二、三、四、五帧，并标出缺页数上升的相邻容量点。Clock 与第二次机会也不是栈算法，不能未经证明就承诺容量增加一定减少缺失。

LRU 的容量临界点

A loop that thrashes 用四页循环三遍，却只有三帧。LRU 每次都淘汰接下来要复用的最旧页，十二次全缺页，零命中。

A loop that fits 只增一帧，变为四次首次缺页、八次命中。性能可能在工作集跨过容量时突变，不必随容量平滑下降。此处展示的三种策略在三帧循环上都不能命中；其他策略可能减少部分缺页，但无法凭空让四个活跃页同时装入三帧。要结合增加内存、缩小工作集和改变访问/I/O 方式。

边界情况

• 有空帧的冷缺页不涉及受害选择。按需、无预取模型中，首次出现的不同页无法靠置换历史避免读入。不同运行未必都能填满全部帧，应按实际访问计数。
• Nothing to reuse 只访问六个不同页各一次，三个策略都是六次缺页，没有复用可利用。
• 曾经载入不等于现在驻留。默认 P0 在第 1 次载入、第 4 次命中，却在第 6 次被逐出，第 7 次仍缺页。
• 命中指针当前帧只置 R=1，不推动指针。扫描与安装新页才移动指针，清过的位也可在下次访问再被设置。
• 一帧没有受害选择，缺页只能替换唯一页，三策略等价；滑块从二帧开始。
• 最多十五次引用、页 P0–P5、最多五帧，是画布限制，不是算法限制。

常见错误

• 把精确 LRU 当成所有操作系统的实际回收策略。逐内存引用维护全序成本高，内核采用采样与近似。Linux 依配置可使用 Multi-Gen LRU 等机制；缓冲池也有 LRU-K、Clock 类变体，不能由名称推断完全相同的实现。
• 只把 Bélády 当 FIFO 的趣事。是否具有栈性质才决定能否保证缺失随容量不增，其他非栈策略也不能自动保证。
• 混淆 TLB 缺失和缺页。前者需查表，后者在本课需读入页；虚拟内存课区分两条路径。
• 工作集装不下时只调受害规则。策略能影响次数，但不能替代容量和访问局部性的改善。
• 把逐出当数据丢失。这里的干净页已有后备副本，只丢内存副本，重新读取有成本但不改变值。
• 认为真实逐出免费。脏页要在复用帧前安全写回，可能在新页读入外再加一次写入；具体 I/O 可批量、提前或重叠进行，不能把总耗时机械翻倍。

模型范围

单进程、按需分页、六个页、最多五帧，无脏位，所有缺页统一计数。Clock 新页 R=0；有些教材装入即为 1，默认首次满环扫描便可能清全部位并选出 FIFO 式受害，轨迹会不同。

LRU 用线性扫描找最小 last_used，适合几帧教学。应用级缓存可用哈希表与双向链表做每次操作 O(1)，参见 LRU Cache，但这不取消追踪每次真实内存引用的成本。

约一百万周期只是沿用虚拟内存课的量级提示，SSD、机械盘、排队和 CPU 频率都会改变它。未展示的 OPT 选择未来最晚再用的页，在线系统不知道未来，离线完整轨迹则能计算它。OPT 给固定轨迹和容量的最少缺页数；其他策略超出的部分可相对此基准改善，OPT 自身的缺页仍可包含首次与容量所迫，不能全部叫首次缺页。