操作系统考研资料：页面淘汰算法CLOCK.doc

时钟(CLOCK)置换算法LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单， 但性能差所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近 LRU的性能，这类算法都是CLOCK算法的变体简单的CLOCK算法是给每一帧关联一个附加位，称为使用位当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，它的使用位也被置为 1对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联当某一页 被替换时，该指针被设置成指向缓冲区中的下一帧当需要替换一页时，操作系统扫描缓冲 区，以查找使用位被置为0的一帧每当遇到一个使用位为1的帧时，操作系统就将该位重 新置为0;如果在这个过程开始时，缓冲区中所有帧的使用位均为 0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置 为0，并且停留在最初的位置上，替换该帧中的页由于该算法循环地检查各页面的情况， 故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU) 算法CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得 CLOCK算法更加高效。

在使用位的基础上再增加一个修改位，则得到 改进型的CLOCK置换算法这样，每一帧都处于以下四种情况之一：1. 最近未被访问，也未被修改(u=0, m=0)2. 最近被访问，但未被修改(u=1, m=0)3. 最近未被访问，但被修改(u=0, m=1)4. 最近被访问，被修改(u=1, m=1)算法执行如下操作步骤：1. 从指针的当前位置开始，扫描帧缓冲区在这次扫描过程中，对使用位不做任何修改选择遇到的第一个帧（u=0, m=0）用于替换2. 如果第1）步失败，则重新扫描，查找（u=0, m=1）的帧选择遇到的第一个这样的帧用于替换在这个扫描过程中，对每个跳过的帧，把它的使用位设置成 03. 如果第2）步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为 0重复第1步，并且如果有必要，重复第 2步这样将可以找到供替换的帧改进型的CLOCK算法优于简单CLOCK算法之处在于替换时首选没有变化的页由于修改过的页在被替换之前必须写回，因而这样做会节省时间。