文章目录
- 1. 改进的时钟置换算法的工作原理
- 2. 改进的时钟置换算法示例
1. 改进的时钟置换算法的工作原理
Clock 算法使用页表项中很重要的 access bit 来表明这个页的访问信息，但需要注意，读和写都是访问，并没有区分到底是读还是写，页表项中除了access bit 之外，还一个 dirty bit，如果这个页做写操作，那么 dirty bit 会置1，如果只是读操作，那 dirty bit 是0。这个 bit 设置也是由硬件来完成，当运行程序对某一页进行访问之后，如果是写操作，硬件会把 access bit 和 dirty bit 都置1，如果是读操作， access bit 是1，dirty bit 还是0，这个 bit 能够区分读和写。
但是区分读和写对页面置换算法有什么帮助？
如果某个页从硬盘读到内存里面来，读进来之后，程序对这个页访问全是读访问，意味着在内存中的这个页的内容和硬盘中存的内容是一致的，如果要把这一页给替换出去，其实不需要把这个页再重新写回到硬盘里去，直接把它释放掉就 OK 了，因为内容是一样的。但是如果程序在访问过程中进行写操作，意味着内存中的数据和硬盘中数据是不一致，如果要把这一页给替换出去，需要把内容写回硬盘，确保硬盘中的数据是最新数据。所以如果通过 dirty bit 判断出来这页在整个访问中没有做写操作，全是读操作，就不需要再去做一次写回操作。
所以这个 bit 可以指导提出一种更高效的 Clock 算法，称为 enhance Clock 算法或者二次机会法。把这两个 bit 都用上了来减少对硬盘的访问。
怎么减少对硬盘的访问？
把所有访问页搞成环形链表，但判断选择哪页时候，不是基于一个 access bit，而基于 access bit dirty bit，这两个 bit 的情况来决定应该选择哪个页给置换出去。
上图是一个例子，选择哪一页？左下角表里面给出映射关系。
- 如果 access bit 和 dirty bit 均为0，会把这个页找出来，替换出去。
- 但如果 access bit 是 0，dirty bit 是1，需要做的是把 dirty bit置为 0，然后指针继续旋转找下一页。
- 同理，如果 access bit 是 1，dirty bit 是 0，会把 access bit 变成 0，dirty bit 保持不变，指针继续往下走。
- 如果说access bit 和 dirty bit 均为1，会把 access bit 变为 0， dirty bit 变为 1 ，指针往下走，假设转一圈，发现是0 1，会变成 0 0。
所以如果一个页的这两个 bit 是1的话，那么它有两次机会让指针经过。但如果说是一个0 和 一个1，那么先变成0 0，再下次经过便被置换出去，只有一次机会。如果都是0 0，没有任何机会，它就是要找被替换出去这个页。
通过这种方式可以把经常使用的 dirty bit 页有更多的机会留在内存中，这是所谓的二次机会法，也是很形象的说法，因为这种访问模式会把写的页有更多机会留在内存中，而那种只读的页会更优先地被换出去，使得写过的页换出概率会减少，从而使得整个对硬盘的访问次数也会减少。
2. 改进的时钟置换算法示例
a b 上面的 w 表示这页的访问是写操作，不是读操作，做个细分。
- 初始情况下 a b c d 都是1 0，代表做了访问，都是读操作，因为dirty bit是0。
- 接下来的4次访问 1 2 3 4，对 c 和 d 做的是读操作，对 a 和 b 是写操作，那做这4次操作之后，对于 a 和 b，从 10 变成 11，而 c 和 d 保持不变还是1 0。因为对 a 和 b 做写操作之后，硬件会把它们 dirty bit 置成1，所以当 4 这个时刻过了之后，环形链表示结构如下。
- 接下来访问 e ，a b c d 存在，但 e 不存在，要把 a，b，c，d 换一个页出去，当产生缺页中断之后，需要看看当前应该选择哪一页给换出去，指针指向 a 位置，那么这时候 两个 bit 是11，会变成 01 ，然后指针往下走， b 也是 11 变成 01，然后再往下走， c 是10 变成00，再往下走， d 也是 10 变成 00。转一圈回来到 a，a 这时候由 0 1 变成 0 0，往下走， b 也是 01会变成0 0，也往下走， c 是 0 0，那对于 dirty bit 和 access bit 是0 0 的页，会把它作为要被换出去页，那其实换出 c，同时指针指向下个地方 d 。由于对 e 做的是读操作，所以说它会设置成1 0。
- 接下来访问 b，所以 b 会变成10，访问 a 会变成11，因为它是写操作，又访问 b，那没有任何变化。
- 第 9 时刻访问 c， 在物理页里面不存在了，这时候就需要去置换哪一页？这时候 d 是00，那么这一页直接被替换掉，指针指向 a，同时第四项会变成 10，放的是 c。
- 访问 d 时候又产生缺页中断，根据刚才特点，走一圈之后替换的是第二项，就是放 b 这个物理页，那么这时候会放 d，把 b 对应地换成 d。
综上，总结出来产生三次缺页中断，还是很接近 LRU 算法，优先地把只读页给换出去，而对于可写页，减少被换出的概率，使得整个内存对硬盘的读写次数会减少，所以说它是对读和写分别对待的一种更好的页置换算法。
