页面置换算法与系统颠簸分析

摘 要： 页面置换算法是操作系统内存管理中的一个重要问题。为了研究不同页面置换算法的区别与联系以及它们对系统颠簸的影响，在此采用了将不同置换算法对比介绍的方法，阐释了几种常见的页面置换算法的原理和思想，并通过它们对系统颠簸影响的分析实验，得到了通过改进页面置换算法解决系统颠簸的三个途径。通过采用局部页面置换算法，动态调整的页面置换算法和跟踪缺页率，可以有效地实现系统颠簸的控制。

关键词： 页面置换算法； 系统颠簸； 缺页中断； 内存管理； 操作系统； 虚拟内存

中图分类号： TN964?34 文献标识码： A 文章编号： 1004?373X（2013）20?0065?06

0 引 言

在系统运行过程中，若程序所要访问的页面不在内存而需要把他们调入内存，但内存已经没有空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的交换区中，这个过程称为页面置换。决定将哪个页面调出，需根据一定的算法来确定，通常，把选择换出页面的算法成为页面置换算法。

置换算法的好坏，将直接影响到系统的性能。当发生缺页中断时，虽然可以随机地选择一个页面置换，但是如果一个被频繁使用的页面被置换出内存，很可能它在很短时间内又要被调入内存，这会带来不必要的开销。 一个好的页面置换算法，应具有较低的页面更换频率。从理论上讲，应将那些以后不再会访问的页面置换出，或者把那些在较长时间内不会再访问的页面调出。这对提高系统性能极其重要。

1 常见的页面置换算法

1.1 最优页面置换算法

1.1.1 算法思想介绍

最佳页面置换算法（Optimal Page Replacement Algorithm，OPT）是一种理想情况下的页面置换算法，它在所有页面置换算法中产生的页错误率最低，但实际上该算法是不可能实现的。

该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也就是下一条指令要访问的那一页），而其他页面则可能要到10、100或者1 000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。

最佳页面置换算法规定：标记最大的页应该被置换。例如，如果某页在800万条指令内不会被使用，另一页在600万条指令内不会被使用，则置换前一个页面。这个算法惟一的一个问题就是它无法实现，因为当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然最佳页面置换算法不可能实现，但是该算法可以用于对可实现算法的性能进行衡量比较。如果一个页面置换算法不是最优的，但是它的性能与最优置换相比相差不大（如仅有2%的性能差距），那么就可以判定该算法是有实用价值的。

1.1.2 算法分析

从理论上说，当置换一个页面出内存时，被置换出的页面在将来仍然需要被访问，那个时候将发生缺页中断。既然不好的事情（缺页中断）总会发生，计算机也和人一样，希望把不愉快的事情尽可能地向后拖延。一个最好的页面置换算法应该把因为需要调入这个页面而发生的缺页中断推迟到将来，越久越好。因此选择最久之后才会被访问的页面换出内存是理论上最佳的，这也是这个算法被称为最优置换的原因。

1.2 先进先出页面置换算法（FIFO）

1.2.1 算法思想介绍

FIFO算法总是淘汰在内存中停留得最久的那个页面。具体实现方法是由操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当发生缺页中断时，淘汰表头页面并把新调入的页面加到表尾。FIFO页面置换算法容易理解和实现，但是其性能并不总是很好。

1.2.2 算法分析

FIFO算法仅仅考虑到在内存中滞留了很久的页面的需求性可能比新进入的页面更小。就像在超级市场中，新引进的商品往往比已经库存了很久的商品更容易被购买，因此当新引进商品时，通常淘汰那个库存了最久的商品。

但是这种考虑显然不太准确，谁说新上架的东西一定比库存很久的东西更有用呢？考虑一个页面，它在很早的时候被调入内存，之后被频繁的引用，这个页面很容易被FIFO算法当作没用的页面从而被淘汰。因此纯粹的FIFO算法很容易淘汰重要的页面，实际很少使用。

1.3 第二次机会页面置换算法

1.3.1 算法思想介绍

第二次机会页面置换算法是对FIFO算法的改进。它在FIFO的基础上进行了修改，其性能较FIFO有了很大的提高，避免了把经常使用的页面置换出去。

和FIFO算法一样，操作系统维护一个所有当前在内存中的页面的链表，最新进入的页面放在表尾，最久进入的页面放在表头。当需要置换页面是，检查最老页面的R位，如果它为0，表示它最近未被使用，也就是说，它又老又没用，可以立即置换。如果是1，则把R位置为0，并把该页面放在链表尾端（即把它作为刚装入的页面一样），然后继续搜索。

1.3.2 算法示例

如图1（a）所示，页面A到页面H按照进入内存的时间先后顺序保存在链表中。页面上的数字是该页面进入内存时的时间。第二次机会算法的一个执行示例过程如下：

