实验3请求调页存储管理方式的模拟1实验目的通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
2实验内容（1）假设每个页面中可存放10条指令，分配给一作业的内存块数为4。
（2）模拟一作业的执行过程。
该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。
在模拟过程中，如果所访问的指令已经在内存中，则显示其物理地址，并转下一条指令。
如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。
如果4个内存块中均已装入该作业，则需进行页面置换。
最后显示其物理地址，并转下一条指令。
在所有320条指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
（3）置换算法：请分别考虑OPT、FIFO和LRU算法。
（4）作业中指令的访问次序按下述原则生成：•50%的指令是顺序执行的。
•25%的指令是均匀分布在前地址部分。
•25%的指令时均匀分布在后地址部分。
代码：package mainDart;import java.util.ArrayList;import java.util.List;import java.util.Random;public class FIFO {private static int times=0;//记录置换内存页面的次数/*** 随机产生0~319之间的数* 产生320条指令** @return 包含320条指令的数组*/public static int[] productNumber(){int order[] = new int[320];//数组存储的数字表示指令Random rand = new Random();for(int i=0;i<320;i++){if(i%4==0){order[i]=rand.nextInt(319); //0<=order<319}else if(i%4==1){order[i]=order[i-1]+1;//1<=order<320}else if(i%4==2){order[i]= rand.nextInt(order[i-1]);}else if(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}return order;}/*** 打印链表* @param list*/public static void printList(List<Integer> list){for(int temt:list){System.out.print(temt+"\t");}System.out.println();}/*** 先进先出算法* 总是淘汰最先进入内存的页面* 在实现的时候，记录上一次所替换的页面在内存的下标，则本次要替换的位置就是上次下标+1的位置，并且下标是0~3循环的* @param memoryNum* @param page*/public static void FIFOChangePage(List<Integer> memoryNum,int page){int index = FIFOChangePage(memoryNum,page,++times);memoryNum.remove(index);memoryNum.add(index, page);}/*** 返回本次替换的页面在内存中的位置* @param memoryNum* @param page* @param times记录替换页面的次数，第一次替换的是内存第0个单元* @return*/public static int FIFOChangePage(List<Integer> memoryNum,int page,int times) {if(times==1){return 0;}int index = (FIFOChangePage(memoryNum,page,times-1)+1)%4;return index;}public static void main(String[] args) {int[] order = productNumber();System.out.println("320条随机指令数：");for(int i =0;i<order.length;i++){System.out.print(order[i]+"\t");if((i+1)%10==0){System.out.println();}}List<Integer> memoryNum= new ArrayList<Integer>(4);//内存块存储的页面int count=0;//记录缺页次数for(int i=0;i<320;i++){int page = 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);}}package mainDart;import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.Random;public class LRU {/*** 随机产生0~319之间的数* 产生320条指令** @return 包含320条指令的数组*/public static int[] productNumber(){int order[] = new int[320];//数组存储的数字表示指令Random rand = new Random();for(int i=0;i<320;i++){if(i%4==0){order[i]=rand.nextInt(319); //0<=order<319}else if(i%4==1){order[i]=order[i-1]+1;//1<=order<320}else if(i%4==2){order[i]= rand.nextInt(order[i-1]);}else if(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}return order;}/*** 打印链表* @param list*/public static void printList(List<Integer> list){for(int temt:list){System.out.print(temt+"\t");}System.out.println();}/*** 最近最久未使用算法* @param order*/public static void LRUChangePage(int [] order){List<Integer> memoryNum = new ArrayList<Integer>(4);//内存块int[] timeFlag =new int[]{-1,-1,-1,-1}; //用来记录内存当中各单元未被访问的时间值int count=0;//记录缺页次数for(int i=0;i<320;i++){int page = order[i]/10;if(memoryNum.contains(page)) //若该指令所在页面已经在内存{int index = memoryNum.indexOf(page);timeFlag[index]=0;//将时间变为0 }else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()<4) //内存没满，直接将所需页面调入内存{//将没有命中的所有页面的时间加一for(int in=0;in<4;in++){if(timeFlag[in]!=-1){timeFlag[in]+=1;}}//将page加入内存并将时间置为0memoryNum.add(page);timeFlag[memoryNum.indexOf(page)]=0;}else//内存存满，需要调用页面置换算法，进行页面置换{int maxIn=-1;//记录拥有最大时间值的标记的下标int maxT=-1;//记录最大的时间值for(int in=0;in<4;in++)//找出内存中时间值最大的进行替换{if(timeFlag[in]>maxT){maxT=timeFlag[in];maxIn=in;}}memoryNum.remove(maxIn);memoryNum.add(maxIn,page);timeFlag[maxIn]=0;//将没有命中的所有页面的时间加一for(int in=0;in<4;in++){if(in!=maxIn){timeFlag[in]+=1;}}}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println("缺页率："+(double)count/320);}public static void main(String[] args) {int[] order = productNumber();System.out.println("320条随机指令数：");for(int i =0;i<order.length;i++){System.out.print(order[i]+"\t");if((i+1)%10==0){System.out.println();}}LRUChangePage(order);}}package mainDart;import java.util.ArrayList;import java.util.List;import java.util.Random;public class Optimal {/*** 随机产生0~319之间的数* 产生320条指令** @return 包含320条指令的数组*/public static int[] productNumber(){int order[] = new int[320];//数组存储的数字表示指令Random rand = new Random();for(int i=0;i<320;i++){if(i%4==0){order[i]=rand.nextInt(319); //0<=order<319}else if(i%4==1){order[i]=order[i-1]+1;//1<=order<320}else if(i%4==2){order[i]= rand.nextInt(order[i-1]);}else if(i%4==3){order[i]=order[i-1]+rand.nextInt(320-order[i-1]);}}return order;}/**** @param order320条指令数组* @return 返回一个链表，依次保存着320条指令每条指令所在的页面*/public static List<Integer> pageSeq(int[] order){List<Integer> pageSeq = new ArrayList<Integer>();for(int temp:order){pageSeq.add(temp/10);}return pageSeq;}/*** 打印链表* @param list*/public static void printList(List<Integer> list){for(int temt:list){System.out.print(temt+"\t");}System.out.println();}/*** 最佳置换算法* 根据当前已经在内存中的页面在之后被需要的先后进行置换** @param pageSeq 整个320条指令，从头到尾所需要的页面* @param memoryNum 已满的内存空间* @param page等待被调入内存的页面*/public static void OptimalChangePage(List<Integer> pageSeq,int start,List<Integer> memoryNum,int page){int maxSeq=-1,index=0;for(int pageNum:memoryNum) //遍历内存{for(int i=start;i<pageSeq.size();i++){if(pageNum==pageSeq.get(i)){if(i>maxSeq){maxSeq=i;}break;}}}if(maxSeq>-1)//maxSeq==-1说明内存当中的四个页面在将来都不会再被使用，这时默认将内存块中的第一个页面置换出{index = memoryNum.indexOf(pageSeq.get(maxSeq));//记录将要被置换的那个页面所在内存位置}memoryNum.remove(index);//将内存中将来最久被使用的页面删除memoryNum.add(index, page);//将需要调入的页面加入内存}public static void main(String[] args) {int[] order = productNumber();System.out.println("320条随机指令数：");for(int i =0;i<order.length;i++){System.out.print(order[i]+"\t");if((i+1)%10==0){System.out.println();}}List<Integer> pageSeq = pageSeq(order); //依次存放着指令所在的页面号List<Integer> memoryNum= new ArrayList<Integer>(4);//内存块存储的页面int count=0;//记录缺页次数for(int i=0;i<320;i++){int page = order[i]/10;if(memoryNum.contains(page)) //若该指令所在页面已经在内存，输出该页面所在内存块的号{}else//没在内存，发生缺页，需要判断内存块是否存满，{if(memoryNum.size()<4) //内存没满，直接将所需页面调入内存{memoryNum.add(page);}else//内存存满，需要调用页面置换算法，进行页面置换{OptimalChangePage(pageSeq,i+1,memoryNum,page);//最佳置换算法}count++;//记录缺页次数}printList(memoryNum);//打印内存所调入页面的情况}System.out.println("缺页率："+(double)count/320);}}package mainDart;import java.util.ArrayList;import java.util.List;public class TestAPP {public static void main(String[] args) {List<Integer> list = new ArrayList<Integer>();list.add(1);list.add(3);list.add(45);System.out.println(list);list.remove(1);list.add(1, -1);System.out.println(list);}}。