#include <iostream>
#include <time.h>
#include <stdlib.h>
#include <conio.h>
using namespace std;
typedef int QElemType;
int m=256,n=4;
typedef struct Qnode
{
QElemType data;
bool B;
struct Qnode *next;
}Qnode,*Queueptr;
typedef struct
{
Queueptr front;
Queueptr rear;
}LinkQueue;
void InitQueue(LinkQueue &Q)
{
Q.front=Q.rear=new Qnode;
if(!Q.front)
exit(0);
Q.front->next=NULL;
}
void EnQueue(LinkQueue &Q,QElemType e)
{
Queueptr p;
p=new Qnode;
if(!p)
exit(0);
p->data=e;
p->B=true;
p->next=NULL;
Q.rear->next=p;
Q.rear=p;
}
int DeQueue(LinkQueue &Q,QElemType &e)
{
Queueptr p;
if(Q.front==Q.rear)
return 0;
p=Q.front->next;
e=p->data;
Q.front->next=p->next;
if(Q.rear==p)
Q.rear=Q.front;
delete []p;
return 1;
}
int RandDEQueue(LinkQueue &Q,QElemType &d,QElemType e)
{
int t;
Queueptr p;
if(Q.front==Q.rear)
return 0;
p=Q.front->next;
t=rand()%n+1;
for(int i=1;i<t;i++)
p=p->next;
d=p->data;
p->data=e;
return 1;
}
int ClockDEQueue(LinkQueue &Q,QElemType &d,QElemType e)
{
if(Q.front==Q.rear)
return 0;
static Queueptr p=Q.front->next;
while(true)
{
if(p->B)
p->B=false;
else
{
p->B=true;
d=p->data;
p->data=e;
break;
}
if(p->next==NULL)
p=Q.front->next;
else
p=p->next;
}
return 1;
}
void VisitQueue(LinkQueue Q)
{
Queueptr p;
p=Q.front->next;
while(p)
{
cout<<p->data<<"\t";
p=p->next;
}
}
int CompareQueue(LinkQueue Q,int page)
{
Queueptr p;
p=Q.front->next;
while(p)
{
if(p->data==page)
return 1;
p=p->next;
}
return 0;
}
void FIFO(int *a,int n,int m)
{
LinkQueue Q;
int page,t=0,flag=0,x;
InitQueue(Q);
for(int i=1;i<=m;i++)
{
page=a[i];
t++;
if(t<=n)
{
EnQueue(Q,page);
cout<<a[i]<<"\t";
}
else
{
for(int j=1;j<=n;j++)
if(CompareQueue(Q,page))
{
t--;
flag=1;
break;
}
if(flag==0)
{
DeQueue(Q,x);
cout<<" :"<<x<<"被调出"<<page<<"被调进";
EnQueue(Q,page);
}
cout<<endl;
VisitQueue(Q);
}
flag=0;
}
cout<<endl<<"缺页率为："<<endl;
cout<<float(t)/float(m)<<endl;
}
void LRU(int *a,int n,int m)
{
LinkQueue Q;
int page,t=0,flag=0,x,e;
InitQueue(Q);
for(int i=1;i<=m;i++)
{
page=a[i];
t++;
if(t<=n)
{
EnQueue(Q,page);
cout<<a[i]<<"\t";
}
else
{
for(int j=1;j<=n;j++)
if(CompareQueue(Q,page))
{
t--;
DeQueue(Q,e);
EnQueue(Q,e);
flag=1;
break;
}
if(flag==0)
{
DeQueue(Q,x);
cout<<" :"<<x<<"被调出"<<page<<"被调入";
EnQueue(Q,page);
}
cout<<endl;
VisitQueue(Q);
}
flag=0;
}
cout<<endl<<"缺页率为："<<endl;
cout<<float(t)/float(m)<<endl;
}
void Rand(int *a,int n,int m)
{
LinkQueue Q;
int page,t=0,flag=0,x;
InitQueue(Q);
for(int i=1;i<=m;i++)
{
page=a[i];
t++;
if(t<=n)
{
EnQueue(Q,page);
cout<<a[i]<<"\t";
}
else
{
for(int j=1;j<=n;j++)
if(CompareQueue(Q,page))
{
t--;
flag=1;
break;
}
if(flag==0)
{
RandDEQueue(Q,x,page);
cout<<" :"<<x<<"被调出"<<page<<"被调入";
}
cout<<endl;
VisitQueue(Q);
}
flag=0;
}
cout<<endl<<"缺页率为："<<endl;
cout<<float(t)/float(m)<<endl;
}
void Clock(int *a,int n,int m)
{
LinkQueue Q;
int page,t=0,flag=0,x;
InitQueue(Q);
for(int i=1;i<=m;i++)
{
page=a[i];
t++;
if(t<=n)
{
EnQueue(Q,page);
cout<<a[i]<<"\t";
}
else
{
for(int j=1;j<=n;j++)
if(CompareQueue(Q,page))
{
t--;
flag=1;
break;
}
if(flag==0)
{
ClockDEQueue(Q,x,page);
cout<<" :"<<x<<"被调出"<<page<<"被调进";
}
cout<<endl;
VisitQueue(Q);
}
flag=0;
}
cout<<endl<<"缺页率为："<<endl;
cout<<float(t)/float(m)<<endl;
}
void XueZhe()
{
cout<<"******************************************************"<<endl;
cout<<" 1.先进先出 2.最近最久未使用"<<endl;
cout<<" 3.随机替换 4.时钟页面替换"<<endl;
cout<<" 5.退出"<<endl;
cout<<"******************************************************"<<endl;
}
void COUT(int *a,int n,int m)
{
cout<<"页面号引用串为:"<<endl;
for(int i=1;i<=m;i++)
{
cout<<a[i]<<"\t";
if(i%8==0)
cout<<endl;
}
}
int main()
{
srand((unsigned)time(NULL));
cout<<"进程占用内存空间共640K,页面大小是8K"<<endl;
cout<<"页面数： "<<m<<endl;
cout<<"内存容量空间数： "<<n<<endl;
int *a=new int[m+1];
for(int i=1;i<=m;i++)
a[i]=rand()%80+1;
int X;
while(true)
{
XueZhe();
cout<<"输入相对应的操作方法："<<endl;
cin>>X;
switch(X)
{
case 1:
system("cls");
COUT(a,n,m);
cout<<endl;
cout<<"先进先出页面替换的结果："<<endl;
FIFO(a,n,m);
break;
case 2:
system("cls");
COUT(a,n,m);
cout<<endl;
cout<<"最近最久未使用页面替换的结果："<<endl;
LRU(a,n,m);
break;
case 3:
system("cls");
COUT(a,n,m);
cout<<endl;
cout<<"随机页面替换的结果："<<endl;
Rand(a,n,m);
case 4:
system("cls");
COUT(a,n,m);
cout<<endl;
cout<<"时钟页面替换的结果："<<endl;
Clock(a,n,m);
cout<<endl;
}
if(X==5)
break;
}
delete []a;
return 0;
}
