#include<iostream.h>
#include<stdio.h>
#include<iomanip.h>
const int Max = 10; //最大块号
const int Size = 30; //最长页号
static int count=0; //缺页数
static int d=0; //自增数
void Init(int block[],int n) //存储块的初始化
{
int i;
for(i=0;i<n;i++)
{
block[i] = -1;
}
}
void creat(int page[],int m) //访问页面的字符串的输入函数
{
int i;
for(i=0;i<m;i++)
{
cin>>page[i];
}
}
void Out(int a[],int aa) //块或者页的输出
{
int i;
for(i=0;i<aa;i++)
cout<<setw(2)<<a[i];
cout<<endl;
}
/*判断块是否已满*/
int isFull(int block[],int n)
{
int index=0; //记录剩余块数
for(int i=0;i<n;i++)
{
if(block[i] == -1)
index++ ;
}
if(index>0)
return 0; //有剩余
else
return 1; //1代表块满了
}
/*查看块中是否存在这个页号*/
int exist(int block[],int page[],int n,int i)
{
for(int x=0;x<n;x++)
{ if(page[i]==block[x])
return x; //x 表示块中有这个页号 返回地址
}
return -1; //-1 表示块中没有这个页号
}
/*LRU中访问页进入存储块 （m是块的序列 i是即将进入块的序号）*/
void pushIn(int block[],int page[],int n,int i)
{
if(exist(block,page,n,i)==-1) //块中没有这个页号
{
count++;
cout<<"缺页产生"<<count<<"次"<<endl;
int k=page[i]; //保存写入当前的页号
if(isFull(block,n)==0) //块剩余的时候读入 page
{
//当插入页的数目不够n-1个时把数组初始位置置为-1，否则不变
for(int j=count;j>0;j--) //把新来的页放着第一位，原来的全部往后挪一位
block[j] =block[j-1];
block[0] = k;
}
else //块满了
{
for(int i=n-1;i>0;i--)
block[i]=block[i-1]; //把block[n-1]踢出 即低下最久未使用的
block[0]=k; //把page[i]写入块中 放在数组首位
}
}
else //块中存在这个页号 exist(block,page,n,i)!=0
{
cout<<"块中已经有这个页号了!"<<endl;
if(isFull(block,n)==0) //有剩余块的时候
{
int flag;
flag=block[exist(block,page,n,i)]; //保存当前的页号值
if(exist(block,page,n,i)>0)
{
for(int j=exist(block,page,n,i);j>1;j--)
block[j]=block[j-1];
block[1]=flag;
}
}
else //块中页面满了
{
int fflag;
fflag=block[exist(block,page,n,i)];
for(int k=exist(block,page,n,i);k>0;k--)
{
block[k]=block[k-1];
}
block[0]=fflag;
}
}
}
/*FIFO中访问页进入存储块 （m是块的序列 i是即将进入块的序号）*/
void isIn(int block[],int page[],int n,int i)
{
if(exist(block,page,n,i)==-1) //块中没有这个页号
{
count++;
cout<<"缺页产生"<<count<<"次"<<endl;
int k=page[i]; //保存写入当前的页号
if(isFull(block,n)==0) //块剩余的时候读入 page
{
block[d] = k;
d++;
}
else //块满了
{
for(int i=0;i<n;i++)
{
if(i<n-1)
{
block[i]=block[i+1]; //把block[0]踢出
}
else
block[i]=k; //把page[i]写入块中
}
}
}
else
cout<<"块中已经有这个页号了!"<<endl;
}
void FIFO(int page[],int block[],int m,int n) //页数为m页 块数为n块
{
cout<<"调用的页号总序列为:";
Out(page,m);
cout<<"块序列为:";
Out(block,n);
for(int i=0;i<m;i++)
{
cout<<"第"<<i+1<<"个页序列 "<<page[i]<<" 入块!";
isIn(block,page,n,i);
cout<<"块序列为:";
Out(block,n);
}
}
void LRU(int page[],int block[],int m,int n) //页数为m页 块数为n块
{
cout<<"调用的页号总序列为:";
Out(page,m);
cout<<"块序列为:";
Out(block,n);
for(int i=0;i<m;i++)
{
cout<<"第"<<i+1<<"个页序列 "<<page[i]<<" 入块!";
pushIn(block,page,n,i);
cout<<"块序列为:";
Out(block,n);
}
}
void main()
{
int m,n;
int block[Max],page[Size];
double rate1,rate2; //FIFO算法和LRU算法的缺页率
cout<<setw(40)<<"存储管理"<<endl;
cout<<"请输入内存块数m（m<=6）:";
while(1)
{
cin>>n;
if(n<0||n>6)
{
cout<<"输入错误!请重新输入!";
cout<<"请重新输入内存块数:";
}
else break;
}
Init(block,n);
cout<<"请输入总页面数m(m<=30):";
cin>>m;
cout<<endl;
cout<<"请输入页面号引用串:";
creat(page,m);
cout<<"算法过程如下："<<endl;
int choose;
cout<<"*********************************"<<endl;
cout<<"请选择序号 1：FIFO算法 2:LRU算法"<<endl;
cin>>choose;
switch(choose)
{
case 1:
cout<<setw(40)<<"这是FIFO算法!"<<endl;
FIFO(page,block,m,n);
rate1=((double)count)/((double)m);
cout<<"FIFO的缺页率为:"<<rate1<<endl;
break;
case 2:
cout<<setw(40)<<"这是LRU算法!"<<endl;
LRU(page,block,m,n);
rate2=((double)count)/((double)m);
cout<<"FIFO的缺页率为:"<<rate2<<endl;
break;
default:
break;
}
}
程序说明:
FIFO算法解析
利用定义两个数组：页号数组和存储块数组。
首先，查询页号在块中是否存在。
如果不存在，则入块，并判断块空和满的情况下分别将页号插入到块中。否则告知已经存在。
LRU算法解析
可利用一个特殊的数组来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从数组中移除，将它放入数组的首位。因此，数组的首位始终是最新被访问页面的编号，而数组的最后一位则是最近最久未使用的页面号。