6、考虑下面的页访问串: 1,2,3,4,2,1,5,6,2,1,2,3,7,6,3,2,1,2,3,6假定分配4个物理块,所给定的物理块初始均为空,应用下面的页面置换算法,各会出现多少次缺页中断,并说明什么时候发生? (1)最近最久未使用(LRU)置换算法 (2)先进先出(FIFO)置换算法 (3)最佳(Optimal)置换算法
时间: 2023-08-01 20:09:29 浏览: 79
使用最近最久未使用(LRU)置换算法:
| 页面 | 1 | 2 | 3 | 4 | 缺页次数 |
|--------|------|------|------|------|----------|
| 1 | 1 | | | | 1 |
| 2 | 1 | 2 | | | 1 |
| 3 | 1 | 2 | 3 | | 1 |
| 4 | 1 | 2 | 3 | 4 | 1 |
| 2 | 1 | 3 | 2 | 4 | 2 |
| 1 | 3 | 2 | 1 | 4 | 3 |
| 5 | 3 | 2 | 1 | 5 | 4 |
| 6 | 3 | 2 | 1 | 6 | 5 |
| 2 | 3 | 1 | 2 | 6 | 6 |
| 1 | 2 | 6 | 1 | 3 | 7 |
| 2 | 6 | 1 | 2 | 3 | 8 |
| 3 | 1 | 2 | 3 | 7 | 9 |
| 7 | 2 | 3 | 7 | 1 | 10 |
| 6 | 3 | 7 | 6 | 1 | 11 |
| 3 | 7 | 6 | 3 | 1 | 12 |
| 2 | 6 | 3 | 2 | 1 | 13 |
| 1 | 3 | 2 | 1 | 6 | 14 |
| 2 | 2 | 1 | 6 | 3 | 15 |
| 3 | 1 | 6 | 3 | 2 | 16 |
| 6 | 6 | 1 | 3 | 2 | 17 |
LRU算法总共产生了17次缺页中断。
缺页中断发生的时刻:
- 第1次:页面1首次出现时;
- 第2次:页面2首次出现时;
- 第3次:页面3首次出现时;
- 第4次:页面4首次出现时;
- 第5次:页面2再次出现时,但页面1比页面2更早未使用;
- 第6次:页面1再次出现时,但页面3和页面4比页面1更早未使用;
- 第7次:页面5首次出现时;
- 第8次:页面6首次出现时;
- 第9次:页面2再次出现时,但页面1、3和4都比页面2更早未使用;
- 第10次:页面1再次出现时,但页面2、3和4都比页面1更早未使用;
- 第11次:页面6再次出现时,但页面3、4和1都比页面6更早未使用;
- 第12次:页面3再次出现时,但页面4和1比页面3更早未使用;
- 第13次:页面2再次出现时,但页面1比页面2更早未使用;
- 第14次:页面1再次出现时,但页面6、3和2都比页面1更早未使用;
- 第15次:页面2再次出现时,但页面6、3和1都比页面2更早未使用;
- 第16次:页面3再次出现时,但页面6、1和2都比页面3更早未使用;
- 第17次:页面6再次出现时,但页面3、1和2都比页面6更早未使用;
使用先进先出(FIFO)置换算法:
| 页面 | 1 | 2 | 3 | 4 | 缺页次数 |
|--------|------|------|------|------|----------|
| 1 | 1 | | | | 1 |
| 2 | 1 | 2 | | | 1 |
| 3 | 1 | 2 | 3 | | 1 |
| 4 | 1 | 2 | 3 | 4 | 1 |
| 2 | 2 | 3 | 4 | 2 | 2 |
| 1 | 3 | 4 | 2 | 1 | 3 |
| 5 | 4 | 2 | 1 | 5 | 4 |
| 6 | 2 | 1 | 5 | 6 | 5 |
| 2 | 1 | 5 | 6 | 2 | 6 |
| 1 | 5 | 6 | 2 | 1 | 7 |
| 2 | 6 | 2 | 1 | 3 | 8 |
| 3 | 2 | 1 | 3 | 7 | 9 |
| 7 | 1 | 3 | 7 | 6 | 10 |
| 6 | 3 | 7 | 6 | 2 | 11 |
| 3 | 7 | 6 | 2 | 1 | 12 |
| 2 | 6 | 2 | 1 | 3 | 13 |
| 1 | 2 | 1 | 3 | 6 | 14 |
| 2 | 1 | 3 | 6 | 2 | 15 |
| 3 | 3 | 6 | 2 | 1 | 16 |
| 6 | 6 | 2 | 1 | 3 | 17 |
FIFO算法总共产生了17次缺页中断。
缺页中断发生的时刻:
- 第1次:页面1首次出现时;
- 第2次:页面2首次出现时;
- 第3次:页面3首次出现时;
- 第4次:页面4首次出现时;
- 第5次:页面2再次出现时,但页面1比页面2更早进入内存;
- 第6次:页面1再次出现时,但页面3比页面1更早进入内存;
- 第7次:页面5首次出现时;
- 第8次:页面6首次出现时;
- 第9次:页面2再次出现时,但页面1、3和4比页面2更早进入内存;
- 第10次:页面1再次出现时,但页面5比页面1更早进入内存;
- 第11次:页面6再次出现时,但页面3、4和1比页面6更早进入内存;
- 第12次:页面3再次出现时,但页面4和1比页面3更早进入内存;
- 第13次:页面2再次出现时,但页面5比页面2更早进入内存;
- 第14次:页面1再次出现时,但页面6比页面1更早进入内存;
- 第15次:页面2再次出现时,但页面3比页面2更早进入内存;
- 第16次:页面3再次出现时,但页面6比页面3更早进入内存;
- 第17次:页面6再次出现时,但页面2比页面6更早进入内存;
使用最佳(Optimal)置换算法:
| 页面 | 1 | 2 | 3 | 4 | 缺页次数 |
|--------|------|------|------|------|----------|
| 1 | 1 | | | | 1 |
| 2 | 1 | 2 | | | 1 |
| 3 | 1 | 2 | 3 | | 1 |
| 4 | 1 | 2 | 3 | 4 | 1 |
| 2 | 1 | 5 | 3 | 4 | 2 |
| 1 | 6 | 5 | 3 | 4 | 3 |
| 5 | 6 | 2 | 3 | 5 | 4 |
| 6 | 6 | 2 | 1 | 5 | 5 |
| 2 | 6 | 3 | 1 | 2 | 6 |
| 1 | 4 | 3 | 1 | 2 | 7 |
| 2 | 4 | 5 | 1 | 2 | 8 |
| 3 | 4 | 5 | 3 | 2 | 9 |
| 7 | 4 | 5 | 3 | 7 | 10 |
| 6 | 4 | 6 | 3 | 7 | 11 |
| 3 | 4 | 6 | 2 | 7 | 12 |
| 2 | 4 | 6 | 1 | 7 | 13 |
| 1 | 4 | 6 | 1 | 2 | 14 |
| 2 | 4 | 5 | 1 | 2 | 15 |
| 3 | 4 | 5 | 3 | 2 | 16 |
| 6 | 4 | 6 | 3 | 2 | 17 |
最佳(Optimal)算法总共产生了17次缺页中断。
缺页中断发生的时刻:
- 第1次:页面1首次出现时;
- 第2次:页面2首次出现时;
- 第3次:页面3首次出现时;
- 第4次:页面4首次出现时;
- 第5次:页面2再次出现时,但页面1在未来不再使用,页面5比页面2更晚使用;
- 第6次:页面1再次出现时,但页面3和页面4在未来不再使用,页面6比页面1更晚使用;
- 第7次:页面5首次出现时;
- 第8次:页面6首次出现时;
- 第9次:页面2再次出现时,但页面1、3和4在未来不再使用,页面5比页面2更晚使用;
- 第10次:页面1再次出现时,但页面5在未来不再使用,页面4比页面1更晚使用;
- 第11次:页面6再次出现时,但页面3和页面7在未来不再使用,页面4比页面6更晚使用;
- 第12次:页面3再次出现时,但页面7在未来不再使用,页面2比页面3更晚使用;
- 第13次:页面2再次出现时,但页面1在未来不再使用,页面7比页面2更晚使用;
- 第14次:页面1再次出现时,但页面6在未来不再使用,页面2比页面1更晚使用;
- 第15次:页面2再次出现时,但页面3在未来不再使用,页面1比页面2更晚使用;
- 第16次:页面3再次出现时,但页面6在未来不再使用,页面2比页面3更晚使用;
- 第17次:页面6再次出现时,但页面2在未来不再使用,页面3比页面6更晚使用;
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)