问答题 在一个请求分页系统中，假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别是3和4时，分别采用LRU和FIFO页面替换算法，计算访问过程中所发生的缺页次数和缺页率，比较所得结果。

【正确答案】(a)当M=3时，采用LRU替换算法，如表3-21所示。
　　　　　　　　　　　　　　　　　　　　　　　　表3-21 LRU算法的缺页情况
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
1
1
1
5
5
5
2
2
2
3
3
3
4
4
4
4
4
4
1
1
2
2
2
3
3
3
3
3
3
5

缺页次数为10次，缺页率为：(10/12)×100%=83%。 当M=3时，采用FIFO替换算法，如表3-22所示。
　　　　　　　　　　　　　　　　　　　　　　　　表3—22 FIFO算法的缺页情况
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
1
1
1
5
5
5
5
5
5
3
3
3
4
4
4
4
4
2
2
2
2
2
2
3
3
3
3
3
1
1

缺页次数为9次，缺页率为：(9/12)×100%=75%。 (b)当M=4时，采用LRU替换算法，如表3-23所示。
　　　　　　　　　　　　　　　　　　　　　　　　　　表3—23 LRU算法的缺页情况
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
4
4
4
4
4
4
4
4
5
3
3
3
3
3
3
3
3
3
3
3
1
1
1
1
1
1
1
2
2
2
缺页次数为8次，缺页率为：(8/12)×100%=67%。 当M=4时，采用FIFO替换算法，如表3-24所示。
　　　　　　　　　　　　　　　　　　　　　　　　　　　表3—24 FIFO算法的缺页情况
4
3
2
1
4
3
5
4
3
2
1
5
4
4
4
4
4
4
5
5
5
4
1
1
3
3
3
4
4
3
4
4
4
4
5
1
1
1
1
1
1
1
2
2
2


缺页次数为10次，缺页率为：(10/12)×100%=83%。
通过以上缺页次数和缺页率的分析计算，可以看出，对于LRU算法，增加物理块数，可以减少缺页次数，降低缺页率；而对FIFO算法，增加物理块数，不一定能减少缺页次数。
【答案解析】