页面置换算法是用来选择换出页面的算法。在请求页式存储管理方式中，由于一个进程运行时不是所有页面都在内存中，因此会出现缺页中断，此时内存没有空闲的物理块，就需要置换出内存中的一页，具体置换出哪一页面是由页面置换算法决定的，页面置换算法的优劣直接影响到系统的效率。

当发生缺页中断后，系统不一定会执行页面置换算法。因为发生缺页中断仅仅说明需要执行的页面没有在内存中，如果内存空间中还有空闲块，只需用缺页中断处理程序把需要的页面从外存调入内存即可，不需要页面置换算法。

1.最佳置换算法（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 算法是最早出现的置换算法。 该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法与实际运行时的规律部适应，因为在进程中，有的页面经常被访问。FIFO算法还会产生当所分配的物理块数增大而页故障数不减反增的异常现象，Belady异常。只有FIFO算法可能出现Belady异常，而LRU和OPT算法永远不会出现Belady异常。

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

利用FIFO置换算法时的置换图

3.最近最久未使用置换算法（LRU）

FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。选择最近最长时间为访问的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。

进程第一次对页面2访问时,将最近最久未被访问的页面7置换出去。然后在访问页面3时，将最近最久未使用的页面1换出。

LRU页面置换算法时的置换图

4.时钟置换算法（CLOCK）

LRU的性能最接近于OPT，但是实现起来比较困难，且开销大；FIFO实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU算法的性能，这类算法都是CLOCK算法的变体。因为算法要循环扫描缓冲区，像时...

无