51.设进程分得三个页框,其执行访问序列为:0,1,2,3,0,1,2,3,0,1,2,3,4,5,6,7试采用:(1)Belady;(2)LRU;(3)LFU;(4)FIFO算法,来分别计算缺页异常次数,并给出缺页时加进内存的页号。
时间: 2023-07-16 20:11:29 浏览: 146
假设系统中的物理页面数为3,进程的访问序列为:0,1,2,3,0,1,2,3,0,1,2,3,4,5,6,7。
首先,需要确定进程的页面访问序列,将其转换成页面号序列:0,0,0,1,1,1,2,2,2,3,3,3,4,5,6,7。
接下来,按照四种算法分别模拟进程的页面置换过程,计算缺页异常次数和加入内存的页号。
1. Belady算法:
页面访问序列:0,0,0,1,1,1,2,2,2,3,3,3,4,5,6,7
缺页异常次数:6
加入内存的页号:0,1,2,3,4,5
2. LRU算法:
页面访问序列:0,0,0,1,1,1,2,2,2,3,3,3,4,5,6,7
缺页异常次数:6
加入内存的页号:0,1,2,3,4,5
3. LFU算法:
页面访问序列:0,0,0,1,1,1,2,2,2,3,3,3,4,5,6,7
缺页异常次数:6
加入内存的页号:0,1,2,3,4,5
4. FIFO算法:
页面访问序列:0,0,0,1,1,1,2,2,2,3,3,3,4,5,6,7
缺页异常次数:6
加入内存的页号:0,1,2,3,4,5
综上所述,四种算法的缺页异常次数和加入内存的页号都是相同的,因为它们都只能根据已有的页面来选择置换哪一个页面。在这个情况下,页面访问序列的规律比较简单,不利于算法的区分。
相关问题
51.设进程分得三个页框,其执行访问序列为: 0,1,2,3,0,1,2,3,0,1,2,3,4,5,6,7 试采用:(1)Belady;(2)LRU;(3)LFU;(4)FIFO算法,来分别计算缺页异常次数,并给出缺页 时加进内存的页号。
假设内存只有三个页框,初始状态为空。
1. Belady算法
Belady算法是一种最佳置换算法,即每次将最长时间内不会被访问的页替换掉。但是由于无法预知未来的访问序列,所以无法实现。
2. LRU算法
LRU算法是Least Recently Used的缩写,即选择最近最少使用的页进行替换。根据给定的访问序列,可以计算出缺页异常次数和加入内存的页号:
| 访问序列 | 缺页异常次数 | 内存状态 | 备注 |
|----------|--------------|-------------|---------------|
| 0 | 1 | 0 | 加入页0 |
| 1 | 2 | 0,1 | 加入页1 |
| 2 | 3 | 0,1,2 | 加入页2 |
| 3 | 4 | 1,2,3 | 替换页0 |
| 0 | 4 | 1,2,0 | 替换页3 |
| 1 | 4 | 2,0,1 | 替换页2 |
| 2 | 4 | 0,1,2 | 替换页1 |
| 3 | 4 | 1,2,3 | 替换页0 |
| 0 | 4 | 1,2,0 | 替换页3 |
| 1 | 4 | 2,0,1 | 替换页2 |
| 2 | 4 | 0,1,2 | 替换页1 |
| 3 | 4 | 1,2,3 | 替换页0 |
| 4 | 5 | 2,3,4 | 加入页4 |
| 5 | 6 | 3,4,5 | 替换页2 |
| 6 | 7 | 4,5,6 | 加入页6 |
| 7 | 8 | 5,6,7 | 加入页7 |
3. LFU算法
LFU算法是Least Frequently Used的缩写,即选择访问次数最少的页进行替换。根据给定的访问序列,可以计算出缺页异常次数和加入内存的页号:
| 访问序列 | 缺页异常次数 | 内存状态 | 备注 |
|----------|--------------|-------------|---------------|
| 0 | 1 | 0 | 加入页0 |
| 1 | 2 | 0,1 | 加入页1 |
| 2 | 3 | 0,1,2 | 加入页2 |
| 3 | 4 | 1,2,3 | 替换页0 |
| 0 | 5 | 2,3,0 | 替换页1 |
| 1 | 6 | 3,0,1 | 替换页2 |
| 2 | 7 | 0,1,2 | 替换页3 |
| 3 | 8 | 1,2,3 | 替换页0 |
| 0 | 9 | 2,3,0 | 替换页1 |
| 1 | 10 | 3,0,1 | 替换页2 |
| 2 | 11 | 0,1,2 | 替换页3 |
| 3 | 12 | 1,2,3 | 替换页0 |
| 4 | 13 | 2,3,4 | 加入页4 |
| 5 | 14 | 3,4,5 | 加入页5 |
| 6 | 15 | 4,5,6 | 加入页6 |
| 7 | 16 | 5,6,7 | 加入页7 |
4. FIFO算法
FIFO算法是First In First Out的缩写,即选择最先进入内存的页进行替换。根据给定的访问序列,可以计算出缺页异常次数和加入内存的页号:
| 访问序列 | 缺页异常次数 | 内存状态 | 备注 |
|----------|--------------|-------------|---------------|
| 0 | 1 | 0 | 加入页0 |
| 1 | 2 | 0,1 | 加入页1 |
| 2 | 3 | 0,1,2 | 加入页2 |
| 3 | 4 | 1,2,3 | 替换页0 |
| 0 | 5 | 2,3,0 | 替换页1 |
| 1 | 6 | 3,0,1 | 替换页2 |
| 2 | 7 | 0,1,2 | 替换页3 |
| 3 | 8 | 1,2,3 | 替换页0 |
| 0 | 9 | 2,3,0 | 替换页1 |
| 1 | 10 | 3,0,1 | 替换页2 |
| 2 | 11 | 0,1,2 | 替换页3 |
| 3 | 12 | 1,2,3 | 替换页0 |
| 4 | 13 | 2,3,4 | 加入页4 |
| 5 | 14 | 3,4,5 | 加入页5 |
| 6 | 15 | 4,5,6 | 加入页6 |
| 7 | 16 | 5,6,7 | 加入页7 |
可以看到,LRU算法和LFU算法的缺页异常次数是相同的,但是LRU算法加入内存的页号和LFU算法不同。FIFO算法的缺页异常次数比LRU算法和LFU算法多,因为它没有考虑页面的访问频率和重要性。
51.设进程分得三个页框,其执行访问序列为:0,1,2,3,0,1,2,3,0,1,2,3,4,5,6,7。试采用:(1)Belady;(2)LRU;(3)LFU;(4)FIFO算法,来分别计算缺页异常次数,并给出缺页时加进内存的页号。
假设物理内存有3个页框。
(1)Belady算法:
| 页面 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | | | | 0 | | | | 0 | | | | 0 | | | |
| 1 | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | |
| 2 | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | |
| 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| 4 | | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| 5 | | | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 | 0 | 1 | 2 | 3 |
| 6 | | | | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 3 | 0 | 1 | 2 | 3 |
| 7 | | | | | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7 | 4 | 5 | 2 | 3 |
|缺页数| 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 |
缺页异常次数为4,加进内存的页号分别为0,1,2,3,4,5,6,7。
(2)LRU算法:
| 页面 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | | | | 0 | | | | 0 | | | | 0 | | | |
| 1 | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | |
| 2 | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | |
| 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| 4 | | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 |
| 5 | | | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 |
| 6 | | | | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 3 |
| 7 | | | | | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7 |
|缺页数| 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 |
缺页异常次数为4,加进内存的页号分别为0,1,2,3,4,5,6,7。
(3)LFU算法:
| 页面 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | | | | 0 | | | | 0 | | | | 0 | | | |
| 1 | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | |
| 2 | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | |
| 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| 4 | | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 0 | 4 | 2 | 3 |
| 5 | | | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 | 0 | 4 | 2 | 3 |
| 6 | | | | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 3 | 0 | 4 | 2 | 3 |
| 7 | | | | | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7 | 4 | 5 | 2 | 3 |
|缺页数| 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 5 | 5 | 5 |
缺页异常次数为5,加进内存的页号分别为0,1,2,3,4,5,6,7。
(4)FIFO算法:
| 页面 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | | | | 0 | | | | 0 | | | | 0 | | | |
| 1 | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | | 0 | 1 | | |
| 2 | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | | 0 | 1 | 2 | |
| 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 | 0 | 1 | 2 | 3 |
| 4 | | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 | 4 | 1 | 2 | 3 |
| 5 | | | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 | 4 | 5 | 2 | 3 |
| 6 | | | | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 3 | 4 | 5 | 6 | 3 |
| 7 | | | | | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7 | 4 | 5 | 6 | 7 |
|缺页数| 1 | 1 | 1 | 1 | 2 | 2 | 2 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 4 | 4 |
缺页异常次数为4,加进内存的页号分别为0,1,2,3,4,5,6,7。
阅读全文