下面，用一个典型的页地址流来评价FIFO、LRU和OPT三种页面替换算法的性能。其中，最主要的是命中率。 　　例3.1：一个程序共有5个页面组成，分别为P1～P5。程序执行过程中的页地址流（即程序执行中依次用到的页面）为：P1，P2，P1，P5，P5，P1，P3，P4，P3，P4。假设分配给这个程序的主存储器共有3个页面。图5.18表示FIFO、LRU和OPT三种页面替换算法对这3页主存的使用情况，包括调入、替换和命中等。图中，用"*"号标记下次将要被替换掉的页面。 　　在上面介绍的5种页面替换算法中，随机算法的命中率比较低，一般仅用于必须用硬件实现，而且对命中率要求不太高的场合。LFU算法由于其实现起来特别困难，目前很少被采用。在虚拟存储器中，实际上有可能被采用的页面替换算法只有FIFO和LRU两种。

图 5.18 三种页面替换算法对同一个页地址流的调度过程

从图5.18中可以看出，FIFO算法的命中率最低，LRU算法的命中率与OPT算法很接近。这一结论具有普遍意义。因此，在实际使用中，LRU算法是一种比较好的算法。目前，许多机器的虚拟存储器都采用LRU算法。 　　在页面调度中，有一个特别需要注意的问题，即所谓的"颠簸"（Thrashing）现象。看下面的有个例子。 　　例3.2：一个循环程序，依次使用P1，P2，P3，P4四个页面，分配给这个程序的主存页面数为3个。FIFO、LRU和OPT三种页面替换算法对主存页面的调度情况如图5.19所示。　　　　OPT算法命中3次，而FIFO和LRU算法一次也没有命中。在FIFO和LRU算法中，总是发生下次就要使用的页面本次被替换出去了。这就是"颠簸"现象。

图 5.19 页面调度中的颠簸现象

一般来说，对于一个循环程序，当分配给它的页面数小于程序所需要的页面数数时，有可能发生"颠簸"现象。这时，无论是FIFO算法，还是LRU算法，它们的命中率都明显地低于OPT算法。 　　对于例3.2，只要再多分配给它一个页面，三种算法的命中率都能达到最大值。因此，命中率不仅与页地址流有关，而且也与分配给程序的主存页面数等有关。 　　一般来说，分配给程序的主存页面数越多，虚页装入到主存到中的机会也就越多，因此命中率也可能越高，至少不应该下降，通常把满足这种关系的页面替换算法称为堆栈型替换算法。这里所说的堆栈型替换算法不是指某一种算法，而是指一类算法，更不是指采用先进先出或先进后出方式工作的堆栈本身。那么，什么是堆栈型替换算法呢？它定义如下： 对任意一个程序的页地址流作两次主存页面数分配，分别分配m个和n个主存页面，并且有m≤n。如果在任何时刻t，主存页面数集合Bt都满足关系：Bt（m）í Bt（n），则这类算法称为堆栈型替换算法。 　　简单地说，堆栈型算法的基本思想是：随着分配给程序的主存页面数增加，主存的命中率也提高，至少不下降。