当选择置换页面时，依然和FIFO一样，选择最早置入内存的页面。但是二次机会法还设置了一个访问状态位。所以还要检查页面的的访问位。如果是0，就淘汰这页；如果访问位是1，就给它第二次机会，并选择下一个FIFO页面。当一个页面得到第二次机会时，它的访问位就清为0，它的到达时间就置为当前时间。如果该页在此期间被访问过，则访问位置为1。这样给了第二次机会的页面将不被淘汰，直至所有其他页面被淘汰过（或者也给了第二次机会）。因此，如果一个页面经常使用，它的R位总保持为1，它就从来不会被淘汰出去。算法的这个特点使它被称为第二次机会算法。

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

　　为什么说老化算法只是LRU的一个近似？下面用一个例子来说明。页面A和页面B的计数器分别为00100000和00101000。它们都是在最近的两个时钟周期内未被访问，但是没有精确的记录。

　　LRU中是按指令而不是时钟周期记录的，老化算法中只知道它们都是在最近的两个时钟周期内未被访问，但是不知道具体的先后顺序（一个时钟周期有多个指令，A，B总有一个更先被访问）。因此在老化算法中只能看它们计数器值的大小来决定，不是真正的最近最少使用算法，仅仅是它的一个近似。

---

期刊库（http://www.zgqkk.com），是一个专门从事期刊推广、投稿辅导的网站。
　　本站提供如何投稿辅导，寻求投稿辅导合作，快速投稿辅导，投稿辅导格式指导等解决方案：省级投稿辅导/国家级投稿辅导/核心期刊投稿辅导//职称投稿辅导。

---

　　【免责声明】本文仅代表作者本人观点，与投稿辅导_期刊发表_中国期刊库专业期刊网站无关。投稿辅导_期刊发表_中国期刊库专业期刊网站站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。