问题
问答题
在页式虚拟管理的页面替换算法中,对于任何给定的驻留集大小,在什么样的访问串情况下,FIFO与LRU替换算法一样(即被替换的页面和缺页情况完全一样)
答案
参考答案:由于驻留集大小任意,现要求两种算法的替换页面和缺页情况完全一样,就意味着要求FIFO与LRU的置换选择一致。FIFO是替换最早进入主存的页面,LRU是替换上次访问以来最久未被访问的页面,这两个页面一致。就是说,最先进入主存的页面在此次缺页之前不能再被访问,这样该页面也就同时是最久未被访问的页面。
例如,合法驻留集大小为4时,对访问串1、2、3、4、1、2、5,当5号页面调入主存时,应在1、2、3、4页中选择一个替换,FIFO选择1,LRU选择3。原因在于1号页面虽然最先进入主存,但由于其进入主存后又被再次访问,所以它不是最久未被访问页面。如果去掉对1号页面的第二次访问,则FIFO与LRU的替换选择就相同。同理,当5号页面调入主存后,若再访问新的6号页面,则2号页面会遇到同样的问题。所以依此类推,访问串中的所有页面号都应不同,但注意到,连续访问相同页面时不影响后面的替换选择,所以对访问串的要求是:
不连续的页面号均不相同。