Question

fifo页面置换法 缺页中断是多少

在一个请求分页面管理中，一个程序的页面走向为1、2、3、4、1、2、5、1、2、3、4、5。
当内存块数量分别为3和4的时，试问使用
（1）FIFO页面置换算法
（2）LRU页面置换算法
（开始时没有装入页面）时的缺页中断次数是多少

Answer 1

内存块3
(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
----------------------------------------
1 1 1 1 1 1 1 0 0 1 1 0 1(miss) 0(hit)
缺页中断次数=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
--------------------------------------
M M M M M M M H H M M M M(miss) H(hit)
缺页中断次数=10

内存块4
(1) FIFO
1 2 3 4 1 2 5 1 2 3 4 5
----------------------------------------
1 2 3 4 4 4 5 1 2 3 4 5
1 2 3 3 3 4 5 1 2 3 4
1 2 2 2 3 4 5 1 2 3
1 1 1 2 3 4 5 1 2
----------------------------------------
M M M M H H M M M M M M M(miss) H(hit)
缺页中断次数=10

(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
1 2 3 4 4 4 5 1 2
-----------------------------------------
M M M M H H M H H M M M M(miss) H(hit)
缺页中断次数=8

Answer 2

内存块3
(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
----------------------------------------
1
1
1
1
1
1
1
0
0
1
1
0
1(miss)
0(hit)
缺页中断次数=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
--------------------------------------
M
M
M
M
M
M
M
H
H
M
M
M
M(miss)
H(hit)
缺页中断次数=10
内存块4
(1)
FIFO
1
2
3
4
1
2
5
1
2
3
4
5
----------------------------------------
1
2
3
4
4
4
5
1
2
3
4
5
1
2
3
3
3
4
5
1
2
3
4
1
2
2
2
3
4
5
1
2
3
1
1
1
2
3
4
5
1
2
----------------------------------------
M
M
M
M
H
H
M
M
M
M
M
M
M(miss)
H(hit)
缺页中断次数=10
(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
1
2
3
4
4
4
5
1
2
-----------------------------------------
M
M
M
M
H
H
M
H
H
M
M
M
M(miss)
H(hit)
缺页中断次数=8