计算机操作系统第四版汤小丹梁红兵哲凤屏_第5章(2016-2017-1)详解.ppt

　该算法须同时检查访问位与修改位，以确定该页是四类页面中的哪一种。其执行过程可分成以下三步： (1) 从指针所指示的当前位置开始，扫描循环队列，寻找A=0且M=0的第一类页面。在第一次扫描期间不改变访问位A。 2.改进型Clock置换算法 (2)如果第一步失败，则开始第二轮扫描寻找A=0且M=1的第二类页面。在第二轮，将所有扫描过的页面的访问位都置0。 (3)如果第二步失败，将所有的访问位复0。然后重复第一步，必要时再重复第二步。 5.3.3　Clock置换算法 5.3.4 页面缓冲算法 (Page Buffering Algorithm, PBA) 1.影响页面换进换出效率的若干因素 (1) 页面置换算法 。影响页面换进换出效率最重要的因素 (2) 写回磁盘的频率。对于已经被修改过的页面，在将其换出时，应写回磁盘。减少已修改页面换出的开销。 (3) 读入内存的频率。减少将页面从磁盘读入内存的频率，减少页面换进的开销。 VAX/VMS操作系统中所使用的PBA：采用可变分配和局部置换方式，置换算法采用FIFO。PBA算法的实现需要内存中设置的两个链表：空闲页面链表、修改页面链表。该算法规定将一个被淘汰的页放入两个链表中的一个，即如果页面未被修改，就将它直接放入空闲链表中；否则，便放入修改页面链表中。 须注意，这时页面在内存中并不做物理上的移动，而只是将页表中的表项移到上述两个链表之一中。 采用PBA算法时，被换出的页面仍留在内存的空闲块中，所有的空闲块形成一个空闲页面缓冲池。 5.3.4 页面缓冲算法(Page Buffering Algorithm, PBA) 思考一 在一采取局部置换策略的请求分页系统中，分配给某个作业的内存块数为4，其中存放的四个页面的情况如下表： 物理块 虚页号 装入时间 最后一次访问时间 访问位 修改位 0 2 60 157 0 1 1 1 160 161 1 0 2 0 26 158 0 0 3 3 20 163 1 1 表中的所有数字均为十进制数，所有时间都是从进程开始运行时，从0开始计数的时钟数。请问，如果系统采用下列置换算法，将选择哪一页进行换出？ (1) FIFO算法； (2) LRU算法； (3) 改进的Clock算法. 思考二 在一个请求分页系统中，假如一个作业的页面走向为4，3，2，1，4，3，5，4，3，2，1，5，目前它还没有任何页装入内存，当分配给该作业的物理块数目M分别为3和4时，请分别计算采用LRU和FIFO页面淘汰算法时，访问过程中所发生的缺页次数和缺页率，并比较所得的结果。 思考三 某虚拟存储器的用户空间共有32个页面，每页1KB，主存16KB。假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、10、4、7，而该用户作业的长度为6页，试将十六进制的虚拟地址0A5C、103C、1A5C转换成物理地址。 5.4　“抖动”与工作集 5.4.1 多道程序度与“抖动”　 “抖动”：系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时频繁地出现缺页。 工作集是指在某段时间间隔Δ内，进程要访问的页面集合。经常被使用的页面需要在工作集中，而长期不被使用的页面要从工作集中被丢弃。 5.4.2 工作集　 工作集模型的原理是：操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动现象。 5.4.3 “抖动”的预防方法　 1. 采用局部置换策略 页面分配采用可变分配方式，置换采用局部置换策略。当某进程发生缺页时，只能在分配给自己的内存空间内进行置换，不允许从其他进程去获得新的物理