在一个请求分页系统中，采用LRU页面置换算法时，加入一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果

采用LRU页面置换算法时，缺页率的计算公式为：

缺页率 = 缺页次数 / 访问次数

对于该作业的页面走向序列，当分配给该作业的物理块数M为3时，其缺页次数和缺页率如下：

| 页面编号 | 1 | 2 | 3 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| -------- | - | - | - | - | - | - | - | - | - | - | - |
| 物理块 | - | - | - | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 |
| 缺页次数 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |

缺页次数为10，访问次数为11，因此缺页率为10/11=0.909。

当分配给该作业的物理块数M为4时，其缺页次数和缺页率如下：

| 页面编号 | 1 | 2 | 3 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
| -------- | - | - | - | - | - | - | - | - | - | - | - |
| 物理块 | - | - | - | 1 | 4 | 3 | 5 | 2 | 3 | 2 | 1 |
| 缺页次数 | 1 | 2 | 3 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 9 |

缺页次数为9，访问次数为11，因此缺页率为9/11=0.818。

可以看出，当分配给该作业的物理块数M为4时，其缺页率较小，说明采用LRU页面置换算法时，物理块数的多少对缺页率有影响。

相关问题

在一个请求分页系统中，采用LRU页面置换算法时，假如 一个作业的页面走向为：1,3,2,1,1,3,5,1,3, 2，1，5，当分配给该作业的物理块数分别为3和4时，试计 算在访问过程中所发生的缺页次数和缺页率。

好的，根据LRU页面置换算法，当物理块已满时，会将最近最少使用的页面进行置换。根据给出的页面走向以及分配的物理块数，我们可以模拟一下整个过程。

当分配给该作业的物理块数为3时，初始情况下物理块为空，访问第一个页面1时产生缺页，物理块变为1，缺页次数为1；访问第二个页面3时产生缺页，物理块变为1,3，缺页次数为2；访问第三个页面2时产生缺页，物理块变为1,3,2，缺页次数为3；访问第四个页面1时未产生缺页，缺页次数为3；访问第五个页面1时未产生缺页，缺页次数为3；访问第六个页面3时未产生缺页，缺页次数为3；访问第七个页面5时产生缺页，物理块变为3,2,5，缺页次数为4；访问第八个页面1时产生缺页，物理块变为2,5,1，缺页次数为5；访问第九个页面3时产生缺页，物理块变为5,1,3，缺页次数为6；访问第十个页面2时产生缺页，物理块变为1,3,2，缺页次数为7；访问第十一个页面1时未产生缺页，缺页次数为7；访问第十二个页面5时产生缺页，物理块变为3,2,5，缺页次数为8。

因此，在物理块数为3时，缺页次数为8，缺页率为8/12=66.67%。

当分配给该作业的物理块数为4时，初始情况下物理块为空，访问第一个页面1时产生缺页，物理块变为1，缺页次数为1；访问第二个页面3时产生缺页，物理块变为1,3，缺页次数为2；访问第三个页面2时产生缺页，物理块变为1,3,2，缺页次数为3；访问第四个页面1时未产生缺页，缺页次数为3；访问第五个页面1时未产生缺页，缺页次数为3；访问第六个页面3时未产生缺页，缺页次数为3；访问第七个页面5时产生缺页，物理块变为3,2,1,5，缺页次数为4；访问第八个页面1时产生缺页，物理块变为2,1,5,1，缺页次数为5；访问第九个页面3时产生缺页，物理块变为1,5,3,2，缺页次数为6；访问第十个页面2时未产生缺页，缺页次数为6；访问第十一个页面1时未产生缺页，缺页次数为6；访问第十二个页面5时未产生缺页，缺页次数为6。

因此，在物理块数为4时，缺页次数为6，缺页率为6/12=50%。

综上所述，当分配给该作业的物理块数分别为3和4时，缺页次数分别为8和6，缺页率分别为66.67%和50%。可以发现，当物理块数增加时，缺页次数和缺页率都会减少。

在一个请求分页系统中,采用LRU页面置换算法时假如一个作业的页面走向为 4、3、2、1、4、3、5、4、3、2、1、5,当分配给该作业的物理块数M分别为3和4时, 试计算在访问过程中所发生的缺页次数和缺页率,并比较所得结果.

当物理块数M为3时，LRU页面置换算法的过程如下：

| 序号 | 页面 | 内存快 | 缺页次数 | 缺页率 |
| ---- | ---- | ------ | -------- | ------ |
| 1 | 4 | 4 _ | 1 | 1/3 |
| 2 | 3 | 4 3 _ | 2 | 2/6 |
| 3 | 2 | 4 3 2 | 3 | 3/9 |
| 4 | 1 | 1 3 2 | 4 | 4/12 |
| 5 | 4 | 1 3 4 | 4 | 4/12 |
| 6 | 3 | 1 3 4 | 4 | 4/12 |
| 7 | 5 | 1 3 5 | 5 | 5/15 |
| 8 | 4 | 1 4 5 | 5 | 5/15 |
| 9 | 3 | 3 4 5 | 6 | 6/18 |
| 10 | 2 | 2 4 5 | 7 | 7/21 |
| 11 | 1 | 1 4 5 | 8 | 8/24 |
| 12 | 5 | 1 5 4 | 8 | 8/24 |

当物理块数M为4时，LRU页面置换算法的过程如下：

| 序号 | 页面 | 内存快 | 缺页次数 | 缺页率 |
| ---- | ---- | ------ | -------- | ------ |
| 1 | 4 | 4 _ | 1 | 1/4 |
| 2 | 3 | 4 3 _ | 2 | 2/8 |
| 3 | 2 | 4 3 2 _ | 3 | 3/12 |
| 4 | 1 | 4 3 2 1 | 4 | 4/16 |
| 5 | 4 | 4 3 2 1 | 4 | 4/16 |
| 6 | 3 | 4 3 2 1 | 4 | 4/16 |
| 7 | 5 | 5 3 2 1 | 5 | 5/20 |
| 8 | 4 | 4 3 2 4 | 6 | 6/24 |
| 9 | 3 | 3 4 2 3 | 7 | 7/28 |
| 10 | 2 | 2 4 3 2 | 8 | 8/32 |
| 11 | 1 | 1 4 3 1 | 9 | 9/36 |
| 12 | 5 | 5 4 3 1 | 10 | 10/40 |

因此，当物理块数M为3时，访问过程中所发生的缺页次数为8，缺页率为8/24=1/3。当物理块数M为4时，访问过程中所发生的缺页次数为10，缺页率为10/40=1/4。可以看出，当物理块数增加时，缺页率会下降，但是分配太多物理块也不一定能够提高性能，因为会浪费内存资源。