import java.util.Random;
import java.util.LinkedList;import java.util.Scanner;public class Manage { public static int[] getOrder(){ int[] a = new int[320]; a[319] = -1; Random ran = new Random(); int count = -1; try { while(a[319] < 0) { int m = ran.nextInt(320); a[++count] = m+1; //在0-320生成随机数 int m1 = ran.nextInt(m+2); a[++count] = m1; a[++count] = m1+1; a[++count] = ran.nextInt(318-m1)+m1+2; } }catch(IllegalArgumentException e) { } return a; } public static int[] getAddress(int[] a) { //获得每个指令对应的页面 int[] b = new int[320]; for(int i = 0;i < 320;i++) { b[i] = a[i]/10; } return b; } public static int FIFO(int num,int[] b) { LinkedList<Integer> list = new LinkedList<Integer>(); //作为物理块 int count = 0; for(int i = 0;i < 320;i++) { if(list.contains(b[i])){ //如果物理块已包含该页面，进行下一次判断 continue; }else if(list.size() < num && !list.contains(b[i])){//物理块不包含该页面而且物理块未满 list.add(b[i]); //装入页面 count++; //缺页次数加一 for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); }else if(list.size() >= num && !list.contains(b[i])){//物理块不包含该页面而且物理块已满 list.poll(); //移出队首元素 list.add(b[i]); //装入页面 count++; //缺页次数加一 for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); } } return count; } public static int LRU(int num,int[] b) { LinkedList<Integer> list = new LinkedList<Integer>(); int count = 0; for(int i = 0;i < 320;i++) { if(list.contains(b[i])){ list.remove(list.indexOf(b[i])); //如果物理块中已包含该页面，就把该页面移到队尾，保证队首元素是最近最久未使用的 list.add(b[i]); }else if(list.size() < num && !list.contains(b[i])){//物理块不包含该页面而且物理块未满 list.add(b[i]); count++; for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); }else if(list.size() >= num && !list.contains(b[i])){//物理块不包含该页面而且物理块已满 list.poll(); list.add(b[i]); count++; for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); } } return count; } public static int OPT(int num,int[] b) { LinkedList<Integer> list = new LinkedList<Integer>(); LinkedList<Integer> list2 = new LinkedList<Integer>(); //用于记录数据是否在list中重复出现 int index = 0; int count = 0; //记录换页次数 for(int i = 0;i < 320;i++) { if(list.contains(b[i])){ //如果物理块中已包含该页面 continue; }else if(list.size() < num && !list.contains(b[i])){ //物理块不包含该页面而且物理块未满 list.add(b[i]); count++; for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); }else if(list.size() >= num && !list.contains(b[i])){ //物理块不包含该页面而且物理块已满 //用来确定需被移除页面在list中的下标 for(int a = i+1;a < 320;a++) { if(list2.size() < list.size()) { if(list.contains(b[a]) && !list2.contains(b[a])) {//确定list中的页面没有被重复扫描 list2.add(b[a]); index = list.indexOf(b[a]); //记录被移除元素下标 } }else{ list2.clear(); //重置list2 break; } } list.remove(index); list.add(b[i]); count++; index = 0; for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); } } return count; } public static int LFR(int num,int[] b) { LinkedList<Integer> list = new LinkedList<Integer>(); int index = 0; int[] count2 = new int[num]; //用于给页面使用次数做记录 for(int z = 0;z < count2.length;z++) { count2[z] = 0; } int count = 0; for(int i = 0;i < 320;i++) { if(list.contains(b[i])){ //如果物理块中已包含该页面 continue; }else if(list.size() < num && !list.contains(b[i])){//物理块不包含该页面而且物理块未满 list.add(b[i]); count++; for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); }else if(list.size() >= num && !list.contains(b[i])){//物理块不包含该页面而且物理块已满 for(int a = 0;a < num;a++) { for(int c = i-1;c >= 0 ;c--) { if(i-c <= 30) { //观察前30次调用 if(b[c] == list.get(a)) { //30次内被调用过一次，标志该页面的值加一，做记录 count2[a]++; } }else { break; } } } int min = count2[0]; //取出最小值下标，即使用次数最少的页数 for(int y = 0;y < count2.length;y++) { if(count2[y] < min) { min = count2[y]; index = y; } } for(int z = 0;z < count2.length;z++) {//重置count2数组 count2[z] = 0; } list.remove(index); list.add(b[i]); //重置index index = 0; count++; for(Integer l: list) { System.out.print(l+"\t"); } System.out.println(); } } return count; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] a = getOrder(); System.out.println("随机生成的指令："); for(int i = 0;i<320;i++) { System.out.print(a[i]+"\t"); if((i+1)%10 == 0) { System.out.println(); } } System.out.println("======================================================================="); int[] b = getAddress(a); System.out.println("形成的地址页号："); for(int i = 0;i<320;i++) { System.out.print(b[i]+"\t"); if((i+1)%10 == 0) { System.out.println(); } } System.out.println("======================================================================="); System.out.println("输入物理块数："); int blocks = sc.nextInt(); System.out.println("选择算法："+"\n"+"1:FIFO"+"\n"+"2:LRU"+"\n"+"3:OPT"+"\n"+"4:LFR"); int algo = sc.nextInt(); switch(algo) { case 1: int count1 = 320 - FIFO(blocks,b); //命中次数=320 - 缺页次数 double rate1 = (double)count1/320; System.out.println("命中次数："+count1); System.out.println("命中率："+rate1); break; case 2: int count2 = 320 - LRU(blocks,b); double rate2 = (double)count2/320; System.out.println("命中次数："+count2); System.out.println("命中率："+rate2); break; case 3: int count3 = 320 - OPT(blocks,b); double rate3 = (double)count3/320; System.out.println("命中次数："+count3); System.out.println("命中率："+rate3); break; case 4: int count4 = 320 - LFR(blocks,b); double rate4 = (double)count4/320; System.out.println("命中次数："+count4); System.out.println("命中率："+rate4); break; default: System.out.println("输入错误！"); } sc.close(); }}