作业四：页面置换算法.docxVIP

在一个请求分页存储管理系统中，一个作业的页面走向为4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数为3时，试计算采用下述页面淘汰算法时的缺页次数及缺页中断率(假设开始执行时主存中没有页面)?。 （1）最佳置换法(OPT) （2）先进先出法(FIFO) （3）最近最久未访问（LRU） 根据页面走向，使用先进先出页面淘汰算法时，页面置换情况见下表。物理块数为3时：走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 1 1 1 5 5 5 5 5块2 3 3 3 4 4 4 4 4 2 2块3 2 2 2 3 3 3 3 3 1缺页 √ √ √ √ √ √ √ √ √缺页率为：9/12。 物理块数为4时：走向 4 3 2 1 4 3 5 4 3 2 1 5块1 4 4 4 4 4 4 5 5 5 5 1 1块2 3 3 3 3 3 3 4 4 4 4 5块3 2 2 2 2 2 2 3 3 3 3块4 1 1 1 1 1 1 2 2 2缺页 √ √ √ √ √ √ √ √ √ √缺页率为：10/12。由上述结果可以看出，对先进先出算法而言，增加分配作业的内存块数反而使缺页率上升，即出现Belady现象。 在一个请求分页系统中，分别采用 FIFO、LRU和 OPT页面置换算法时，假如一个作业的页面走向为 4、3、2、1、4、3、5、4、3、2、1、5，当分配给该作业的物理块数M分别为 3、4时，试计算在访问过程中所发生的缺页次数和缺页率，并比较所得结果。 分析思路： 先进先出（FIFO）更新算法： 也称为最早出现的页面更新算法。该算法总是淘汰最先进入内存的页面，即选择在内存中停留时间最长的一页予以淘汰。如果同时有多个页面符合淘汰的条件，则任意选择一个予以淘汰即可。 技巧：谁先连成和题目所给物理块总数，谁先被置换掉 最近最久未使用（LRU）更新算法： 以“最近的过去”作为“不久的将来”的近似，选择最近一段时间内最久没有使用的页面淘汰。 它的实质是：当需要更新一页时，选择在最近一段时间内最久没有被使用的页面予以淘汰 技巧：在内存中没有的页面开始往前看，置换“最前面的“，但不是从一开始的，那样这个算法就没有意义了 最优（OPT）更新算法 该算法所选择的被淘汰页面，将是以后永久不被访问，或者是在未来最长时间内不再被访问的页面。采用最优更新算法通常可以保证获得最低的缺页率。 技巧：往后看，当前未在页面中的页面去置换距离当前需要置换页面最远的页面,最后一个不在页面中的置换谁都可以 缺页率=缺页次数/总页数 置换率=置换次数/总页数 置换次数=缺页次数-物理块数 注意：这两个率最后一定要写成%的形式，不可以写分数 题解： 当物理块数M=3时， FIFO：共发生 9次缺页中断 缺页率=9/12=75% LRU：共发生 10次缺页中断 缺页率=10/12=83.3% OPT：共发生 7次缺页中断 缺页率=7/12=58.3% 当物理块数M=4时， FIFO：共发生 10次缺页中断 缺页率=10/12=83.3% LRU：共发生 8次缺页中断 缺页率=8/12=66.7% OPT：共发生 6次缺页中断 缺页率=6/12=50% 上述结果可以看出，对先进先出算法而言，增加分配给作业的内存块数反而出现缺页次数增加的异常现象。