#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();

}