//实验3-请求调页
#include<iomanip>
#include<stdlib.h>
#include<time.h>
#include<iostream>
using namespace std;
double cnt1,cnt2,cnt3;
double r1,r2,r3;
int a[4][2],b[320][2],c[320];
int f;
int opt()
{//opt算法
cnt1=0;
f=0;
int max[2];
for(int t=0;t<4;t++)
{
a[t][1]=1;
}
for(int i=0;i<320;i++)
{
for(int t=0;t<4;t++)
{
if(a[t][1]<=0)
{
for(int m=i+1;m<320;m++)
{
if(a[t][0]==b[m][1])
{
a[t][1]=m-i;
break;
}
}
}
}
if(f<4)
{
int l=0;
if(f>0)
{
for(int j=0;j<f;j++)
{
if(a[j][0]==b[i][1])
{//内存中有该页
l++;
a[j][1]=0;
break;
}
}
}
if(l==0)
{
a[f][0]=b[i][1];
for(int j=i+1;j<320;j++)
{
if(b[j][1]==b[i][1])
{
a[f][1]=j-i;
break;
}
}
f++;
}
}
else
{
int e=0;
for(int j=0;j<4;j++)
{
if(a[j][0]==b[i][1])
{//内存中有该页
e++;
break;
}
}
if(e==0)
{
cnt1++;
cout<<"\nOPT第"<<cnt1<<"次缺页..."<<endl;
cout<<"当前缺页的页号为："<<b[i][1]<<endl;
cout<<"当前内存的情况为："<<endl;
for(int j=0;j<4;j++)
{
cout<<setw(5)<<a[j][0];
}
cout<<endl;
for(int j=0;j<4;j++)
{
cout<<setw(5)<<a[j][1];
}
cout<<endl;
max[1]=-10;
for(int j=0;j<4;j++)
{
if(a[j][1]<0)
{
max[1]=a[j][1];
max[0]=j;
break;
}
else
{
if(a[j][1]>=max[1])
{
max[1]=a[j][1];
max[0]=j;
}
}
}
a[max[0]][0]=b[i][1];
for(int j=i+1;j<320;j++)
{
if(b[j][1]==b[i][1])
{
a[max[0]][1]=j-i;
break;
}
}
}
}
for(int i=0;i<4;i++)
{
a[i][1]--;
}
}
return 0;
}
int fifo()
{//先进先出FIFO算法
cnt2=0;
f=0;
int max[2];
for(int i=0;i<320;i++)
{
if(f<4)
{
int l=0;
if(f>0)
{
for(int j=0;j<f;j++)
{
if(a[j][0]==b[i][1])
{//内存中有该页
l++;
break;
}
}
}
if(l==0)
{
a[f][0]=b[i][1];
a[f][1]=0;
f++;
}
}
else
{
int e=0;
for(int j=0;j<4;j++)
{
if(a[j][0]==b[i][1])
{//内存中有该页
e++;
break;
}
}
if(e==0)
{
cnt2++;
max[1]=0;
cout<<"\nFIFO第"<<cnt2<<"次缺页..."<<endl;
cout<<"当前缺页的页号为："<<b[i][1]<<endl;
cout<<"当前内存的情况为："<<endl;
for(int j=0;j<4;j++)
{
cout<<setw(5)<<a[j][0];
}
cout<<endl;
for(int j=0;j<4;j++)
{
cout<<setw(5)<<a[j][1];
}
cout<<endl;
for(int j=0;j<4;j++)
{
if(a[j][1]>=max[1])
{
max[1]=a[j][1];
max[0]=j;
}
}
a[max[0]][0]=b[i][1];
a[max[0]][1]=0;
}
}
for(int i=0;i<4;i++)
{
a[i][1]++;
}
}
return 0;
}
int lru()
{//最近最久未使用LRU算法
cnt3=0;
f=0;
int max[2];
for(int i=0;i<320;i++)
{
if(f<4)
{
int l=0;
if(f>0)
{
for(int j=0;j<f;j++)
{
if(a[j][0]==b[i][1])
{//内存中有该页
l++;
a[j][1]=0;
break;
}
}
}
if(l==0)
{
a[f][0]=b[i][1];
a[f][1]=0;
f++;
}
}
else
{
int e=0;
for(int j=0;j<4;j++)
{
if(a[j][0]==b[i][1])
{//内存中有该页
e++;
a[j][1]=0;
break;
}
}
if(e==0)
{
cnt3++;
max[1]=0;
cout<<"\nLRU第"<<cnt3<<"次缺页..."<<endl;
cout<<"当前缺页的页号为："<<b[i][1]<<endl;
cout<<"当前内存的情况为："<<endl;
for(int j=0;j<4;j++)
{
cout<<setw(5)<<a[j][0];
}
cout<<endl;
for(int j=0;j<4;j++)
{
cout<<setw(5)<<a[j][1];
}
cout<<endl;
for(int j=0;j<4;j++)
{
if(a[j][1]>=max[1])
{
max[1]=a[j][1];
max[0]=j;
}
}
a[max[0]][0]=b[i][1];
a[max[0]][1]=0;
}
}
for(int i=0;i<4;i++)
{
a[i][1]++;
}
}
return 0;
}
void suijishu()
{//产生随机数
cout<<"输入一个随机数: ";
for(int i=0;i<320;i++)
{
c[i]=0;
}
int m,m1;
int count;
cin>>m;
b[0][0]=m;
b[1][0]=m+1;
c[m]=1;
c[m+1]=1;
srand(time(0));
for(int i=2;i<320;i=i+4)
{
int m1=rand()%m;
count=0;
while(c[m1]==1||c[m1+1]==1)
{
m1=rand()%m;
count++;
if((c[m1]==0||c[m1+1]==0)&&count>=50)
{
break;
}
}
b[i][0]=m1;
b[i+1][0]=m1+1;
c[m1]=1;
c[m1+1]=1;
int m=rand()%(318-m1)+m1+2;
count=0;
while(c[m]==1||c[m+1]==1)
{
m=rand()%(318-m1)+m1+2;
count++;
if((c[m]==0||c[m+1]==0)&&count>=50)
{
break;
}
}
b[i+2][0]=m;
b[i+3][0]=m+1;
c[m]=1;
c[m+1]=1;
}
int hh=0;
for(int i=0;i<320;i++)
{
if(c[i]==1)
hh++;
}
cout<<"所覆盖的指令条数: "<<hh<<"\n\n";
}
int main()
{
suijishu();
for(int i=0;i<320;i++)
{
b[i][1]=b[i][0]/10;
}
cout<<"********************************************* OPT"<<endl;
opt();
cout<<"********************************************* FIFO"<<endl;
fifo();
cout<<"********************************************* LRU"<<endl;
lru();
cout<<"\n\npage default rate..."<<endl;
r1=cnt1/320*100;
cout<<"OPT ："<<r1<<"%"<<endl;
r2=cnt2/320*100;
cout<<"FIFO："<<r2<<"%"<<endl;
r3=cnt3/320*100;
cout<<"LRU ："<<r3<<"%"<<endl;
return 0;
}
转载：https://blog.csdn.net/enazh/article/details/100989004
查看评论