操作系统 页面置换算法实现
程序员文章站
2024-03-18 12:04:40
...
操作系统 页面置换算法实现
import java.util.Scanner;
public class page_change {
final int M=3;
final int N=20;
class block
{
int iPageNum; //物理块里存储的页面号
int iBlockFlag; //在三种算法中用到的标记。例如在FIFO中为在内存中的时间
public block(int iPageNum, int iBlockFlag) {
this.iPageNum = iPageNum;
this.iBlockFlag = iBlockFlag;
}
public int getiPageNum() {
return iPageNum;
}
public void setiPageNum(int iPageNum) {
this.iPageNum = iPageNum;
}
public int getiBlockFlag() {
return iBlockFlag;
}
public void setiBlockFlag(int iBlockFlag) {
this.iBlockFlag = iBlockFlag;
}
};
//算法模拟移位寄存器原理
public void pageChange()
{
Scanner in=new Scanner(System.in);
block []myBlock=new block[M];
int []iPageString={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
//页面引用串
int []iTempPage =new int[N]; //临时页面引用串
int []flag=new int[N]; //缺页标记;1为缺页,0为不缺页,在统计缺页次数时用
int i;
boolean bExitFlag=true; //退出标记
char ch; //接收选择算法时传进来的值
while(bExitFlag)
{
System.out.println("请选择页面置换算法:");
System.out.println("f:FIFO置换算法 \to:OPT置换算法 \tl:LRU置换算法 \tx:退出置换算法程序.");
ch=(in.next()).charAt(0);
//初始化数据
if((ch=='f')||(ch=='o')||(ch=='l'))
{
for(i=0;i<N;i++)
{
iTempPage[i]=iPageString[i]; //初始化临时页面引用串
flag[i]=0; //初始化缺页标记为0,即不缺页
}
}
switch(ch)
{
case 'f':
System.out.println("FIFO置换算法的结果是:");
FIFO(iTempPage,flag,myBlock);
//用PageNum(flag)统计缺页次数
System.out.println("\n缺页次数为"+PageNum(flag));
break;
case 'o':
System.out.println("OPT置换算法的结果是:");
Optimal(iTempPage,flag,myBlock);
System.out.println("\n缺页次数为"+PageNum(flag));
break;
case 'l':
System.out.println("LRU置换算法的结果是:");
LRU(iTempPage,flag,myBlock);
System.out.println("\n缺页次数为"+PageNum(flag));
break;
case 'x':
System.out.println("退出置换算法。");
bExitFlag=false;
break;
default:
System.out.println("输入有误,请重新选择置换算法:");
}
}
}
//对数组中的数累加
int PageNum(int array[])
{
int num=0;
for(int j=0;j<N;j++)
num=num+array[j];
return num;
}
//定位函数,在最佳算法中用于定位;
//定位物理块中的某一个页面在引用串中还未访问串中页面的位置
int allocate(int iPage,int iLoc,int []iTempPage)
{
int i;
for(i=iLoc;i<N;i++)
{
if (iPage==iTempPage[i])
return i;
}
//永远不再访问的页面位置假定为N
return N;
}
//在LRU置换算法的时候使用
int reverse_allocate(int iPage,int iLoc,int []iTempPage)
{
int i;
for(i=iLoc;i>=0;i--)
{
if (iPage==iTempPage[i])
return i;
}
//永远不再访问的页面位置假定为0
return 0;
}
//找数组中最大值所在的下标,返回最大值在数组中的位置(下标)
int max_sign(block []array)
{
int j,loc;
int temp=array[0].iBlockFlag;
loc=0;
for(j=1;j<M;j++)
{
if (temp<array[j].iBlockFlag)
{
temp=array[j].iBlockFlag;
loc=j;
}
}
return loc;
}
int little_sign(block []array)
{
int j,loc;
int temp=array[0].iBlockFlag;
loc=0;
for(j=1;j<M;j++)
{
if (temp>array[j].iBlockFlag)
{
temp=array[j].iBlockFlag;
loc=j;
}
}
return loc;
}
//输出剩余的数据
//loc为页面引用串中
void output(int iPage,int flag,block []myBlock,int blockNum)
{
int j;
//如果缺页则输出缺页标志,否则不输出
if (flag==1)
System.out.print("\n "+flag);
else
System.out.println("");
System.out.print("\t "+iPage);
for(j=0;j<blockNum;j++)
System.out.print("\t "+myBlock[j].iPageNum);
}
//初始化物理块的内容,因任一种算法在物理块内容为空时,结果都一样的
//同时将目前物理块中的内容输出
void InitialBlock(int []iTempPage,int []flag,block []myBlock)
{
int i;
for(i=0;i<M;i++)
{
//初始化物理块的内容,因任一种算法在物理块内容为空时,结果都一样的
myBlock[i]=new block(iTempPage[i],(M-1)-i);
//myBlock[i].iBlockFlag的值:0为最后进来的,数越大表示进来的越早
//在最佳置换算法中则初始化此值没有意义
flag[i]=1; //此时为缺页
}
//输出
System.out.println("\n缺页\t引用串\t物理块1\t物理块2\t物理块3");
for(i=0;i<M;i++)
output(iTempPage[i],flag[i],myBlock,i+1);
}
//FIFO置换算法
void FIFO(int []iTempPage,int []flag,block []myBlock)
{
int i,j,k,loc;
boolean ExistFlag=false;
//初始化物理块的内容,因任一种算法在物理块内容为空时,结果都一样的
//同时将目前物理块中的内容输出
InitialBlock(iTempPage,flag,myBlock);
//从引用串中的第4个页面开始
for(i=3;i<N;i++)
{
ExistFlag=false;
for(j=0;j<M;j++)
{
//物理块中存在
if (myBlock[j].iPageNum==iTempPage[i])
{
//模拟移位寄存器
for(k=0;k<M;k++)
myBlock[k].iBlockFlag++;
ExistFlag=true;
flag[i]=0;
break;
}
}
//物理块中不存在
if (!ExistFlag)
{
//查找最先进来的页面,也就是block中iBlockFlag最大的物理块
loc=max_sign(myBlock);
myBlock[loc].iPageNum=iTempPage[i];
//置缺页标志
flag[i]=1;
//模拟移位寄存器
for(k=0;k<M;k++)
if (k!=loc)
myBlock[k].iBlockFlag++;
else
myBlock[k].iBlockFlag=0;
}
//输出
output(iTempPage[i],flag[i],myBlock,M);
}
System.out.println("");
}
//Optimal置换算法
void Optimal(int []iTempPage,int []flag,block []myBlock)
{
boolean ExistFlag=false;
//初始化
InitialBlock(iTempPage,flag,myBlock);
for(int i=3;i<N;i++)
{
ExistFlag=false;
for(int j=0;j<M;j++)
{
if(iTempPage[i]==myBlock[j].iPageNum)
{
ExistFlag=true;
flag[i]=0;
break;
}
}
if(!ExistFlag) //如果不存在的话
{
for(int j=0;j<M;j++)
{
myBlock[j].iBlockFlag=allocate(myBlock[j].iPageNum,i,iTempPage); //更新每个块的下标
}
int item=max_sign(myBlock);
myBlock[item].iPageNum=iTempPage[i]; //将得到的页面换入
flag[i]=1;
}
//输出
output(iTempPage[i],flag[i],myBlock,M);
}
}
//LRU置换算法
void LRU(int []iTempPage,int []flag,block []myBlock)
{
boolean ExistFlag=false;
//初始化
InitialBlock(iTempPage,flag,myBlock);
for(int i=3;i<N;i++)
{
ExistFlag=false;
for(int j=0;j<M;j++)
{
if(iTempPage[i]==myBlock[j].iPageNum)
{
ExistFlag=true;
flag[i]=0;
break;
}
}
if(!ExistFlag) //如果不存在的话
{
for(int j=0;j<M;j++)
{
myBlock[j].iBlockFlag=reverse_allocate(myBlock[j].iPageNum,i,iTempPage); //更新每个块的下标
}
int item=little_sign(myBlock);
myBlock[item].iPageNum=iTempPage[i]; //将得到的页面换入
flag[i]=1;
}
//输出
output(iTempPage[i],flag[i],myBlock,M);
}
}
public static void main(String[] args) {
new page_change().pageChange();
}
}