#include<stdio.h>
#include<string.h>
#include<iostream.h>
/************************************************************
页面调度算法主要有：FIFO，最近最少使用调度算法（LRU），最近最不常用调度算法（LFU），最佳算法（OPT）
此程序包括 :FIFO ，最近最少使用调度算法（ LRU ），最近最不常用调度算法（ LFU ） 第二次机会算法
************************************************************/
const int MAXSIZE=1000;//定义最大页面数
const int MAXQUEUE=3;//定义页框数
typedef struct node
{
int loaded;
int hit;
} page;
page pages[MAXQUEUE]; //定义页框表
int queue[MAXSIZE];
int quantity;
//初始化结构函数
void initial()
{
int i;
for ( i=0; i<MAXQUEUE; i++ )
{
pages[i].loaded=-1;
pages[i].hit=0;
}
for ( i=0; i<MAXSIZE; i++ )
{
queue[i]=-1;
}
quantity=0;
}
//初始化页框函数
void init()
{
int i;
for ( i=0; i<MAXQUEUE; i++ )
{
pages[i].loaded=-1;
pages[i].hit=0;
}
}
//读入页面流
void readData()
{
FILE *fp;
char fname[20];
int i;
cout<<"请输入页面流文件名:";
cin>>fname;
if ( ( fp=fopen ( fname,"r" ) ) ==NULL )
{
cout<<"错误,文件打不开,请检查文件名";
}
else
{
while ( !feof ( fp ) )
{
fscanf ( fp,"%d ",&queue[quantity] );
quantity++;
}
}
cout<<"读入的页面流:";
for ( i=0; i<quantity; i++ )
{
cout<<queue[i]<<" ";
}
}
//FIFO调度算法
void FIFO()
{
int i,j,p,flag;
int absence=0;
p=0;
cout<<endl<<"----------------------------------------------------"<<endl;
cout<<"FIFO调度算法页面调出流:";
for ( i=0; i<quantity; i++ )
{
flag=0;
for ( j=0; j<MAXQUEUE; j++ )
{
if ( pages[j].loaded==queue[i] )
{
flag=1;
}
}
if ( flag==0 )
{
if ( absence>=MAXQUEUE )
{
cout<<pages[p].loaded<<" ";
}
pages[p].loaded=queue[i];
p= ( p+1 ) %MAXQUEUE;
absence++;
}
}
absence-=MAXQUEUE;
cout<<endl<<"总缺页数:"<<absence<<endl;
}
//最近最少使用调度算法（LRU）
void LRU()
{
int absence=0;
int i,j;
int flag;
for ( i=0; i<MAXQUEUE; i++ )
{
pages[i].loaded=queue[i];
}
cout<<endl<<"----------------------------------------------------"<<endl;
cout<<"最近最少使用调度算法(LRU)页面流:";
for ( i=MAXQUEUE; i<quantity; i++ )
{
flag=-1;
for ( j=0; j<MAXQUEUE; j++ )
{
if ( queue[i]==pages[j].loaded )
{
flag=j;
}
}
//CAUTION pages[0]是队列头
if ( flag==-1 )
{
//缺页处理
cout<<pages[0].loaded<<" ";
for ( j=0; j<MAXQUEUE-1; j++ )
{
pages[j]=pages[j+1];
}
pages[MAXQUEUE-1].loaded=queue[i];
absence++;
}
else
{
//页面已载入
pages[quantity]=pages[flag];
for ( j=flag; j<MAXQUEUE-1; j++ )
{
pages[j]=pages[j+1];
}
pages[MAXQUEUE-1]=pages[quantity];
}
}
cout<<endl<<"总缺页数:"<<absence<<endl;
}
//最近最不常用调度算法(LFU)
void LFU()
{
int i,j,p;
int absence=0;
int flag;
for ( i=0; i<MAXQUEUE; i++ )
{
pages[i].loaded=queue[i];
}
cout<<endl<<"----------------------------------------------------"<<endl;
cout<<"最近最不常用调度算法(LFU)页面流:";
for ( i=MAXQUEUE; i<quantity; i++ )
{
flag=-1;
for ( j=0; j<MAXQUEUE; j++ )
{
if ( pages[j].loaded==queue[i] )
{
flag=1;
pages[j].hit++;
}
}
if ( flag==-1 )
{
//缺页中断
p=0;
for ( j=0; j<MAXQUEUE; j++ )
{
if ( pages[j].hit<pages[p].hit )
{
p=j;
}
}
cout<<pages[p].loaded<<" ";
pages[p].loaded=queue[i];
for ( j=0; j<MAXQUEUE; j++ )
{
pages[j].hit=0;
}
absence++;
}
}
cout<<endl<<"总缺页数:"<<absence<<endl;
}
//第二次机会算法
void second()
{
int i,j,t;
int absence=0;
int flag,temp;
for ( i=0; i<MAXQUEUE; i++ )
{
pages[i].loaded=queue[i];
}
cout<<endl<<"----------------------------------------------------"<<endl;
cout<<"第二次机会算法页面流:";
for ( i=MAXQUEUE; i<quantity; i++ )
{
flag=-1;
for ( j=0; j<MAXQUEUE; j++ )
{
if ( pages[j].loaded==queue[i] )
{
flag=1;
pages[j].hit=1;
}
}
if ( flag==-1 )
{
//缺页处理
t=0;
while ( t==0 )
{
if ( pages[0].hit==0 )
{
cout<<pages[0].loaded<<" ";
for ( j=0; j<MAXQUEUE-1; j++ )
{
pages[j]=pages[j+1];
}
pages[MAXQUEUE-1].loaded=queue[i];
pages[MAXQUEUE-1].hit=0;
t=1;
}
else
{
temp=pages[0].loaded;
for ( j=0; j<MAXQUEUE-1; j++ )
{
pages[j]=pages[j+1];
}
pages[MAXQUEUE-1].loaded=temp;
pages[MAXQUEUE-1].hit=0;
}
}
absence++;
}
}
cout<<endl<<"总缺页数:"<<absence<<endl;
}
//显示版权信息函数
void version()
{
cout<<endl<<endl;
cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;
cout<<" ┃ 虚拟存储管理器的页面调度 ┃"<<endl;
cout<<" ┠───────────────────────┨"<<endl;
cout<<" ┃ (c)All Right Reserved Neo ┃"<<endl;
cout<<" ┃ sony006@163.com ┃"<<endl;
cout<<" ┃ version 2004 build 1122 ┃"<<endl;
cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;
cout<<endl<<endl;
}
void main()
{
version();
initial();
readData();
FIFO();
init();
LRU();
init();
LFU();
init();
second();
}