clock缓存置换算法
简介
clock缓存置换算法(时钟置换算法)是LRU算法的一个变种，其使用环形数组代替链表；- clock缓存置换算法的性能比普通的LRU算法要好；
基本思想
- 每个缓存槽都有一个对应的状态，每当这个缓存槽中的数据被访问后，将状态至为 1，否则为0；
- 设置两个指针A，B；
- A：指向下一个将要被淘汰的位置，每次需要淘汰缓存中，A指针顺时针遍历，找到第一个状态为0的槽，将其淘汰；
- B：指针会定时顺时针遍历，把所有的缓存槽的状态为都重置为0
即逐出的页面都是最近没有使用的那个。给每一个页面设置一个标记位u，
u=1：最近有使用
u=0：该页面最近没有被使用，应该被逐出。
capacity=4, 1->2->3->4->5
改进
时钟置换算法的基础上可以做一个改进，就是增加一个标记为m，
修改过标记为1，没有修改过则标记为0。
那么u和m组成了一个元组，有四种可能，其被逐出的优先顺序也不一样：
- (u=0, m=0) 没有使用也没有修改，被逐出的优先级最高；
- (u=1, m=0) 使用过，但是没有修改过，优先级第二；
- (u=0, m=1) 没有使用过，但是修改过，优先级第三；
- (u=1, m=1) 使用过也修改过，优先级第四。