前言
上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
本文内容
1 最佳置换算法（OPT，Optimal）
算法思想：每次选择淘汰的页面将是以后永不使用，或者在最长时间内不再被访问的页面，这样可以保证最低的缺页率。
举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
第一个访问的是7号页，内存中没有此页，由缺页中断机构将7号页调入内存。此时有三个可用的内存块，不需要置换。即第一次(7) ：7
同理，第二个访问的是0号页，和第一次一样，第三次访问的是1号页，同样1号页也会被调入内存，1号内被调入内存后，此时分配给该进程内存空间已占满。
第二次(0)：7 0
第三次(1)：7 0 1
第四个访问的页是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%。
注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此，最佳置换算法是无法实现的。
2 先进先出置换算法（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算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此，算法性能差。
3 最近最久未使用置换算法（LRU，Least Recently Used）
算法思想：每次淘汰的页面是最近最久未使用的页面。
实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间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号页。
结果图
4 时钟置换算法
最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近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号页。如下图
这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。
5 改进型的时钟置换算法
简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
改进型时钟置换算法的算法思想：在其他在条件相同时，应该优先淘汰没有被修改过的页面，从而来避免I/O操作。
为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
算法规则：将所有可能被置换的页面排成一个循环队列
第一轮：从当前位置开始扫描第一个（0,0）的页用于替换，本轮扫描不修改任何标志位。
第二轮：若第一轮扫描失败，则重新扫描，查找第一个（0,1）的页用于替换。本轮将所有扫描的过的页访问位设为0。
第三轮：若第二轮扫描失败，则重新扫描，查找第一个（0,0）的页用于替换。本轮扫描不修改任何标志位。
第四轮：若第三轮扫描失败，则重新扫描，查找第一个（0,1）的页用于替换。
由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此改进型CLOCK置换算法最多会进行四轮扫描。
5.1 第一轮就找到替换的页的情况
假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图
如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。
5.2 第二轮就找到替换的页的情况
某一时刻页面状态如下
如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。
5.3 第三轮就找到替换的页的情况
某一时刻页面状态如下
第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图
接着开始第三轮扫描，尝试找状态为（0，0）的页，此轮扫描不修改标志位，第三轮扫描就找到了要替换的页。
5.4 第四轮就找到替换的页的情况
某一时刻页面状态如下
具体的扫描过程和上面相同，这里只给出最后的结果，如下图
所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
(1) 第一优先级淘汰的是最近没有访问且没有修改的页面。
(2) 第二优先级淘汰的是最近没有访问但修改的页面。
(3) 第三优先级淘汰的是最近访问但没有修改的页面。
(4) 第四优先级淘汰的是最近访问且修改的页面。
第三、四优先级为什么是访问过的？因为如果到了第三轮扫描，所有页的访问位都在第二轮扫描被设置为了0，如果访问位不是0的话，也达到不了第三轮扫描，前两轮就会被淘汰。所以到了第三轮，第四轮淘汰的页都是最近被访问过的。
6 小结
网友评论