Question

页面置换算法FIFO 、LRU求缺页中断次数

在一个请求分页面管理中，一个程序的页面走向为1、2、3、4、1、2、5、1、2、3、4、5。
当内存块数量分别为3和4的时，试问使用
（1）FIFO页面置换算法
（2）LRU页面置换算法
我找到答案如下就是有些地方看不懂，请详细解释！

(1) FIFO
1 2 3 4 1 2 5 1 2 3 4 5
----------------------------------------
1 2 3 4 1 2 5 5 5 3 4 4
1 2 3 4 1 2 2 2 5 3 3 该行是怎么算出来的？
1 2 3 4 1 1 1 2 5 5 该行是怎么算出来的？
----------------------------------------
缺页中断次数=9

(2) LRU
1 2 3 4 1 2 5 1 2 3 4 5
--------------------------------------
1 2 3 4 1 2 5 1 2 3 4 5
1 2 3 4 1 2 5 1 2 3 4
1 2 3 4 1 2 5 1 2 3
--------------------------------------
缺页中断次数=10 从上面的3行数据 怎么就看出来有10次中断？

Answer 1

(1) FIFO
1  2 3  4  1 2  5  1 2  3  4  5
----------------------------------------
1  2 3  4  1 2  5  5 5  3  4  4              
    1 2  3  4 1  2  2 2  5  3  3                该行是怎么算出来的？  
        1 2  3  4 1  1  1 2  5  5                该行是怎么算出来的？
----------------------------------------
缺页中断次数=9                               
FIFO是这样的：3个内存块构成一个队列，前3个页面依次入队（3个缺页），内存中为3-2-1；
接着要访问4号页面，内存中没有（1个缺页），按FIFO，1号页面淘汰，内存中为4-3-2；
接着要访问1号页面，内存中没有（1个缺页），按FIFO，2号页面淘汰，内存中为1-4-3；
接着要访问2号页面，内存中没有（1个缺页），按FIFO，3号页面淘汰，内存中为2-1-4；
接着要访问5号页面，内存中没有（1个缺页），按FIFO，4号页面淘汰，内存中为5-2-1；
接着要访问1号页面，内存中有（命中），内存中为5-2-1；
接着要访问2号页面，内存中有（命中），内存中为5-2-1；
接着要访问3号页面，内存中没有（1个缺页），按FIFO，1号页面淘汰，内存中为3-5-2；
接着要访问4号页面，内存中没有（1个缺页），按FIFO，2号页面淘汰，内存中为4-3-5；
接着要访问5号页面，内存中有（命中），内存中为4-3-5；
缺页中断次数=9 （12次访问，只有三次命中）
LRU不同于FIFO的地方是，FIFO是先进先出，LRU是最近最少用，如果1个页面使用了，要调整内存中页面的顺序，如上面的FIFO中：     
接着要访问1号页面，内存中有（命中），内存中为5-2-1；
在LRU中，则为
接着要访问1号页面，内存中有（命中），内存中为1-5-2；