考虑下述页面走向:1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6;当内存块数量分别为3和5时,试问LRU,FIFO,OPT三种置换算法的缺页次数各是多少?(初始所有内存块都是空的)
时间: 2024-05-16 09:18:06 浏览: 11
当内存块数量为3时,LRU,FIFO和OPT的缺页次数分别为:
LRU:9次缺页
```
1 2 3 |4 2 1 |5 6 2 |1 2 3 |7 6 3 |2 1 2 |3 6
1 2 3 |4 2 1 |5 6 2 |1 2 3 |7 6 3 |2 1 6 |3 2 1 |2
缺页次数:9
```
FIFO:10次缺页
```
1 2 3 |4 2 1 |5 6 2 |1 2 3 |7 6 3 |2 1 6 |3 2 1 |2
缺页次数:10
```
OPT:7次缺页
```
1 2 3 |4 2 1 |5 6 2 |1 2 3 |7 6 3 |2 1 6 |3 2 1 |2
缺页次数:7
```
当内存块数量为5时,LRU,FIFO和OPT的缺页次数分别为:
LRU:8次缺页
```
1 2 3 4 2 |1 5 6 2 3 |7 6 3 1 2 |2
缺页次数:8
```
FIFO:12次缺页
```
1 2 3 4 2 |1 5 6 2 3 |7 6 3 1 2 |2
缺页次数:12
```
OPT:5次缺页
```
1 2 3 4 2 |1 5 6 2 3 |7 6 3 1 2 |2
缺页次数:5
```
因为OPT算法可以预知未来页面的访问情况,所以在这个例子中表现最好。LRU算法次之,FIFO算法表现最差。
相关问题
考虑下述页面走向: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6 当内存页框数为3时,试用LRU置换算法画出页面变化情况,并计算缺页次数和页面置换次数各是多少?
假设内存页框数为3,初始时内存中没有任何页面,那么页面置换的顺序和缺页次数如下:
页面走向 | 内存中的页面 | 缺页/置换 | 缺页次数 | 置换次数
:-: | :-: | :-: | :-: | :-:
1 | 1 | 缺页 | 1 | 0
2 | 1 2 | 缺页 | 2 | 0
3 | 1 2 3 | 缺页 | 3 | 0
4 | 2 3 4 | 缺页 | 4 | 0
2 | 2 3 4 | 缺页 | 4 | 0
1 | 1 3 4 | 缺页 | 5 | 1
5 | 1 3 5 | 缺页 | 6 | 1
6 | 3 5 6 | 缺页 | 7 | 1
2 | 2 5 6 | 缺页 | 8 | 1
1 | 1 5 6 | 缺页 | 9 | 1
2 | 1 2 6 | 缺页 | 10 | 2
3 | 3 2 6 | 缺页 | 11 | 2
7 | 7 2 6 | 缺页 | 12 | 2
6 | 7 2 6 | 缺页 | 12 | 2
3 | 7 2 3 | 缺页 | 13 | 3
2 | 7 2 3 | 缺页 | 13 | 3
1 | 1 2 3 | 缺页 | 14 | 4
2 | 1 2 3 | 缺页 | 14 | 4
3 | 1 2 3 | 缺页 | 14 | 4
6 | 6 2 3 | 缺页 | 15 | 4
所以LRU置换算法的页面变化情况为:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6
缺页次数为15,页面置换次数为4。
2(8分)考虑下述页面走向: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6,当分配的内存块数量为5时,试画出LRU、FIFO这两种置换算法的页面置换图,并计算出它们的缺页率。
LRU(最近最少使用)算法的页面置换图下:
1, 2, 3, 4, 2 (缺页)
1, 2, 3, 4, 2, 1 (缺页)
1, 2, 3, 4, 2, 1, 5 (缺页)
1, 2, 3, 4, 2, 1, 5, 6 (缺页)
1, 2, 3, 4, 2, 1 (缺页)
2, 3, 4, 2, 1 (缺页)
2, 3, 4, 2, 1, 7 (缺页)
2, 3, 4, 2, 1, 7, 6 (缺页)
2, 3, 4, 2, 1 (缺页)
2, 3, 4, 2, 1 (缺页)
2, 3, 4 (缺页)
6 (缺页)
3 (缺页)
2 (缺页)
1 (缺页)
2 (缺页)
3 (缺页)
6 (缺页)
LRU算法的缺页率为:16/21 = 0.76(约等于76%)
FIFO(先进先出)算法的页面置换图如下:
1, X (缺页)
1, 2 (缺页)
1, 2, X (缺页)
1, 2, X, X (缺页)
1, X (缺页)
X (缺页)
X, 7 (缺页)
X, 7, 6 (缺页)
X, 7, 6, X (缺页)
X, 7, 6, X, X (缺页)
X, 7, 6, X, X, X (缺页)
X, X, X (缺页)
X (缺页)
X (缺页)
X (缺页)
X (缺页)
X (缺页)
X (缺页)
X (缺页)
FIFO算法的缺页率为:17/21 = 0.81(约等于81%)