页面置换算法

操作系统中的页面置换算法主要包括最佳置换算法（OPT，Optimal）、先进先出置换算法（FIFO）、最近最久未使用置换算法（LRU，Least Recently Used）、时钟置换算法和改进型的时钟置换算法。

最佳置换算法（OPT，Optimal）

算法思想

每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

举例说明

假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1。

1. 第一个访问的是 7 号页，内存中没有此页，由缺页中断机构将 7 号页调入内存。此时有三个可用的内存块，不需要置换。即第一次(7) ：7

2. 同理，第二个访问的是 0 号页，和第一次一样，第三次访问的是 1 号页，同样 1 号页也会被调入内存，1 号内被调入内存后，此时分配给该进程内存空间已占满。

   • 第二次(0)：7 0

   • 第三次(1)：7 0 1

3. 第四个访问的页是 2 号页，此时内存已经用完，需要将一个页调出内存，根据最佳置换算法，淘汰一个以后永不使用或最长时间不使用的，此时内存中的页有 7、0、1，查看待访问页号序列中这三个页号的先后位置，下图可以看到，0 号页和 1 号页在不久又会被访问到，而 7 号页需要被访问的时间最久。所以该算法会淘汰 7 号页。

第一次(7) ：7
第二次(0)：7 0
第三次(1)：7 0 1
第四次(2)：0 1 2

按照此算法依次执行，最后的结果如下：

第一次(7) ：7
第二次(0)：7 0
第三次(1)：7 0 1
第四次(2)：0 1 2
第五次(0)：0 1 2（命中）
第六次(3) ：0 3 1
第七次(0) ：0 3 1（命中）
第八次(4) ：3 2 4
第九次(2) ：3 2 4（命中）
第十次(3) ：3 2 4（命中）
第十一次(0) ：3 2 0
第十二次(3) ：3 2 0（命中）
.....

结果图：

整个过程缺页中断发生了 9 次，页面置换发生了 6 次。缺页率 = 9 / 20 = 45%。

注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。

最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。

先进先出置换算法（FIFO）

算法思想

每次选择淘汰的页面是最早进入内存的页面。

举例说明

该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为 3,2,1,0,3,2,4,3,2,1,0,4。

分配三个内存块的情况：

第一次(3) ：3
第二次(2) ：3 2
第三次(1) ：3 2 1
第四次(0) ：2 1 0
第五次(3) ：1 0 3
第六次(2) ：0 3 2
第七次(4) ：3 2 4
第八次(3) ：3 2 4（命中）
第九次(2) ：3 2 4（命中）
第十次(1) ：2 4 1
第十一次(0) ：4 1 0
第十二次(4) ：4 1 0（命中）

分配三个内存块时，缺页次数：9 次。

分配四个内存块的情况：

第一次(3) ：3
第二次(2) ：3 2
第三次(1) ：3 2 1
第四次(0) ：3 2 1 0
第五次(3) ：3 2 1 0（命中）
第六次(2) ：3 2 1 0 （命中）
第七次(4) ：2 1 0 4
第八次(3) ：1 0 4 3
第九次(2) ：0 4 3 2
第十次(1) ：4 3 2 1
第十一次(0) ：3 2 1 0
第十二次(4) ：2 1 0 4

分配四个内存块时，缺页次数：10 次。当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为贝莱迪（Belay）异常。

只有 FIFO 算法会产生 Belay 异常。另外，FIFO 算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此，算法性能差。

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

算法思想

每次淘汰的页面是最近最久未使用的页面。

实现方法

赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间 t。当需要淘汰一个页面时，选择现有页面中 t 最大的页面，即最近最久未使用。

举例说明

加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7

这里先直接给出答案：

第一次(1) ：1
第二次(8) ：1 8
第三次(1) ：8 1 （命中）（由于1号页又被访问过了，所以放到最后）
第四次(7) ：8 1 7
第五次(8) ：1 7 8（命中）
第六次(2) ：1 7 8 2
第七次(7) ：1 8 2 7（命中）
第八次(2) ：1 8 7 2（命中）
第九次(1) ：8 7 2 1（命中）
第十次(8) ：7 2 1 8（命中）
第十一次(3) ：2 1 8 3
第十二次(8) ：2 1 3 8（命中）
第十三次(2) ：1 3 8 2（命中）
第十四次(1) ：3 8 2 1（命中）
第十五次(3) ：8 2 1 3（命中）
第十六次(1) ：8 2 3 1（命中）
第十七次(7) ：2 3 1 7
....

这里前 10 次都 1、8、7、2 这四个页，四个内存块号正好可以满足，当第 11 次要访问的 3 号页进入内存时，需要从 1、8、7、2 这四个页淘汰一个页，按照该算法，从页号为3的开始，从右往左一次找到这 4 个页第一次出现的地方，在最左边的就是最近最少使用的页。

