日月明 · 2021 年 408 考 127 分 · 全栈程序员
页面置换算法
第 1 关 · 3 个页框 · 五种算法对比
请求流（完整）
页框满了就点黄色页框选一个淘汰；每种算法规则不同，看上方提示徽章。先在随机教学关熟悉，再挑战经典考题横向对比。
页面置换算法对比链（点开看）
页面置换算法对比链（本游戏 5 套，每套「随机教学 + 经典考题」两关）：
• FIFO：先进先出，淘汰最早装入的。实现最简单，但可能命中率最差（Belady 异常）。
• LRU（Least Recently Used，最久未使用）：淘汰最久没被用过的。精确但硬件代价高（要维护全序）。
• NRU（Not Recently Used，近似）：每页维护 (R,M) 两位，OS 周期性清 R；淘汰时按 (0,0)>(0,1)>(1,0)>(1,1) 选最低类。用周期清 R 近似 LRU 的"最近"。
• Clock：NRU 分类思想的环形实现，用一个指针扫 R 位，R=1 清 0 跳过、R=0 淘汰，免去全序维护。
• 改进型 Clock：在 Clock 上加脏位 M，优先淘汰干净页（M=0，无需写回），减少磁盘 I/O。
本演示约定：偶数页号=写操作（脏位 M=1），奇数页号=读（M=0）；NRU 每 3 次请求 OS 统一把 R 位清零。经典考题串「1 2 3 4 1 2 5 1 2 3 4 5」(3 框) 标准结果：FIFO/Clock 9 缺页、LRU 10 缺页、NRU ≈10 缺页、改进型 Clock ≈8 缺页——可横向对比看出近似算法与脏位优化的效果。
玩法：页面已在页框 → 命中（绿）；页框有空位 → 直接放（缺页但无需淘汰）；页框满了还不在 → 缺页，点黄色页框选择淘汰谁。
提示徽章按算法而异：LRU「第N新」=最近使用排名；FIFO「装N」=装入顺序（命中不刷新）；Clock/改进Clock「R=0/1 M=0/1」+「▶指针」；NRU「类(R,M)」四分类 (0,0)>(0,1)>(1,0)>(1,1)。金色箭头括号仅 LRU 关显示。提示默认教学关开、经典关关，「提示」按钮随时切换。
写操作标注：NRU / 改进Clock 关的请求流中，页号带红色「写」标的 = 写操作（本演示约定偶数页号=写），装入或命中时会把该页框脏位 M 置 1——这正是改进Clock 优先淘汰干净页（M=0，无需写回）的原因。