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

发表于 更新于 分类于 ， 阅读次数： 本文字数： 781 阅读时长 ≈ 1 分钟

页面置换算法

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