操作系统原理：页置换算法，FIFO，LRU，Clock，LFU，二次机会法

     在虚存管理中。当发生缺页中断时，进行页面的换入操作。对于一些不能够被换出的内存，通常采用页面锁定的方式，在页表中添加锁定标志位（lock  bit）以区分该页是否是常驻内存。当内存满需要换出时，为了减少缺页频率通常由几种页面置换算法。例如、最优页面置换算法、先进先出算法、最近最久未使用算法、时钟页面置换算法、二次机会法等。

目录

一、最优页面置换算法（OPT）

二、先进先出算法（FIFO）

三、最近最久未使用方法（LRU）

四、时钟页面置换算法。（Clock）

五、二次机会法

六、最不常用法（LFU）

七、Belady现象

     离下次访问最久的页进行置换。这是一个理想的置换算法。在现实系统中几乎是无法实现的。它通过页帧存放变量，用某个东西来计算出下次访问的时长。替换“将来”最久未使用的页。

      判断哪一个页在内存中存留的时间最长，并淘汰掉。通常用队列或者链表来实现。例如在队列中记录页号，队列头的页存放的时间最长，最先淘汰，把置换进来的页面对应的页号加入近队列尾。此方法性能较差并且有belady现象，被换出的页面可能是被经常访问的页面。性能差，很少用于实际应用中。替换“活”得最久的页。

      当需要页面置换时，判断哪一个页号最近一次使用的时间离当前最久，则该页被换出。即哪一个页“荒废”的最久，则被换出。此方法，需要记录每一个页帧记入未被引用的次数，当被引用时次数归零。或者可以用链表实现，把最近访问的页号插入/移动到链头，置换时换出链尾。LRU算法也是一个性能比较差的算法。

      是LRU的一个近似，FIFO的一种改进。利用页表项中的访问位 used bit，当一个页面被装入内存时，访问位会被初始化为0，当CPU对该页进行访问时，CPU会把访问位置1。修改访问位可以由CPU硬件自动操作，当然访问位可以由操作系统主动操作。具体实现逻辑为： 把所有页号组成一个环形链表（像时钟一样），最初把指针指向“最老”的页面，当缺页中断时，如果指针所指的页表项的访问位为0，则置换该页，如果访问位为1，则将此页的访问位置0后 。移动指针到下一个页表，判断访问位是否为0，重复操作，直到有页被换出。 可以说，Clock算法由环形链表、FIFO、和访问位完成的。

    在页表项中有一个dirty bit，用来记录是否进行过写操作，CPU进行写内存操作时，会自动将次位改1。而访问位，读和写都会被CPU置1.当然，这个位也可被操作系统修改。而二次机会法在Clock法上多了一个bit位，即dirtybit。如果两个bit都是零就会被替换出去，先置访问位，后置脏位。

      最不常用并不是说这个算法不常用，而是这个策略是置换最不常用的算法。把最少访问的页给置换出去，需要一个计数器来记录访问页的次数。LRU是最久未访问，LFU为最少被访问。这个算法的缺陷是，当执行某一段新程序段时，老页可能之前被频繁访问，但是在未来中不去访问，LFU也很长一段时间也不会被置换出去。

       即分配的物理页越多，产生缺页中断的次数反而越多。例如FIFO。主要原因是，算法并不是为了保留将来即将访问的物理页，算法与程序执行逻辑无关。

看看LRU算法：