操作系统实验五：手写 FIFO / LRU / OPT 页面置换模拟器（附完整代码与结果分析）
📌 《操作系统实验笔记》· 实验五：存储管理——页面置换算法模拟
作者：AVA
环境：Linux（glibc）+ gcc⚠️ 看之前先注意一件事：
rand()的实现依赖 C 库。同一个seed，在 Linux/glibc 和 Windows/MinGW（UCRT）下生成的指令流并不相同，结果表不能直接对比。本文数据在 glibc 环境跑出；换平台前先看第八节。
用 320 条指令构造页地址流，在 4~32 个物理块下分别模拟 FIFO、LRU、OPT 三种页面置换算法，统计缺页次数和命中率。代码不长，但把「虚拟存储 → 缺页 → 置换 → 统计」这条链路完整走了一遍。
这篇文章按「原理 → 数据结构 → 三个算法 → 结果分析 → 踩坑」的顺序写。重点不是贴代码，而是解释三个算法为什么只差十几行，以及结果表里哪些地方和教科书直觉不一样。
一、实验目标与环境
这次实验要解决四个问题：
- 请求分页里，一次内存访问到底发生了什么？
- 内存满了以后，FIFO / LRU / OPT 分别淘汰谁？
- 怎么用缺页次数和命中率评价一个置换算法？
- 物理块数从 4 增加到 32，命中率会怎么变？有没有反直觉的地方？
实验环境
| 项目 | 值 |
|---|---|
| 操作系统 | Linux（glibc 环境） |
| 编译器 | gcc |
| 编辑器 | VS Code / 任意文本编辑器 |
| 运行方式 | 命令行，带一个 seed 参数 |
编译与运行
gcc -O2 -Wall -o page_replacement page_replacement.c
./page_replacement 12345
Windows 下可执行文件带 .exe，运行 page_replacement.exe 12345。
不传 seed 时，程序用 time(NULL) 当种子；每次运行都会把 seed 打印出来，方便复现。
二、原理速览：一次访问发生了什么
请求分页系统里，页表项至少有两个关键信息：这个虚页在不在内存、在哪个物理块。代码里用 pl[cur].pfn == INVALID 判断前者。
一次访问的流程可以压缩成：
访问页号 cur
│
├─ pfn != INVALID ──→ 命中（LRU 要更新访问时间）
│
└─ pfn == INVALID ──→ 缺页，diseffect++
├─ 有空闲块 → 直接装入
└─ 没有空闲块 → 选一页淘汰 → 装入
命中率用缺页次数算：
命中率 = 1 - 缺页次数 / 总访问次数 = 1 - diseffect / 320
页面置换的核心目的不是“省内存”这么简单，而是让进程的虚拟地址空间可以大于物理内存：只把当前要用的页装进内存，其余的留在外存。这样同一台机器能同时跑更多、更大的程序。
但换页是有代价的：一次缺页要访问外存，速度比内存慢几个数量级。所以置换算法要尽量把“马上还要用”的页留在内存里，把缺页率压到可接受的范围。命中率（1 − 缺页率）就是衡量这件事的指标：命中率越高，花在换页上的时间越少。
三、整体设计：三个算法共用一个骨架
三个算法共用同一套“缺页 → 淘汰 → 装入”的骨架，唯一的区别是淘汰时看哪段时间的信息：FIFO 看过去（谁最早进来），LRU 看现在（谁最久没被访问），OPT 看未来（谁下一次访问来得最晚）。
程序的主线只有四步：
生成 320 条指令地址
↓
地址 / 10 → 页地址流（32 个虚页）
↓
for 每个物理块数 frames = 4..32：
↓
逐条访问 page[i] → 缺页？→ 有空闲块？→ 淘汰？→ 装入
↓
统计 diseffect，算命中率
三个算法函数 FIFO()、LRU()、OPT() 的长度差不多，因为它们共用同一个骨架（下面用伪代码表示）：
for (i = 0; i < TOTAL_INSTRUCTION; i++) {
int cur = page[i];
if (pl[cur].pfn == INVALID) { /* ① 缺页 */
diseffect++;
if (freepf_head == NULL) /* ② 没有空闲块 */
/* 淘汰谁？—— 三个算法唯一不同的地方 */;
/* ③ 把拿到的块装给 cur —— 三个算法完全一样 */
} else {
/* 命中：LRU 在这里更新 time，FIFO/OPT 什么都不做 */
}
}
把这段骨架记住，后面三个算法就只需要看“淘汰谁”那几行。
四、两个结构体，两条链
4.1 页表 pl_type：虚页 → 物理块
| 字段 | 含义 | 谁在用 |
|---|---|---|
pn | 虚页号 | 初始化时填，算法里基本不直接用 |
pfn | 物理块号；INVALID 表示不在内存 | 三个算法都靠它判断命中/缺页 |
time | 最近一次访问的时刻 | 只有 LRU 用 |
pl[] 是正查表：给定虚页号，查出它在哪个物理块。
4.2 物理块 pfc_type：物理块 → 虚页
| 字段 | 含义 | 谁在用 |
|---|---|---|
pn | 这个块里装的是哪个虚页 | FIFO 淘汰时要知道该把谁的页表项置为 INVALID |
pfn | 块号（等于数组下标） | 三个算法分配时写回页表 |
next | 链表指针 | 空闲链 / FIFO 忙队列 |
pfc[] 是反查表：给定物理块，查出里面装的是哪个虚页。
4.3 三根指针：同一个数组，两条链
空闲链：freepf_head → [0] → [1] → [2] → ... → NULL
忙队列：busypf_head → [a] → [b] → [c] → busypf_tail
- 分配：从空闲链头摘一个块，挂到忙队列尾。
- 淘汰（FIFO）：从忙队列头摘一个块，清掉旧页的页表项，再重新分配。
- 同一个
pfc[]数组里的节点，在两条链之间“搬家”，不需要额外拷贝。
这里有一个实现上的小技巧：pfc[i].pfn == i，所以 LRU/OPT 淘汰时可以用页表里的块号直接反查数组下标：
freepf_head = &pfc[pl[minj].pfn];
把“搬家”过程画出来，三根指针的关系就很清楚了（以 3 个物理块为例）：
初始：
空闲链 freepf_head → [0] → [1] → [2] → NULL
忙队列 busypf_head = busypf_tail = NULL
装入页 A（第 1 次缺页）：
空闲链 freepf_head → [1] → [2] → NULL
忙队列 busypf_head / busypf_tail → [0: A]
装入页 B（第 2 次缺页）：
空闲链 freepf_head → [2] → NULL
忙队列 busypf_head → [0: A] → [1: B] ← busypf_tail
没有空闲块，淘汰 A（FIFO）：
1. 从忙队列头摘下 [0: A]；
2. 把页表 pl[A].pfn 置为 INVALID；
3. 把 [0] 重新装上新页 C，挂到队尾；
4. busypf_head 后移，busypf_tail 指向 [0: C]。
为什么 busypf_tail 必须单独维护？因为 FIFO 要在队尾 O(1) 追加新装入的页。如果只留 busypf_head，每次追加都要从头遍历整个队列，单次缺页就退化成 O(物理块数)。头指针负责淘汰，尾指针负责追加，两个操作都保持 O(1)。
4.4 初始化：每个算法都从干净状态起跑
initialize(total_pf) 做三件事：
diseffect = 0；- 把
TOTAL_VP个页表项的pfn置为INVALID、time置为-1； - 把
pfc[0..total_pf-1]串成空闲链，busypf_head = busypf_tail = NULL。
三个算法函数开头都会先调它，所以 FIFO 跑完留下的链表状态不会带进 LRU/OPT。这一点在对比实验里很重要：每个算法都必须从同一条指令流、同一个初始状态起跑，结果才有可比性。
五、指令流与页地址流
5.1 为什么要“造”一条指令流
真实程序的访问有两个特点：大部分时间是顺序执行，偶尔跳回前面。这叫局部性。如果地址完全随机，三种算法的差距会小很多；正因为有局部性，LRU 的“最近用过”才有意义。
代码用经典规则生成 320 条指令：50% 顺序 + 25% 前地址 + 25% 后地址。每 4 条一组：
a[i] = m; /* 随机起点 */
a[i + 1] = m + 1; /* 顺序执行 */
mp = rand() % (m + 1); /* 往前跳，mp ∈ [0, m] */
a[i + 2] = mp;
a[i + 3] = mp + 1; /* 再顺序执行 */
m = low + rand() % (...); /* 下一组起点 */
5.2 两个容易写错的边界
max_start = 318而不是 319：因为要保证a[i+1] = m+1 <= 319。如果按某些教材写成rand() % 320，m可能取到 319，a[i+1]就写到 320，数组越界。low = mp + 2可能超过 318：所以后面有一句if (low > max_start) low = max_start;，否则rand() % (max_start - low + 1)的模数会变成 0 或负数。
5.3 地址除法得到页号
page[i] = a[i] / PAGE_SIZE; /* 每页 10 条指令 */
320 条指令、每页 10 条，所以正好 32 个虚页。注意：TOTAL_VP 和 PAGE_SIZE 是分开定义的，改一个要同步改另一个（TOTAL_VP = TOTAL_INSTRUCTION / PAGE_SIZE），否则页号可能越界。
以 seed = 12345 为例，前 20 条地址和页号是：
address: 182 183 77 78 252 253 233 234 304 305 79 80 298 299 5 6 239 240 168 169
page: 18 18 7 7 25 25 23 23 30 30 7 8 29 29 0 0 23 24 16 16
这里的关键是：页号不是指令地址，而是指令地址除以页大小后向下取整。
PAGE_SIZE = 10，所以地址 0~9 属于第 0 页，10~19 属于第 1 页，……，310~319 属于第 31 页。182 和 183 都在 180~189 这一段，整数除法 182 / 10 和 183 / 10 都等于 18，所以它们落在同一页；77 和 78 同理，都落在第 7 页。
320 条指令、每页 10 条，正好得到 32 个虚页。这也是为什么后面的物理块数最大取 32：块数给到 32，就能把所有虚页一次装完。
六、三种置换算法
6.1 FIFO：淘汰最早进来的
判据：忙队列按装入顺序排列，队头就是最早进来的页。
关键代码：
if (freepf_head == NULL) {
p = busypf_head->next;
pl[busypf_head->pn].pfn = INVALID; /* 旧页不在内存了 */
freepf_head = busypf_head; /* 它的块被收回 */
freepf_head->next = NULL;
busypf_head = p; /* 队头后移 */
}
命中时 FIFO 不移动队列——它只关心“什么时候进来的”，不关心“用了多少次”。
用 3 个物理块，页序列 1 2 3 4 1 2 5 1 2 3 4 5 走一遍 FIFO。为了看清“谁最早进来”，内存里的页按装入顺序从左到右排列，最左边是队头：
| 访问 | 3 块内存 | 3 块是否缺页 | 4 块内存 | 4 块是否缺页 |
|---|---|---|---|---|
| 1 | 1 | 缺 | 1 | 缺 |
| 2 | 1, 2 | 缺 | 1, 2 | 缺 |
| 3 | 1, 2, 3 | 缺 | 1, 2, 3 | 缺 |
| 4 | 2, 3, 4 | 缺 | 1, 2, 3, 4 | 缺 |
| 1 | 3, 4, 1 | 缺 | 1, 2, 3, 4 | 命中 |
| 2 | 4, 1, 2 | 缺 | 1, 2, 3, 4 | 命中 |
| 5 | 1, 2, 5 | 缺 | 2, 3, 4, 5 | 缺 |
| 1 | 1, 2, 5 | 命中 | 3, 4, 5, 1 | 缺 |
| 2 | 1, 2, 5 | 命中 | 4, 5, 1, 2 | 缺 |
| 3 | 2, 5, 3 | 缺 | 5, 1, 2, 3 | 缺 |
| 4 | 5, 3, 4 | 缺 | 1, 2, 3, 4 | 缺 |
| 5 | 5, 3, 4 | 命中 | 2, 3, 4, 5 | 缺 |
数一下：3 个块缺页 9 次，4 个块缺页 10 次。块数增加了，缺页反而更多，这就是 Belady 异常。
原因在于 FIFO 的淘汰顺序依赖“装入时刻”，而装入时刻又受物理块数影响：块数一变，同一个页的装入顺序可能完全变了，于是它保留了不同的页。FIFO 不满足栈式算法“m 个块的驻留集一定是 m+1 个块驻留集的子集”这一性质，所以会出现这种反直觉现象。LRU 和 OPT 是栈式算法，不会出现 Belady 异常。
6.2 LRU：淘汰最久没用的
判据：给每个页记一个“最近一次访问时间”，淘汰 time 最小的页。
关键代码：
/* 不管是命中还是缺页装入，每次访问都要更新 */
pl[cur].time = present_time;
present_time++;
/* 淘汰：扫一遍页表，找 time 最小的在内存页 */
min = INF;
minj = -1;
for (j = 0; j < TOTAL_VP; j++)
if (pl[j].pfn != INVALID && pl[j].time < min) {
min = pl[j].time;
minj = j;
}
freepf_head = &pfc[pl[minj].pfn];
代码里 pl[cur].time = present_time; 分别写在命中分支和缺页装入分支，效果都是每次访问更新一次。
LRU 完全不用忙队列，它靠页表里的时间戳找“最久没用过”的页。
如果只在缺页时更新 time，命中时不更新，会发生什么？
time 记录的是“这个页最近一次被访问是什么时候”。如果命中不更新，一个刚刚被反复访问的页，时间戳还停留在它第一次装入的时刻，看起来反而“很老”。下次缺页时，LRU 就可能把它当成最久未使用的页淘汰掉。
举个 3 个块的例子：页序列 1 2 3 1 1 4。前三个页依次装入；接着两次访问 1 都是命中。如果命中不更新时间，此时 time(1) 仍是最小的，访问 4 触发缺页时，LRU 会淘汰刚刚用过两次的 1，而不是真正最久没用的 2。正确的 LRU 更新后，time 从小到大是 2、3、1，应该淘汰 2。
为什么 present_time 每处理一条指令都要自增？
因为 LRU 比较的是“访问的先后顺序”，不是“缺页的先后顺序”。命中也是一次访问，它同样会把该页的“最近使用时间”刷新到当前时刻。如果只在缺页时自增，时间戳就无法区分“两个都在内存里的页，谁刚刚被访问过”，LRU 的判据就失真了。present_time 是一条逻辑时钟，每访问一条指令走一格，才能准确表示“最近”。
6.3 OPT：淘汰未来最远才会用的
判据：往后看，找出每个在内存的页下一次什么时候被访问；淘汰“下一次最晚”或“以后再也不用了”的页。
关键代码分三步：
/* ① 先假设在内存的页都是“以后不再用” */
for (j = 0; j < TOTAL_VP; j++)
dist[j] = (pl[j].pfn != INVALID) ? INF : 0;
/* ② 从当前位置往后扫，只记第一次出现 */
for (j = i + 1; j < TOTAL_INSTRUCTION; j++) {
int pj = page[j];
if (pl[pj].pfn != INVALID && dist[pj] == INF)
dist[pj] = j - i;
}
/* ③ 取 dist 最大的页淘汰 */
INF 表示“以后不再使用”，优先级最高；不在内存的页 dist = 0，永远不会被选中。
dist[j] 的含义是：页 j 下一次被访问，距离当前位置还有多远。三步分别解决“谁是候选”“下一次在哪”“淘汰谁”。
① 先把在内存的页设成 INF，不在内存的设成 0。 只有已经在内存里的页才可能被淘汰，所以不在内存的页给 0，后面取最大值时永远不会选中它们；在内存的页先统一设成 INF，表示“暂时假设以后不再使用”，等第二步再用真实的下一次访问距离覆盖。
② 向后扫描时，只在 dist[pj] == INF 时赋值。 因为扫描是从 i+1 往后走，第一次遇到某个页的位置，就是它的“下一次访问”；只有 dist 还是 INF 时才写，保证一个页只记录第一次出现。如果每次都覆盖，记下来的会变成“最后一次出现”的距离，淘汰判据就完全错了。
③ 取 dist 最大的页淘汰。 dist 越大，说明这个页下一次被访问越晚；INF 表示以后再也不用了，是最理想的淘汰对象。OPT 的“最优”就来自这里：它每次都淘汰未来最晚才需要的页，所以缺页次数不可能比任何其他算法更少。
OPT 为什么不能用在真实操作系统里？ 因为它需要知道未来的页访问序列。真实系统只能看到已经发生的访问，无法预知下一个页是什么；所以 OPT 只能作为离线分析的理论上界，用来衡量 FIFO/LRU 离最优还有多远。
6.4 三者对比
| 算法 | 看什么 | 靠什么找淘汰页 | 单次缺页代价 | 真实系统能用吗 |
|---|---|---|---|---|
| FIFO | 过去（装入时间） | 忙队列头 | O(1) | 能，但可能 Belady |
| LRU | 现在（最近访问） | 扫页表找最小 time | O(VP) | 能，但开销大/需硬件支持 |
| OPT | 未来（下次访问） | 向后扫描指令流 | O(剩余指令数) | 不能，只作理论上界 |
一句话记忆：FIFO 看过去，LRU 看现在，OPT 看未来。
理论上，OPT 是命中率的上界；LRU 是栈式算法，不会出现 Belady 异常；FIFO 不是栈式算法，所以“块数增加、命中率反而下降”是有可能发生的。
七、运行结果与分析
7.1 怎么复现
./page_replacement 12345
程序会先打印 seed、前 20 条指令地址和页号，再输出 frames 从 4 到 32 的命中率表。因为 seed 是显式传入的，同一平台、同一个 C 库下结果可复现。
7.2 为什么从 4 个块跑到 32 个块
- 4 是代码设定的下限，用来观察“内存很紧张”时的表现；
- 32 等于虚页总数，32 个块能把所有页都装下，此时任何置换算法都不会再淘汰页面，三个结果必然相同——这正好是一个内置的正确性对照。
如果 32 块时三个算法结果不一样，说明某个算法的分配/淘汰逻辑写错了。
7.3 seed = 12345 的结果
表里是命中率；想看缺页率，用 1 - 命中率。
| 物理块数 | FIFO | LRU | OPT |
|---|---|---|---|
| 4 | 0.5000 | 0.5000 | 0.6250 |
| 5 | 0.5219 | 0.5156 | 0.6594 |
| 6 | 0.5406 | 0.5406 | 0.6844 |
| 7 | 0.5469 | 0.5625 | 0.7063 |
| 8 | 0.5687 | 0.5719 | 0.7250 |
| 9 | 0.5781 | 0.5844 | 0.7438 |
| 10 | 0.5906 | 0.5969 | 0.7594 |
| 11 | 0.6281 | 0.6250 | 0.7750 |
| 12 | 0.6438 | 0.6312 | 0.7906 |
| 13 | 0.6500 | 0.6438 | 0.8031 |
| 14 | 0.6562 | 0.6719 | 0.8156 |
| 15 | 0.6781 | 0.6937 | 0.8250 |
| 16 | 0.7000 | 0.7063 | 0.8344 |
| 17 | 0.7250 | 0.7406 | 0.8438 |
| 18 | 0.7312 | 0.7562 | 0.8500 |
| 19 | 0.7406 | 0.7625 | 0.8562 |
| 20 | 0.7781 | 0.7750 | 0.8625 |
| 21 | 0.7906 | 0.7969 | 0.8688 |
| 22 | 0.7937 | 0.8031 | 0.8719 |
| 23 | 0.8156 | 0.8125 | 0.8750 |
| 24 | 0.8250 | 0.8156 | 0.8781 |
| 25 | 0.8250 | 0.8313 | 0.8812 |
| 26 | 0.8531 | 0.8375 | 0.8844 |
| 27 | 0.8531 | 0.8594 | 0.8875 |
| 28 | 0.8531 | 0.8688 | 0.8906 |
| 29 | 0.8781 | 0.8750 | 0.8938 |
| 30 | 0.8812 | 0.8844 | 0.8969 |
| 31 | 0.8875 | 0.8906 | 0.9000 |
| 32 | 0.9000 | 0.9000 | 0.9000 |
7.4 结果分析
① 正确性自检：32 块时三者相同。 表里 frames=32 时 FIFO、LRU、OPT 都是 0.9000。原因很直接：32 个物理块正好等于 32 个虚页，所有页都能装下，装入之后不会再发生置换，缺页只发生在每个页的第一次访问。这条指令流覆盖了全部 32 个页，所以缺页 32 次，命中率 = 1 − 32 / 320 = 0.9000。三个算法结果一致，说明分配和淘汰逻辑没有写错。
② OPT 每一行都最高，符合理论预期。 从 4 块到 32 块，OPT 的命中率始终不低于 FIFO 和 LRU（32 块时三者相等）。这不是巧合：OPT 每次淘汰“未来最晚才用”的页，缺页次数是所有算法里最少的，所以它是命中率的上界。它不能真正实现，但可以作为一把尺子，衡量 FIFO/LRU 离最优差多少。
③ 这条指令流上，FIFO 没有出现 Belady 异常。 从 4 块到 32 块，FIFO 的命中率单调不降（中间有几段持平，比如 24→25 块、26→28 块），没有出现“块数增加、命中率反而下降”。但这只说明 seed=12345 这条指令流没触发，不代表 FIFO 不会发生 Belady——6.1 的手工例子就是反例：3 块缺页 9 次，4 块反而缺页 10 次。根本原因是 FIFO 不是栈式算法。
④ LRU 并不处处赢 FIFO。 表里有 9 行 FIFO 的命中率反而高于 LRU：frames = 5、11、12、13、20、23、24、26、29。比如 5 块时 FIFO 是 0.5219、LRU 是 0.5156；12 块时 FIFO 是 0.6438、LRU 是 0.6312；29 块时 FIFO 是 0.8781、LRU 是 0.8750。原因不是“随机”，而是 LRU 用“最近访问”预测“下一次访问”，这个预测并不总成立：某些访问模式下，LRU 会把马上还要用的页当成最久未用淘汰掉，而 FIFO 的装入顺序恰好留下了这些页。所以“LRU 比 FIFO 好”是统计意义上的经验结论，不是对任意指令流都成立的定理。
7.5 缺页次数还和什么有关
同样的代码，换一组参数，缺页次数会变。主要看四个因素：
| 因素 | 影响 |
|---|---|
| 物理块数 | 块越多，能同时装下的页越多，缺页通常越少；FIFO 可能例外（Belady） |
| 页面大小 | 页越大，一次装入的内容越多，页表越短，但内部碎片越大；本题固定 10 条/页 |
| 指令流局部性 | 顺序/循环越多，命中率越高；纯随机访问会让三种算法都变差 |
| 置换算法 | 同样的块数和指令流，OPT 缺页最少，LRU/FIFO 次之 |
所以看结果表时，不要死记某一行的具体数字，要看趋势和反例；换一个 seed，数值会变，但“OPT 是上界”“LRU 不保证处处赢 FIFO”这些结论仍然成立。
八、踩坑与边界
8.1 把“指令地址”当成了“页号”
一开始看代码时，我只盯着 page[i]，没有注意它是怎么来的，潜意识里把 320 条指令地址当成了页号。准备验收时，老师的问题里有“指令流和页地址流是什么关系”，我才发现中间还有一步 page[i] = a[i] / PAGE_SIZE。
现象：如果直接把 a[i] 当页号去访问 pl[]，地址 0~319 会大面积越界；即使不越界，页表也只有 32 项，根本装不下 320 个“页”。
原因：虚拟页是“地址空间按固定大小切出来的块”，页号 = 地址 / 页大小（向下取整），不是地址本身。
改法：先生成完整的指令地址流，再统一做一次 a[i] / 10 得到页地址流；后面的算法只和 page[] 打交道，不再碰原始地址。
8.2 同一个 seed，Windows 和 Linux 结果不一样
现象：把这份代码原样搬到 Windows（MinGW / UCRT）上编译，用 seed = 12345 运行，前 20 条指令地址会和本文的表对不上，整张命中率表都变了。
原因：rand() 的行为由 C 库实现决定。Linux 的 glibc 和 Windows 的 UCRT/MinGW 用的是不同的随机数发生器，同一个种子生成的序列不同。本文的数据是在 glibc 环境跑的。
改法：如果要跨平台复现，别依赖 rand() 的具体实现；可以自己写一个固定算法的伪随机数生成器，或者把生成的指令流直接保存成文件。本文的做法是把 seed 打印出来，并注明运行平台。
8.3 LRU 命中时忘了更新 time
现象：LRU 的命中率明显偏低，某些刚被访问过的页很快就被淘汰。
原因：只在缺页时更新 time，命中时没有刷新。这样“最近使用”的时间戳停留在旧值，LRU 会把热点页误判成最久未使用。
改法：把 pl[cur].time = present_time; 放在“命中”和“缺页装入”两条路径都会经过的位置，或者两条分支各写一次；同时 present_time 每处理一条指令自增一次。
九、复杂度与改进方向
按 320 条指令、32 个虚页来算，三个算法的开销都很小；但把规模放大，差距就出来了。
| 算法 | 命中 | 缺页 | 总复杂度（n 条指令） |
|---|---|---|---|
| FIFO | O(1) | O(1) | O(n) |
| LRU | O(1) | O(VP) | O(n·VP) |
| OPT | O(1) | O(n) | O(n²) |
几个可以继续做的改进：
- LRU 用双向链表 + 哈希表：把“找最久未使用”从 O(VP) 降到 O(1)，这就是常见的 LRU Cache 实现。
- OPT 预处理“下一次出现位置”：从后往前扫一遍，把每次缺页的 O(n) 降下来；但它仍然需要未来信息，只能做离线分析。
- Clock（二次机会）算法：用引用位近似 LRU，开销比精确 LRU 小，真实操作系统更常用。
- 输出改成百分比/CSV/图表：现在打印的是 0~1 的小数，改成百分比更直观；多跑几个 seed 还能画命中率随帧数变化的折线图。
十、总结
算法层：三个算法的骨架完全一样，区别只在淘汰判据。FIFO 看过去——谁最早装入；LRU 看现在——谁最久没被访问；OPT 看未来——谁下一次访问最晚。把这三句话记住，三个函数的代码差异就很好理解了。
工程层：这个程序用两张表把“正查”和“反查”分开了。页表 pl[] 负责“虚页 → 物理块”，物理块数组 pfc[] 负责“物理块 → 虚页”；同一批 pfc 节点在空闲链和忙队列之间搬家，分配和 FIFO 淘汰都是 O(1)。initialize() 让每个算法都从干净状态起跑，对比才公平。
认知层：跑完数据最大的收获，是发现“教科书结论”和“具体数据”不是一回事。LRU 理论上更符合局部性，但在这条指令流上有 9 个帧数反而输给 FIFO；OPT 最优，却需要未来信息，只能当上界。实验的价值不是背下“LRU 比 FIFO 好”，而是知道这个结论在什么条件下成立、什么时候会被反例打破。
附录：完整代码
编译（Linux / glibc 环境）：
gcc -O2 -Wall -o page_replacement page_replacement.c
运行时把 seed 作为参数传进去，换台机器也能复现同一条指令流：
./page_replacement 12345
完整源码：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
/* 实验五 存储管理——页面置换算法模拟（完整版）
* 编译：gcc -O2 -Wall -o page_replacement page_replacement.c
* 运行：./page_replacement [seed]
*/
#define TOTAL_INSTRUCTION 320 /* 指令流长度 */
#define TOTAL_VP 32 /* 虚页数：320 条指令 / 每页 10 条 */
#define PAGE_SIZE 10 /* 每页 10 条指令 */
#define INVALID (-1) /* 页面不在内存 */
#define INF 32767 /* OPT 中表示“以后不再使用” */
/* 页表项 */
typedef struct {
int pn; /* 虚页号 */
int pfn; /* 物理块号，INVALID 表示不在内存 */
int time; /* LRU 用：最近一次访问时间 */
} pl_type;
/* 物理块控制块 */
typedef struct pfc_struct {
int pn; /* 块中存放的虚页号 */
int pfn; /* 物理块号 */
struct pfc_struct *next; /* 空闲块链表 / FIFO 忙块队列指针 */
} pfc_type;
static pl_type pl[TOTAL_VP]; /* 页表 */
static pfc_type pfc[TOTAL_VP]; /* 物理块数组 */
static pfc_type *freepf_head; /* 空闲块链表头 */
static pfc_type *busypf_head, *busypf_tail; /* FIFO 忙块队列头、尾 */
static int diseffect; /* 缺页次数 */
static int a[TOTAL_INSTRUCTION]; /* 指令地址流 */
static int page[TOTAL_INSTRUCTION]; /* 页地址流 */
/* 生成 320 条指令地址：50% 顺序、25% 前地址、25% 后地址 */
static void generate_instruction_stream(unsigned seed)
{
int i, m, mp, low;
const int max_start = TOTAL_INSTRUCTION - 2; /* 318，保证 m+1 <= 319 */
srand(seed);
m = rand() % (max_start + 1);
for (i = 0; i < TOTAL_INSTRUCTION; i += 4) {
a[i] = m; /* 随机起点 m */
a[i + 1] = m + 1; /* 顺序执行 m+1 */
mp = rand() % (m + 1); /* 前地址 m' ∈ [0,m] */
a[i + 2] = mp;
a[i + 3] = mp + 1; /* 顺序执行 m'+1 */
low = mp + 2; /* 下一段起点 ∈ [m'+2,318] */
if (low > max_start)
low = max_start;
m = low + rand() % (max_start - low + 1);
}
}
/* 指令地址 -> 页地址流：页号 = 地址 / 10 */
static void build_page_stream(void)
{
int i;
for (i = 0; i < TOTAL_INSTRUCTION; i++)
page[i] = a[i] / PAGE_SIZE;
}
/* 初始化页表和空闲块链表 */
static void initialize(int total_pf)
{
int i;
diseffect = 0;
for (i = 0; i < TOTAL_VP; i++) {
pl[i].pn = i;
pl[i].pfn = INVALID;
pl[i].time = -1;
}
for (i = 0; i < total_pf - 1; i++) {
pfc[i].pn = INVALID;
pfc[i].pfn = i;
pfc[i].next = &pfc[i + 1];
}
pfc[total_pf - 1].pn = INVALID;
pfc[total_pf - 1].pfn = total_pf - 1;
pfc[total_pf - 1].next = NULL;
freepf_head = &pfc[0];
busypf_head = busypf_tail = NULL;
}
/* 先进先出（FIFO）：淘汰最早装入的页 */
static double FIFO(int total_pf)
{
int i;
pfc_type *p;
initialize(total_pf);
for (i = 0; i < TOTAL_INSTRUCTION; i++) {
int cur = page[i];
if (pl[cur].pfn == INVALID) {
diseffect++;
if (freepf_head == NULL) {
p = busypf_head->next;
pl[busypf_head->pn].pfn = INVALID;
freepf_head = busypf_head;
freepf_head->next = NULL;
busypf_head = p;
}
p = freepf_head->next;
freepf_head->next = NULL;
freepf_head->pn = cur;
pl[cur].pfn = freepf_head->pfn;
if (busypf_tail == NULL) {
busypf_head = busypf_tail = freepf_head;
} else {
busypf_tail->next = freepf_head;
busypf_tail = freepf_head;
}
freepf_head = p;
}
}
return 1.0 - (double)diseffect / TOTAL_INSTRUCTION;
}
/* 最近最久未使用（LRU）：淘汰 time 最小的页 */
static double LRU(int total_pf)
{
int i, j, min, minj;
int present_time = 0;
initialize(total_pf);
for (i = 0; i < TOTAL_INSTRUCTION; i++) {
int cur = page[i];
if (pl[cur].pfn == INVALID) {
diseffect++;
if (freepf_head == NULL) {
min = INF;
minj = -1;
for (j = 0; j < TOTAL_VP; j++) {
if (pl[j].pfn != INVALID && pl[j].time < min) {
min = pl[j].time;
minj = j;
}
}
freepf_head = &pfc[pl[minj].pfn];
freepf_head->next = NULL;
pl[minj].pfn = INVALID;
pl[minj].time = -1;
}
pl[cur].pfn = freepf_head->pfn;
pl[cur].time = present_time;
freepf_head = freepf_head->next;
} else {
pl[cur].time = present_time;
}
present_time++;
}
return 1.0 - (double)diseffect / TOTAL_INSTRUCTION;
}
/* 最佳置换（OPT）：淘汰下一次使用距离最远的页 */
static double OPT(int total_pf)
{
int i, j, max, maxpage;
int dist[TOTAL_VP];
initialize(total_pf);
for (i = 0; i < TOTAL_INSTRUCTION; i++) {
int cur = page[i];
if (pl[cur].pfn == INVALID) {
diseffect++;
if (freepf_head == NULL) {
for (j = 0; j < TOTAL_VP; j++)
dist[j] = (pl[j].pfn != INVALID) ? INF : 0;
for (j = i + 1; j < TOTAL_INSTRUCTION; j++) {
int pj = page[j];
if (pl[pj].pfn != INVALID && dist[pj] == INF)
dist[pj] = j - i; /* 只记第一次出现 */
}
max = -1;
maxpage = -1;
for (j = 0; j < TOTAL_VP; j++) {
if (dist[j] > max) {
max = dist[j];
maxpage = j;
}
}
freepf_head = &pfc[pl[maxpage].pfn];
freepf_head->next = NULL;
pl[maxpage].pfn = INVALID;
pl[maxpage].time = -1;
}
pl[cur].pfn = freepf_head->pfn;
pl[cur].time = i;
freepf_head = freepf_head->next;
}
}
return 1.0 - (double)diseffect / TOTAL_INSTRUCTION;
}
int main(int argc, char *argv[])
{
unsigned seed;
int frames, i;
double fifo_hit, lru_hit, opt_hit;
if (argc > 1)
seed = (unsigned)strtoul(argv[1], NULL, 10);
else
seed = (unsigned)time(NULL);
generate_instruction_stream(seed);
build_page_stream();
printf("seed = %u\n", seed);
printf("instructions = %d, virtual pages = %d, instructions per page = %d\n",
TOTAL_INSTRUCTION, TOTAL_VP, PAGE_SIZE);
printf("instruction addresses (first 20): ");
for (i = 0; i < 20; i++)
printf("%d ", a[i]);
printf("\npage stream (first 20): ");
for (i = 0; i < 20; i++)
printf("%d ", page[i]);
printf("\n\n");
printf("%-6s %-10s %-10s %-10s\n", "frames", "FIFO", "LRU", "OPT");
printf("----------------------------------------\n");
for (frames = 4; frames <= TOTAL_VP; frames++) {
fifo_hit = FIFO(frames);
lru_hit = LRU(frames);
opt_hit = OPT(frames);
printf("%-6d %-10.4f %-10.4f %-10.4f\n",
frames, fifo_hit, lru_hit, opt_hit);
}
return 0;
}
如果这篇文章对你有帮助，欢迎点赞、收藏；有讲错的地方也欢迎在评论区指出
openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目，面向数字基础设施四大核心场景（服务器、云计算、边缘计算、嵌入式），全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构
更多推荐
0
0- 0
已为社区贡献1条内容
所有评论(0)