操作系统6-页面置换算法

页面置换算法

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

最优页面置换算法

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

先进先出页面置换算法

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

最近最久未使用算法 LRU

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

时钟页面置换算法

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

二次机会法

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

最不常用法 LFU

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

Belady现象

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

工作集替换算法

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

缺页率页面置换算法

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

抖动问题

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

量化抖动

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