问题
问答题
在页式虚存管理系统中,假定驻留集为m个页帧(初始所有页帧均为空),在长为p的引用串中具有n个不同页号(n>m),对于FIFO、LRU两种页面置换算法,试给出页故障数的上限和下限,说明理由并举例说明。
答案
参考答案:发生页故障的原因是当前访问的页不在主存,需要将该页调入主存。此时不管主存中是否已满(已满则先调出一页),都要发生一次页故障,即无论怎样安排,n个不同的页号在首次进入主存必须要发生一次页故障,总共发生n次,这是页故障数的下限。虽然不同页号数为n,小于或等于总长度p(访问串可能会有一些页重复出现),但驻留集m<n,所以可能会有某些页进入主存后又被调出主存,当再次访问时又发生一次页故障的现象,即有些页可能会出现多次页故障。最差的情况是每访问一个页号时,该页都不在主存,这样共发生p次故障。
所以,对于FIFO、LRU置换算法,页故障数的上限均为p,下限均为n。例如,当m=3,D=12,n=4时,有如下访问串:
1 1 1 2 2 3 3 3 4 4 4 4
则页故障数为4,这是下限n的情况。
又如访问串:
1 2 3 4 1 2 3 4 1 2 3 4
则页故障数为12,这是上限p的情况。