（1）在时间20发生了一次缺页中断；

（2）检查最老的页面A，如果A的R位为0，则将它淘汰出内存；

（3）现在页面A的R位为1，则将A放到链表的尾部，并且重新设置页面的进入时间为当前时刻，并置A的R位为0。即让A页面好像是刚刚调入内存一样；

（4）检查当前最老的页面B，重复以上过程。

可以看出在上面的过程中，如果A到H页面都被访问过了，那么在遍历了一次之后，仍然是页面A被淘汰，此算法就变成了纯粹的FIFO算法。

1.3.3 算法分析

该算法的思想是找到一个最近的时钟滴答中从来没有被访问过的页面，而且这个页面是最老的（最先调入内存），这样综合了两个方面的考虑：

（1）老的页面比新的页面需求量小（FIFO算法的想法）

（2）局部性：最近未被访问的页面今后也可能不被访问

并且算法优先考虑局部性，例如在上面的过程中，如果A～H页面都被访问过了，那么在遍历了一次之后，仍然是最老的页面A被淘汰，此算法就变成了纯粹的FIFO算法。

当选择置换页面时，依然和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.2 LRU算法的实现方法

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

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

1.5.3 LRU算法的优缺点

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.2 NFU算法的问题

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

例如，可能某页面一开始被频繁使用，其计数器值可能已经高达10 000，但是这个页面在程序运行后期就很少使用了。但是由于前期的频繁访问，它的计数器值已经很高了，因此按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总有一个更先被访问）。因此在老化算法中只能看它们计数器值的大小来决定，不是真正的最近最少使用算法，仅仅是它的一个近似。

第二个与LRU的区别是，老化算法的计数器只有有限位数，限制了其对以往页面访问历史的记录。

2 系统颠簸的分析与解决

2.1 系统颠簸的概念

颠簸（Thrashing）（又称抖动）就是指当内存中已无空闲空间而又发生缺页中断时，需要从内存中调出一页程序或数据到磁盘的交换区中，如果算法不适当，刚被换出的页面很快被访问，需重新调入，因此需再选一页调出，而此时被换出的页面很快又要被访问，因而又需将它调入，如此频繁更换页面，以致花费大量的CPU时间，极大地降低系统的效率，我们称这种现象为“颠簸”（或“抖动”）。一般如果每执行几条指令程序就会发生一次缺页中断，那么就可以称这个程序发生了颠簸。

2.2 系统颠簸的产生

2.2.1 局部页面置换算法与全局页面置换算法

页面置换算法可以分为两大类，全局置换和局部置换。全局置换允许一个进程从所有页帧集合中选择一个页帧置换，而不管该帧是否已经分配给其他进程，即一个进程可以从另一个进程中拿到帧。局部置换要求每个进程仅从自己的分配帧中进行选择。局部置换和全局置换的一个示例如下：如图4所示，三个进程A，B，C构成了可运行进程的集合。假设页面置换算法是LRU算法，每个页面的生存时间列在页面的右边。当进程A产生缺页中断时，如果采用全局置换算法，将选择所有页面中生存时间最少的页面B3进行置换。如果采用局部替换算法，将选择分配给A的所有页面中生存时间最少的页面A6进行置换。

2.2.2 因为物理内存不足而产生系统颠簸

采用全局页面置换时容易产生系统颠簸，即使是使用最优页面置换算法的全局页面置换也不例外。因为当某个进程需要更多的页帧时，为了增加该进程的页帧数目，可能直接导致另一进程的页帧数目减少。当整个系统的物理块不能满足所有进程的需要时，缺页率将持续维持于一高水平值，意味着颠簸的产生。其具体表现形式如下：

（1）进程竞争临界资源

考虑这样的情况：系统中已不存在空闲物理块，而进程A却要求增加物理块，于是，中断处理程序只得将原属于进程B的物理块分配给进程A；同样地，进程B又分配到原属于进程C的物理块，如此下去。在一定时候，各缺页进程都将被阻塞，就绪队列为空，颠簸从此形成。

（2）增加多道程序度

当CPU利用率处于低水平时，为提高多道程序度，调度程序要求从后备输入队列选择进程加载到内存。图5可清楚地说明这种情形下颠簸的形成原因。首先，随着多道程序度的增加，CPU 利用率随之增加而达到一个理论极值。但在极值点右边，再增加多道程序度，因为进程事实上只能从已加载的进程处获得页帧，从而使得更多的进程因缺页而阻塞，随着更多的进程执行内外存的I/O操作，CPU利用率反而更低；为提高CPU利用率，调度程序又要求调入新进程.如此形成恶性循环，系统诸进程都将缺页，颠簸形成。

