5.2.页面置换算法——简单的Clock置换算法

1.1.算法思想

为每页设置一访问位,将内存中的所有页面链成一个循环队列。当某页被访问时,访问位置1。置换算法在选择一页淘汰时，只需检查页的访问位。如果是0，将该页换出；若为1，将该页重新置0，暂不换出，给予该页第二次驻留内存的机会，再检查下一个页面。

当检查到队列的最后一个页面时，若访问位仍为1，则返回队首去检查第一个页面。

1.2.算法流程

• 访问的页面在内存中：

  • 若该页面的访问位为0，将其置为1
  • 如果为1，仍保留位1

• 访问的页面不在内存中：

  

1.3.示例

在请求分页系统中，假设系统为进程P分配5个物理块，并将页面5,7,3,2预先装入主存且访问位A为1,0,0,0，页面访问串如下，采用Clock页面置换算法。说明：低物理地址优先，替换指针开始指向最低地址的物理块。6,5,2,5,6,3,0,5,6,1,0,7,2,6,5,2,4,6,0,5。

①求缺页中断次数

②求页面置换次数；求页面置换次数；并给出最后主存中的页面P及对应的访问位A的值（用P-A表示）

注：其中：红色表示访问位为1，星号表示替换指针的位置（初始在低地址）。

答案：

• ①缺页次数：9

• ②页面置换次数：8

  主存中的页面及访问位：2-0,4-1,6-1,0-1,5-1