如下图所示，所以该算法最终淘汰的是 7 号页。同时直接从第十次的访问结果 7 2 1 8 也可以直接看出，7 号页在最前面，是最久没有被访问过的，所以淘汰应该是 7 号页。

结果图

时钟置换算法

算法思想

最佳置换算法性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近 OPT 算法性能的，但是实现起来需要专门的硬件支持，算法开销大。时钟置换算法是一种性能和开销均平衡的算法。又称 CLOCK 算法，或最近未用算法（NRU，Not Recently Used）。

简单 CLOCK 算法算法思想：为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某个页被访问时，其访问位置 1。当需要淘汰一个页面时，只需检查页的访问位。如果是 0，就选择该页换出；如果是 1，暂不换出，将访问位改为 0，继续检查下一个页面，若第一轮扫描中所有的页面都是 1，则将这些页面的访问位一次置为 0 后，再进行第二轮扫描（第二轮扫描中一定会有访问位为 0 的页面，因此简单的 CLOCK 算法选择一个淘汰页面最多会经过两轮扫描）。

例如，假设某系统为某进程分配了五个内存块，并考虑有以下页面号引用串：1,3,4,2,5,6,3,4,7。刚开始访问前 5 个页面，由于都是刚刚被访问所以它们的访问位都是 1，在内存的页面如下图所示：

此时页面 6 需要进入内存，那么需要从中淘汰一个页面，于是从循环队列的队首（1 号页）开始扫描，尝试找到访问位为 0 的页面。经过一轮扫描发现所有的访问位都是 1，经过一轮扫描后，需要将所有的页面标志位设置为 0，如下图：

之后进行第二轮扫描，发现 1 号页的访问位为 0，所以换出 1 号页，同时指针指向下一页，如下图：

接下来是访问 3 号页和 4 号页，这两个页都在内存中，直接访问，并将访问位改为 1。在访问 3 号页和 4 号页时指针不需要动，指针只有在缺页置换时才移动下一页。如下图：

最后，访问 7 号页，此时从 3 号页开始扫描循环队列，扫描过程中将访问位为 1 的页的访问位改为 0，并找到第一个访问位为 0 的页，即 2 号页，将 2 号页置换为 7 号页，最后将指针指向 7 号页的下一页，即 5 号页。如下图：

这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。

改进型的时钟置换算法

算法思想

简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行 I/O 操作写回外存。只有淘汰的页面被修改过时，才需要写回外存。因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。

改进型时钟置换算法的算法思想：在其他在条件相同时，应该优先淘汰没有被修改过的页面，从而来避免 I/O 操作。为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。

算法规则

将所有可能被置换的页面排成一个循环队列：

1. 第一轮：从当前位置开始扫描第一个（0,0）的页用于替换，本轮扫描不修改任何标志位。

2. 第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0,1）的页用于替换。本轮将所有扫描的过的页访问位设为 0。

3. 第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0,0）的页用于替换。本轮扫描不修改任何标志位。

4. 第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0,1）的页用于替换。

由于第二轮已将所有的页的访问位都设为 0，因此第三轮、第四轮扫描一定会选中一个页，因此改进型 CLOCK 置换算法最多会进行四轮扫描。

第一轮就找到替换的页的情况

假设系统为进程分配了 5 个内存块，某时刻，各个页的状态如下图：

如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。

第二轮就找到替换的页的情况

某一时刻页面状态如下:

如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。

然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为 0，第二轮扫描找到了要替换的页。

第三轮就找到替换的页的情况

某一时刻页面状态如下:

第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。

然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为 1，第二轮扫描后，状态为下图：

接着开始第三轮扫描，尝试找状态为（0，0）的页，此轮扫描不修改标志位，第三轮扫描就找到了要替换的页。

第四轮就找到替换的页的情况

某一时刻页面状态如下：

具体的扫描过程和上面相同，这里只给出最后的结果，如下图：

所以，改进型的 CLOCK 置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的 CLOCK 置换算法：

1. 第一优先级淘汰的是最近没有访问且没有修改的页面。

2. 第二优先级淘汰的是最近没有访问但修改的页面。

3. 第三优先级淘汰的是最近访问但没有修改的页面。

4. 第四优先级淘汰的是最近访问且修改的页面。

第三、四优先级为什么是访问过的？因为如果到了第三轮扫描，所有页的访问位都在第二轮扫描被设置为了 0，如果访问位不是0的话，也达到不了第三轮扫描，前两轮就会被淘汰。

所以到了第三轮，第四轮淘汰的页都是最近被访问过的。

总结