您的当前位置:首页正文

改进型时钟置换算法

2024-12-12 来源:个人技术集锦

简单的时钟置换算法只考虑到最近一个页面有没有被访问过,没考虑到这个页面有没有被修改过。

如果这个页面没有被修改过就不需要执行I/O操作被写回外村。

为了满足被淘汰的页面是被修改过的才需要写回外存,我们为其增加了一个修改位。

修改位=0,则表示没有被修改过。

修改位=1,表示页面被修改过。

总之,我们现在应该要使用(访问位,修改位)的形式表示各个页面的状态。

如:(1,1)表示该页面最近被访问过,而且被修改过。

啥时候应该被写回外存?

扫描找到(0,0)的页面。

最近没被访问也没被修改的页面才是优先级最高被置换出来的。

算法规则:将所有可能被置换的页面排成一个循环队列。

第一轮:从当前位置开始扫描到第一个(0,0)的页帧(页面),第一轮不做任何标志位上的修改。

第二轮:查找第一个(0,1)的页帧用于替换,将所有的页帧访问位设置为0。

第三轮:查找第一个(0,0)的页帧用于替换,本轮不修改任何标志位。

第四轮:查找第一个(0,1)的页帧用于替换。

显示全文