操作系统课程设计-页面置换算法模拟程序报告

1引言 11.1问题的提出 11.2国内外研究的现状 11.3任务与分析 22需求分析 22.1页面置换算法概念 22.2关于页面置换算法的一些根本思想 3先进先出〔FIFO〕页面置换算法 3最近最久未使用〔LRU〕置换算法 3最正确〔Optimal〕置换算法 42.3需求分析 53程序运行平台 54总体设计 55详细设计 65.1界面设计 65.2随机产生长度为20的页面走向 65.3FIFO算法设计 85.4LRU算法设计 116系统测试 156.1测试的数据 176.2测试小结 21总结 23致谢 24参考文献 24

摘要随着计算机的普及，人们生活得到极大改善，人们在精神方面也同样需要提高，所以越来越多的人进行着各种各样的学习。操作系统是计算机中最重要的环节之一，也是计算机专业学生的一门重要的专业课程。操作系统的好坏，直接影响整个计算机系统的性能和用户对计算机的使用。一个精心设计的操作系统能极大的扩展计算机的功能，充分发挥系统中的各种设备的使用效率，提高系统的可靠性。由于操作系统中各种软硬件资源的管理，内容比拟繁琐，具有很强的实践性，要学号这门课程，必须把理论和实践紧密结合，才能取得教好的学习效果。本次课程设计是在学习完《操作系统教程》后，进行的一次全面的综合训练，通过课程设计，让学生更好的掌握操作系统的原理以及实现方法，加深对操作系统根底理论和重要算法的理解，加强对学生的动手能力。熟悉页面置换算法及其实现，引入计算机操作性能评价方法的概念。关键词：页面置换算法，LRU算法，OPT算法，FIFO算法1引言1.1问题的提出在存储器管理方式中，有一个特点，就是当要求作业全部装入内存才能运行。但是这样就存在两种情况：〔1〕有的作业很大，不能全部装入内存，致使作业无法进行。〔2〕有大量作业要求运行时，内存容量缺乏容纳所有作业，而虚拟内存技术正是下哦那个逻辑上扩充内存容量，将会解决以上两个问题。所以，可以当进程开始运行时，先将一局部程序装入内存，另一局部暂时留在外存；当要执行的指令不在内存时，由系统自动完成将它们从外存调入内存的工作；当没有足够的内存空间时系统自动选择局部内存空间，将其中原有的内容交换到磁盘上，并释放这些内存空间供其它进程使用通常，把选择换出页面的页面的算法称为页面置换算法，模拟页面置换算法用以客观解决内存缺乏的矛盾。1.2国内外研究的现状1961年英国曼彻斯特大学推出了“虚拟存储”管理技术，并在ATRAS计算机上实现这一技术，70年代以后，这一技术才真正广泛使用，目前许多大型计算机均采用此技术。虚拟存储管理技术的关键在于页面置换算法的选择。1966年Belady在理论上提出最优页面置换算法(OptimalReplacementAlgorithm,OPT)，此外还有先进先出置换算法(firstinputfirstoutput,FIFO)，最近最少使用页面置换算法(leastrecentlyused,LRU)，最少使用页面置换算法(leastfrequentused,LFU，或最不常用算法〕，时钟置换算法〔clock，或称最近未使用页面置换算法(notusedrecently,NUR)〕，页面缓冲〔pagebuffering〕置换算法等。1.3任务与分析本课程设计完成一个简单页面置换算法的模拟，加深理解页面置换算个算法对于存储器内存扩展使用的原理以及对于不同置换算法的使用的优缺点。在此次课程设计中完成的只是一个小小的模拟算法，对于操作系统中对于置换算法的选择远远不止这些。用随机数方法产生页面走向，页面走向长度为L。根据页面走向，分别采用FIFO和LRU算法进行页面置换，统计缺页率；为简化操作，在淘汰一页时，只将该页在页表中抹去,而不再判断它是否被改写过，也不将它写回到辅存。假定可用内存块和页表长度(作业的页面数)分别为m和k，初始时，作业页面都不在内存。随机数产生程序：functionrandom:real:beginSeed:=125.0(seed+1.0)Seed:=Seed8192.0trunc(seed/8192)random:=(Seed+0.5)/8192end;上述随机数发生函数产生的随机数为0.0～1.0，稍另变化就可得到0～n1之间的随机数。程序开始时，应对变量Seed(实型)赋初值。2需求分析2.1页面置换算法概念所谓页面置换算法，是操作系统中对于页式存储管理中的一种软件虚拟存储管理方式实现的一种具体的算法操作，页面置换算法的优劣将会影响虚拟存储系统的性能，进而影响整个系统的性能。2.2关于页面置换算法的一些根本思想先进先出〔FIFO〕页面置换算法这是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面，按照先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比方，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。以下为采用FIFO算法进行页面置换的例子〔图1〕。当进程第一次访问页面2时，将把第7页置换出，因为它是最先被调入内存的；在第一次访问页面3时，又将把页0置换出，因为它在现有的2，0，1三个页面中是最老的页。由图1可以看出，利用FIFO算法时进行了12次页面置换。引用率777222444000777000333222111001110003332221页框图1利用FIFO置换算法时的置换图最近最久未使用〔LRU〕置换算法FIFO置换算法性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用〔LRU〕的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中其t值最大的，即最近最久未使用的页面予以淘汰。利用LRU算法对上例进行页面置换算法的结果如图2所示。当进程第一次对页面2进行访问时，由于页面7是最近最久未访问的，故将它置换出去。当进程第一次对页面3进行访问时，第1页成为最近最久未使用的页，将它换出。根据各页以前的使用情况来判断，页面过去和未来的走向之间并无必然的关系。引用率777224440111000000333001133222227页框图1利用LRU置换算法时的置换图最正确〔Optimal〕置换算法最正确置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰的页面，将是以后永不使用的，或是在最长〔未来〕时间内不再被访问的页面。采用最正确置换算法，通常可保证获得最低的缺页率。但由于人们目前还无法预知一个进程在内存的假设干个页面中，哪一个页面是将来最长时间内不再访问的，因而该算法时无法实现的，但可以利用该算法评价其他算法。现举例说明如下〔图3〕。进程运行时，先将前三个页面装入内存。以后，当进程要访问页面2时，将会产生缺页中断。此时OS根据最正确置换算法，将选择页面7予以淘汰。这是因为页面0将作为第5个被访问的页面，页面1是第14个被访问的页面，而页面7那么要在第18次页面访问时才需要调入。下次访问页面0时，因它已在内存而不必产生缺页中断。当进程第一次访问页面3时，又将引起页面1被淘汰，因为，它在现有的1，2，0三个页面中，将是以后最晚才被访问的。由图可以看出，采用最正确置换算法发生了6次页面置换。引用率777222227000040001133311页框图1利用LRU置换算法时的置换图2.3需求分析在进程中运行过程中，假设所要访问的页面不在内存中，需要调入页面时，选择内存中的那个物理页面将其调出。通常只能再局部性原理指导下，把未来不再使用的页面调出。如何选择调度策略即页面置换算法至关重要，置换算法的好坏，直接影响着系统的性能，因此我们有必要将常见的FIFO、LRU、OPT三种算法进行比拟，分析性能。因此我们需要选择一种好的算法来对内存虚拟扩充的一种有效方法，提高内存利用率。3程序运行平台Windows7或Windowsxp及以上版本JavaJDKNeatBeans6.5的版本上运行NetBeansIDE6.5，JDK1.6。4总体设计开始开始产生页面中页面走向的随机数选择FIFO算法选择LRU算法产生页面中页面走向的随机数选择FIFO算法选择LRU算法5详细设计5.1界面设计由于此次程序是使用JAVA程序设计语言所写，所以为了外表美观，便于用户操作，改程序使用了GUI设计，界面主要由1个JFrame、1个JPanel、57个JLabel组件、2个JButton组件、2个JRadioButton组件、6个JTextField组件组成，界面如下：5.2随机产生长度为20的页面走向主要设计思想由于GUI设计的特殊性，所以为了界面的显示和美观，那么产生20个随机数并不是像C语言那样用一个函数就可以搞定的，而是需要定义20个线程来产生20个数〔页号〕，每一个线程产生一个随机数并且控制一个JLabel组件的输出。然后利用一个JButton组件“开始”，产生一组随机数，然后再用JButton组件“停止”显示输出结果。主要代码由于20个线程的代码根本相同，因此现将其中一个线程的代码列出如下：classmylabel2implementsRunnable{//内部类代表一个线程publicbooleanstop;//publicvoidrun(){//线程的run方法stop=false;intj;for(;;){j=(int)(Math.random()*10);///////////////????????????????!!!!!!!!!!!!!!!!!!!!!1找的我好辛苦，一定要加括号jLabel2.setText(Integer.toString(j));try{Thread.sleep(100);}catch(InterruptedExceptionex){Logger.getLogger(main_frame.class.getName()).log(Level.SEVERE,null,ex);}if(stop)break;}//for}//run}5.2.3stop=falsestop=falsej=(int)(Math.random()*10)stop=false?NYbreak;产生随机数结果5.3FIFO算法设计5.3.1首先初始化页表信息，将所有页的block_num属性赋值为-1，表示开始的时候任何页都不在内存中；其次再初始化内存表信息，将所有页的page_num属性赋值为-1，表示开始时候内存块中没有任何一页。然后，利用一个for循环循环20次，实现20次访问页面。由于置换的算法是FIFO〔先进先出〕算法，所以将内存中四个块建立成一个队列，访问页面时依次将页面调入内存。如果内存中没有空间了那么将队首内存块中的页面置换出去，将将要访问的页面调入该内存块，然后依次这样继续下去，直到20次访问结束。最后再在每次循环结束后判断是否发生缺页，如果缺页那么计数器自动加1，如果不缺页计数器就不变。FIFO程序模块代码classrun_FIFOimplementsRunnable{///////////执行FIFO算法线程//////////////publicPage[]table=newPage[10];//具有十个页面的页表publicMemary[]memary=newMemary[4];//内存中有四个块run_FIFO(){inti;for(i=0;i<10;i++){table[i]=newPage(i,-1,0);}for(i=0;i<4;i++){memary[i]=newMemary(i,-1,i);}}publicvoidrun(){///显示两个表的信息num++;inti,j,n=0,visit_page;//当前访问页Memarytemp;//中间变量for(i=0;i<20;i++){//循环20次if(stop==true){//JOptionPane.showMessageDialog(null,"如果执行此操作\n\n将终止当前正在执行运行的FIFO算法");return;}jTextField5.setText(Integer.toString(i+1));//显示执行次数visit_page=visit[i];j=4;if(table[visit_page].flag==0){//表示当前页不在内存，缺页n++;//记录缺页次数if(memary[3].page_num==-1){for(j=0;j<4;j++){//查找内存中是否有空位if(memary[j].page_num==-1)break;}//for}//ifif(j<4){//有空位table[visit_page].flag=1;//修改页表table[visit_page].block_num=memary[j].block_num;memary[j].page_num=visit_page;//修改内存表}else{//没有空位，进行替换table[memary[0].page_num].flag=0;//将内存表中第一个结点替换出去，并修改页表信息table[memary[0].page_num].block_num=-1;table[visit_page].block_num=memary[0].block_num;table[visit_page].flag=1;memary[0].page_num=visit_page;//修改内存表信息temp=memary[0];//将头节点插到队尾memary[0]=memary[1];memary[1]=memary[2];memary[2]=memary[3];memary[3]=temp;}jTextField1.setText(Integer.toString(n));//时刻显示缺页率}//if//else{}//不缺页，不做任何处理jTextField2.setText(Float.toString((float)n/(i+1)*100));init_jLabel_FIFO(memary);try{Thread.sleep(1500);}catch(InterruptedExceptionex){Logger.getLogger(main_frame.class.getName()).log(Level.SEVERE,null,ex);}}//forJOptionPane.showMessageDialog(null,"\nFIFO算法执行结束！\n");jTextField1.setText(Integer.toString(n));jTextField2.setText(Float.toString((float)n/20*100));}//run}//run_FIFOFIFO算法程序流程图该页调入内存该页调入内存n++结束创立两个表初始化表信息num++,i++i=0visit[i].flag=0?YNi<20YN5.4LRU算法设计主要思想首先初始化页表信息，将所有页的block_num属性赋值为-1，表示开始的时候任何页都不在内存中；其次再初始化内存表信息，将所有页的page_num属性赋值为-1，表示开始时候内存块中没有任何一页。然后，利用一个for循环循环20次，实现20次访问页面。由于置换的算法是LRU〔最近最少使用〕算法，所以将内存中四个块建立成一个队列，访问页面时依次将页面调入内存。如果内存中没有空间了那么将队首内存块中的页面置换出去，将将要访问的页面调入该内存块，然后依次这样继续下去，直到20次访问结束。需要强调的是，LRU算法在有一方面与FIFO算法不一样，那就是当被访问的页面已在内存中，FIFO算法不做任何处理，但是LRU算法需要将该存有该页面的内存块放到队尾。最后再在每次循环结束后判断是否发生缺页，如果缺页那么计数器自动加1，如果不缺页计数器就不变。LRU程序模块代码classrun_LRUimplementsRunnable{///////////执行FIFO算法线程//////////////publicPage[]table=newPage[10];//具有十个页面的页表publicMemary[]memary=newMemary[4];//内存中有四个块run_LRU(){inti;for(i=0;i<10;i++){table[i]=newPage(i,-1,0);}for(i=0;i<4;i++){memary[i]=newMemary(i,-1,i);}}publicvoidrun(){///显示两个表的信息num++;inti,j,k,l,h,n=0,visit_page;//当前访问页Memarytemp;//中间变量for(i=0;i<20;i++){//循环20次if(stop==true){//JOptionPane.showMessageDialog(null,"如果执行此操作\n\n将终止当前正在执行运行的LRU算法");return;}jTextField6.setText(Integer.toString(i+1));//显示执行次数visit_page=visit[i];j=5;if(memary[3].page_num==-1){//此目的是判断当内存中已经满了就不用查找，降低复杂度for(j=0;j<4;j++){//查找内存中是否有空位if(memary[j].page_num==-1)break;}//for}//ifif(table[visit_page].flag==0){//表示当前页不在内存，缺页n++;//记录缺页次数if(j<4){//有空位table[visit_page].flag=1;//修改页表table[visit_page].block_num=memary[j].block_num;memary[j].page_num=visit_page;//修改内存表}else{//没有空位，进行替换table[memary[0].page_num].flag=0;//将内存表中第一个结点替换出去，并修改页表信息table[memary[0].page_num].block_num=-1;table[visit_page].block_num=memary[0].block_num;table[visit_page].flag=1;memary[0].page_num=visit_page;//修改内存表信息temp=memary[0];//将头节点插到队尾memary[0]=memary[1];memary[1]=memary[2];memary[2]=memary[3];memary[3]=temp;}jTextField3.setText(Integer.toString(n));//时刻显示缺页次数}//ifelse{//不缺页，需要将当前结点从当前位置移到队列的存在的已存的最后一页位置上，而当前页以后的页就依次前移k=0;for(j=0;j<4;j++){//查找if(memary[j].page_num==visit_page)//查找被访问页在内存中的位置k=j;//k记录被访问页在内存中的位置if(memary[j].page_num==-1)//记录内存中最后一页的位置，即为j-1break;}//forif(j-1==k){//说明被访问结点是最后一个结点;//不做任何操作}else{//进行替换操作temp=memary[k];for(l=k+1;l<j;l++){memary[l-1]=memary[l];}memary[l-1]=temp;}}//elsejTextField4.setText(Float.toString((float)n/(i+1)*100));init_jLabel_LRU(memary);try{Thread.sleep(1500);///为便于观察，使线程暂停}catch(InterruptedExceptionex){Logger.getLogger(main_frame.class.getName()).log(Level.SEVERE,null,ex);}}//forJOptionPane.showMessageDialog(null,"\nLRU算法执行结束！\n");jTextField3.setText(Integer.toString(n));jTextField4.setText(Float.toString((float)n/20*100));}//run}//run_LRULRU算法程序流程图该页调入内存该页调入内存n++结束创立两个表初始化表信息num++,i++i=0visit[i].flag=0?YNi<20YN6系统测试首先进入NetBeansIDE6.5，翻开工程，选择“页面置换算法”工程工程翻开，实例如图：图表翻开工程界面然后再运行运行该工程,进入模拟程序界面，界面如图：图表点击“开始”按钮，产生一组长度为20的随机数，也即长度为20的页面走向，如图:图表6.1测试的数据现在利用图表产生的测试数组进行测试，由该图可以看出，产生的页面走向是如下序列：61725398131673955331在图中可以看出有两种置换方式,即LRU算法和FIFO算法,在演示的过程中看以动态的看到页面的访问次数(执行次数)、缺页次数、缺页率，并且为了比拟两种算法的结果，可以同时进行两种算法的演示，也可以先后进行。由于程序是动态进行的，所以只能随机截几张图，并不能依次的截图演示，如下列图所示。1、如图可以看出，当FIFO算法执行3次的时候，缺页数为3次，缺页率是100%。而此时由于LRU不是与FIFO算法同时开始，所以只执行了2两次，缺页次数也是2次，缺页率为100%。图表6.1.SEQ图表\*ARABIC12、如下图，当FIFO算法执行了10次时，缺页次数是9次，缺页率是90%；而此时LRU算法执行了9次，缺页次数是9次，所以缺页率还是100%。图表6.1.SEQ图表\*ARABIC23、如图，可以看出当最后两种算法都执行结束时FIFO算法缺页次数是15次，缺页率是75%；LRU算法缺页次数是14，缺页率是70%。图表6.1.SEQ图表\*ARABIC36.2测试小结根据以上演示，可以看出在访问次数有限的情况下，LRU算法与FIFO算法的缺页次数结果根本相似，所以这两中算法差异不大，下面再给几组测试以说明结论。1、如图，