1.4时钟页面置换算法

　　时钟页面置换算法是对第二次机会算法的改进，也是现实中最常用的页面置换算法之一。第二次机会算法比较合理，但是效率较低，由于它经常需要在链表中移动页面。因此，时钟页面置换算法改进了链表的组织方式。它将所有页面放置在一个类似钟面的环形链表中，用一个表针指向最老的页面。

　　当发生缺页中断时，算法首先检查表指针指向的页面，如果它的R位是0就淘汰该页面，并把置换进来的新的页面插入到这个位置，然后把表针前移一个位置。如果R位是1，那么清除R位并把表针前移一个位置。重复这个过程直到找到了一个R位为0的页面为止。

　　算法的示意图如图2所示。

　　1.5最近最少使用页面置换算法（LRU）

　　1.5.1算法思想介绍

　　LRU算法基于这样的原理：在前面几条指令中频繁使用的页面很可能在后面几条指令中被使用。而已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。

　　因此，可以置换未使用时间最长的页面。这个策略就是LRU（最近最少未使用）页面置换算法的核心。显然，LRU算法的主要问题是如何找出最近未被使用时间最长的页面。

　　1.5.2LRU算法的实现方法

　　方式1：硬件有一个64位的计数器C，它在每条指令执行完后自动加1。每个页表项中有一个足够容纳这个计数器值的域。在每次访问内存之后，将当前的C值保存到被访问页面的页表项中。发生缺页中断时，操作系统检查所有页表项中计数器的值，找到一个该值最小的页面，这个页面显然就是最近最少使用的页面。

　　方式2：在一个有n个页帧的机器中，LRU硬件维持一个初值都为0的n×n位矩阵。当访问到页帧k时，硬件首先把k行的位都置为1，再把第k列的位都置为0。在任何时刻，二进制数值最小的行就是最近最少使用的，第二小的行是下一个最近最少使用的，以此类推。

　　1.5.3LRU算法的优缺点

　　LRU的优点是性能很好，它提供了对最优页面置换算法很好的近似，并且它在理论上可以实现。但是LRU算法的缺点在于它实际上实现很难。因为以上讨论的实现方式都需要硬件的参与，在现实中只有非常少的计算机拥有这种硬件。通常在实践中，人们使用软件方案实现一个LRU的近似算法。最著名的近似LRU算法是最不经常使用页面置换算法（NFU）和老化算法。

　　1.6最不经常使用页面置换算法（NFU）

　　1.6.1算法思想介绍

　　最不经常使用页面置换算法（NFU）是一种用软件实现的对LRU粗略的近似。

　　算法的基本思想是每个页面拥有一个软件计数器，计数器的初始值为0。每次时钟中断时，操作系统扫描内存中的所有页面，将每个页面的R位加到它的计数器上。（R为1则代表在最近的一个时钟周期内页面被访问了，因此页面的该计数器值大致代表了该页面被访问了多少次）。在N个时钟周期内，如果页面有m次R位为1，则表示N个时钟周期内，在m个时钟周期里该页面被访问了，因此这个计数器跟踪了该页面被访问的频繁程度。发生缺页中断时，将置换计数器值最小的页面。

　　算法蕴含的思想是：统计从程序开始运行到现在为止，每个页面被访问的频繁程度。换页时，选择访问最不频繁的页面换出内存。

　　1.6.2NFU算法的问题

　　NFU算法的问题，用一句话简单概括就是：它从来不忘记任何事情。

　　例如，可能某页面一开始被频繁使用，其计数器值可能已经高达10000，但是这个页面在程序运行后期就很少使用了。但是由于前期的频繁访问，它的计数器值已经很高了，因此按NFU算法的原理，它很难被换出，尽管它应该在程序执行的后期被换出才是合理的。

　　1.7老化算法

　　1.7.1算法思想介绍

　　老化算法是对NFU的一个修改，实现了对LRU的很好的近似。

　　对NFU的修改：

　　在R位被加进之前先将计数器右移1位。

　　将R位加到计数器最左端的位而不是最右端的位。

　　发生缺页中断时，将置换计数器值最小的页面。

　　1.7.2算法示例

　　如图3所示，一开始5个页面的计数器值均为0。第0个时钟周期内，各个页面的R位分别为1，0，1，0，1，1，将其加到计数器的最左端得到图3（a）。第1个时钟周期内，各个页面的R位分别为1，1，0，0，1，0，将其加到计数器的最左端得到图3（b）。依此类推，如果图3（e）时发生缺页中断，那么计数器值最小的页面3将被置换。

　　图3老化算法示例

　　1.7.3算法分析

　　这个算法解决了NFU的问题，如果一个页面前期频繁访问，如值为11111111，但是后期不再被访问，它的计数器值会越来越小，从01111111到00111111到00011111到00001111……；相反，如果一个页面前期不被访问，后期频繁访问，它的计数器值会越来越大，从00000000到10000000到11000000到11100000……。

　　一个在最近一个时钟周期内被访问的页面获得的计数器增量是最大的（左端加1，相当于给计数器加了10000000），由于页面最近一次时钟周期被访问了，表示以后可能也要被访问，这个信息的参考价值是最大的，应该提供最大的计数器增量，这是很合理的。而在前一个时钟周期内被访问的页面获得的计数器增量会慢慢变小，由于这个访问记录逐渐成为了历史，可参考价值越变越低，这样设计也是很正常的。这就是蕴含在算法背后的思想。