操作系统第5章虚拟存储器剖析.ppt

5.3　页面置换算法 同例 缺页中断次数=15 缺页率=15/20=75% 页面置换次数=12 5.3　页面置换算法 再例 页面访问序列 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 0 1 4 4 4 2 3 3 0 1 2 3 0 1 1 1 4 2 2 0 1 2 3 0 0 0 1 4 4 + + + + + + + + + 缺页次数 = 9 ； 缺页率 f = 9 /12= 7 5% 页面访问序列 0 1 2 3 0 1 4 0 1 2 3 4 0 1 2 3 3 3 4 0 1 2 3 4 0 1 2 2 2 3 4 0 1 2 3 0 1 1 1 2 3 4 0 1 2 0 0 0 1 2 3 4 0 1 + + + + + + + + + + 缺页次数 = 10 ； 缺页率 f = 10 /12= 83 % 5.3　页面置换算法 最近最久未使用（LRU）置换算法 选择最近最久未使用的页面予以淘汰 该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰 理论上可行，但实现代价很高 5.3　页面置换算法 同例 缺页中断次数=12 缺页率=12/20=60% 页面置换次数=9 5.3　页面置换算法 硬件支持 寄存器 每个页面设立移位寄存器，被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。 5.3　页面置换算法 栈 把被访问的页面移到栈顶，于是栈底的是最久未使用页面 例，假定现有一进程所访问的页面的页面号序列为： 　4，7，0，7，1，0，1，2，1，2，6 5.3　页面置换算法 最少使用（LFU）置换算法 为在内存中的每个页面设置一个移位寄存器，用来记录该页面被访问的频率 每次访问某页时，便将该移位寄存器的最高位置1，再每隔一定时间右移一次 在最近一段时间使用最少的页面将是∑Ri最小的页 5.3　页面置换算法 Clock置换算法 简单的Clock置换算法 也称最近未使用算法NRU，是LRU和FIFO的折衷 内存中所有页面通过链接指针形成一个循环队列 每页有一个访问位，某页被访问则其访问位置1 在选择一页淘汰时，只需检查页的访问位。如果是0，就选择该页换出；若为1，则重新将它置0，暂不换出，而给该页第二次驻留内存的机会，再按照FIFO算法检查下一个页面。 当检查到队列中的最后一个页面时，若其访问位仍为1，则再返回到队首去检查第一个页面。 5.3　页面置换算法 简单Clock置换算法的流程和示例 5.3　页面置换算法 改进型Clock置换算法 选择页面时，尽量选择既未使用又没有修改的页面 页面（访问位A，修改位M）有四种不同情形 1类（A=0,M=0）既未访问又没有修改，最佳淘汰页 2类（A=0,M=1）未访问但有修改 3类（A=1,M=0）被访问但没有修改 4类（A=1,M=1）既被访问又有修改 5.3　页面置换算法 算法： （1）指针从当前位置开始，开始第一轮扫描循环队列，寻找未使用且没有修改过的页面（第1类页面），找到则可换出。 （2）如果找不到，则开始第二轮扫描，寻找未使用但修改过的页面（第2类页面），并且每经过一个页面时，将其访问位A设置为0。如果找到一个第2类页面，则可换出。 （3） 如果仍旧未找到合适的换出页面，则此时指针回到初始位置，且所有页面其访问位A为0。 再转回（1）继续工作。 5.3　页面置换算法 页面缓冲算法（PBA） 是对FIFO算法的发展，通过被置换页面的缓冲，有机会找回刚被置换的页面 被置换页面的选择和处理：由操作系统中专门的页面置换进程，用FIFO算法选择被置换页，把被置换的页面放入两个链表（空闲页面链表和已修改页面链表）之一 如果页面未被修改，就将其归入到空闲页面链表的末尾 否则将其归入到已修改页面链表 5.3　页面置换算法 访问内存的有效时间 t—访问一次内存的时间；