页面调度问题.doc

一、 问题描述假设有n个页面驻留在内存中，且有一个能容纳k个页面的高速缓存。现有依次访问内存中m个页面的请求序列I=I1,I2,Ii,Im，其中mk。我们必须确定任何时刻哪k个页面放在高速缓存中。对某个访问请求Ii，若该页面在高速缓存中，则可很快完成访问。否则发生一次缺页，必须将其调入高速缓存。这时，若高速缓存未满，则直接将其调入，否则必须确定将高速缓存中哪个页面置换出来以便为Ii腾出空间。高速缓存调度问题是指如何调度页面使得缺页的总数尽可能少。二、 算法分析页面调度策略可以分为两类：一类是基于进程驻留集大小不变的策略；另一类基于进程驻留集可变策略。在本问题中，驻留集大小是固定的，所以只能采用进程驻留集大小不变的策略。由于页面调度根程序的执行有关，所以没有最优解，只能得到一般的结论。在本题中，我采用的是多种贪心策略，不同的贪心策略得到的结果不同，不同的输入对结果也有较大的影响。驻留集不变的策略中共同的是驻留集大小不变。若设k为驻留集的大小，为时刻t的驻留集，为时刻t访问的页号（t是以访问串的每一项为单位的时间），如访问串为1，4，5，即时刻1访问第1页，时刻2访问第4页，时刻3访问第5页，则记为，。驻留集大小固定的替换策略有如下控制过程。 式中y为被替换页。根据不同的选择y的方法可形成不同策略。我在做本题过程中，每个算法都是先将页面访问的前几个页面填入驻留集中，接下来再看其他的页是否需要替换。没有计算空驻留集情况下的页面调度的缺页情况。（1） 先进先出（FIFO）调度算法这是一个比较简单的调度策略，就是当出现页面替换时，选择最先进入驻留集的页面将其调出。例如，驻留集大小为3个页帧时，在FIFO策略的控制下，对于访问串为（3 2 3） 5 6 8 6 3 4 7 2 1 3 1 3 4 3，驻留集的变化过程如下图所示，出现10次调页。 页号56863472131343355553332222244226666444111111333888877733333弃页323Hit568347HitHit2Hit（2） 最近最少使用（LRU）调度算法LRU策略就是淘汰上次使用距离当前最远的页。例如，驻留集大小为3个页帧，访问串为3 2 3 5 6 8 6 3 4 7 2 1 3 1 3 4 3。在LRU控制下，驻留集的变化如下表所示，共出现10次页故障。页号56863472131343323558634722211235686347213134356863472131343弃页323Hit586377HitHit2Hit（3） 最近最不常使用（LFU）调度算法LFU策略就是要淘汰驻留集中第一个hit位为0的页。例如，驻留集大小为3个页帧，访问串为3 2 3 5 6 8 6 3 4 7 2 1 3 1 3 4 3。在LFU控制下，驻留集的变化如下表所示，共出现8次页故障。页号5686347213134335/06/08/06/06/04/07/07/01/01/01/11/11/01/022/02/02/02/02/02/02/02/12/02/02/02/04/04/033/03/03/03/03/13/03/03/03/03/13/13/23/03/1弃页3568Hit64Hit7HitHitHit2Hit（4） 第二次机会调度算法第二次机会调度算法就是要给访问过的页第二次机会，当淘汰寻找到它时将其hit为从1变为0，但是不淘汰它，给他第二次被访问的机会。例如，驻留集大小为3个页帧，访问串为3 2 3 5 6 8 6 3 4 7 2 1 3 1 3 4 3。在第二次机会调度算法控制下，驻留集的变化如下表所示，共出现10次页故障。页号5686347213134332/03/05/05/06/13/06/04/07/02/02/02/01/11/123/05/06/06/18/06/04/07/02/01/01/11/13/13/135/06/08/08/03/04/02/02/01/03/03/03/14/04/0弃页323Hit583647HitHit2Hit三、 时空效率分析（1） 先进先出（FIFO）调度算法：由于函数体内有两个嵌套的for循环。一个是循环访问页面（m），但是前三个不用访问，已经被放入驻留集；另一个循环是访问驻留集（k），所以时间复杂度为,即。主要的空间是用于存储页面的数组和驻留集的大小，所以空间复杂度为。（2） 最近最少使用（LRU）调度算法：在LRU算法中，出现了两个嵌套的for循环，如果每次都缺页，那么这三重循环都要执行。第一个for循环是顺序访问页面（m），但是前三个页面已经放入驻留集中就不用再考虑；第二个for循环是在需要调度页面的情况下，将驻留集中的前k-1个页面经行位置的调整。所以时间复杂度为，即。空间复杂度与FIFO调度算法相同，复杂度为。（3） 最近最不常用（LFU）调度算法：在LFU算法中，出现了两个嵌套的for循环，如果每次都有缺页中断，那么这三重循环都会执行。第一个for循环是顺序访问页面（m），但是前三个页面已经被放入驻留集就不用考虑；第二个for循环式寻找驻留集中hit位最小的页面。所以时间复杂度为，即。空间复杂度与FIFO调度算法也是相同，复杂度为。（4） 第二次机会调度算法：在第二次机会调度算法中，出现了两嵌套的for循环，中间还加了一个while循环，最坏情况就是要将hit为1的页面保护一次，而且驻留集中有k-1个hit为1的页面。这时，三重循环都要执行，第一个循环就是和前面描述的都一样，while循环是寻找hit位为1的页面，第二个for循环是将找到满足条件的页面调整在驻留集中的位置，所以算法的时间复杂度为，即。空间复杂度与FIFO调度算法也是相同，复杂度为。四、 运行结果(1) 在算法分析中出现的页面序列的执行结果： 驻留集大小为3； 页面数量为17； 页面的访问序列为： 3 2 3 5 6 8 6 3 4 7 2 1 3 1 3 4 3(2) 下面是驻留集大小不同、输入序列相同时得到的结果：i. 驻留集大小为3时： 访问串为1 2 3 4 1 2 5 1 2 3 4 5时的结果访问串为1 2 3 4 5 6 7 8 1 2 3 4 5 1 2 3 4 5 6 7时的结果ii. 驻留集大小为4时： 访问串为1 2 3 4 1 2 5 1 2 3 4 5时的结果 访问串为1 2 3 4 5 6 7 8 1 2 3 4 5 1 2 3 4 5 6 7时的结果五、 分析输出结果从上面驻留集大小不同以及输入不同的输出情况可以看出，一般的策略驻留集大小增大，页故障数就会减小。其实FIFO策略中存在一种叫做Belady奇异的现象。Belady奇异是指替换策略不符合随着驻留集大小的增大，页故障数就一定减小的规律。但是经过我的多方努力并没有找到一种输入可以使得随着驻留集大小增大但是FIFO输出的页故障数减小的情况（但是Belady一定在FIFO中出现）。没有Belady奇异的策略随着驻留集大小的增大，页故障数目一定减小，如下图所示。而对具有Belady奇异的策略而言，有时随着驻留集大小增大，页故障数目反而会增多，如下图所示。除了FIFO调度策略外，其他的策略都没有Belady奇异现象。在使用时，可以适当的平衡一下驻留集大小和耗费高低之间的关系。因为操作系统中LRU等其他的策略比FIFO的耗费要