评价标准
- 缺页发生频率少，防止系统发生抖动（Thrashing）
- 算法本身的复杂度小
驻留集（Resident Set）
- 进程当前在内存中的物理页帧集合
- 固定驻留集 + 局部置换：每个进程分配固定页帧数，只在本进程内置换
- 可变驻留集 + 全局置换：动态调整驻留集大小，系统范围内置换
重点 固定驻留集算法
FIFO（先进先出）
- 淘汰最早进入内存的页面（队列实现：队首淘汰，队尾插入）
- 实现简单，无需额外硬件支持，但效果差
- Belady 异常：分配更多页帧反而缺页更多
- 演算示例（访问串
7,0,1,2,0,3,0,4,2,3,0,3,2，驻留集=3）：- 7→0→1 依次入内存；访问 2 时缺页，淘汰最早进入的 7
- 访问 3 时缺页，淘汰当前最早的 0 … 依次类推
OPT（最佳置换）
- 淘汰未来最长时间内不再访问的页面（或永不访问的页面）
- 理论上缺页中断次数最少
- 不可实现（未来访问串未知）
- 价值：作为理论参照标准（性能下界标尺）
重点 LRU（最近最久未使用）
- 淘汰过去最长时间未被访问的页面（” 往后看未知，往前看已知 ”）
- 栈式算法：驻留集大小为 M 时的页帧集合 ⊆ 驻留集为 M+1 时的页帧集合
- 无 Belady 异常（栈式算法可证明，驻留集增大时缺页次数一定不增）
- 实现：每页帧配计数器，访问时清零、其余加一，淘汰计数值最大的页
- 性能好，但实现代价高（需额外硬件支持）
Clock（时钟算法 / 第二次机会）
- 物理页帧组成循环链表（钟面），指针（钟针）在其中旋转
- 页表增加访问位，循环检查：
- 访问位 = 1 → 置 0，指针下移（给第二次机会）
- 访问位 = 0 → 淘汰
- 若全部访问位均为 1，转一圈后全部变 0，回到原点淘汰
- 性能接近 LRU，实现简单（仅需一位访问位）
NRU（最近未使用算法）
- 结合 FIFO 和 LRU 思想：页表项增加使用位，定时清零
- 淘汰优先级（同时考虑使用位和修改位）：
- 使用位=0，修改位=0（最优先，无需回写外存）
- 使用位=0，修改位=1（需回写）
- 使用位=1，修改位=0
- 使用位=1，修改位=1（最后）
- 优先淘汰修改位=0 的页面：避免回写开销
动态驻留集算法
程序形态
- 局部性形态：程序在一段时间内工作于某个局部热点（工作集）
- 阶段转换形态：执行热点从工作集 A 跳转到工作集 B
工作集模型（Working Set, WS）
- 设置 δ 间隔（delta window），每经过 δ 次页面访问，淘汰在该间隔内未被访问的页面
- 驻留集大小随工作集动态变化
- 实现：每页配计数器，访问时清零、其余加一；淘汰计数器值 = δ 的页
- 开销大（每页一个计数器）
SWS（Sampled Working Set）
- 改进 WS：页表项中记录当前时间戳（访问时写入时钟值）
- 操作系统定时检查：
当前时钟值 - 页表项时间戳 > δ→ 淘汰 - 无需额外计数器，硬件消耗仍较大
实用 OS 策略：SWS + 延迟清除
- 自由列表（Free List）：修改位=0，页面内容无需回写
- 修改列表（Modified List）：修改位=1，待回写
- 修改链过长或自由链过短时，将修改链页面回写外存后移至自由链
- 缺页中断时，从自由链直接分配物理页帧（数据可覆盖）
- 关键优化：若自由链/修改链中的页面被再次访问，只需将合法位置 1，无需从外存重新加载
缺页频率控制（PFF）
- 动态调整进程的驻留集大小，防止抖动
- 驻留集 < 工作集 → 频繁抖动
- 驻留集 >> 工作集 → 内存浪费
多级页表
- 为什么需要：32 位系统，页大小 4K（2¹²），页表项 4B → 页表需 2²² = 4MB 连续物理空间。页表本身也可分页存储，避免大块连续分配
- 二级页表结构（10+10+12）：
- 页内偏移：12 位
- 二级页号（内层页表）：10 位
- 页目录号（一级页表）：10 位
- 地址转换：先查页目录 → 获二级页表地址 → 查二级页表 → 获物理帧号 → 拼接偏移
- 计算示例：逻辑地址空间 2¹⁶ 个页（64MB），页大小 1K（10 位偏移），页表项 2B：
- 每页可存放页表项数：1K / 2B = 2⁹ = 512 项（9 位索引）
- 页目录号位数：26 - 10 - 9 = 7 位 → 128 项
- 64 位系统使用哈希页表（逻辑页号作哈希值，链表解决冲突）
最佳页面大小推导
假设进程平均大小 S 字节，页面大小 P 字节，页表项 1B：
- 页表开销：S/P
- 内部碎片：P/2（每页平均浪费半页）
- 总开销：
C(P) = S/P + P/2 - 求导得最优：
P = sqrt(2S) - 实际系统据此选择页大小（如 4K）
比较
| 算法 | 性能 | 实现开销 | Belady 异常 | 类别 |
|---|---|---|---|---|
| OPT | 最优（理论） | 不可实现 | — | 局部 |
| LRU | 好 | 高 | 无（栈式算法） | 局部 |
| Clock | 较好 | 低 | — | 局部 |
| NRU | 较好 | 低 | — | 局部 |
| FIFO | 一般 | 最低 | 有 | 局部 |
| WS | 好 | 高 | — | 全局 |
| SWS | 好 | 较高 | — | 全局 |