2.2.3 因为页面置换算法而产生颠簸

基于局部性原理，几乎所有的页面置换算法总是试图从当前正在引用的页面去”预测”将要引用的页面，据此产生淘汰页和置换页。大多数情形下，这种预测的命中率可以很高。但对于特定的程序（如有大量的跳转语句的程序），命中率将很低，其结果很可能是所选择的淘汰页却是即将要引用的页；而从磁盘置换到内存的页面在最近很长时间却不会被引用。不得已，继续进行页面置换，反反复复，颠簸形成。当然，不应用局部性原理的页面置换算法在大多数的情形下都有可能产生颠簸。

2.3 系统颠簸的解决

解决系统颠簸主要有3个方式：好的页面替换算法；减少运行的进程数；增大内存。

这里主要分析如何使用好的页面替换算法尽量避免颠簸的发生。

（1）局部置换

采用局部置换算法，当某个进程产生缺页中断时，只允许从本进程分配的页帧中选择置换页面，而不能从其他进程处拿到帧，就不会使其他进程也发生颠簸，可将颠簸框定在一个特定的、较小的范围内。

当然，这种方法并不理想。全局置换提供了更好的性能，这与局部分配本身是矛盾的。另外，它并不能从根本上防止颠簸，只能局限其范围。如果某个进程处于颠簸状态，则其将长期处于阻塞队列，不断地进行内外存交换，又必然会影响其他进程进行缺页处理。

（2）动态调整页面置换算法

页面置换算法与实际应用相关，对于大多数的进程，与置换算法同时吻合了局部性原理，从而缺页率低。而其余少数进程因与局部性原理相背，而使”预测”失效，其缺页率偏高可能引发颠簸。

因此，我们可以在一个系统中预备2种以上不同的选择淘汰页和置换页策略的置换算法，并定义一个缺页率的临界值，在缺页处理程序中设置一个判断，当缺页率大于临界值时改用另一种页面置换算法。

（3）跟踪缺页率

根据局部性原理，绝大多数时候，进程是从一个局部区域转移到另一个局部区域执行。所以，必须有足够的页帧供使用，以减少缺页，避免颠簸。到底应为每个进程分配多少页帧呢，实际上，它是系统拥有总的页帧数目与当前系统实际应用相关的一个经验值。这从缺页率与所分配的页帧数关系曲线得到证实。（如图6所示）在拐点附近，每增加（减少）进程的页帧数目都能显著地改变缺页率。

而一定时间以后，即使再增加页帧，缺页率变化也不明显。拐点左边缺页率非常高的区域就是本来的颠簸，拐点就是理想的页帧数目。据此，可对系统中的进程定义其缺页率的上限和下限阀值，此区间内的页帧数是进程拥有的相对合理的页帧数，缺页率高于上限时说明其分配到的页帧太少应当追加；而当缺页率低于下限时说明该进程所拥有的页帧数太多，可收回一部分。

3 算法间的关系

在页面置换的过程中，选择好的页面置换算法是提高系统整体性能的关键。本文分析了常见的7种页面置换算法的原理和思想，并对一些算法给出了实例。

另外作者对各个算法的本质提出了个人的见解，从为什么会有这样的算法？算法解决了什么问题？算法的优点和问题是什么？算法和其他算法之间的联系是什么？等多个方面剖析了页面置换算法的方方面面。

图7小结了各个页面置换算法之间的关系。

4 结 语

系统颠簸也是内存管理中的一个重要问题，本文详细分析了系统颠簸产生的原因并阐述了如何使用好的页面置换算法尽量避免颠簸的产生。

参考文献

[1] [荷]TANENBAUM A S.现代操作系统[M].陈向群，马洪兵，译.北京：机械工业出版社，2009.

[2] 张尧学，史美林，张高.计算机操作系统教程[M].北京：清华大学出版社，2006.

[3] GALVIN P B，GAGNE G.操作系统概念[M].郑扣根，译.北京：高等教育出版社，2011.

[4] [美]BRYANT R E， O’HALLARON D R. 深入理解计算机系统[M].龚奕利，雷迎春，译.北京：机械工业出版社，2010.

[5] 严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.

[6] NULL L，LOBUR J.计算机组成与体系结构[M].北京：机械工业出版社，2004.

[7] 李芳，徐丽，陈亮亮.LRU近似算法的研究[J].现代电子技术，2009，32（3）：36?38.

[8] 王凌飞，王保保.Java虚拟机内存管理分析[J].现代电子技术，2007，30（5）：172?174.

[9] 刘小军，李秀娟.嵌入式操作系统VxWorks的内存管理技术研究[J].电子科技，2008（6）：62?65.

[10] 刘东栋 .一种VxWorks内存管理方案[J].电子科技，2007（2）：63?65.