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

页面置换算法

当缺页中断发生的时候,需要做交换,我们需要尽量减少交换的次数。 # 最优页面置换算法 将等待下一层的访问时间最长的那个页面置换出去,这个算法不可能实现,但是可作为评价其他算法的标准 # 先进先出页面置换算法 维护一个队列,FIFO即可 性能很差,被调出的页面可能是要经常访问的页面 # 最近最久未使用算法 LRU 这个算法基于空间局部性 维护一个页面链表,将刚刚使用过的页面作为首节点,那么缺页中断的时候淘汰链表尾部即可 # 时钟页面置换算法 让页表组织成一个环形链表,把指针指向最老的页面,当发生缺页中断的时候,从老页面开始扫描,对碰到的访问位为0的页表置换出去,如果都是1以后,把他们清0 # 二次机会法 同时利用修改位和访问位来指导置换,当访问位位0修改位为1的时候,将它保留下来,并把修改位改为0,这里改为0以后还要写回内存。给这个页面第二次机会。 # 最不常用法 LFU 淘汰掉访问次数最少的那个,对每个页面都增加一个访问计数器,当访问后计数器+1,注意到这个算法新页很吃亏,我们尝试定期将计数器除以2,又是ADMI和式增加积式减少的手段。 # Belady现象 在FIFO算法中,会出现分配物理页面数增加缺页率反而提高的异常现象。 # 工作集替换算法 工作集大小 单位时间内访问的页面总类, 将不再工作集中的页面换走 # 缺页率页面置换算法 缺页率: 缺页次数除以内存访问次数 基于缺页率来动态调整常驻集的大小 常驻集大小 当前实际驻内存的页面种类, # 抖动问题 随着驻留内存的进程数目不断增加,分配给每个进程的物理页面数不断减少,缺页率上升,造成频繁的替换,这就是抖动 # 量化抖动 缺页频度: 两次缺页的平均间隔时间, 工作集大小