Question

怎么用LRU和FIFO算法计算“缺页中断”

若作业的页面走向为0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2，作业在得到两块和四块主存空间时采用LRU，FIFO置换算法，试计算缺页中断次数。
其中如果用列表法分别列出LRU和FIFO的页面装入调出情况，该怎么排列？

Answer 1

四块主存空间 FIFO：先入先出，应用队列概念
装入0 1 2 3
之后的2132四个序列无需出入队。

执行到5
0出队，5入队：1235
执行到6
1出队，6入队：2356
执行到1
2出队，1入队：3561

执行到4
3出队，4入队：5614
执行到最后的2
5出队，2入队：6142

两块主存空间的 LRU：
0.装入0
1.装入1
2.0出2入 12

3.1出3入 23
2.使用2 32

1.3出1入 21（2最近被使用过）
3.2出3入 13
2.1出2入 32

5.3出5入 25

2.使用2 52
3.5出3入 23

6.2出6入 36

2.3出2入 62

1.6出1入 21

4.2出4入 14

2.1出2入 42
到此结束
最右边的序号是当前作业标号
然后是执行的换页操作
最后2位是当前内存中的作业标号，其中靠左边的是下一次要被换出去的。

Answer 2

两块内存时：
LRU
0 一次中断
0 1 两次中断
1 2 三次
2 3 四次
3 2
2 1 五次
1 3 六次
3 2 七次
2 5 八次
5 2
2 3 九次
3 6 十次
6 2 十一次
2 1 十二次
1 4 十三次
4 2 十四次
所以总共的缺页中断次数为十四次（若是十二次，即是没有算开始的两次调入而已）
四块的自己算！
FIFO
我用四块的内存空间
0 1 2 3 四次
0 1 2 3
0 1 2 3
0 1 2 3
0 1 2 3
1 2 3 5 五次
...
2 3 5 6 六次
3 5 6 1 七次
5 6 1 4 八次
6 1 4 2 九次
所以。。。。 一共九次~