clock置换算法

回答
爱扬教育

2022-06-12

  • 相关推荐
时钟置换算法可以认为是一种最近未使用算法,即逐出的页面都是最近没有使用的那个。我们给每一个页面设置一个标记位u,u=1表示最近有使用u=0则表示该页面最近没有被使用,应该被逐出。

扩展资料

  假设我们接下来会访问2号页面,那么可以直接命中指针指向的页面,并将这个页面的标记为u置为1。

  但是考虑一个问题,数据库里逐出的页面是要写回磁盘的,这是一个很昂贵的操作,因此我们应该优先考虑逐出那些没有被修改的页面,这样可以降低IO。

  因此在时钟置换算法的基础上可以做一个改进,就是增加一个标记为m,修改过标记为1,没有修改过则标记为0。那么u和m组成了一个元组,有四种可能,其被逐出的优先顺序也不一样:

  (u=0, m=0) 没有使用也没有修改,被逐出的优先级最高;

  (u=1, m=0) 使用过,但是没有修改过,优先级第二;

  (u=0, m=1) 没有使用过,但是修改过,优先级第三;

  (u=1, m=1) 使用过也修改过,优先级第四。