在请求分页系统中,采用FIFO,OPT ,LRU页面置换算法时。假如一个作业的页面走向为4、3、2、1、4、3,5、4、3、2、1、5。当分配给该作业的物理块数分别为3、4时,试计算在访问过程中,所发生的缺页率和缺页次数,并比较所得结果。
时间: 2023-07-10 13:34:19 浏览: 107
假设分配给该作业的物理块数分别为3、4,那么总共可以分配7个物理块。下面分别采用FIFO、OPT和LRU三种页面置换算法来计算在访问过程中所发生的缺页率和缺页次数。
### FIFO页面置换算法
使用FIFO页面置换算法时,对于发生的缺页,总是选择最早进入内存的页面进行替换。
当分配3个物理块时:
| 页面号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 缺页 | 1 | 2 | 3 | 4 | | | | 5 | | | | | |
| 缺页数 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 6 |
当分配4个物理块时:
| 页面号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 缺页 | 1 | 2 | 3 | 4 | | | | 5 | | | | | |
| 缺页数 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
### OPT页面置换算法
使用OPT页面置换算法时,对于发生的缺页,总是选择未来最长时间内不再使用的页面进行替换。
当分配3个物理块时:
| 页面号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 缺页 | 1 | 2 | 3 | 4 | | | | 5 | | | | | |
| 缺页数 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 6 |
当分配4个物理块时:
| 页面号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 缺页 | 1 | 2 | 3 | 4 | | | | 5 | | | | | |
| 缺页数 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
### LRU页面置换算法
使用LRU页面置换算法时,对于发生的缺页,总是选择最长时间没有被使用的页面进行替换。
当分配3个物理块时:
| 页面号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 缺页 | 1 | 2 | 3 | 4 | | | | 5 | | | | | |
| 缺页数 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 5 | 5 | 5 | 5 | 6 |
当分配4个物理块时:
| 页面号 | 1 | 2 | 3 | 4 | 3 | 2 | 1 | 5 | 4 | 3 | 2 | 1 | 5 |
| ------ | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- |
| 缺页 | 1 | 2 | 3 | 4 | | | | 5 | | | | | |
| 缺页数 | 1 | 2 | 3 | 4 | 4 | 4 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
综上所述,无论采用哪种页面置换算法,当分配3个物理块时,缺页率和缺页次数都是一样的,为6/14。当分配4个物理块时,缺页率和缺页次数也都是一样的,为10/14。这是因为该作业的页面访问模式比较简单,所有的页面都会经常访问,很难通过页面置换算法来减少缺页率。