计算机操作系统教程(张尧学(第三版)第五章.ppt

5.6 局部性原理和抖动问题 ? 什么是局部性原理？ 绝大部分的程序在执行过程中的某段时间内，CPU总是集中地访问程序中的某一个部分而不是随机地访问程序的所有部分。这种现象称为局部性原理。 ? 什么是抖动问题 工作集： 实验表明，任何程序在访问内存时，都有一个临界值的要求，当内存分配小于这个临界值时，内存和外存之间的交换频率将急剧增加，而内存分配大于这个临界值时，再增加内存分配也不能显著减少交换次数。这个内存要求的临界值称为“工作集”。内存与交换次数之间的关系如下图所示： 临界值 进程内存量 交换次数 工作集 当给进程分配的内存小于所要求的工作集时，由于内外存之间交换频繁，使得输入/输出处理的时间大大增加，造成CPU因等待数据空转，系统性能下降，形成了“系统抖动”。 解决系统抖动的方法： （1）?????? 扩大进程的工作集 （2）?????? 选择适当的页面淘汰算法。 解：在该进程执行过程中，链表的变化过程如下： (3) 7 0 1 链表首指针 链表尾指针 7,0,1 (1) 7 链表首指针 链表尾指针 7 (2) 7 0 链表首指针 链表尾指针 7,0 (4) 0 1 2 链表首指针 链表尾指针 7,0,1,2 (5) 1 2 3 链表首指针 链表尾指针 7,0,1,2,0,3 (6) 2 3 0 链表首指针 链表尾指针 7,0,1,2,0,3,0 (7) 3 0 4 链表首指针 链表尾指针 7,0,1,2,0,3,0,4 (8) 0 4 2 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2 (9) 4 2 3 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2,3 (10) 2 3 0 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2,3,0 (11) 3 0 1 链表首指针 链表尾指针 7,0,1,2,0,3,0,4,2,3,0,3,2,1 链表尾指针 (12) 0 1 2 链表首指针 7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1 可以看出，在该题中缺页率为12/17=70.5% 若给进程P分配4个页面时，我们可以利用同样方法计算 出发生缺页中断的此时为9次，缺页率为9/17=52.9% 在正常情况下，如果分配给一个进程或作业的页面数 越多，缺页率越低，但是有时并非如此，从P131例题中， 我们可以看出当分配给进程的页面数增多时，缺页率反而 上升，这种现象称为Belady现象。 返回 最近最久未使用页面置换算法（LRU）。 该方法的着眼点是在要进行页面淘汰时，检查这些 对象的被访问时间，总是把最长时间未被访问过的页面 淘汰出去。 LRU算法需要较多的硬件支持，系统花费大，故常使 用近似算法。 例：（LRU）系统为某进程分配3个页面，页面引用顺序： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 12次缺页中断 7 7 0 7 0 1 2 0 1 2 0 3 4 0 3 4 0 2 4 3 2 0 3 2 1 3 2 1 0 7 1 0 2 返回 最佳置换算法（OPT） 其所选择的被淘汰的页面，将是永不使用的，或者是在最长时间内不再被访问的页面 例：（OPT）系统为某进程分配3个页面，页面引用顺序： 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 9次缺页中断 7 7 0 7 0 1 2 0 1 2 0 3 2 4 3 2 0 3 2 0 1 7 0 1 返回 时钟置换算法（CLOCK） 是常用的LRU的近似算法。 为每页设置一访问位，再将内存中的所有页面都通过链接指针链成一个循环队列。该算法循环地检查各页面的使用情况，若页面的访问位为0，则换出；若为1，则将其置为0，暂不换出，再按FIFO的顺序检查下一个页面。称为CLOCK算法。 该算法所需的页表及算法流程如下图： 查询指针前进一步，指向下一个表目 选择该页面淘汰 置页面访问位为0 入口 返回 页面访问位=0？ 是 否 访问位 页号 页面号 0 6 0 1 13 1 2 32 1 返回 存储保护 地址越界保护： 由页表控制寄存器中页表的长度与虚地址相比较来完成。如：在读取页表