0引言

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

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

　　1常见的页面置换算法

　　1.1最优页面置换算法

　　1.1.1算法思想介绍

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

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

　　最佳页面置换算法规定：标记最大的页应该被置换。例如，如果某页在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，它就从来不会被淘汰出去。算法的这个特点使它被称为第二次机会算法。