页面置换算法先进先出java_页面替换算法（FCFS，LRU,OPT三种）
import java.util.Scanner;
import java.util.Arrays;
import java.util.LinkedList;
class PageReplacementAlgorithm
{
PageReplacementAlgorithm(){}
public void FIFO(int? PageOrder[],int block[])
{
//先進(jìn)先出算法
/*
*最開(kāi)始，先把物理塊放滿
*在物理塊放滿之后，對(duì)物理塊進(jìn)行判斷，判斷當(dāng)前頁(yè)面是否在物理快中,在則不用置換，不在則從當(dāng)前頁(yè)面向序列前尋找，找到最先開(kāi)始在物理塊中出現(xiàn)的頁(yè)面(即最小數(shù)組下標(biāo))
*找到后,將其替換掉(替換的同時(shí)計(jì)置換的次數(shù)),進(jìn)行下一輪判斷
* */
int [][]LackPageIndex=new int [PageOrder.length][2];//保存每一次缺頁(yè)索引以及插入的頁(yè)面
int [][]PagePrint=new int [PageOrder.length] []; //保存每一次缺頁(yè)記錄
int []blockCopy=new int [block.length];
int LackPage=0; //缺頁(yè)數(shù)
boolean existence; //用來(lái)標(biāo)記頁(yè)面是否存在于物理塊中
for(int i=0;i
{
//開(kāi)放內(nèi)存空間
PagePrint[i]=new int [block.length];
}
for(int i=0;i
{
//開(kāi)放內(nèi)存空間
LackPageIndex[i]=new int [2];
}
for(int currentPosition=0;currentPosition
{
existence=false;
for(int j=0;j
{
if(block[j]==PageOrder[currentPosition])
{
//當(dāng)前頁(yè)面存在物理塊中
existence=true;
break;
}
else? continue;
}
if(existence)
{
continue;
}
if(!existence)
{
//當(dāng)前頁(yè)面不存在物理塊中：1.物理塊沒(méi)滿，直接加入；2.物理快滿了，從當(dāng)前位置向前找，篩選出最先開(kāi)始在物理塊中出現(xiàn)的頁(yè)面
if(BlockIsFull(block))
{
//物理塊滿了
int firstIn=FindFirstIn(block,currentPosition,LackPageIndex);//找出最開(kāi)始在物理快中出現(xiàn)的頁(yè)面下標(biāo)
int pagePosition=ReplacePage(block,PageOrder[firstIn]);//頁(yè)面在物理塊中的位置
block[pagePosition]=PageOrder[currentPosition];? //用當(dāng)前頁(yè)面替換舊的頁(yè)面
blockCopy=Arrays.copyOf(block, block.length);//拷貝當(dāng)前缺頁(yè)數(shù)組
PagePrint[currentPosition]=blockCopy; //保存次缺頁(yè)記錄，后續(xù)打印
LackPageIndex[currentPosition][0]=currentPosition;//0下標(biāo)保存每一次缺頁(yè)索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下標(biāo)保存插入的頁(yè)面
LackPage++;//缺頁(yè)數(shù)++
continue;
}
else
{
//物理塊沒(méi)滿
for(int k=0;k
{
if(block[k]==-1)
{
block[k]=PageOrder[currentPosition];//將頁(yè)面放入物理塊中
blockCopy=Arrays.copyOf(block, block.length); //拷貝當(dāng)前缺頁(yè)數(shù)組
PagePrint[currentPosition]=blockCopy; //保存第(i+1)次缺頁(yè)記錄，后續(xù)打印
LackPageIndex[currentPosition][0]=currentPosition;//0下標(biāo)保存每一次缺頁(yè)索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下標(biāo)保存插入的頁(yè)面
LackPage++;//缺頁(yè)數(shù)++
break;//下一個(gè)頁(yè)面
}
}
}
}
}
double LackPagePercent=((double)LackPage/(double)PageOrder.length);
System.out.println("FIFO算法缺頁(yè)率，缺頁(yè)次數(shù)，缺頁(yè)情況如下");
System.out.println("缺頁(yè)率為"+LackPagePercent*100+"%"+" ;"+"缺頁(yè)次數(shù)為"+LackPage);
Print(PageOrder,PagePrint);
}
public int ReplacePage(int block[] ,int page)
{
//找到頁(yè)面在物理塊中相應(yīng)的位置并返回
int i;
for( i=0;i
{
if(block[i]==page)
{
return i;
}
}
System.out.println("該頁(yè)面在物理塊中不存在：返回-1");
return -1;
}
public? int FindFirstIn(int block[],int currentPosition,int[][]LackPageIndex)
{
//找到這三個(gè)頁(yè)面出現(xiàn)的三個(gè)最小下標(biāo)
//從當(dāng)前位置向前找，找到在物理塊中最早出現(xiàn)的頁(yè)面,返回最早出現(xiàn)在物理快中頁(yè)面的索引
LinkedList List=new LinkedList();
A:for(;currentPosition>=0;currentPosition--)
{
for(int i=0;i
{
//從當(dāng)前位置向前尋找,找到了
if(block[i]==LackPageIndex[currentPosition][1]&&(LackPageIndex[currentPosition][0]!=0|| LackPageIndex[currentPosition][1]!=0))
{
//找到了第i個(gè)頁(yè)面出現(xiàn)的位置
List.add(LackPageIndex[currentPosition][0]); //保存最小索引
if(List.size()==block.length)
break A;
}
else continue;//沒(méi)找到則繼續(xù)往前
}
}
Integer [] saveIndex=new Integer[List.size()];
List.toArray(saveIndex);
int FirstInIndex=100;
for(int j=0;j
{
if(saveIndex[j]
{
//找到最早出現(xiàn)的下標(biāo)
FirstInIndex=saveIndex[j];
}
}
return FirstInIndex;//返回最早出現(xiàn)頁(yè)面的下標(biāo)
}
public? int FindFirstIn(int block[],int currentPosition,int[]PageOrder)
{
//找到這三個(gè)頁(yè)面出現(xiàn)的三個(gè)最小下標(biāo)
//從當(dāng)前位置向前找，找到在物理塊中最早出現(xiàn)的頁(yè)面,返回最早出現(xiàn)在物理快中頁(yè)面的索引
LinkedList List=new LinkedList();
LinkedList Page=new LinkedList();
A:for(;currentPosition>=0;currentPosition--)
{
for(int i=0;i
{
//從當(dāng)前位置向前尋找,找到了
if(block[i]==PageOrder[currentPosition])
{
//找到了第i個(gè)頁(yè)面出現(xiàn)的位置
if(!Page.contains(PageOrder[currentPosition]))
{
Page.add(PageOrder[currentPosition]);//保存頁(yè)面
List.add(currentPosition); //保存最大索引
}
if(List.size()==block.length)
break A;
}
else continue;//沒(méi)找到則繼續(xù)往前
}
}
Integer [] saveIndex=new Integer[List.size()];
List.toArray(saveIndex);
int FirstInIndex=100;
for(int j=0;j
{
if(saveIndex[j]
{
//找到最早出現(xiàn)的下標(biāo)
FirstInIndex=saveIndex[j];
}
}
return FirstInIndex;//返回最早出現(xiàn)頁(yè)面的下標(biāo)
}
public boolean BlockIsFull(int block[])
{
//判斷物理塊是否滿了，滿則返回true，不滿則返回false
for(int i=0;i
{
if(block[i]==-1)
return false;
else continue;
}
return true;
}
public void OPI(int? PageOrder[],int block[])
{
//最佳置換算法
/*
* 最開(kāi)始，先把物理塊放滿
* 在物理塊放滿之后，對(duì)物理塊進(jìn)行判斷，判斷當(dāng)前頁(yè)面是否在物理塊中，在則不用置換，不在則從當(dāng)前頁(yè)面向后尋找，找到最后出現(xiàn)在物理塊中的頁(yè)面(即最大數(shù)組下標(biāo))
* 找到后，將其替換掉(替換的同時(shí)計(jì)置換的次數(shù)),進(jìn)行下一輪判斷
* */
int [][]LackPageIndex=new int [PageOrder.length][2];//保存每一次缺頁(yè)索引以及插入的頁(yè)面
int [][]PagePrint=new int [PageOrder.length] []; //保存每一次缺頁(yè)記錄
int []blockCopy=new int [block.length];
int LackPage=0; //缺頁(yè)數(shù)
boolean existence; //用來(lái)標(biāo)記頁(yè)面是否存在于物理塊中
for(int i=0;i
{
//開(kāi)放內(nèi)存空間
PagePrint[i]=new int [block.length];
}
for(int i=0;i
{
//開(kāi)放內(nèi)存空間
LackPageIndex[i]=new int [2];
}
for(int currentPosition=0;currentPosition
{
existence=false;
for(int j=0;j
{
if(block[j]==PageOrder[currentPosition])
{
//當(dāng)前頁(yè)面存在物理塊中
existence=true;
break ;
}
else? continue;
}
if(existence)
{
continue;
}
if(!existence)
{
//當(dāng)前頁(yè)面不存在物理塊中：1.物理塊沒(méi)滿，直接加入；2.物理快滿了，從當(dāng)前位置向前找，篩選出最先開(kāi)始在物理塊中出現(xiàn)的頁(yè)面
if(BlockIsFull(block))
{
//物理塊滿了
int firstIn=FindLastIn(block,currentPosition,PageOrder);//找出最遲在物理快中出現(xiàn)的頁(yè)面下標(biāo)
int pagePosition=ReplacePage(block,PageOrder[firstIn]);//頁(yè)面在物理塊中的位置
block[pagePosition]=PageOrder[currentPosition];? //用當(dāng)前頁(yè)面替換舊的頁(yè)面
blockCopy=Arrays.copyOf(block, block.length);//拷貝當(dāng)前缺頁(yè)數(shù)組
PagePrint[currentPosition]=blockCopy; //保存次缺頁(yè)記錄，后續(xù)打印
LackPageIndex[currentPosition][0]=currentPosition;//0下標(biāo)保存每一次缺頁(yè)索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下標(biāo)保存插入的頁(yè)面
LackPage++;//缺頁(yè)數(shù)++
continue;
}
else
{
//物理塊沒(méi)滿
for(int k=0;k
{
if(block[k]==-1)
{
block[k]=PageOrder[currentPosition];//將頁(yè)面放入物理塊中
blockCopy=Arrays.copyOf(block, block.length);//拷貝當(dāng)前缺頁(yè)數(shù)組
PagePrint[currentPosition]=blockCopy; //保存第(i+1)次缺頁(yè)記錄，后續(xù)打印
LackPageIndex[currentPosition][0]=currentPosition;//0下標(biāo)保存每一次缺頁(yè)索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下標(biāo)保存插入的頁(yè)面
LackPage++;//缺頁(yè)數(shù)++
break;//下一個(gè)頁(yè)面
}
}
}
}
}
double LackPagePercent=((double)LackPage/(double)PageOrder.length);
System.out.println("OPI算法缺頁(yè)率，缺頁(yè)次數(shù)，缺頁(yè)情況如下");
System.out.println("缺頁(yè)率為"+LackPagePercent*100+"%"+" ;"+"缺頁(yè)次數(shù)為"+LackPage);
Print(PageOrder,PagePrint);
}
public int FindLastIn(int block[],int currentPosition,int[]PageOrder)
{
//找到這三個(gè)頁(yè)面出現(xiàn)的三個(gè)最大下標(biāo)
//從當(dāng)前位置向后找，找到在物理塊中最遲出現(xiàn)的頁(yè)面,返回最遲出現(xiàn)在物理快中頁(yè)面的索引
int FindIndex=currentPosition;
LinkedList List=new LinkedList();
LinkedList Page=new LinkedList();
A:for(;currentPosition
{
for(int i=0;i
{
//從當(dāng)前位置向后尋找,找到了
if(block[i]==PageOrder[currentPosition])
{
//找到了第i個(gè)頁(yè)面出現(xiàn)的位置? ? ? ? ? 如果頁(yè)面不存在，保存頁(yè)面，保存索引，如果頁(yè)面已存在，則不保存索引
if(!Page.contains(PageOrder[currentPosition]))
{
Page.add(PageOrder[currentPosition]);//保存頁(yè)面
List.add(currentPosition); //保存最大索引
}
if(List.size()==block.length)
break A;
}
else continue;//沒(méi)找到則繼續(xù)往后
}
}
boolean existence=false;
int minIndex=PageOrder.length;
if(currentPosition==PageOrder.length)
{
//頁(yè)面序列找到頭了,有一個(gè),或多個(gè)頁(yè)面沒(méi)有找到；
//直接返回該頁(yè)面的下標(biāo)
for(int i=0;i
{
if(Page.contains(block[i]))//篩選出沒(méi)有找到的頁(yè)面
continue;
else
{
//返回該頁(yè)面的下標(biāo)
if(block.length-Page.size()==1)
{
//有一個(gè)頁(yè)面沒(méi)找到
for(;0
{
if(block[i]==PageOrder[FindIndex])
return FindIndex;
}
}
if(block.length-Page.size()>1)
{
//有多個(gè)頁(yè)面未找到,返回頁(yè)面最小的下標(biāo)
//找到找不到的頁(yè)面，比較兩個(gè)頁(yè)面所在物理塊的下標(biāo)，選擇下標(biāo)最小的頁(yè)面返回，返回物理快中出現(xiàn)的頁(yè)面最小下標(biāo)
existence=true;//確實(shí)存在多個(gè)頁(yè)面未找到
int FindIndexCopy=FindIndex;
for(;0
{
if(block[i]==PageOrder[FindIndex])
{
if(FindIndex
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
{
if(saveIndex[j]>FirstLastIndex)
{
//找到最遲出現(xiàn)的下標(biāo)
FirstLastIndex=saveIndex[j];
}
}
return FirstLastIndex;//返回最遲出現(xiàn)頁(yè)面的下標(biāo)
}
public void LRU(int? PageOrder[],int block[])
{
//最久未使用算法
/*
* 最開(kāi)始，先把物理塊放滿
* 在物理塊放滿之后，對(duì)物理塊進(jìn)行判斷，判斷當(dāng)前頁(yè)面是否在物理塊中，在則不用置換，不在則找到最早出現(xiàn)在物理塊中的頁(yè)面(最小數(shù)組下標(biāo))
* 找到后，將其替換掉(替換的同時(shí)計(jì)置換的次數(shù)),進(jìn)行下一輪判斷
* */
int [][]LackPageIndex=new int [PageOrder.length][2];//保存每一次缺頁(yè)索引以及插入的頁(yè)面
int [][]PagePrint=new int [PageOrder.length] []; //保存每一次缺頁(yè)記錄
int []blockCopy=new int [block.length];
int LackPage=0; //缺頁(yè)數(shù)
boolean existence; //用來(lái)標(biāo)記頁(yè)面是否存在于物理塊中
for(int i=0;i
{
//開(kāi)放內(nèi)存空間
PagePrint[i]=new int [block.length];
}
for(int i=0;i
{
//開(kāi)放內(nèi)存空間
LackPageIndex[i]=new int [2];
}
for(int currentPosition=0;currentPosition
{
existence=false;
for(int j=0;j
{
if(block[j]==PageOrder[currentPosition])
{
//當(dāng)前頁(yè)面存在物理塊中
existence=true;
break;
}
else? continue;
}
if(existence)
{
continue;
}
if(!existence)
{
//當(dāng)前頁(yè)面不存在物理塊中：1.物理塊沒(méi)滿，直接加入；2.物理快滿了，從當(dāng)前位置向前找，篩選出最先開(kāi)始在物理塊中出現(xiàn)的頁(yè)面
if(BlockIsFull(block))
{
//物理塊滿了
int firstIn=FindFirstIn(block,currentPosition,PageOrder);//找出最開(kāi)始在物理快中出現(xiàn)的頁(yè)面下標(biāo)
int pagePosition=ReplacePage(block,PageOrder[firstIn]);//頁(yè)面在物理塊中的位置
block[pagePosition]=PageOrder[currentPosition];? //用當(dāng)前頁(yè)面替換舊的頁(yè)面
blockCopy=Arrays.copyOf(block, block.length);//拷貝當(dāng)前缺頁(yè)數(shù)組
PagePrint[currentPosition]=blockCopy; //保存次缺頁(yè)記錄，后續(xù)打印
LackPageIndex[currentPosition][0]=currentPosition;//0下標(biāo)保存每一次缺頁(yè)索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下標(biāo)保存插入的頁(yè)面
LackPage++;//缺頁(yè)數(shù)++
continue;
}
else
{
//物理塊沒(méi)滿
for(int k=0;k
{
if(block[k]==-1)
{
block[k]=PageOrder[currentPosition];//將頁(yè)面放入物理塊中
blockCopy=Arrays.copyOf(block, block.length);//拷貝當(dāng)前缺頁(yè)數(shù)組
PagePrint[currentPosition]=blockCopy; //保存次缺頁(yè)記錄，后續(xù)打印
LackPageIndex[currentPosition][0]=currentPosition;//0下標(biāo)保存每一次缺頁(yè)索引
LackPageIndex[currentPosition][1]=PageOrder[currentPosition];//1下標(biāo)保存插入的頁(yè)面
LackPage++;//缺頁(yè)數(shù)++
break;//下一個(gè)頁(yè)面
}
}
}
}
}
double LackPagePercent=((double)LackPage/(double)PageOrder.length);
System.out.println("LRU算法缺頁(yè)率，缺頁(yè)次數(shù)，缺頁(yè)情況如下");
System.out.println("缺頁(yè)率為"+LackPagePercent*100+"%"+";"+"缺頁(yè)次數(shù)為"+LackPage);
Print(PageOrder,PagePrint);
}
public void Print(int[]PageOrder,int [][]PagePrint)
{
System.out.println("缺頁(yè)情況如下：———————————————————————————————————————————————————————————————————————————————————————");
for(int i=0;i
System.out.print(PageOrder[i]+"? ? ");
System.out.println();
for(int i=0;i
{
for(int j=0;j
{
String zere="00";
String isZero="";
for(int n=0;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("輸入頁(yè)面訪問(wèn)序列：(以逗號(hào)隔開(kāi))");
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("請(qǐng)輸入物理塊大小：");
int blockSize=Input.nextInt();
Input.close();
String []pageOrder=GetpageOrder.split(",");
int []PageOrder=new int [pageOrder.length];
for(int i=0;i
PageOrder[i]=Integer.parseInt(pageOrder[i]);
int block[]=new int [blockSize];
for(int i=0;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};//頁(yè)面訪問(wèn)序列
//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);
}
}
總結(jié)
以上是生活随笔為你收集整理的页面置换算法先进先出java_页面替换算法（FCFS，LRU,OPT三种）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： JAVA类思维_面向对象思维 Java中
- 下一篇： java.lang.illegalagr