1、功能与目标

功能： 当缺页中断发生，需要调入新的页面而内存已满时，选择内存当中哪个物理页面被置换。

目标： 尽可能地减少页面的换金换出次数（即缺页中断的次数）。具体来说，把未来不再使用的或者短期内较少使用的页面换出，通常只能在局部性原理指导下依据过去的统计数据来进行预测。

页面锁定(frame lock)： 用于描述必须常驻内存的操作系统的关键部分或者时间关键(time-critical)的应用程序。实现的方法是：在页表中添加锁定标志位(lock bit)。

2、最优页面置换算法

基本思路： 当一个缺页中断发生时，对于保存在内存当中的每一个逻辑页面，计算在他的下一次访问之前，还需要等待多长的时间，从中选出时间最长的那个，作为被置换的页面。但这只是一种理想的情况，在实际系统中时无法实现的，因为操作系统无法知道每一个页面要等待多长时间之后才会再次被访问。Anyway，最优页面置换算法依然可以用作其他算法的性能评价依据(在一个模拟器上运行某个程序，并记录每一次页面访问的情况，在第二遍运行时即可用最优页面置换算法)。

最优页面置换算法的示意图如下图所示。

3、先进先出算法-FIFO

基本思路： 选择在内存中驻留时间最长的页面并将之淘汰。具体来说，系统会维护一个链表，记录了所有位于内存之中的逻辑页面。从链表的排列顺序来看，链首页面的驻留时间最长，链尾页面的驻留时间最短。当发生一个缺页中断时，把链首的页面淘汰出局，并把新的页面添加到链表的末尾。

性能较差： 调出的页面可能有经常要访问的页面，并且有"Belady"现象。所以FIFO算法很少单独使用。

FIFO算法的示意图如上图所示，其中Fault行中的红点表示在某一次执行过程中产生了缺页中断。

4、最近最久未使用算法-Least Recently Used

基本思路： 当一个缺页中断发生时，选择最久未使用的那个页面，并淘汰之。LRU是对最优页面置换算法的一个近似，其依据是程序的局部性原理，即在最近一小段时间（最近几条指令）内，如果某些页面被频繁地访问，那么在将来一小段时间内，他们还可能会再一次被频繁地访问。反过来说，如果在过去某些页面长时间未被访问，那么在将来他们还可能会长时间地得不到访问。

在这里插入图片描述

LRU算法的示意图如上图所示，其中Fault行中的红点表示在某一次执行过程中产生了缺页中断。

实现LRU可以使用的数据结构思路：

首先可以考虑使用链表，最近各个使用的页面作为首节点，最久未被使用的作为尾结点。每一次访问内存时，找到相应的页面，把他从链表中摘下来，在移动到链表首。每次缺页中断时，淘汰链表尾部的页面。

·还可以使用队列，利用其先进先出的特点，当访问某页时，将此页号压入队列，之后考察队列中是否有榆次页面相同的页号，若有则将其删除(相当于重新构建了一次队列，步入链表划算)。当需要淘汰一个页面时，直接将最先压入队列的页面淘汰即可(先进先出)。

5、时钟页面置换算法

Clcok页面置换算法，LRU的近似，对FIFO的一种改进，其基本思路为： 需要用到页表项当中的访问位Access bit，当一个页面被装入内存时，把该位初始化为0，然后如果这个页面被访问（读/写），则把该位置置为1；把各个页面组织成环形链表（类似时钟表面），把指针指向最老的页面（最先进来的）；当发生一个缺页中断时，考察指针所指向的最老的页面，若它的访问位为0，立即淘汰；若访问位为1，则把该位置置为0，然后指针往下移动一格。如此下去，直到找到被淘汰的页面，然后把指针移动到它的下一格。

Clock置换算法流程如上图所示。

Clock置换算法的示意图如上图所示。

6、二次机会法-Enhanced Clock Algorithm

对于进行了“读”操作和“写”操作的页分别进行处理，优先替换掉没有进行“写”操作的页(称之为“脏”页)，因为这种页替换掉之后需要重新写回到内存之中进行信息的更新操作，而只进行了“读”操作的页无需重新写回到内存之中。

因为替换“脏”页的代价巨大，所以对上述的Clock算法进行修改，使他允许脏页总是在一次时钟头扫描中保留下来，将脏位为1的页的脏位置为0，同时使用脏位和使用位来指导替换，最终选择脏位和使用位均为0的页进行替换。

Enhanced Clock置换算法的示意图如上图所示。

7、最不常用算法-Least Frequently Used

基本思路： 当一个缺页中断发生时，选择访问次数最少的那个页面，并淘汰。

实现方法： 对每个页面设置一个访问计数器，每当一个页面访问时，该页面的访问计数器加1。在发生缺页中断时，淘汰计数值最小的那个页面。