文章目录
- 1.时钟置换算法的工作原理
- 2.时钟置换算法的具体实现过程
- 3. 时钟置换算法示例
1.时钟置换算法的工作原理
需要考虑有没有新的办法，既能有 LRU 算法这种效果，产生缺页次数比较少，同时实现的效率比较简洁和方便，有点类似于 FIFO，只需要维护一个简单 List 就 OK 了。为此提出一种基于时钟的页面置换算法。这是一个形象的比喻，因为它整个处理过程像对闹钟在做相应的操作，所以叫做 clock 页面置换算法。
本来为了精确地统计每页的访问时间，要搞一个链表或者堆栈，那链表或堆栈的顺序，就意味着访问时间的顺序，那精确地记录其实带来开销很大。第一要插到相应的位置，第二还需要查找。
那能不能用一种不太精确，但是能够近似地表明访问的先后顺序的状态呢？
在前面讲页表时候，一个页表项存的是这个页帧号，这个页表项的 index 是页号，页表项里面的内容很重要是页号，这样页帧号和页号就有对应关系了，知道页号，可以知道页帧号，就可以查对应的地址。
除了页帧号之外，还有一些 bit，这些位有很重要的含义。其中有一位叫访问位 access bit ，当程序访问这个页之后，它会把这个页表项中 bit 给置1，置1的过程是由硬件来完成，整个置1过程不需要软件参与，由硬件来完成。当 CPU 访问某个页时候，它会把这个页对应的页表项的 access bit 给置1，这样的话根据这个access bit ，可以把它作为一个粗略的估计，如果这个页被置1，认为这个页最近被访问了，如果这个页是0，认为这个页最近没有被访问。
它只用一个 bit 来表示时间信息，这个表示肯定是不精确的，但它是有效的，clock 算法充分利用这个 access bit 来完成对这个访问时间的粗略估计，同时把这个程序访问的所有页面组成一个环形的链表，这时候通过一个指针指向当前是否要去探测这个页是否是最老页。把它做一个指标来探测，那这个指针走一圈，不停地在走，不停地在转，来查找来判断这个页是不是老页，如果是老页就把它换出去，但需要注意，这个老是一个近似的老，或者相对老，它不像刚才说 LRU 算法，那找的确实是最老的页，这也是不太一样。
2.时钟置换算法的具体实现过程
那它怎么来判断老和不老？就是看那个 access bit ，因为硬件访问某一个页之后，把那个页对应页表项中 access bit 给置1，然后操作系统定期会把那个 bit 给清零，操作系统定期清零，进程一旦访问这个页并且access bit 为1，那可以简单地、粗略地估计说这个页最近被访问了，如果是0，意味着有段时间没被访问。
clock 算法通过把所有的页组成一个环形链表，有一个指针，就像时钟一样，指针不停地扫描这个页表，看看access bit 是 0 还是1，如果是1，它认为这个页正在被访问，如果是0，认为这个页有段时间没访问，认为是老页，认为这个页可以被换出去，这种方式就可以把老页给找出来。它里面依据是 access bit，这个是很重要一个特例。
基于上图来看，假设运行程序有5个物理页帧，它可能在系统里面要访问的虚拟页有8个，建好一个环形的 List， 虚拟页有 7 4 0 3 1，这5个虚拟页放物理内存中：
- 同时最左边这一位代表它是否存在，如果是1，代表这个页在物理内存中存在，一旦存在代表这个映射关系是正常的
- 第二位代表 access bit，如果是1代表当前这个页已经被访问一次，然后硬件把它置1了
- 再后面 0 3 4 1 5 是页帧号
这里面首先要关注它的映射是合理的，即存在位必须是1，假定它们都是1了，Clock 算法依据第二个 bit，以这个 bit 作为置换依据。 Cloud 算法首先有一个指针，指针指向了它上一次访问的位置，访问这个环形列表的位置。这时候这个程序还在正常地跑，当它访问某一页产生了缺页中断，它需要去把新的页调到物理内存中来，发现5个物理页帧已经满了，那需要替换，怎么替换？
- 从当前指针指向页目录项来看它的情况，当前指针指向虚拟页0对应的页表项，页表项里面access bit 是1，意味着这个页最近刚被访问过。所以它做处理时，第一要把这个 bit 清零，同时指针顺时针往下挪一格，去看下一个页表项存的信息是什么。
- 然后再找页号为 3 的页表项，看它的access bit也是1，再挪一格。
- 依此类推，一直找到 access bit 为0的页表项，一旦找到，这个页表项对应的物业页帧就应该被替换出去。比如这里面虚拟页为1的页表项，它就会替换出去，会替换成当前缺页时候需要访问的虚拟页号，就把那个页面内容填到这个物理页里面去。
简单地再回顾一下怎么来做，把所有这些页形成一个 List 环，指针指向当前被置换页的位置，然后判断 access bit 为1，就把它清 0，然后去寻找下个位置，为0，把这个页拎出来作为要去替换的页，这就是 Clock 算法。
3. 时钟置换算法示例
同样的序列，如果采取 Clock 算法，那和 LRU 算法和 FIFO 算法相比，它会产生多少缺页中断？
-
完全一样的初始条件和访问序列，前四次访问序列是 c a d b，因为 a，b，c，d 都已经在物理页帧中，由于访问 4 次之后，硬件会把 access bit 置成1，指针指向 a 位置。
-
接下来访问 e 时候，产生了一次缺页中断，基于 Clock 算法，首先看当前指针指向那个位置它的 access bit 是多少，如果是 1 把它变成 0，然后指针继续旋转往下挪，如果是1，继续变成0，走一圈，都把它变成0，再回来第二次再访问 a 的时候，是第一次碰到0，那么这个页就会做被替换页，同时这个指针指向下一个位置 b，替换 a 之后，a 的位置放虚拟页 e 的内容，所以 e的 access bit 是 1 ，硬件置 1 了，但是它的内容已经从 a 变成了 e。
-
接下来再访问 b ，需要注意，虽然没有产生中断，但是硬件会把它的 b 的 access bit 置成1。
-
访问 a，时钟指向的是 b 这个位置，所以说会把它变成 0，同时指针跳到下一项 c，因为c 的access bit 是 0，所以要替换页是c，替换掉之后会把 a 放进去，同时把 access bit 置1，指针指向下一个。
-
再接下来访问的是 b，需要注意刚才 b 的 access bit 是0，所以硬件会把它置成1.
-
再接下来访问 c， 由于 d 的 access bit 是0，则开始就把这个页找到了， d 替换出去，所以把放 d 位置 换成 c，同时指针移到下一项 e
-
又访问 d，从 e 这位置开始往下走，接下来的四项都是1，那转一圈，转回来之后把第一项 e 给它替换掉，存成 d，同时执行下一个。
可以看到它产生了四次缺页中断，比 LRU 要稍微差一些，与FIFO 差不多，当然这个序列给得很短，在实际系统里面，Clock 页面置换算法和 LRU 算法的缺页中断次数其实接近，因为它用了一个 bit 来模拟了整个历史信息，它不精确，所以它达不到 LRU 最佳的效果，但是可以接近这个效果。
