import java.util.Scanner;
import java.util.Arrays;
import java.util.LinkedList;
class PageReplacementAlgorithm
{
PageReplacementAlgorithm(){}
public void FIFO(int PageOrder[],int block[])
{
//先进先出算法
/*
*最开始，先把物理块放满
*在物理块放满之后，对物理块进行判断，判断当前页面是否在物理快中,在则不用置换，不在则从当前页面向序列前寻找，找到最先开始在物理块中出现的页面(即最小数组下标)
*找到后,将其替换掉(替换的同时计置换的次数),进行下一轮判断
* */
int [][]LackPageIndex=new int [PageOrder.length][2];//保存每一次缺页索引以及插入的页面
int [][]PagePrint=new int [PageOrder.length] []; //保存每一次缺页记录
int []blockCopy=new int [block.length];
int LackPage=0; //缺页数
boolean existence; //用来标记页面是否存在于物理块中
for(int i=0;i<PagePrint.length;i++)
{
//开放内存空间
PagePrint[i]=new int [block.length];
}
for(int i=0;i<LackPageIndex.length;i++)
{
//开放内存空间
LackPageIndex[i]=new int [2];
}
for(int currentPosition=0;currentPosition<PageOrder.length;currentPosition++)
{
existence=false;
for(int j=0;j<block.length;j++)
{
if(block[j]==PageOrder[currentPosition])
{
//当前页面存在物理块中
existence=true;
break;
}
else continue;
}
if(existence)
{
continue;
}
if(!existence)
{
//当前页面不存在物理块中：1.物理块没满，直接加入；2.物理快满了，从当前位置向前找，筛选出最先开始在物理块中出现的页面
if(BlockIsFull(block))
{
//物理块满了
int firstIn=FindFirstIn(block,currentPosition,LackPageIndex);//找出最开始在物理快中出现的页面下标
int pagePosition=ReplacePage(block,PageOrder[firstIn]);//页面在物理块中的位置
block[pagePosition]=PageOrder[currentPosition]; //用当前页面替换旧的页面
blockCopy=Arrays.copyOf(block, block.length);//拷贝当前缺页数组
PagePrint[currentPosition]=blockCopy; //保存次缺页记录，后续打印
LackPageIndex[currentPosition][0]=currentPosition;//0下标保存每一次缺页索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下标保存插入的页面
LackPage++;//缺页数++
continue;
}
else
{
//物理块没满
for(int k=0;k<block.length;k++)
{
if(block[k]==-1)
{
block[k]=PageOrder[currentPosition];//将页面放入物理块中
blockCopy=Arrays.copyOf(block, block.length); //拷贝当前缺页数组
PagePrint[currentPosition]=blockCopy; //保存第(i+1)次缺页记录，后续打印
LackPageIndex[currentPosition][0]=currentPosition;//0下标保存每一次缺页索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下标保存插入的页面
LackPage++;//缺页数++
break;//下一个页面
}
}
}
}
}
double LackPagePercent=((double)LackPage/(double)PageOrder.length);
System.out.println("FIFO算法缺页率，缺页次数，缺页情况如下");
System.out.println("缺页率为"+LackPagePercent*100+"%"+" ;"+"缺页次数为"+LackPage);
Print(PageOrder,PagePrint);
}
public int ReplacePage(int block[] ,int page)
{
//找到页面在物理块中相应的位置并返回
int i;
for( i=0;i<block.length;i++)
{
if(block[i]==page)
{
return i;
}
}
System.out.println("该页面在物理块中不存在：返回-1");
return -1;
}
public int FindFirstIn(int block[],int currentPosition,int[][]LackPageIndex)
{
//找到这三个页面出现的三个最小下标
//从当前位置向前找，找到在物理块中最早出现的页面,返回最早出现在物理快中页面的索引
LinkedList<Integer> List=new LinkedList<Integer>();
A:for(;currentPosition>=0;currentPosition--)
{
for(int i=0;i<block.length;i++)
{
//从当前位置向前寻找,找到了
if(block[i]==LackPageIndex[currentPosition][1]&&(LackPageIndex[currentPosition][0]!=0|| LackPageIndex[currentPosition][1]!=0))
{
//找到了第i个页面出现的位置
List.add(LackPageIndex[currentPosition][0]); //保存最小索引
if(List.size()==block.length)
break A;
}
else continue;//没找到则继续往前
}
}
Integer [] saveIndex=new Integer[List.size()];
List.toArray(saveIndex);
int FirstInIndex=100;
for(int j=0;j<saveIndex.length;j++)
{
if(saveIndex[j]<FirstInIndex)
{
//找到最早出现的下标
FirstInIndex=saveIndex[j];
}
}
return FirstInIndex;//返回最早出现页面的下标
}
public int FindFirstIn(int block[],int currentPosition,int[]PageOrder)
{
//找到这三个页面出现的三个最小下标
//从当前位置向前找，找到在物理块中最早出现的页面,返回最早出现在物理快中页面的索引
LinkedList<Integer> List=new LinkedList<Integer>();
LinkedList<Integer> Page=new LinkedList<Integer>();
A:for(;currentPosition>=0;currentPosition--)
{
for(int i=0;i<block.length;i++)
{
//从当前位置向前寻找,找到了
if(block[i]==PageOrder[currentPosition])
{
//找到了第i个页面出现的位置
if(!Page.contains(PageOrder[currentPosition]))
{
Page.add(PageOrder[currentPosition]);//保存页面
List.add(currentPosition); //保存最大索引
}
if(List.size()==block.length)
break A;
}
else continue;//没找到则继续往前
}
}
Integer [] saveIndex=new Integer[List.size()];
List.toArray(saveIndex);
int FirstInIndex=100;
for(int j=0;j<saveIndex.length;j++)
{
if(saveIndex[j]<FirstInIndex)
{
//找到最早出现的下标
FirstInIndex=saveIndex[j];
}
}
return FirstInIndex;//返回最早出现页面的下标
}
public boolean BlockIsFull(int block[])
{
//判断物理块是否满了，满则返回true，不满则返回false
for(int i=0;i<block.length;i++)
{
if(block[i]==-1)
return false;
else continue;
}
return true;
}
public void OPI(int PageOrder[],int block[])
{
//最佳置换算法
/*
* 最开始，先把物理块放满
* 在物理块放满之后，对物理块进行判断，判断当前页面是否在物理块中，在则不用置换，不在则从当前页面向后寻找，找到最后出现在物理块中的页面(即最大数组下标)
* 找到后，将其替换掉(替换的同时计置换的次数),进行下一轮判断
* */
int [][]LackPageIndex=new int [PageOrder.length][2];//保存每一次缺页索引以及插入的页面
int [][]PagePrint=new int [PageOrder.length] []; //保存每一次缺页记录
int []blockCopy=new int [block.length];
int LackPage=0; //缺页数
boolean existence; //用来标记页面是否存在于物理块中
for(int i=0;i<PagePrint.length;i++)
{
//开放内存空间
PagePrint[i]=new int [block.length];
}
for(int i=0;i<LackPageIndex.length;i++)
{
//开放内存空间
LackPageIndex[i]=new int [2];
}
for(int currentPosition=0;currentPosition<PageOrder.length;currentPosition++)
{
existence=false;
for(int j=0;j<block.length;j++)
{
if(block[j]==PageOrder[currentPosition])
{
//当前页面存在物理块中
existence=true;
break ;
}
else continue;
}
if(existence)
{
continue;
}
if(!existence)
{
//当前页面不存在物理块中：1.物理块没满，直接加入；2.物理快满了，从当前位置向前找，筛选出最先开始在物理块中出现的页面
if(BlockIsFull(block))
{
//物理块满了
int firstIn=FindLastIn(block,currentPosition,PageOrder);//找出最迟在物理快中出现的页面下标
int pagePosition=ReplacePage(block,PageOrder[firstIn]);//页面在物理块中的位置
block[pagePosition]=PageOrder[currentPosition]; //用当前页面替换旧的页面
blockCopy=Arrays.copyOf(block, block.length);//拷贝当前缺页数组
PagePrint[currentPosition]=blockCopy; //保存次缺页记录，后续打印
LackPageIndex[currentPosition][0]=currentPosition;//0下标保存每一次缺页索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下标保存插入的页面
LackPage++;//缺页数++
continue;
}
else
{
//物理块没满
for(int k=0;k<block.length;k++)
{
if(block[k]==-1)
{
block[k]=PageOrder[currentPosition];//将页面放入物理块中
blockCopy=Arrays.copyOf(block, block.length);//拷贝当前缺页数组
PagePrint[currentPosition]=blockCopy; //保存第(i+1)次缺页记录，后续打印
LackPageIndex[currentPosition][0]=currentPosition;//0下标保存每一次缺页索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下标保存插入的页面
LackPage++;//缺页数++
break;//下一个页面
}
}
}
}
}
double LackPagePercent=((double)LackPage/(double)PageOrder.length);
System.out.println("OPI算法缺页率，缺页次数，缺页情况如下");
System.out.println("缺页率为"+LackPagePercent*100+"%"+" ;"+"缺页次数为"+LackPage);
Print(PageOrder,PagePrint);
}
public int FindLastIn(int block[],int currentPosition,int[]PageOrder)
{
//找到这三个页面出现的三个最大下标
//从当前位置向后找，找到在物理块中最迟出现的页面,返回最迟出现在物理快中页面的索引
int FindIndex=currentPosition;
LinkedList<Integer> List=new LinkedList<Integer>();
LinkedList<Integer> Page=new LinkedList<Integer>();
A:for(;currentPosition<PageOrder.length;currentPosition++)
{
for(int i=0;i<block.length;i++)
{
//从当前位置向后寻找,找到了
if(block[i]==PageOrder[currentPosition])
{
//找到了第i个页面出现的位置 如果页面不存在，保存页面，保存索引，如果页面已存在，则不保存索引
if(!Page.contains(PageOrder[currentPosition]))
{
Page.add(PageOrder[currentPosition]);//保存页面
List.add(currentPosition); //保存最大索引
}
if(List.size()==block.length)
break A;
}
else continue;//没找到则继续往后
}
}
boolean existence=false;
int minIndex=PageOrder.length;
if(currentPosition==PageOrder.length)
{
//页面序列找到头了,有一个,或多个页面没有找到；
//直接返回该页面的下标
for(int i=0;i<block.length;i++)
{
if(Page.contains(block[i]))//筛选出没有找到的页面
continue;
else
{
//返回该页面的下标
if(block.length-Page.size()==1)
{
//有一个页面没找到
for(;0<FindIndex;FindIndex--)
{
if(block[i]==PageOrder[FindIndex])
return FindIndex;
}
}
if(block.length-Page.size()>1)
{
//有多个页面未找到,返回页面最小的下标
//找到找不到的页面，比较两个页面所在物理块的下标，选择下标最小的页面返回，返回物理快中出现的页面最小下标
existence=true;//确实存在多个页面未找到
int FindIndexCopy=FindIndex;
for(;0<FindIndex;FindIndex--)
{
if(block[i]==PageOrder[FindIndex])
{
if(FindIndex<minIndex)
minIndex=FindIndex;
}
}
FindIndex=FindIndexCopy;//重置
}
}
}
}
if(existence==true)
return minIndex;
Integer [] saveIndex=new Integer[List.size()];
List.toArray(saveIndex);
int FirstLastIndex=0;
for(int j=0;j<saveIndex.length;j++)
{
if(saveIndex[j]>FirstLastIndex)
{
//找到最迟出现的下标
FirstLastIndex=saveIndex[j];
}
}
return FirstLastIndex;//返回最迟出现页面的下标
}
public void LRU(int PageOrder[],int block[])
{
//最久未使用算法
/*
* 最开始，先把物理块放满
* 在物理块放满之后，对物理块进行判断，判断当前页面是否在物理块中，在则不用置换，不在则找到最早出现在物理块中的页面(最小数组下标)
* 找到后，将其替换掉(替换的同时计置换的次数),进行下一轮判断
* */
int [][]LackPageIndex=new int [PageOrder.length][2];//保存每一次缺页索引以及插入的页面
int [][]PagePrint=new int [PageOrder.length] []; //保存每一次缺页记录
int []blockCopy=new int [block.length];
int LackPage=0; //缺页数
boolean existence; //用来标记页面是否存在于物理块中
for(int i=0;i<PagePrint.length;i++)
{
//开放内存空间
PagePrint[i]=new int [block.length];
}
for(int i=0;i<LackPageIndex.length;i++)
{
//开放内存空间
LackPageIndex[i]=new int [2];
}
for(int currentPosition=0;currentPosition<PageOrder.length;currentPosition++)
{
existence=false;
for(int j=0;j<block.length;j++)
{
if(block[j]==PageOrder[currentPosition])
{
//当前页面存在物理块中
existence=true;
break;
}
else continue;
}
if(existence)
{
continue;
}
if(!existence)
{
//当前页面不存在物理块中：1.物理块没满，直接加入；2.物理快满了，从当前位置向前找，筛选出最先开始在物理块中出现的页面
if(BlockIsFull(block))
{
//物理块满了
int firstIn=FindFirstIn(block,currentPosition,PageOrder);//找出最开始在物理快中出现的页面下标
int pagePosition=ReplacePage(block,PageOrder[firstIn]);//页面在物理块中的位置
block[pagePosition]=PageOrder[currentPosition]; //用当前页面替换旧的页面
blockCopy=Arrays.copyOf(block, block.length);//拷贝当前缺页数组
PagePrint[currentPosition]=blockCopy; //保存次缺页记录，后续打印
LackPageIndex[currentPosition][0]=currentPosition;//0下标保存每一次缺页索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下标保存插入的页面
LackPage++;//缺页数++
continue;
}
else
{
//物理块没满
for(int k=0;k<block.length;k++)
{
if(block[k]==-1)
{
block[k]=PageOrder[currentPosition];//将页面放入物理块中
blockCopy=Arrays.copyOf(block, block.length);//拷贝当前缺页数组
PagePrint[currentPosition]=blockCopy; //保存次缺页记录，后续打印
LackPageIndex[currentPosition][0]=currentPosition;//0下标保存每一次缺页索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下标保存插入的页面
LackPage++;//缺页数++
break;//下一个页面
}
}
}
}
}
double LackPagePercent=((double)LackPage/(double)PageOrder.length);
System.out.println("LRU算法缺页率，缺页次数，缺页情况如下");
System.out.println("缺页率为"+LackPagePercent*100+"%"+";"+"缺页次数为"+LackPage);
Print(PageOrder,PagePrint);
}
public void Print(int[]PageOrder,int [][]PagePrint)
{
System.out.println("缺页情况如下：———————————————————————————————————————————————————————————————————————————————————————");
for(int i=0;i<PageOrder.length;i++)
System.out.print(PageOrder[i]+" ");
System.out.println();
for(int i=0;i<PagePrint[i].length;i++)
{
for(int j=0;j<PagePrint.length;j++)
{
String zere="00";
String isZero="";
for(int n=0;n<PagePrint[j].length;n++)
isZero=isZero+PagePrint[j][n];
if(PagePrint[j][i]==-1)
{
System.out.print(" ");
continue;
}
if(isZero.trim().contains(zere))
{
System.out.print(" ");
continue;
}
System.out.print(" "+PagePrint[j][i]+" ");
}
System.out.println();
}
}
}
public class Experiment_5 {
//物理块为3 OPI算法： 45% 9次
//物理块为3 FIFO算法： 75% 15次
//物理块为3 LRU算法： 60% 12次
//物理块为4 OPI算法： 40% 8次
//物理块为4 FIFO算法： 50% 10次
//物理块为4 LRU算法： 40% 8次
public static void main(String[] args)
{
Scanner Input=new Scanner(System.in);
System.out.println("输入页面访问序列：(以逗号隔开)");
String GetpageOrder=Input.nextLine();//7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
System.out.println("请输入物理块大小：");
int blockSize=Input.nextInt();
Input.close();
String []pageOrder=GetpageOrder.split(",");
int []PageOrder=new int [pageOrder.length];
for(int i=0;i<PageOrder.length;i++)
PageOrder[i]=Integer.parseInt(pageOrder[i]);
int block[]=new int [blockSize];
for(int i=0;i<block.length;i++)
block[i]=-1;
//7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7
// int PageOrder[]= {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};//页面访问序列
//int block[]= {-1,-1,-1};//物理块
// int block[]= {-1,-1,-1,-1};//物理块
//new PageReplacementAlgorithm().OPI(PageOrder, block);
//new PageReplacementAlgorithm().FIFO(PageOrder, block);
new PageReplacementAlgorithm().LRU(PageOrder, block);
}
}
网友评论