考虑下面页面的走向:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6,当分配给3个物理块,采用局部置换,试问FIFO,LRU两种置换算法的缺页次数各是多少?写出置换过程
时间: 2024-05-31 20:14:29 浏览: 19
如果将上述页面序列分配给3个物理块,采用局部置换算法进行页面置换,那么FIFO和LRU两种算法的缺页次数如下:
1. FIFO置换算法的缺页次数:
首先填满3个物理块,初始状态为:[1,2,3]。
序号 | 页面 | 物理块 | 缺页次数
:-: | :-: | :-: | :-:
1 | 1 | [1,2,3] | 0
2 | 2 | [1,2,3] | 0
3 | 3 | [1,2,3] | 0
4 | 4 | [4,2,3] | 1
5 | 2 | [4,2,3] | 1
6 | 1 | [4,2,3] | 1
7 | 5 | [5,2,3] | 2
8 | 6 | [5,6,3] | 3
9 | 2 | [5,6,2] | 3
10 | 1 | [1,6,2] | 4
11 | 2 | [1,6,2] | 4
12 | 3 | [1,3,2] | 5
13 | 7 | [1,3,7] | 6
14 | 6 | [1,6,7] | 7
15 | 3 | [1,6,3] | 7
16 | 2 | [2,6,3] | 8
17 | 1 | [2,6,1] | 9
18 | 2 | [2,6,1] | 9
19 | 3 | [3,6,1] | 10
20 | 6 | [3,6,1] | 10
因此,FIFO置换算法的缺页次数为10。
FIFO置换算法的置换过程如下:
初始状态:[1,2,3]
4 -> [4,2,3]
5 -> [5,2,3]
6 -> [5,6,3]
7 -> [5,6,2]
1 -> [1,6,2]
2 -> [1,6,2]
3 -> [1,3,2]
7 -> [1,3,7]
6 -> [1,6,7]
3 -> [1,6,3]
2 -> [2,6,3]
1 -> [2,6,1]
2 -> [2,6,1]
3 -> [3,6,1]
6 -> [3,6,1]
2. LRU置换算法的缺页次数:
首先填满3个物理块,初始状态为:[1,2,3]。
序号 | 页面 | 物理块 | 缺页次数
:-: | :-: | :-: | :-:
1 | 1 | [1,2,3] | 0
2 | 2 | [1,2,3] | 0
3 | 3 | [1,2,3] | 0
4 | 4 | [4,2,3] | 1
5 | 2 | [4,2,3] | 1
6 | 1 | [4,2,3] | 1
7 | 5 | [5,2,3] | 2
8 | 6 | [5,6,3] | 3
9 | 2 | [5,6,2] | 3
10 | 1 | [5,6,1] | 4
11 | 2 | [2,6,1] | 5
12 | 3 | [2,3,1] | 6
13 | 7 | [7,3,1] | 7
14 | 6 | [6,3,1] | 8
15 | 3 | [3,6,1] | 8
16 | 2 | [2,6,3] | 9
17 | 1 | [1,6,3] | 10
18 | 2 | [2,6,1] | 11
19 | 3 | [3,6,2] | 12
20 | 6 | [6,3,2] | 13
因此,LRU置换算法的缺页次数为13。
LRU置换算法的置换过程如下:
初始状态:[1,2,3]
4 -> [4,2,3]
5 -> [4,5,3]
6 -> [4,6,5]
7 -> [7,6,5]
1 -> [7,6,1]
2 -> [2,6,1]
3 -> [2,3,1]
7 -> [7,3,1]
6 -> [6,3,1]
3 -> [3,6,1]
2 -> [2,6,3]
1 -> [1,6,3]
2 -> [1,2,3]
3 -> [1,2,3]
6 -> [6,2,3]