行政组织学4.

实验3请求调页存储管理方式的模拟1实验目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。2实验内容（1）假设每个页面中可存放10条指令，分配给一作业的内存块数为4。（2）模拟一作业的执行过程。该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已经在内存中，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块中均已装入该作业，则需进行页面置换。最后显示其物理地址，并转下一条指令。在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。（3）置换算法：请分别考虑OPT、FIFO和LRU算法。（4）作业中指令的访问次序按下述原则生成：•50%的指令是顺序执行的。•25%的指令是均匀分布在前地址部分。•25%的指令时均匀分布在后地址部分。代码：packagemainDart;importjava.util.ArrayList;importjava.util.List;importjava.util.Random;publicclassFIFO{privatestaticinttimes=0;//记录置换内存页面的次数/***随机产生0~319之间的数*产生320条指令**@return包含320条指令的数组*/publicstaticint[]productNumber(){intorder[]=newint[320];//数组存储的数字表示指令Randomrand=newRandom();for(inti=0;i320;i++){if(i%4==0){order[i]=rand.nextInt(319);//0=order319}elseif(i%4==1){order[i]=order[i-1]+1;//1=order320}elseif(i%4==2){order[i]=rand.nextInt(order[i-1]);}elseif(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}returnorder;}/***打印链表*@paramlist*/publicstaticvoidprintList(ListIntegerlist){for(inttemt:list){System.out.print(temt+\t);}System.out.println();}/***先进先出算法*总是淘汰最先进入内存的页面*在实现的时候，记录上一次所替换的页面在内存的下标，则本次要替换的位置就是上次下标+1的位置，并且下标是0~3循环的*@parammemoryNum*@parampage*/publicstaticvoidFIFOChangePage(ListIntegermemoryNum,intpage){intindex=FIFOChangePage(memoryNum,page,++times);memoryNum.remove(index);memoryNum.add(index,page);}/***返回本次替换的页面在内存中的位置*@parammemoryNum*@parampage*@paramtimes记录替换页面的次数，第一次替换的是内存第0个单元*@return*/publicstaticintFIFOChangePage(ListIntegermemoryNum,intpage,inttimes){if(times==1){return0;}intindex=(FIFOChangePage(memoryNum,page,times-1)+1)%4;returnindex;}publicstaticvoidmain(String[]args){int[]order=productNumber();System.out.println(320条随机指令数：);for(inti=0;iorder.length;i++){System.out.print(order[i]+\t);if((i+1)%10==0){System.out.println();}}ListIntegermemoryNum=newArrayListInteger(4);//内存块存储的页面intcount=0;//记录缺页次数for(inti=0;i320;i++){intpage=order[i]/10;if(memoryNum.contains(page))//若该指令所在页面已经在内存，输出该页面所在内存块的号{}else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()4)//内存没满，直接将所需页面调入内存{memoryNum.add(page);}else//内存存满，需要调用页面置换算法，进行页面置换{FIFOChangePage(memoryNum,page);//先进先出算法}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println(缺页率：+(double)count/320);}}packagemainDart;importjava.util.ArrayList;importjava.util.HashMap;importjava.util.List;importjava.util.Map;importjava.util.Random;publicclassLRU{/***随机产生0~319之间的数*产生320条指令**@return包含320条指令的数组*/publicstaticint[]productNumber(){intorder[]=newint[320];//数组存储的数字表示指令Randomrand=newRandom();for(inti=0;i320;i++){if(i%4==0){order[i]=rand.nextInt(319);//0=order319}elseif(i%4==1){order[i]=order[i-1]+1;//1=order320}elseif(i%4==2){order[i]=rand.nextInt(order[i-1]);}elseif(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}returnorder;}/***打印链表*@paramlist*/publicstaticvoidprintList(ListIntegerlist){for(inttemt:list){System.out.print(temt+\t);}System.out.println();}/***最近最久未使用算法*@paramorder*/publicstaticvoidLRUChangePage(int[]order){ListIntegermemoryNum=newArrayListInteger(4);//内存块int[]timeFlag=newint[]{-1,-1,-1,-1};//用来记录内存当中各单元未被访问的时间值intcount=0;//记录缺页次数for(inti=0;i320;i++){intpage=order[i]/10;if(memoryNum.contains(page))//若该指令所在页面已经在内存{intindex=memoryNum.indexOf(page);timeFlag[index]=0;//将时间变为0}else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()4)//内存没满，直接将所需页面调入内存{//将没有命中的所有页面的时间加一for(intin=0;in4;in++){if(timeFlag[in]!=-1){timeFlag[in]+=1;}}//将page加入内存并将时间置为0memoryNum.add(page);timeFlag[memoryNum.indexOf(page)]=0;}else//内存存满，需要调用页面置换算法，进行页面置换{intmaxIn=-1;//记录拥有最大时间值的标记的下标intmaxT=-1;//记录最大的时间值for(intin=0;in4;in++)//找出内存中时间值最大的进行替换{if(timeFlag[in]maxT){maxT=timeFlag[in];maxIn=in;}}memoryNum.remove(maxIn);memoryNum.add(maxIn,page);timeFlag[maxIn]=0;//将没有命中的所有页面的时间加一for(intin=0;in4;in++){if(in!=maxIn){timeFlag[in]+=1;}}}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println(缺页率：+(double)count/320);}publicstaticvoidmain(String[]args){int[]order=productNumber();System.out.println(320条随机指令数：);for(inti=0;iorder.length;i++){System.out.print(order[i]+\t);if((i+1)%10==0){System.out.println();}}LRUChangePage(order);}}packagemainDart;importjava.util.ArrayList;importjava.util.List;importjava.util.Random;publicclassOptimal{/***随机产生0~319之间的数*产生320条指令**@return包含320条指令的数组*/publicstaticint[]productNumber(){intorder[]=newint[320];//数组存储的数字表示指令Randomrand=newRandom();for(inti=0;i320;i++){if(i%4==0){order[i]=rand.nextInt(319);//0=order319}elseif(i%4==1){order[i]=order[i-1]+1;//1=order320}elseif(i%4==2){order[i]=rand.nextInt(order[i-1]);}elseif(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}returnorder;}/****@paramorder320条指令数组*@return返回一个链表，依次保存着320条指令每条指令所在的页面*/publicstaticListIntegerpageSeq(int[]order){ListIntegerpageSeq=newArrayListInteger();for(inttemp:order){pageSeq.add(temp/10);}returnpageSeq;}/***打印链表*@paramlist*/publicstaticvoidprintList(ListIntegerlist){for(inttemt:list){System.out.print(temt+\t);}System.out.println();}/***最佳置换算法*根据当前已经在内存中的页面在之后被需要的先后进行置换**@parampageSe