3.2.4 页面置换算法
原书定位
印刷页P218起,对应PDF第229页。下文为目视整理的知识提要;完整内容见原书对照。
| 算法 | 淘汰规则 | 要点 |
|---|---|---|
| OPT | 未来最长时间不再使用 | 理论最优,需预知未来,作为比较基准 |
| FIFO | 最早进入内存 | 简单,可能出现Belady异常 |
| LRU | 过去最长时间未使用 | 利用近期行为,维护精确顺序开销较大 |
| CLOCK | 环形扫描访问位 | 为访问过的页清位并给第二次机会 |
| 改进CLOCK | 同时考察访问位A与修改位M | 优先未访问且干净的页,兼顾写回成本 |
Belady异常指增加页框后缺页数反而增加;教材中的OPT与LRU不会出现这种情况。页面命中时FIFO装入顺序不变,LRU最近使用顺序要更新。
改进CLOCK按教材规则先找(A,M)=(0,0),第一轮不清访问位;再找(0,1),本轮同时清扫描过的访问位;未找到则重新扫描。不能简单把四种状态当成一次静态排序。

Belady异常,原书P219。

CLOCK置换示例,原书P220。

CLOCK指针,原书P221。
对应练习
关联知识
原书对照
展开原书对照截图




