3.2.4 页面置换算法

教材导航 · 第3章

原书定位

印刷页P218起,对应PDF第229页。下文为目视整理的知识提要;完整内容见原书对照。

算法淘汰规则要点
OPT未来最长时间不再使用理论最优,需预知未来,作为比较基准
FIFO最早进入内存简单,可能出现Belady异常
LRU过去最长时间未使用利用近期行为,维护精确顺序开销较大
CLOCK环形扫描访问位为访问过的页清位并给第二次机会
改进CLOCK同时考察访问位A与修改位M优先未访问且干净的页,兼顾写回成本

Belady异常指增加页框后缺页数反而增加;教材中的OPT与LRU不会出现这种情况。页面命中时FIFO装入顺序不变,LRU最近使用顺序要更新。

改进CLOCK按教材规则先找(A,M)=(0,0),第一轮不清访问位;再找(0,1),本轮同时清扫描过的访问位;未找到则重新扫描。不能简单把四种状态当成一次静态排序。

Belady异常

Belady异常,原书P219。

CLOCK置换示例

CLOCK置换示例,原书P220。

CLOCK指针

CLOCK指针,原书P221。

对应练习

3.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P218,PDF第229页

原书对照,原书P219,PDF第230页

原书对照,原书P220,PDF第231页

原书对照,原书P221,PDF第232页

原书对照,原书P222,PDF第233页