模拟页面置换算法FIFO、LRU的实现

实验报告五实验名称:模拟页面置换算法FIFO、LRU的实现日期：2015-12-9班级：13级计科学号:姓名：一、实验目的了解页面置换的概念，理解页面置换的算法加深对页面置换算法的理解。二、实验内容Java编程语言实现FIFO和LUR页面算法。三、项目要求与分析FIFO算法当需要置换页面时，主要通过置换最早进入内存的页面从而达到先进先出的目的。LRU算法当需要置换页面时，主要通过置换进入内存中最久没有被访问的页面而达到最近最久未使用的目的。程序中可以通过标志位进行记录。四、具体实现1.FIFO算法实现代码以及运行结果：publicclassFIFO{/***内存块的个数*/publicstaticintN;/***内存块数组*/Object[]array=newObject[N];/***要访问的页面数组*/publicstaticint[]visit;privateintsize;/***内存是非空为否*@return*/publicbooleanisEmpty(){if(0==size)returntrue;elsereturnfalse;}/***内存是非空满*@return*/publicbooleanisFulled(){if(size=N)returntrue;elsereturnfalse;}/***元素(页框)的个数*@return*/publicintsize(){returnsize;}/***查找元素o在数组中的位置*@paramo*@return*/publicintindexOfElement(Objecto){for(inti=0;iN;i++){if(o==array[i]){returni;}}return-1;}/***页面转换*@paramobj*/publicObjecttrans(Objectobj){Objecte=null;intt=0;if(indexOfElement(obj)!=-1){t=indexOfElement(obj);for(inti=t;isize-1;i++){array[i]=array[i+1];}array[size-1]=obj;}else{if(!isFulled()){array[size]=obj;size++;}else{for(inti=0;isize-1;i++){array[i]=array[i+1];}array[size-1]=obj;}}if(-1==t){returnnull;}else{returnarray[t];}}/***输出内存区中的各数据*/publicvoidshowMemoryBlock(){for(inti=0;isize;i++){System.out.print(array[i]+);}}/***清空队列(页框)*/publicvoidclear(){}/***@paramargs*/publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);System.out.print(请输入内存块的数量:);N=sc.nextInt();System.out.print(请输入总页面数目：);intn=sc.nextInt();visit=newint[n];System.out.println(请输入各个页的页面号码：);for(inti=0;in;i++)visit[i]=sc.nextInt();FIFOfifo=newFIFO();for(inti=0;ivisit.length;i++){fifo.trans(visit[i]);fifo.showMemoryBlock();System.out.println();}运行结果：2.LUR算法实现代码以及运行结果：publicclassLRU{staticintvolum;//栈的容量staticListIntegerlist=newLinkedListInteger();//链表用来模拟栈存放页面staticint[]visit;//要访问的页面数组staticintcount=0;//记录缺页次数publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);System.out.print(请输入栈的容量:);volum=sc.nextInt();System.out.print(请输入总页面数目：);intn=sc.nextInt();visit=newint[n];System.out.println(请输入各个页的页面号码：);for(inti=0;in;i++)visit[i]=sc.nextInt();sLRU();//调用最近最久未使用算法System.out.println(置换页面的数目为：+count);}publicstaticvoidsLRU(){intindex=0;while(indexvisit.length){booleanflag=false;if(list.size()=volum){for(inti=0;ilist.size();i++){if((int)(list.get(i))==visit[index]){list.remove(i);//先删除list.add(visit[index]);//再添加到尾部flag=true;break;}}if(!flag){if(list.size()volum){//如果栈未满，而且此页面没有在栈中，就将它入栈list.add(visit[index]);}else{//如果栈已经满了，且该页面号码没有在栈中，就把栈底元素删除，将新页插入inttemp=list.get(0);list.remove(0);//最开始一个换出list.add(visit[index]);//加到末尾count++;System.out.println(开始换页了,将栈底的+temp+换出);System.out.println(这也是没有办法的事情，毕竟栈是有限的);}}System.out.print(经过第+(index+1)+个页面的栈内容为);for(intk=0;klist.size();k++)System.out.print(list.get(k)+);System.out.println();index++;}运行结果：五、所遇问题与解决方法问题：针对于FIFO算法定义选择在内存中驻留时间最久的页面予以淘汰，对于内存中的驻留时间理解复杂了不知道如何下手。解决方案：我们只需要设置一个先进先出队列就可以。最先进入内存的页面最早被转换出去。六、实验总结1.通过本次实验，加深了对操作系统的页面置换有了一定的了解，并能够用高级语言进行模拟演示。通过查阅相关资料基本掌握了JAVA应用程序编写的基本方法。2.两种页面置换算法FIFO和LUR理解起来相当容易，但在实际编程实现的时候需要注意各种细节，需要耐心细致，实际编程过程中遇到一些细节性的问题确实需要仔细考虑才行。