页面置换算法

当缺页中断发生的时候，需要做交换，我们需要尽量减少交换的次数。

最优页面置换算法

将等待下一层的访问时间最长的那个页面置换出去，这个算法不可能实现，但是可作为评价其他算法的标准

先进先出页面置换算法

维护一个队列，FIFO即可
性能很差，被调出的页面可能是要经常访问的页面

最近最久未使用算法 LRU

这个算法基于空间局部性
维护一个页面链表，将刚刚使用过的页面作为首节点，那么缺页中断的时候淘汰链表尾部即可

时钟页面置换算法

让页表组织成一个环形链表，把指针指向最老的页面，当发生缺页中断的时候，从老页面开始扫描，对碰到的访问位为0的页表置换出去，如果都是1以后，把他们清0

二次机会法

同时利用修改位和访问位来指导置换，当访问位位0修改位为1的时候，将它保留下来，并把修改位改为0，这里改为0以后还要写回内存。给这个页面第二次机会。

最不常用法 LFU

淘汰掉访问次数最少的那个，对每个页面都增加一个访问计数器，当访问后计数器+1，注意到这个算法新页很吃亏，我们尝试定期将计数器除以2，又是ADMI和式增加积式减少的手段。

Belady现象

在FIFO算法中，会出现分配物理页面数增加缺页率反而提高的异常现象。

工作集替换算法

工作集大小 单位时间内访问的页面总类，
将不再工作集中的页面换走

缺页率页面置换算法

缺页率: 缺页次数除以内存访问次数
基于缺页率来动态调整常驻集的大小
常驻集大小 当前实际驻内存的页面种类，

抖动问题

随着驻留内存的进程数目不断增加，分配给每个进程的物理页面数不断减少，缺页率上升，造成频繁的替换，这就是抖动

量化抖动

缺页频度： 两次缺页的平均间隔时间，
工作集大小