实验五虚拟内存页面置换算法1、实验目的通过这次实验，加深对虚拟内存页面置换概念的理解，进一步掌握先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的实现方法。

2、试验内容问题描述：设计程序模拟先进先出FIFO、最佳置换OPI和最近最久未使用LRU页面置换算法的工作过程。

假设内存中分配给每个进程的最小物理块数为m，在进程运行过程中要访问的页面个数为n，页面访问序列为P1, … ,P n，分别利用不同的页面置换算法调度进程的页面访问序列，给出页面访问序列的置换过程，计算每种算法缺页次数和缺页率。

3、程序要求：1）利用先进先出FIFO、最佳置换OPI和最近最久未使用LRU 三种页面置换算法模拟页面访问过程。

2）模拟三种算法的页面置换过程，给出每个页面访问时的内存分配情况。

3）输入：最小物理块数m，页面个数n，页面访问序列P1, … ,P n，算法选择1-FIFO，2-OPI，3-LRU。

4）输出：每种算法的缺页次数和缺页率。

4、需求分析(1) 输入的形式和输入值的范围算法选择物理块数页面个数页面访问序列P1, …,Pn(2) 输出的形式每种算法的缺页次数和缺页率(3)测试用例引用率70 7701712210323042432303212120177101页框(物理块）2 0 3引用率70 7701712210323104432303211320177201页框23424232312712711引用率70 7701712210323044323032113220171701页框4243232125、调试分析通过二次编程，又一次加深了对先进先出（FIFO）页面置换算法，最佳（OPI）置换算法，最近最久未使用（LRU）置换算法的理解。

同时，也掌握了一些使界面输出看起来更工整的办法。

还有，在平时做作业的时候，总是默认为物理块数是3，其实只是比较常用而已，并不是每次都是3.这个在编程中有体现，在今后做题中会更注意。

6、测试结果(1)先进先出FIFO页面置换算法输入输出(2)最佳页面OPI置换算法输入输出(3)最近最久未使用LRU置换算法输入输出7、附录(java)package experiment;import java.io.BufferedInputStream;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.Scanner;public class E_PageDisplace {private static int MaxNumber = 100;// 页面序列P1, … ,Pn，private static int PageOrder[] = new int[MaxNumber];// 模拟页面置换过程private static int Simulate[][] = new int[MaxNumber][MaxNumber];//private static int PageCount[] = new int[MaxNumber];// 页面数private static int PageNum;// 缺页数private static int LackNum;// 缺页率private static double LackPageRate;private static boolean found;// 物理块数量private static int BlockNum;// NULL的int标记private static int NULL=-1;// for循环用到变量private static int i;private static int j;private static int k;// 算法选择// 1-先进先出FIFO页面置换算法// 2-最佳页面OPI置换算法// 3-最近最久未使用LRU置换算法private static int option = 0;private static Scanner stdin;public static void main(String[] args) throws FileNotFoundException { // 输入数据input();// 算法选择//算法选择\n FIFO: 输入'1'\n OPI: 输入'2'\n LRU: 输入'3'\n exit: 输入'4'\n";\switch(option){case 1:System.out.println("先进先出FIFO页面置换算法：");FIFO();output();break;case 2:System.out.println("最佳页面OPI置换算法：");OPI();output();break;case 3:System.out.println("最近最久未使用LRU置换算法：");LRU();output();break;default:System.out.println("你的输入有问题请重新输入！");break;}}// 输入数据public static void input() throws FileNotFoundException {BufferedInputStream in = new BufferedInputStream(new FileInputStream( "./file/05"));System.setIn(in);stdin = new Scanner(System.in);// 算法选择// 1-先进先出FIFO页面置换算法// 2-最佳页面OPI置换算法// 3-最近最久未使用LRU置换算法option = stdin.nextInt();// 物理块数BlockNum = stdin.nextInt();// 页面个数PageNum = stdin.nextInt();// 页面访问序列P1, … ,Pnfor (i = 0; i < PageNum; i++) {PageOrder[i] = stdin.nextInt();}}///public static void original(){for(i=0;i<PageNum;i++){for(j=0;j<BlockNum;j++){Simulate[i][j]=NULL;}}LackNum=1;}//先进先出:最早出现的置换算法，总是淘汰最先进入内存的页面。

public static void FIFO(){original();Simulate[0][0]=PageOrder[0];int temp=0,flag=0;for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j])break;}if(j==BlockNum){//该页面不在内存中for(k=0;k<BlockNum;k++){//模拟置换过程if(Simulate[flag][k]==NULL)break;elseSimulate[i][k]=Simulate[flag][k];}//淘汰最先进入内存的页面temp++;temp=temp%BlockNum;Simulate[i][temp]=PageOrder[i];LackNum++;flag=i;}//该页面在内存中elsecontinue;}}//最佳置换:选择的被淘汰的页面都是以后永不使用或者在最长（未来）时间内不被访问的页面。

public static void OPI(){original();Simulate[0][0]=PageOrder[0];int temp,flag=0;//flag表示上一个模拟内存的下标for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j])break;}//j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;//模拟置换过程for(k=0;k<BlockNum;k++){if(Simulate[flag][k]==NULL)break;elseSimulate[i][k]=Simulate[flag][k];}//内存中页面进行选择//两种情况：内存已满和内存未满for(j=0;j<BlockNum;j++){if(Simulate[i][j]==NULL){Simulate[i][j]=PageOrder[i];LackNum++;flag=i;break;}}if(j!=BlockNum)//内存未满continue;//内存已满temp=0;//temp表示要置换的页面内存下标for(j=0;j<BlockNum;j++){//选取要置换的页面内存下标for(k=i+1;k<PageNum;k++){//最长时间内不被访问的页面if(Simulate[i][j]==PageOrder[k]){PageCount[j]=k;break;}}if(k==PageNum)//之后没有进行对该页面的访问PageCount[j]=PageNum;if(PageCount[temp]<PageCount[j]){temp=j;}}Simulate[i][temp]=PageOrder[i];LackNum++;flag=i;}}//最近最久未使用:LRU算法选择最近最久未使用的页面予以淘汰。

public static void LRU(){original();Simulate[0][0]=PageOrder[0];int temp,flag=0;//flag表示上一个模拟内存的下标PageCount[0]=0;//最近的页面下标for(i=1;i<PageNum;i++){//判断该页面是否存在内存中for(j=0;j<BlockNum;j++){if(PageOrder[i]==Simulate[flag][j]){PageCount[j]=i;break;}}//j!=BlockNum表示该页面已经在内存中if(j!=BlockNum)continue;//模拟置换过程for(k=0;k<BlockNum;k++){if(Simulate[flag][k]==NULL)break;elseSimulate[i][k]=Simulate[flag][k];}//内存中页面进行选择//两种情况：内存已满和内存未满for(j=0;j<BlockNum;j++){if(Simulate[i][j]==NULL){//内存未满Simulate[i][j]=PageOrder[i];PageCount[j]=i;LackNum++;flag=i;break;}}if(j!=BlockNum)continue;//内存已满temp=0;//temp表示要置换的页面内存下标for(j=0;j<BlockNum;j++){//最近最久时间内不被访问的页面if(PageCount[temp]>PageCount[j])temp=j;}Simulate[i][temp]=PageOrder[i];PageCount[temp]=i;LackNum++;flag=i;}}//模拟三种算法的页面置换过程，//给出每个页面访问时的内存分配情况//每种算法的缺页次数和缺页率。