页面置换算法(最终版本).cpp

这是我们自己写~~~~~希望各位给点意见

#include <stdio.h>//标准输入/输出函数
#include <math.h>//数学函数 
#include<stdlib.h>//动态存储分配函数
#include<time.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[total_vp];    /*页面结构数组*/

struct pfc_struct{    /*页面控制结构*/
    int pn,pfn;
    struct pfc_struct *next;
};

typedef struct pfc_struct pfc_type;
pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;
int diseffect, a[total_instruction];
int page[total_instruction], offset[total_instruction];
   
void initialize(int);
void FIFO(int);
void LRU(int);
void OPT(int);
void LFU(int);
void NUR(int);

int main(){
    int S,i,j;
 time_t t; //产生随机数用
 srand((unsigned) time(&t)); 
 S= rand() % 319+1;//随机数1到319

    for(i=0;i<total_instruction;i+=4){    /*产生指令队列*/    
     a[i]= S;   /*任选一指令访问点*/
     a[i+1]=a[i]+1;    /*顺序执行一条指令*/
  j=rand()%32767;
     a[i+2]=a[i]*j/32767;    /*执行前地址指令m'*/
     a[i+3]=a[i+2]+1;    /*执行后地址指令*/
  j=rand()%32767;
     S=j*(318-a[i+2])/32767+a[i+2]+2;
    }
 
 for(i=0;i<total_instruction;i++){    /* 将指令序列变换成页地址流 */    
     page[i]=a[i]/10;
     offset[i]=a[i]%10;
    } 

  
i = rand()%32+4;/*用户内存工作区随机产生页面(4-32个页面) */
 
int a;
do{
printf("\n页面置换算法模拟\n");//菜单
printf("*********************************\n");
printf("1。FIFO算法实现\n");
printf("2。LUR算法实现\n");
printf("3。OPT算法实现\n");
printf("4。LFU算法实现\n");
printf("5。NUR算法实现\n");
printf("6。重新产生随机页面\n");
printf("7。退出\n");
printf("***********************************\n");
printf("请输入您的选择(1,2,3,4,5,6,7)\n");
 scanf("%d",&a);//选择算法实现
  switch(a){
  case 1:{
  printf("第%d页面:",i);
  FIFO(i);break;
  }
   case 2:{
  printf("第%d页面:",i);
   LRU(i);break;
    }
    case 3:{
  printf("第%d页面:",i);
    OPT(i);break;
    }
    case 4:{
  printf("第%d页面:",i);
    LFU(i);break;
    }
    case 5:{
  printf("第%d页面:",i);
    NUR(i);break;
    }
    case 6:i = rand()%32+4;break;
    case 7:exit(0);
  printf("\n");
    }
}while(a<=7);
getchar();
}

   
void FIFO(int total_pf)    /* FIFO(First in First Out)ALGORITHM 先进先出*/
//int total_pf;    /* 用户进程的内存页面数 */
{ 
 int i;
 pfc_type *p;
 
 initialize(total_pf);    /* 初始化相关页面控制用数据结构 */
 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;
				busypf_tail=freepf_head;  		
			}
			freepf_head=p;
		}
	}
	printf("  FIFO:%6.4f",1-(float)diseffect/320);
}

void LRU(int total_pf)    /* LRU(Last Recently Used)ALGORITHM 最近最久未使用*/
//int total_pf;		/* 用户进程的内存页面数 */
{
	int min,minj,i,j,present_time;
	initialize(total_pf);	 /* 初始化相关页面控制用数据结构 */
	present_time=0;//初定时间为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++)
					if(min>pl[j].time && pl[j].pfn!=INVALID){
						min=pl[j].time;
						minj=j;
					}
					freepf_head=&pfc[pl[minj].pfn];/* 按LRU方式调新页面入内存页面 */
					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;
		}else
			pl[page[i]].time=present_time;
		present_time++;
	}
	printf("  LRU:%6.4f",1-(float)diseffect/320);
}

void NUR(int total_pf)// NUR(No Used Recently) ALGORITHM最近未使用
//int total_pf;
{
	int i,j,dp,cont_flag,old_dp;
   	//pfc_type *t;
   	initialize(total_pf);/* 初始化相关页面控制用数据结构 */
   	dp=0;
   	for(i=0;i<total_instruction;i++){
		if(pl[page[i]].pfn==INVALID){    /* 页面失效 */
			diseffect++;				/* 失效次数 */
			if(freepf_head==NULL){    /* 无空闲页面 */
				cont_flag=TRUE;old_dp=dp;
				while(cont_flag)
					if(pl[dp].counter==0 && pl[dp].pfn!=INVALID)
						cont_flag=FALSE;
					else{
						dp++;if(dp==total_vp)dp=0;
						if(dp==old_dp)
							for(j=0;j<total_vp;j++)
								pl[j].counter=0;
					}
					freepf_head=&pfc[pl[dp].pfn];/* 按NUR方式调新页面入内存页面 */
					pl[dp].pfn=INVALID;
					freepf_head->next=NULL;
			}
			pl[page[i]].pfn=freepf_head->pfn;
			freepf_head=freepf_head->next;
		}else
			pl[page[i]].counter=1;
		if(i%clear_period==0)
			for(j=0;j<total_vp;j++)
				pl[j].counter=0;
   	}
   	printf("  NUR:%6.4f",1-(float)diseffect/320);
}

void OPT(int total_pf)    /* OPT(Optimal Replacement)ALGORITHM最佳 */
//int total_pf;
{
	int i,j,max,maxpage,d,dist[total_vp];
//	pfc_type *t;
	initialize(total_pf);/* 初始化相关页面控制用数据结构 */
	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[j]].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];/* 按OPT方式调新页面入内存页面 */
						freepf_head->next=NULL;
						pl[maxpage].pfn=INVALID;
			}
			pl[page[i]].pfn=freepf_head->pfn;
			freepf_head=freepf_head->next;
		}
	}
	printf("  OPT:%6.4f",1-(float)diseffect/320);
}
  
void LFU(int total_pf)    /* LFU(leat Frequently Used)ALGORITHM 最少使用*/
//int total_pf;
{	
	int i,j,min,minpage;
//   	pfc_type *t;
   	initialize(total_pf);/* 初始化相关页面控制用数据结构 */
   	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++){
					if(min>pl[j].counter && pl[j].pfn!=INVALID){
						min=pl[j].counter;minpage=j;
					}
					pl[j].counter=0;
				}
				freepf_head=&pfc[pl[minpage].pfn];/* 按LFU方式调新页面入内存页面 */
				pl[minpage].pfn=INVALID;
				freepf_head->next=NULL;
			}
			pl[page[i]].pfn=freepf_head->pfn;
			freepf_head=freepf_head->next;
		}else
			pl[page[i]].counter++;
   	}
   	printf("  LFU:%6.4f",1-(float)diseffect/320);
}
   
void initialize(int total_pf)    /* 初始化相关数据结构 */
//int total_pf;    /* 用户进程的内存页面数 */
{ 
 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=1;i<total_pf;i++){
  pfc[i-1].next=&pfc[i];
  pfc[i-1].pfn=i-1;
 }    /* 建立pfcD一门和pfcD]之间的链接 */

    pfc[total_pf-1].next=NULL;pfc[total_pf-1].pfn=total_pf-1;
    freepf_head=&pfc[0];    /*空页面队列的头指针为pfc[0] */
}