项目4-页面置换算法.doc

IV页面置换算法1项目概述2全局页面置换算法3局部页面置换算法4产生引用串5性能评价6具体任务总结5附加任务的建议1项目概述在本项目中,我们将实现不同的全局和局部页面置换算法,并利用随机产生的引用串一比较它们的相对性能。2全局页面置换算法全局页面置换算法采用固定数目的页框。我们考虑一个单进程系统并做如下假设:进程的虚拟内存由P个页面组成,编号从0~P-1。引用串RS是范围从0~P-1的的连续的整数。RS的每一个元素p表示对页面p的一次引用。内存由F个页框组成,编号从0~F-1。使用数组M[F]表示。数组的每一项M[f]包含当前驻留在页框f中的页面的页面号。原理教材中讨论了几种不同的全局页面置换算法。每一个算法顺序读取RS的元素。对于RS中的每一个元素p,置换算法会搜索内存数组以便找到匹配的项,也就是要找到一个f满足M[f]==p。如果没有找到匹配项,便会发生缺页。算法必须根据其实施的策略选择一个页框M[i],并用p置换该页框的内容,即M[i]=p。为了实现置换算法,必须根据不同的算法而提供辅助的数据结构。以下列表总结了不同算法的需求:最佳置换算法和随机置换算法不需要辅助的数据结构。在最佳置换算法中,算法搜索RS来寻找要置换的页。随机置换算法为了选择要置换的页,必须在0~F-1之间产生一个随机数。FIFO置换算法只需要在内存中维持一个指向最旧的页面的指针(数组索引)。只要当前页面被置换了,该指针就递增1(以F为模)。LRU置换算法需要维护一个大小为F、用来实现队列的辅助数组;在每次引用时该队列都会重新排序,以便把被引用的页面放在队列的末尾。第二次机会置换算法(即时钟置换算法)必须维护一个和FIFO算法相似的指针。此外,它需要一个a位的数组,每位表示一个页框。第三次机会置换算法必须维护一个指针和3个数组;这些数组分别表示u位、w位和marker位。一旦开发出这些算法,就可以使用第4节中叙述和各种引用串进行测试了。3局部页面置换算法在局部页面置换算法中,页框的数目不是固定的。相反,我们必须记录进程的当前工作集。对于一个进程,我们用数组VM[P]表示其虚拟内存,其中P是虚拟内存中的页面的数目。依照不同的算法,需要记录如下信息作为VM的每个元素的一部分:对于工作集WS算法来说,每个元素VM[p]只记录了页面p当前是否驻留在虚存中,即是否是工作集中的一员。为了记录当前滑窗口,我们实现了另外一个数组WIN[T+1],其中T是一个系统常量。该数组起到一个有固定长度的队列的作用:任何时候,它都包含了最后T+1步期间的页面引用。WS算法将按照如下方法使用这两个数组。对于在RS中的每个引用p,它会在队列WIN的最前面插入p,同时移除当前在队尾的元素q。然后,再搜索队列WIN以便查找出现的q,如果没有,相应的数组项VM[q]设为0,表明它没有驻留。然后,检索数组项VM[p],如果它不为1,算法设置其为1 并记录产生了一次缺页。对于最佳页面置换算法VMIN来说,使用同样的数组VM和MIN。VM还是记录页面是否驻留在虚存中;WIN对应向前查找窗口,也就是说,它总是包含下次要引用的T+1页。每一次引用时,在未来的T步要被引用的页面将会代替当前在WIN中被引用的页面P。如果在引用页面时该页面没有在虚存中(VM[p]==0),VM[p]置1,并记录产生了一次缺页。此外,没有出现在WI