某请求分页系统的局部页面置换策略如下:
系统从0时刻开始扫描,每隔36个时间滴答扫描一轮工作集(扫描时间忽略不计),
本轮没有被访问过的页框将被系统回收,并放入到空闲页框链尾,其中内容在下一次被分配之前不被清空。当发生缺页时,如果该页曾被使用过且还在空闲页框链表中,则重新放回进程的工作集中;否则,从空闲页框链表头部取出一个页框进行分配。
假设不考虑其它进程的影响和系统开销,初始时进程工作集为空。目前系统空闲页框链表中页框号依次为198、156、188、230。进程P依次访问的<虚拟页号,访问时刻>是:<1,1>、<3,20>、<0,32>、<0,65>、<1,73>、<0,90>、<2,104>。请回答下列问题。
(1)访问<0,32>时,对应的页框号是什么
(2)访问<1,73>时,对应的页框号是什么说明理由。
(3)访问<2,104>时,对应的页框号是什么说明理由。
(4)该策略是否适合于时间局部性好的程序说明理由。
参考答案:[解答] (1)页框号为188。因为起始工作集为空,而0页对应的页框为空闲链表中的第三个空闲页框,其对应的页框号为188。
(2)页框号为198。理由:因73>(36×2)故发生第二轮扫描,页号为1、3的页框198、156在第二轮已处于空闲页框链表中,此刻1页又被重新访问,因此应被重新放回到工作集中。其页框号为198。
(3)页框号为230。理由:因为第2页从来没有被访问过,它不在工作集中,因此从空闲页框链表中取出链表头的页框230,页框号为230。
(4)适合。理由:如果程序的时间局部性越好,从空闲页框链表中重新取回的机会越大,该策略的优势越明显。
解析: 本题考查同学对虚拟存储中页面管理的掌握。工作集就是驻留集,指调入内存的那些页面,并且停留在内存被进程所用。根据本题的题意,描述的是对工作集的管理的策略,我们依照题目给定的策略,来依次分析每一个页框的动作。
第一问,问:访问<0,32>时对应的页框号是什么我们看到,该页位于第三个序列,因此,要知道第三个序列的动作,必须要看第一、二个序列的动作,第一个序列是<1,1>,因为驻留集为空,所以要从空闲链表从取出一个空闲页框,第一个页框号是198,将其分配给1页号,同理,第二个访问序列<3,20>将页框156分配给3页号,第三个访问序列<0,32>得到页框号188;
第二问,问:访问<1,73>时,对应的页框号是什么从第一问我们可知,在分配完第三个访问序列<0,32>以后,到达时刻36,此时根据题意,需要扫描一次驻留集,而在本轮中,共分配了3个页框,而且,三个页框均被使用过,因此扫描程序不做任何动作;将进入到第四个序列<0,65>的访问,0页面已经在内存,因此,不发生任何缺页,程序继续运行,到达时刻72,进行第二次扫描,此时。在本轮中,仅有0页面在时刻65被访问过,1、3页面在本轮没有被访问过,被扫描程序收回,放入空闲链表末尾,则此时,空闲链表为230,198,156,其中198,156中有原1、3页面的内容;接下去,到达时刻73,第五个序列请求<1,73>,此时,页面1虽然被回收到空闲链表,按策略,内容尚未被清空,故直接放回到工作集中,对应的页框号还为198,此时空闲链表中为230,156,其中156中有原3页的内容;
第三问,问:访问<2,104>时,对应的页框号是什么在访问<2,104>前,先访问第六个序列<0,90>,此时,0页尚在驻留集中,没有任何动作,下一个是<2,104>,此时第三次扫描还没开始,2页是新页面,需要分配新页面,而空闲页面第一个空闲的页面是230页框,则,将页框230分配给页面2;
第四问,从第2问中可以看出,该策略适合时间局部性好的程序。