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

则页故障数为4,这恰好是页故障数的下限n值。
又如,访问串为:
1 2 3 4 1 2 34 1 2 3 4

则页故障数为12,这恰好是页故障数的上限p值。