Linux使用的页面置换算法

Linux区分四种不同的页面：不可回收的、可交换的、可同步的、可丢弃的。

不可回收的：保留的和锁定在内存中的页面，以及内核态栈等。

可交换的：必须在回收之前写回到交换区或者分页磁盘分区。

可同步的：若为脏页面，必须要先写回。

可丢弃的：可以被立即回收的页面。

Linux并没有像我们之前单纯讨论算法时那样，在缺页中断产生的时候才进行页面回收。Linux有一个守护进程kswapd，比较每个内存区域的高低水位来检测是否有足够的空闲页面来使用。每次运行时，仅有一个确定数量的页面被回收。这个阈值是受限的，以控制I/O压力。

每次执行回收，先回收容易的，再处理难的。回收的页面会加入到空闲链表中。

算法是一种改进地LRU算法，维护两组标记：活动/非活动和是否被引用。第一轮扫描清除引用位，如果第二轮运行确定被引用，就提升到一个不太可能回收的状态，否则将该页面移动到一个更可能被回收的状态。

处于非活动列表的页面，自从上次检查未被引用过，因而是移除的最佳选择。被引用但不活跃的页面同样会被考虑回收，是因为一些页面是守护进程访问的，可能很长时间不再使用。

另外，内存管理还有一个守护进程pdflush，会定期醒来，写回脏页面；或者可用内存下降到一定水平后被内核唤醒。