在一个请求分页系统中,分别采用 fifo、lru和 opt页面置换算法时,假如一个作业的页面走向为 4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数m分别为 3、4时,
时间: 2023-05-02 22:05:21 浏览: 127
这个问题是在一个请求分页系统中,使用不同的页面置换算法fifo、lru和opt,假如有一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数m分别为3、4时,求分别使用这三种页面置换算法的缺页次数。
答案:
使用fifo算法的缺页次数分别为9、10。
使用lru算法的缺页次数分别为7、8。
使用opt算法的缺页次数分别为6、6。
相关问题
在一个请求分页系统中,假如一个作业的页面走向为4,3,2,1,4,3,5,4,3,2,1,5,当分配给该作业的物理块为3时,试采用FIFO、LRU、OPT三种页面置换算法计算在访问过程中所发生的缺页次数和缺页率。
好的,让我来回答你的问题。
首先,根据请求分页系统的工作原理,当作业需要访问一个页面时,如果该页面不在内存中,则会发生缺页中断,需要将该页面从外存装入内存中。如果内存已满,则需要使用页面置换算法来选择一个页面进行替换。
针对你提供的作业页面走向和物理块数,我们可以分别采用FIFO、LRU、OPT三种页面置换算法来计算缺页次数和缺页率。
1. FIFO页面置换算法
FIFO算法采用先进先出的原则,即最早进入内存的页面最先被替换。在该作业的页面走向中,当物理块为3时,FIFO算法的页面置换过程如下:
首先,将页面1、4、3依次装入内存中,此时内存中的页面为1、4、3,发生3次缺页中断。
接着,访问页面2,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
接下来,访问页面1,由于页面1已经在内存中,因此也不需要发生缺页中断。
然后,访问页面4,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
接着,访问页面3,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
然后,访问页面5,由于内存中已经有了页面1、4、3,因此需要发生缺页中断,此时发生第4次缺页中断。
最后,访问页面4、3、2、1、5,由于内存中已经有了页面1、4、3、5,因此不需要再发生缺页中断。
因此,FIFO算法总共发生了4次缺页中断,缺页率为4/12=33.33%。
2. LRU页面置换算法
LRU算法采用最近最少使用的原则,即在内存中保留最近最少被使用的页面。在该作业的页面走向中,当物理块为3时,LRU算法的页面置换过程如下:
首先,将页面1、4、3依次装入内存中,此时内存中的页面为1、4、3,发生3次缺页中断。
接着,访问页面2,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
然后,访问页面1,由于页面1最近被使用,因此也不需要发生缺页中断。
接下来,访问页面4,由于页面4最近被使用,因此也不需要发生缺页中断。
然后,访问页面3,由于页面3最近被使用,因此也不需要发生缺页中断。
接着,访问页面5,由于内存中只有页面1、4、3,因此需要选择一个最近最少被使用的页面进行替换,即页面1,此时发生第4次缺页中断。
最后,访问页面4、3、2、1、5,由于内存中已经有了页面4、3、5,因此不需要再发生缺页中断。
因此,LRU算法总共发生了4次缺页中断,缺页率为4/12=33.33%。
3. OPT页面置换算法
OPT算法采用最优页面替换原则,即选择未来最长时间内不会被访问的页面进行替换。在实际中,由于无法预测未来的页面访问情况,因此无法实现OPT算法。在该作业的页面走向中,我们可以手动模拟OPT算法的页面置换过程,如下所示:
首先,将页面1、4、3依次装入内存中,此时内存中的页面为1、4、3,发生3次缺页中断。
接着,访问页面2,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
然后,访问页面1,由于页面1已经在内存中,因此也不需要发生缺页中断。
接下来,访问页面4,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
然后,访问页面3,由于内存中已经有了页面1、4、3,所以不需要发生缺页中断。
接着,访问页面5,由于内存中只有页面1、4、3,因此需要选择一个未来最长时间内不会被访问的页面进行替换。根据该作业的页面走向,我们可以发现,在访问完页面5之后,再次访问页面1、4、3、2、5时,都不需要访问页面2和页面1,因此可以选择其中一个进行替换。假设选择页面2进行替换,则发生第4次缺页中断。
最后,访问页面4、3、2、1、5,由于内存中已经有了页面4、3、5、1,因此不需要再发生缺页中断。
因此,手动模拟的OPT算法总共发生了4次缺页中断,缺页率为4/12=33.33%。
综上所述,无论是采用FIFO、LRU还是OPT页面置换算法,该作业在访问过程中的缺页次数和缺页率均为4次和33.33%。
在请求分页系统中,采用FIFO,OPT ,LRU页面置换算法时。假如一个作业的页面走向为4、3、2、1、4、3,5、4、3、2、1、5。当分配给该作业的物理块数分别为3、4时,试计算在访问过程中,所发生的缺页率和缺页次数,并比较所得结果。
假设分配给该作业的物理块数分别为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。这是因为该作业的页面访问模式比较简单,所有的页面都会经常访问,很难通过页面置换算法来减少缺页率。