操作系统 页面置换算法：LRU和FIFO

LRU（Least Recently Used）最少使用页面置换算法，顾名思义，就是替换掉最少使用的页面。

FIFO（first in first out，先进先出）页面置换算法，这是的最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面给予淘汰。

       FIFO置换算法有这样一个奇怪现象：内存空间块数越多，缺页中断率可能相反的越高(缺页中断次数越高)。

LFU（Least Frequently Used）最近最少使用算法，它是基于“如果一个数据在最近一段时间内使用次数很少，那么在将来一段时间内被使用的可能性也很小”的思路。

　　注意LFU和LRU算法的不同之处，LRU的淘汰规则是基于访问时间，而LFU是基于访问次数的。

 

 

1.最佳置换算法（OPT）

不可能实现的理想算法：是指选择的淘汰页面，将是以后不再使用或未来最长时间内不再被访问的页面。来保证最低的缺页率。

例子： 假定系统为某进程分配了三个物理块，并考虑有以下的页面号引用串：

          7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1

 

（1）进程运行时，先将7，0，1 三个页面装入内存。
（2）当进程要访问页面2 时，将会产生缺页中断。此时OS根据最佳置换算法，将选择页面7 予以淘汰。这是因为页面0 将作为第5 个被访问的页面，页面1 是第14 个被访问的页面，而页面7 则要在第18 次页面访问时才需调入。
（3）下次访问页面0时，因它已在内存而不必产生缺页中断。同理类推
由图可看出，采用最佳置换算法发生了6 次页面置换。

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

置换最先调入内存的页面，即置换在内存中驻留时间最久的页面。即先进入主存的页面先淘汰（换的位置依次前进）

按照进入内存的先后次序排列成队列，从队尾进入，从队首删除。

但是该算法会淘汰经常访问的页面，不适应进程实际运行的规律，目前已经很少使用。

参考https://www.cnblogs.com/fkissx/p/4712959.html

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

算法的实质是：当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。 

它认为过去一段时间里不曾被访问过的页面，在最近的将来可能也不会再被访问

再对上面的实例釆用LRU算法进行页面置换，如图所示。
进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。
然后访问页面3时，将最近最久未使用的页面1换出。

 

4. 时钟(CLOCK)置换算法

LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。又称最近未用(Not Recently Used, NRU)算法

CLOCK算法的性能比较接近LRU，而通过增加使用的位数目，可以使得CLOCK算法更加高效。在使用位的基础上再增加一个修改位，则得到改进型的CLOCK置换算法。这样，每一帧都处于以下四种情况之一：

最近未被访问，也未被修改(u=0, m=0)。
最近被访问，但未被修改(u=1, m=0)。
最近未被访问，但被修改(u=0, m=1)。
最近被访问，被修改(u=1, m=1)。

算法执行如下操作步骤：
从指针的当前位置开始，扫描帧缓冲区。在这次扫描过程中，对使用位不做任何修改。选择遇到的第一个帧(u=0, m=0)用于替换。
如果第1)步失败，则重新扫描，查找(u=0, m=1)的帧。选择遇到的第一个这样的帧用于替换。在这个扫描过程中，对每个跳过的帧，把它的使用位设置成0。
如果第2)步失败，指针将回到它的最初位置，并且集合中所有帧的使用位均为0。重复第1步，并且如果有必要，重复第2步。这样将可以找到供替换的帧。