1.设计内容:
编制页面置换算法的模拟程序。
2.设计要求
1).用随机数方法产生页面走向,页面走向长度为L(15<=L<=20),L由控制台输入。
2).根据页面走向,分别采用Optinal、FIFO、LRU算法进行页面置换,统计缺页率。
3).假定可用内存块为m(3<=m<=5),m由控制台输入,初始时,作业页面都不在内存。
#include<iostream.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#define L 20//页面走向最大长度为20
int M; //M为物理块数
struct Physic //定义一个结构体
{
int num,time;
};
Input(int *m,Physic p[L])
{
cout<<"请输入实际页面走向长度L(15<=L<=20):";
do
{
cin>>*m;
if(*m>20||*m<15)cout<<"错误!请重新输入L: ";
else break;
}while(1);
int i,j;
j=time(NULL); //取时钟时间
srand(j); //以时钟时间x为种子,初始化随机数发生器
cout<<"输出随机数: ";
for(i=0;i<*m;i++)
{
p[i].num=rand( )%10+1;
p[i].time=0;
cout<<p[i].num<<" ";
}
cout<<endl;
return *m;//返回页面长度
}
void print(Physic *page1)//打印当前的页面
{
Physic *page=new Physic[M];
page=page1;
for(int i=0;i<M;i++)
cout<<page[i].num<<" ";
cout<<endl;
}
int Search(int num,Physic *page1 )//查看当前要装入的页面num是否已经在内存中
{
Physic *page=new Physic[M];
page=page1;
for(int i=0;i<M;i++)
if(num==page[i].num)return i;//num已在内存中,返回与其相等的块号
return -1;
}
int Max(Physic *page1)
{
Physic *page=new Physic[M];
page=page1;
int t=page[0].time,i=0;
while(i<M) //找出离现在时间最长的页面
{
if(t<page[i].time)t=page[i].time;//每次把内存中时间小的页面的time赋给t
i++;
}
for( i=0;i<M;i++)
if(t==page[i].time)return i;//返回time最小的块号
return -1;
}
int Count(Physic *page1,int i,int t,Physic p[L])//记录当前物理块中页面离下一次使用间隔长度
{
Physic *page=new Physic[M];
page=page1;
int count=0; //初始化为0
for(int j=i;j<L;j++)
{
if(page[t].num==p[j].num )break;
else count++;//count++直到在页面走向中找到与当前块相同的页面
}
return count;//返回count的值
}
int main()
{
cout<<endl;
cout<<" *****页面置换算法模拟程序!***** "<<endl;
cout<<endl;
int c;
int m=0,t=0;
float n=0;
Physic p[L];
cout<<endl;
m=Input(&m,p);//调用Input函数,取得页面走向长度m
cout<<"请输入可用内存页面数M(3<=M<5): ";
do
{
cin>>M;
if(M>5||M<3)
cout<<"错误!请重新输入M: ";
else break;
}while(1);
Physic *page=new Physic[M];
do{
for(int i=0;i<M;i++) //初试化内存块的基本情况
{
page[i].num=0;
page[i].time=M-1-i;
}
i=0;
cout<<"请按1.2.3选择算法!"<<endl;
cout<<"1:FIFO页面置换"<<endl;
cout<<"2:LRU页面置换"<<endl;
cout<<"3:OPT页面置换"<<endl;
cout<<"按其它键结束程序;"<<endl;
cin>>c;
if(c==1) //选择FIFO页面置换
{
n=0;
cout<<" <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"<<endl;
cout<<" FIFO算法页面置换情况如下: "<<endl;
cout<<" >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;
while(i<m)
{
if(Search(p[i].num,page)>=0)//找到相同的页面,不缺页
{ cout<<p[i].num<<" ";//打印要装入的页面
cout<<"不缺页"<<endl;
i++;
}
else
{
if(t==M)t=0;
else
{
n++;//缺页数加一
page[t].num=p[i].num;
cout<<p[i].num<<" ";
print(page);//打印内存块
t++;
i++;
}
}
}
cout<<"缺页次数:"<<n<<" 缺页率:"<<n/m<<endl;
}
if(c==2)//选择LRU页面置换
{
n=0;
cout<<" <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<"<<endl;
cout<<" LRU算法页面置换情况如下: "<<endl;
cout<<" >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>"<<endl;
while(i<m)
{
int a;
t=Search(p[i].num,page);
if(t>=0)//t>=0说明当前要装入的页面在内存中
{
page[t].time=0;//把第t个内存块的time置0
for(a=0;a<M;a++)
if(a!=t)page[a].time++;//其它全部自增1
cout<<p[i].num<<" ";
cout<<"不缺页"<<endl;
}
else //当前页面没在内存中
{
n++;
t=Max(page);//寻找最近最久未使用的页面,即time最大的页面换出
page[t].num=p[i].num;