17 页面置换算法

进程运行时，若其访问的页面不在内存而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区中。

通常，将选择调出页面的算法称为页面置换算法。置换算法的好坏将直接影响操作系统的性能。下面介绍几种常见的置换算法：

1 最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。但由于人们无法预知进程页面未来的使用情况，因而该算法无法实现。

最佳置换算法可以用来评价其他算法。假定系统为某进程分配了三个物理块，并考虑有以下页面号引用串：
7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1

进程运行时，先将7, 0, 1三个页面依次装入内存。进程要访问页面2时，产生缺页中断，根据最佳置换算法，选择第18次访问才需调入的页面7予以淘汰。然后，访问页面0时，因为已在内存中所以不必产生缺页中断。访问页面3时又会根据最佳置换算法将页面1淘汰，依此类推。

从图可知，发生缺页中断的次数为9，页面置换的次数为6。

2 先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

仍用上面的实例，釆用FIFO算法进行页面置换。进程访问页面2时，把最早进入内存的页面7换出。然后访问页面3时，再把2, 0, 1中最先进入内存的页换出。由图可知，利用FIFO算法时进行了 12次页面置换，比最佳置换算法正好多一倍。

FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，这是由 Belady于1969年发现，故称为Belady异常，如下图所示。只有FIFO算法可能出现Belady 异常，而LRU和OPT算法永远不会出现Belady异常。

3 最近最久未使用(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

再对上面的实例釆用LRU算法进行页面置换，如下图所示。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。

图中前5次置换的情况与最佳置换算法相同，但两种算法并无必然联系。实际上，LRU算法根据各页以前的情况，是“向前看”的，而最佳置换算法则根据各页以后的使用情况，是“向后看”的。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类的算法。理论上可以证明，堆栈类算法不可能出现Belady异常。FIFO算法基于队列实现，不是堆栈类算法。

4 时钟(Clock)置换算法

LRU算法的性能接近于OPT，但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是Clock算法的变体。

简单的Clock算法是给每一页设置一个访问位，再将内存中所有页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置1。置换算法在选择一页淘汰时，只需要检查页的访问位。若是0，则将该页换出；若是1，则重新将它置为0，暂时不换出，给该页二次驻留内存的机会，接着按照FIFO的算法检查下一个页面。当检查到队列中最后一个页面时，其访问位仍为1，则再放回队首区检查下一个页面。由于该算法循环地检查各页面的情况，故称为Clock算法，又称为最近未用(Not Recently Used, NRU)算法。

Clock算法的性能比较接近LRU，而通过增加使用的位数目，可以使得Clock算法更加高效。在使用位的基础上再增加一个修改位M（访问位为设为A），则得到改进型的Clock置换算法。这样，每一页都处于以下四种情况之一：

• 最近未被访问，也未被修改(A=0, M=0)。
• 最近被访问，但未被修改(A=1, M=0)。
• 最近未被访问，但被修改(A=0, M=1)。
• 最近被访问，被修改(A=1, M=1)。

算法执行如下操作步骤：

• 从指针的当前位置开始，扫描循环队列。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个(A=0, M=0)页，则进行置换。
• 如果第1步失败，则重新扫描，查找(A=0, M=1)页。选择遇到的第一个这样的页则置换。在这个扫描过程中，对每个跳过的页，把它的使用位设置成0。
• 如果第2步失败，指针将回到它的最初位置，并且集合中所有页的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供置换的页。

改进型的Clock算法优于简单Clock算法之处在于：替换时首选没有变化的页。由于修改过的页在被替换之前必须写回，因而这样做会节省时间。

5 其他置换算法

还有许多其他进行页面置换的算法。例如：最少使用置换算法(LFU)、页面缓冲算法(PBA)等。

最少使用置换算法(LFU)采用移位寄存器来记录页面访问频率，置换一段时间内最少使用的页。页面缓冲算法(PBA)则通过空闲物理块链表，使得页面在内存中不做物理上的移动，已修改和未修改的页面仍在内存中备用。