页式管理器模拟程序.cpp

操作系统的几个实验

#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<fstream.h>
#include<stdio.h>


#define TRUE 1
#define FAlSE 0
#define INVALID -1
#define NULL 0

#define total_instruction 320
#define total_vp 32
#define clear_period 50

typedef struct
{
	int pn,pfn,counter,time;
}pl_type;
pl_type pl[32];
typedef struct pfc_struct
{
	int pn,pfn;
	struct pfc_struct *next;
}pfc_type;
pfc_type pfc[32],*freepf_head,*busypf_head,*busypf_tail;

int diseffect,a[total_instruction];
int page[total_instruction],offset[total_instruction];
int RandNum(int ,int );

void initalize();
void FIFO();
void LRU();
void OPT();

int   RandNum(int start,int end)//在start到end的区间里产生随机数
{
	int number=-1;
	if(start==0)
	{number=rand()%(end+1);}
	else
	{
     int a=end/(end-start+1)+1;
	 int temp=rand()%(end+1);
	 number=temp/a+start;
	 return number;
	}
	return number;
}


void main()
{
	int b;
	srand(time(NULL));       
    int a[320];
	int i;
	cout<<"请选择参数来源:"<<endl<<"1.从文本文件中读取"<<endl<<"2.由随机函数生成"<<endl;
	cin>>b;
	switch (b)
	{
	case 1:                                     //从文本文件中读取320个数作为指令流
		{
			char name[30] ;
			ifstream instuf(".\\1.txt",ios::in );
			if(!instuf)
			{
				cerr<<"File could not be open."<<endl;
				abort();
			}
			for ( i=0;i<320;i++)
			{
				instuf>>a[i];
				cout<<a[i]<<endl;
			}
			instuf.close(); break;}
	case 2:                                     //由随机函数生成一组随机数作为指令流
		{
			int m,m1;
			srand(time(NULL));
			m=rand()%320;
			cout<<"m="<<m<<endl;
			for(i=0;i<320;i+=4)
			{
				a[i]=m;
		        cout<<"a["<<i<<"]="<<a[i]<<endl;
		        a[i+1]=a[i]+1;
		        m1=RandNum(0,m-1);
		        a[i+2]=m1;
		        a[i+3]=m1+1;
		        m=RandNum(m1+2,319);
			}
			break;
		}
	}
	for(i=0;i<320;i++)
	{
		cout<<"a["<<i<<"]="<<a[i]<<endl;
	}
	for (i=0;i<total_instruction;i++)                   //将指令序列变换成页地址流
	{
		//a[i]=rand()/320+1;
		page[i]=a[i]/10;
		offset[i]=a[i]%10;
	}
	
	FIFO();
	LRU();
	OPT();
	getchar();
}

void initialize()                   //初始化相关数据结构
                             //用户进程的内存页面数
{
	int total_pf=4; 
	int i;
	diseffect=0;

	for(i=0;i<total_vp;i++)
	{
		pl[i].pn=i;
		pl[i].pfn=INVALID;                      //置页面控制结构中的页号，页面为空
		pl[i].counter=0;
		pl[i].time=-1;                         //页面控制结构中的访问次数为0，时间为－1
	}
	for(i=0;i<total_pf-1;i++)
	{
		pfc[i].next=&pfc[i+1];
		pfc[i].pfn=i;
	}                                               //建立pfc[i-1]和pfc[i]之间的链接
	pfc[total_pf-1].next=NULL;
	pfc[total_pf-1].pfn=total_pf-1;
	freepf_head=&pfc[0];                             //空页面队列的头指针为pfc[0]
}

void FIFO()                               //先进先出算法FIFO
                                   //用户进程的内存页面数
{
	int total_pf=4; 
	int i;
	pfc_type *p;
	initialize();                             //初始化相关页面控制用数据结构
	busypf_head=busypf_tail=NULL;                   //忙页面队列头，队列尾链接
	for(i=0;i<total_instruction;i++)
	{
		if(pl[page[i]].pfn==INVALID)                  //页面失效
		{
			diseffect+=1;                     //失效次数
			if(freepf_head==NULL) //无空闲页面
			{
				p=busypf_head->next;
				pl[busypf_head->pn].pfn=INVALID;
				freepf_head=busypf_head; //释放忙页面队列的第一个页面
				freepf_head->next=NULL;
				busypf_head=p;
			}
			p=freepf_head->next;                  //按FIFO方式调新页面入内存页面
			freepf_head->next=NULL;
			freepf_head->pn=page[i];
			pl[page[i]].pfn=freepf_head->pfn;
			if(busypf_tail==NULL)
				busypf_head=busypf_tail=freepf_head;
			else
			{
				busypf_tail->next=freepf_head;        //free页面减少一个
				busypf_tail=freepf_head;
			}
			freepf_head=p;
		}
	}
	cout<<"FIFO算法的命中率为"<<1-(float)diseffect/320<<endl;
}

void LRU()                   //最近最久未使用页面置换算法LRU

{
	int total_pf=4;
	int min,minj,i,j,present_time;
	initialize();
	present_time=0;
	
	for(i=0;i<total_instruction;i++)
	{
		if(pl[page[i]].pfn==INVALID)         //页面失效
		{
			diseffect++;
			if(freepf_head==NULL)                //无空闲页面
			{
				min=32767;
				for(j=0;j<total_vp;j++)               //找出time的最小值
					if(min>pl[j].time&&pl[j].pfn!=INVALID)
					{
						min=pl[j].time;
						minj=j;
					}
					freepf_head=&pfc[pl[minj].pfn];       //腾出一个单元
					pl[minj].pfn=INVALID;
					pl[minj].time=-1;
					freepf_head->next=NULL;
			}
			pl[page[i]].pfn=freepf_head->pfn;      //有空闲页面，改为有效
			pl[page[i]].time=present_time;

			freepf_head=freepf_head->next;           //减少一个free页面
		}
		else
			pl[page[i]].time=present_time;         //命中则增加该单元的访问次数
		present_time++;
	}
	cout<<"LRU算法的命中率为"<<1-(float)diseffect/320<<endl;
}

void OPT()                  //理想型淘汰算法OPT

{
	int total_pf=4;
	int i,j,max,maxpage,d,dist[total_vp];
	//pfc_type *t;
	initialize();
	for(i=0;i<total_instruction;i++)
	{
		if(pl[page[i]].pfn==INVALID)
		{
			diseffect++;
			if(freepf_head==NULL)
			{
				for(j=0;j<total_vp;j++)
					if(pl[j].pfn!=INVALID)
						dist[j]=32767;
					else
						dist[j]=0;
					d=1;
					for(j=i+1;j<total_instruction;j++)
					{
						if(pl[page[i]].pfn!=INVALID)
							dist[page[j]]=d;
						d++;
					}
					max=-1;
					for(j=0;j<total_vp;j++)
						if(max<dist[j])
						{
							max=dist[j];
							maxpage=j;
						}
						freepf_head=&pfc[pl[maxpage].pfn];
						freepf_head->next=NULL;
						pl[maxpage].pfn=INVALID;
			}
			pl[page[i]].pfn=freepf_head->pfn;
			freepf_head=freepf_head->next;
		}
	}
	cout<<"OPT算法的命中率为"<<1-(float)diseffect/320<<endl;
}