在一个请求分页系统中,采用FIFO,LRU页面置换算法时,假如一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数M分别为4时,试计算在访问过程中所发生的缺页次数和缺页率,并比较所得结果。
时间: 2023-07-10 19:30:56 浏览: 78
好的,根据您提供的页面访问情况和物理块数,我们可以分别使用FIFO和LRU算法来计算缺页次数和缺页率。
首先,使用FIFO算法:
在物理块数为4时,我们可以使用一个长度为4的队列来模拟4个物理块,初始队列为空。访问过程中,每访问一个页面,如果该页面已经在队列中,则不发生缺页,否则将该页面加入队列末尾,并将队列头部的页面移出队列,作为被淘汰的页面。
| 访问页面 | 队列状态 | 缺页次数 |
| -------- | -------- | -------- |
| 4 | 4 | 1 |
| 3 | 4 3 | 2 |
| 2 | 4 3 2 | 3 |
| 1 | 4 3 2 1 | 4 |
| 4 | 3 2 1 4 | 5 |
| 3 | 2 1 4 3 | 6 |
| 5 | 1 4 3 5 | 7 |
| 4 | 4 3 5 4 | 8 |
| 3 | 3 5 4 3 | 9 |
| 2 | 5 4 3 2 | 10 |
| 1 | 4 3 2 1 | 11 |
| 5 | 3 2 1 5 | 12 |
因此,FIFO算法的缺页次数为12,缺页率为12/12=100%。
接下来,使用LRU算法:
在物理块数为4时,我们可以使用一个长度为4的栈来模拟4个物理块,初始栈为空。访问过程中,每访问一个页面,如果该页面已经在栈中,则将该页面移动到栈顶,否则将该页面加入栈顶,并将栈底的页面移出栈,作为被淘汰的页面。
| 访问页面 | 栈状态 | 缺页次数 |
| -------- | -------- | -------- |
| 4 | 4 | 1 |
| 3 | 3 4 | 2 |
| 2 | 2 3 4 | 3 |
| 1 | 1 2 3 4 | 4 |
| 4 | 4 1 2 3 | 4 |
| 3 | 3 4 1 2 | 4 |
| 5 | 5 3 4 1 | 5 |
| 4 | 4 5 3 1 | 5 |
| 3 | 3 4 5 1 | 5 |
| 2 | 2 3 4 5 | 6 |
| 1 | 1 2 3 4 | 7 |
| 5 | 5 1 2 3 | 8 |
因此,LRU算法的缺页次数为8,缺页率为8/12=66.67%。
可以看出,LRU算法的缺页次数和缺页率都比FIFO算法低,因此LRU算法更优秀。
阅读全文