页面置换算法

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（命中）
.....

 

2 先进先出置换算法（FIFO）

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

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

 当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为贝莱迪（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号页。如下图

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

 

参考链接

 https://www.jianshu.com/p/18285ecffbfb