什么是页面置换算法？FIFO、LRU、Clock 对比
这是“操作系统系列教程”的第三十二篇。上一篇我们讲了缺页中断，知道了当程序访问的页不在内存时，操作系统需要从磁盘加载。但如果物理内存已经满了，没有空闲页框，该怎么办？答案是——页面置换。选择换出哪个页，就是页面置换算法要解决的问题。
一个“座位不够”的问题
先来想象一个场景。你经营一家咖啡馆，店里有 10 张桌子。客人来了，如果还有空桌，直接安排入座。但如果 10 张桌子都坐满了，又有新客人来，你该怎么办？
你必须请一位现有的客人离开，腾出桌子给新客人。请谁离开？请刚来的客人？请坐得最久的客人？请消费最少的客人？还是随机请一位？
不同的选择策略，就是不同的“置换算法”。选得好，客人满意度高；选得不好，客人可能再也不来了。
操作系统管理物理内存，面临同样的问题：
- 物理内存有限，页框数量固定；
- 进程需要访问的页可能很多；
- 当需要加载新页而没有空闲页框时，必须换出某个页。
选择换出哪个页，就是页面置换算法（Page Replacement Algorithm）的任务。
页面置换算法的好坏，直接影响系统的缺页率和性能。一个好的算法，能让缺页率尽可能低；一个差的算法，可能导致系统频繁换页，甚至抖动。
这篇文章，我们就来把页面置换算法讲清楚。
说明：本文涉及 FIFO、LRU、Clock 等算法。初学者如果遇到暂时看不懂的术语，可以先跳过细节，重点理解“当内存满了，操作系统选择换出哪个页，不同选择策略就是不同的置换算法”这一核心思想。
一、为什么需要页面置换？
1.1 物理内存有限
物理内存是有限的，而进程需要访问的页可能很多。虚拟内存让程序可以使用比物理内存更大的地址空间，但当程序访问的页不在内存中，且没有空闲页框时，就必须换出某个页。
1.2 页面置换的时机
页面置换发生在缺页中断处理过程中：
- 程序访问一个不在内存中的页；
- 触发缺页中断；
- 操作系统查找空闲页框；
- 如果没有空闲页框，执行页面置换；
- 选择牺牲页，换出到磁盘；
- 把新页加载到腾出的页框。
图 1：页面置换的触发时机。 没有空闲页框时，必须换出某个页。
1.3 页面置换算法的目标
页面置换算法的核心目标是：最小化缺页率。
缺页率越低，磁盘 I/O 越少，系统性能越好。理想情况下，我们希望换出“未来最长时间不会被访问的页”。但未来不可预知，所以实际算法只能根据历史信息做预测。
图 2：页面置换算法的目标。
二、页面置换算法的评价指标
评价一个页面置换算法，主要看以下几个指标：
| 指标 | 说明 |
|---|---|
| 缺页率 | 缺页次数 / 总访问次数 |
| 命中率 | 命中次数 / 总访问次数 |
| 实现复杂度 | 算法需要的额外数据结构和开销 |
| 是否会产生 Belady 现象 | 增加页框反而缺页更多 |
2.1 缺页率的计算
假设有一个进程，访问序列如下：
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
物理内存有 3 个页框。我们来看不同算法的缺页情况。
2.2 引用串
引用串（Reference String）是进程访问页的序列。上面的访问序列就是引用串。
页面置换算法的输入是引用串和页框数量，输出是缺页次数。
三、最佳置换算法（OPT）
3.1 算法思想
最佳置换算法（Optimal，OPT）的思想是：换出未来最长时间不会被访问的页。
这是理论上最优的算法，缺页率最低。但问题是：未来不可预知，所以 OPT 无法实际实现，只能作为衡量其他算法的标准。
3.2 示例
引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，3 个页框。
| 访问 | 页框状态 | 缺页 |
|---|---|---|
| 1 | 1 | 是 |
| 2 | 1, 2 | 是 |
| 3 | 1, 2, 3 | 是 |
| 4 | 4, 2, 3（换出 1） | 是 |
| 1 | 4, 1, 3（换出 2） | 是 |
| 2 | 4, 1, 2（换出 3） | 是 |
| 5 | 5, 1, 2（换出 4） | 是 |
| 1 | 5, 1, 2（命中） | 否 |
| 2 | 5, 1, 2（命中） | 否 |
| 3 | 5, 3, 2（换出 1） | 是 |
| 4 | 5, 3, 4（换出 2） | 是 |
| 5 | 5, 3, 4（命中） | 否 |
缺页次数：9 次。
图 3：OPT 算法的缺页情况。 理论最优，但无法实现。
四、先进先出算法（FIFO）
4.1 算法思想
先进先出算法（First-In First-Out，FIFO）的思想是：换出最早进入内存的页。
实现方式：维护一个队列，页进入内存时加入队尾，需要换出时从队头取。
4.2 示例
引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，3 个页框。
| 访问 | 页框状态 | 缺页 |
|---|---|---|
| 1 | 1 | 是 |
| 2 | 1, 2 | 是 |
| 3 | 1, 2, 3 | 是 |
| 4 | 4, 2, 3（换出 1） | 是 |
| 1 | 4, 1, 3（换出 2） | 是 |
| 2 | 4, 1, 2（换出 3） | 是 |
| 5 | 5, 1, 2（换出 4） | 是 |
| 1 | 5, 1, 2（命中） | 否 |
| 2 | 5, 1, 2（命中） | 否 |
| 3 | 5, 3, 2（换出 1） | 是 |
| 4 | 5, 3, 4（换出 2） | 是 |
| 5 | 5, 3, 4（命中） | 否 |
缺页次数：9 次。
图 4：FIFO 算法的缺页情况。
4.3 FIFO 的优缺点
| 优点 | 缺点 |
|---|---|
| 实现简单 | 缺页率可能较高 |
| 开销小 | 可能换出常用页 |
| 公平 | 会产生 Belady 现象 |
4.4 Belady 现象
Belady 现象是指：增加页框数量，缺页次数反而增加。这是 FIFO 算法的一个反常现象。
例如，引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5：
- 3 个页框时，缺页 9 次；
- 4 个页框时，缺页 10 次。
增加页框反而缺页更多。Belady 现象将在后续文章中详细讲解。
五、最近最少使用算法（LRU）
5.1 算法思想
最近最少使用算法（Least Recently Used，LRU）的思想是：换出最长时间未被访问的页。
LRU 基于局部性原理：最近被访问的页，很可能在不久的将来再次被访问；很久未被访问的页，很可能在未来也不会被访问。
5.2 示例
引用串：1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5，3 个页框。
| 访问 | 页框状态 | 缺页 |
|---|---|---|
| 1 | 1 | 是 |
| 2 | 1, 2 | 是 |
| 3 | 1, 2, 3 | 是 |
| 4 | 4, 2, 3（换出 1） | 是 |
| 1 | 4, 1, 3（换出 2） | 是 |
| 2 | 4, 1, 2（换出 3） | 是 |
| 5 | 5, 1, 2（换出 4） | 是 |
| 1 | 5, 1, 2（命中） | 否 |
| 2 | 5, 1, 2（命中） | 否 |
| 3 | 5, 3, 2（换出 1） | 是 |
| 4 | 5, 3, 4（换出 2） | 是 |
| 5 | 5, 3, 4（命中） | 否 |
缺页次数：9 次。
图 5：LRU 算法的缺页情况。
5.3 LRU 的实现
LRU 的实现需要记录每个页的访问时间或维护访问顺序。常见实现方式：
| 实现方式 | 说明 | 开销 |
|---|---|---|
| 链表 | 访问页时移到链表头，换出时取链表尾 | 中 |
| 计数器 | 每个页记录访问时间戳，换出时间戳最小的 | 大 |
| 栈 | 用栈维护访问顺序 | 大 |
5.4 LRU 的优缺点
| 优点 | 缺点 |
|---|---|
| 缺页率较低 | 实现开销大 |
| 符合局部性原理 | 需要额外硬件支持 |
| 不会产生 Belady 现象 | 维护访问顺序成本高 |
5.5 LRU 与 OPT 的对比
LRU 是“向前看”的 OPT 的“向后看”版本：
- OPT：换出未来最长时间不访问的页；
- LRU：换出过去最长时间未访问的页。
LRU 用过去预测未来，虽然不如 OPT，但实际效果通常很好。
六、时钟算法（Clock）
6.1 为什么需要 Clock 算法？
LRU 算法效果好，但实现开销大。每次访问都要更新访问顺序，硬件成本高。实际系统中，需要一种近似 LRU 且开销小的算法。
时钟算法（Clock）就是一种近似 LRU 的算法，也叫二次机会算法（Second Chance）。
6.2 算法思想
Clock 算法把页框组织成一个环形链表，类似时钟。每个页框有一个访问位（Reference Bit）：
- 访问位为 1：该页最近被访问过；
- 访问位为 0：该页最近未被访问。
指针指向一个页框。需要换出时：
- 检查指针指向的页框；
- 如果访问位为 1，把它置为 0，指针前移（给它“第二次机会”）；
- 如果访问位为 0，换出该页，指针前移。
图 6：Clock 算法的流程。 访问位为 1 时给第二次机会。
6.3 示例
假设页框中的页为：A（访问位 1）、B（访问位 1）、C（访问位 0）、D（访问位 1）。指针指向 A。
需要换出时：
- A 访问位 1 → 置 0，指针移到 B；
- B 访问位 1 → 置 0，指针移到 C；
- C 访问位 0 → 换出 C，指针移到 D。
图 7：Clock 算法的示例。 C 的访问位为 0，被换出。
6.4 Clock 的优缺点
| 优点 | 缺点 |
|---|---|
| 实现简单 | 只是近似 LRU |
| 开销小 | 效果不如 LRU |
| 不需要额外硬件 | 访问位精度有限 |
6.5 改进型 Clock 算法
改进型 Clock 算法同时考虑访问位和修改位，优先换出“未访问且未修改”的页。
| 访问位 | 修改位 | 优先级 |
|---|---|---|
| 0 | 0 | 最高（直接换出） |
| 0 | 1 | 较高（需要写回） |
| 1 | 0 | 较低 |
| 1 | 1 | 最低 |
改进型 Clock 算法减少了磁盘写回次数，提高了性能。
七、三种算法的对比
7.1 缺页次数对比
以引用串 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5、3 个页框为例：
| 算法 | 缺页次数 |
|---|---|
| OPT | 9 |
| FIFO | 9 |
| LRU | 9 |
| Clock | 近似 LRU |
这个例子中三种算法缺页次数相同。但在其他引用串中，差异可能很大。
7.2 综合对比
| 对比项 | OPT | FIFO | LRU | Clock |
|---|---|---|---|---|
| 思想 | 换出未来最久不用的页 | 换出最早进入的页 | 换出过去最久不用的页 | 近似 LRU |
| 实现复杂度 | 无法实现 | 简单 | 复杂 | 中等 |
| 开销 | — | 小 | 大 | 小 |
| 缺页率 | 最低 | 较高 | 较低 | 接近 LRU |
| Belady 现象 | 无 | 有 | 无 | 无 |
| 实际应用 | 理论标准 | 简单场景 | 需要硬件支持 | 实际系统常用 |
图 8：四种页面置换算法的对比。
7.3 算法选择建议
| 场景 | 推荐算法 |
|---|---|
| 理论分析 | OPT |
| 简单嵌入式系统 | FIFO |
| 有硬件支持的系统 | LRU |
| 通用操作系统 | Clock / 改进型 Clock |
| 数据库缓冲池 | LRU / LRU-K |
八、页面置换算法的实际应用
8.1 Linux 中的页面置换
Linux 使用近似 LRU 的算法，称为双链策略：
- 活跃链表：最近被访问的页；
- 非活跃链表：较久未被访问的页。
页在活跃链表和非活跃链表之间移动。需要换出时，从非活跃链表尾部取。
# 查看内存统计
cat /proc/meminfo | grep -i active
8.2 Windows 中的页面置换
Windows 使用工作集（Working Set）模型，结合 LRU 和 Clock 算法。每个进程有一个工作集，记录当前活跃的页。当工作集超过限制时，换出最久未使用的页。
8.3 数据库中的页面置换
数据库系统（如 MySQL、PostgreSQL）有自己的缓冲池管理算法：
- LRU：最常用，但可能被全表扫描污染；
- LRU-K：考虑最近 K 次访问，更准确；
- 2Q：结合 LRU 和 FIFO，避免污染。
图 9：页面置换算法的实际应用。
九、常见误区澄清
| 误区 | 真相 |
|---|---|
| “FIFO 是最好的算法” | FIFO 简单但缺页率可能较高 |
| “LRU 可以完美实现” | LRU 需要硬件支持，实际系统多用近似 LRU |
| “OPT 可以实际使用” | OPT 需要预知未来，无法实现 |
| “Clock 算法就是 LRU” | Clock 是近似 LRU，效果不如 LRU |
| “增加页框一定减少缺页” | FIFO 可能产生 Belady 现象 |
| “页面置换算法只影响性能” | 还影响磁盘寿命（写回次数） |
| “所有系统都用同一种算法” | 不同系统、不同场景使用不同算法 |
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
5
0- 0
已为社区贡献27条内容
所有评论(0)