www.pudn.com > RRWMFfd.rar > RRWMFfd.CPP

#include "stdio.h" 
#include "stdlib.h" 
#include "string.h" 
#include  
typedef struct node 
{ 
   char name[10];  /*进程标识符*/ 
   int prio;   /*进程优先数*/ 
   int round;  /*进程时间轮转时间片*/ 
   int cputime; /*进程占用CPU时间*/ 
   int needtime; /*进程到完成还要的时间*/ 
   int count;  /*计数器*/ 
   int ArriTime;//进程到达时间 
   char state; /*进程的状态*/ 
   struct node *next; /*链指针*/ 
}PCB; 
    int Ctime=0;//当前时钟 
    PCB *NewProcess,*TimeOver,*Ntail,*Ttail;//多级反馈算法的两个就绪队列   
    PCB *finish,*ftail,*ready,*tail,*run,*rtail; /*完成队列，优先级，FCFS，时间片轮转算法下就绪队列，运行队列指针*/ 
    int N; /*进程数*/ 
 
 
 
 
void init()//多级反馈算法初始化    置队列为空 
{ 
   ready=NULL; 
   finish=NULL; 
   run=NULL; 
   NewProcess=NULL; 
   TimeOver=NULL;   
} 
 
 
 
/*优先级，FCFS，时间片轮转算法下           将就绪队列中的第一个进程投入运行*/ 
void firstin() 
{ 
   run=ready;   /*就绪队列头指针赋值给运行头指针*/ 
   run->state='R';   /*进程状态变为运行态*/ 
   ready=ready->next;  /*就绪对列头指针后移到下一进程*/ 
} 
 
 
/******************************************************************************************/ 
/***********************多级反馈算法下      将新创建进程队列中的第一个进程投入运行************************/ 
void Nfirstin() 
{ 
   run=NewProcess;   /*就绪队列头指针赋值给运行头指针*/ 
   rtail=NewProcess; 
   rtail->next=NULL; 
   run->state='R';   /*进程状态变为运行态*/ 
   run->round=3; 
   NewProcess=NewProcess->next;  /*就绪对列头指针后移到下一进程*/ 
} 
/*********************多级反馈算法下      将时间片完进程队列中的第一个进程投入运行***************/ 
void Tfirstin() 
{ 
   run=TimeOver;   /*就绪队列头指针赋值给运行头指针*/ 
   rtail=TimeOver; 
   rtail->next=NULL; 
 
   run->state='R';   /*进程状态变为运行态*/ 
   run->round=2; 
   TimeOver=TimeOver->next;  /*就绪对列头指针后移到下一进程*/ 
} 
 
 
/******************************************************************************/ 
/***********************标题输出函数*******************************************/ 
void prt1(char a) 
{ 
   if(toupper(a)=='P') /*优先级法*/ 
      printf("  name     cputime  needtime  priority  state\n"); 
   else if(toupper(a)=='R') 
      printf("  name     cputime  needtime   count   round     state\n"); 
   else if(toupper(a)=='F') 
	  printf("  name     cputime  needtime   count   state\n"); 
   else 
	  printf("  name     cputime  needtime   count   state    ArriTime\n"); 
	    
 
} 
 
/**************************进程PCB信息输出*****************************************/ 
void prt2(char a,PCB *q) 
{ 
   if(toupper(a)=='P')  /*优先级法的输出*/ 
      printf("  %-10s%-10d%-10d%-10d %c\n",q->name, 
       q->cputime,q->needtime,q->prio,q->state); 
   else if(toupper(a)=='R')/*轮转法的输出*/ 
      printf("  %-10s%-10d%-10d%-10d%-10d %-c\n",q->name, 
       q->cputime,q->needtime,q->count,q->round,q->state); 
   else if(toupper(a)=='F')/*FCFS法的输出*/ 
      printf("  %-10s%-10d%-10d%-10d %-c\n",q->name, 
       q->cputime,q->needtime,q->count,q->state); 
   else/*多级反馈算法的输出*/ 
	   printf("  %-10s%-10d%-10d%-10d %-10c%-d\n",q->name, 
       q->cputime,q->needtime,q->count,q->state,q->ArriTime); 
} 
/**************************进程各队列输出*****************************************/ 
void prt(char algo) 
{ 
   PCB *p; 
   prt1(algo);  /*输出标题*/ 
 
   printf("\n运行队列的进程：\n"); 
   if(run!=NULL) /*如果运行指针不空*/ 
      prt2(algo,run); /*输出当前正在运行的PCB*/ 
 
   printf("\n等待队列的进程：\n"); 
   p=ready;  /*输出就绪队列PCB*/ 
   while(p!=NULL) 
   { 
      prt2(algo,p); 
      p=p->next; 
   } 
 
   printf("\n完成队列的进程：\n"); 
   p=finish;  /*输出完成队列的PCB*/ 
   while(p!=NULL) 
   { 
      prt2(algo,p); 
      p=p->next; 
   } 
 
   printf("\n多级反馈算法时的新创建进程就绪队列：\n"); 
   p=NewProcess;  /*输出新进程队列的PCB*/ 
   while(p!=NULL) 
   { 
      prt2(algo,p); 
      p=p->next; 
   } 
 
    printf("\n多级反馈算法时的时间片用完进程就绪队列：\n"); 
   p=TimeOver;  /*输出时间片用完队列的PCB*/ 
   while(p!=NULL) 
   { 
      prt2(algo,p); 
      p=p->next; 
   } 
   
   getch();  /*按任意键继续*/ 
} 
 
 
 
/*****************************************************************************/ 
/*******************************优先级的插入算法*******************************/ 
void insert1(PCB *q) 
{ 
   PCB *p1,*s,*r; 
   int b; 
   s=q;  /*待插入的PCB指针*/ 
   p1=ready; /*就绪队列头指针*/ 
   r=p1; /*r做p1的前驱指针*/ 
   b=1; 
   while((p1!=NULL)&&b)  /*根据优先数确定插入位置*/ 
      if(p1->prio>=s->prio) 
      { 
          r=p1; 
          p1=p1->next; 
      } 
      else 
		  b=0; 
      if(r!=p1)  /*如果条件成立说明插入在r与p1之间*/ 
	  { 
		  r->next=s; 
          s->next=p1; 
	  } 
      else 
	  { 
		  s->next=p1;  /*否则插入在就绪队列的头*/ 
          ready=s; 
	  } 
} 
 
 
 
/*****************************************************************************/ 
/*******************************轮转法的插入算法*******************************/ 
 
void insert2(PCB *p2) 
{ 
   tail->next=p2;  /*将新的PCB插入在当前就绪队列的尾*/ 
   tail=p2; 
   p2->next=NULL; 
} 
 
/*****************************************************************************/ 
/*******************************多级反馈轮转法的插入算法*******************************/ 
////////////////////////向新创建进程就绪队列插入进程/////////////////////////////////// 
void NewInsert() 
{ 
	  if(NewProcess!=NULL) 
	   { 
		   Ntail->next=ready; 
		   Ntail=ready; 
		   ready=ready->next; 
		   Ntail->next=NULL; 
		   Ntail->state='N'; 
	   } 
	   else 
	   { 
		   NewProcess=ready; 
		   Ntail=ready; 
		   ready=ready->next; 
		   Ntail->next=NULL; 
		   NewProcess->state='N'; 
		    
	   } 
} 
////////////////////////向时间片用完进程就绪队列插入进程/////////////////////////////////// 
void Tinsert() 
{ 
	if(TimeOver!=NULL) 
	   { 
		   Ttail->next=run; 
		   Ttail=run; 
		   run=NULL; 
		   Ttail->next=NULL; 
		   Ttail->state='N'; 
	   } 
	   else 
	   { 
		   TimeOver=run; 
		   Ntail=run; 
		   run=NULL; 
		   Ntail->next=NULL; 
		   TimeOver->state='T'; 
		    
	   } 
} 
 
////////////////////////向完成队列插入进程/////////////////////////////////// 
void FinishInsert() 
{ 
	if(finish==NULL) 
	{ 
	finish=run; 
	ftail=run; 
    run->state='F'; 
    ftail->next=NULL; 
    run=NULL; 
	} 
	else 
	{ 
		ftail->next=run; 
		ftail=run; 
		run=NULL; 
		ftail->next=NULL; 
		ftail->state='F'; 
 
	} 
} 
/*****************************************************************************/ 
/*******************************优先级创建初始PCB信息*******************************/ 
void create1(char alg) 
{ 
   PCB *p; 
   int i,time; 
   char na[10]; 
   ready=NULL; /*就绪队列头指针*/ 
   finish=NULL;  /*完成队列头指针*/ 
   run=NULL; /*运行队列指针*/ 
   printf("Enter name and time of process\n"); /*输入进程标识和所需时间创建PCB*/ 
   for(i=1;i<=N;i++) 
   { 
      p=(PCB *)malloc(sizeof(PCB)); 
      scanf("%s",na); 
      scanf("%d",&time); 
      strcpy(p->name,na); 
      p->cputime=0; 
      p->needtime=time; 
      p->state='w'; 
      p->prio=50-time; 
      if(ready!=NULL) /*就绪队列不空调用插入函数插入*/ 
         insert1(p); 
      else 
      { 
         p->next=ready; /*创建就绪队列的第一个PCB*/ 
         ready=p; 
      } 
   } 
   system("cls"); 
   printf("          output of priority:\n"); 
   printf("************************************************\n"); 
   prt(alg);  /*输出进程PCB信息*/ 
   run=ready; /*将就绪队列的第一个进程投入运行*/ 
   ready=ready->next; 
   run->state='R'; 
} 
/*****************************************************************************/ 
/*******************************轮转法创建进程PCB*******************************/ 
 
void create2(char alg) 
{ 
   PCB *p; 
   int i,time; 
   char na[10]; 
   ready=NULL; 
   finish=NULL; 
   run=NULL; 
   printf("Enter name and time of round process\n"); 
   for(i=1;i<=N;i++) 
   { 
      p=(PCB *)malloc(sizeof(PCB)); 
      scanf("%s",na); 
      scanf("%d",&time); 
      strcpy(p->name,na); 
      p->cputime=0; 
      p->needtime=time; 
      p->count=0; /*计数器*/ 
      p->state='w'; 
      p->round=2;  /*时间片*/ 
      if(ready!=NULL) 
         insert2(p); 
      else 
      { 
         p->next=ready; 
         ready=p; 
         tail=p; 
      } 
   } 
   system("cls"); 
   printf("              output of round\n"); 
   printf("************************************************\n"); 
   prt(alg);   /*输出进程PCB信息*/ 
   run=ready;  /*将就绪队列的第一个进程投入运行*/ 
   ready=ready->next; 
   run->state='R'; 
} 
 
/*****************************************************************************/ 
/*******************************先来先服务创建进程*******************************/ 
 
void create3(char alg) 
{ 
   PCB *p; 
   int i,time; 
   char na[10]; 
   ready=NULL; 
   finish=NULL; 
   run=NULL; 
   printf("Enter name and time of round process\n"); 
   for(i=1;i<=N;i++) 
   { 
      p=(PCB *)malloc(sizeof(PCB)); 
      scanf("%s",na); 
      scanf("%d",&time); 
      strcpy(p->name,na); 
      p->cputime=0; 
      p->needtime=time; 
      p->count=0; /*计数器*/ 
      p->state='w'; 
      if(ready!=NULL) 
         insert2(p); 
      else 
      { 
         p->next=ready; 
         ready=p; 
         tail=p; 
      } 
   } 
   system("cls"); 
   printf("              output of FCFS\n"); 
   printf("************************************************\n"); 
   prt(alg);   /*输出进程PCB信息*/ 
   run=ready;  /*将就绪队列的第一个进程投入运行*/ 
   ready=ready->next; 
   run->state='R'; 
} 
/*****************************************************************************/ 
/*******************************多级反馈轮转创建进程*******************************/ 
 
void create4(char alg) 
{ 
   PCB *p; 
   int i,time,arritime; 
   char na[10]; 
 
    
   printf("Enter name & time of round process & arrive time\n");//按进程到来先后顺序出入进程信息 
   for(i=1;i<=N;i++) 
   { 
      p=(PCB *)malloc(sizeof(PCB)); 
      scanf("%s",na); 
      scanf("%d",&time); 
      scanf("%d",&arritime); 
      strcpy(p->name,na); 
      p->cputime=0; 
      p->needtime=time; 
      p->count=0; /*计数器*/ 
      p->state='w'; 
      p->round=2;  /*时间片*/ 
	  p->ArriTime=arritime; 
      if(ready!=NULL) 
        insert2(p); 
      else 
      { 
         p->next=ready; 
         ready=p; 
         tail=p; 
      } 
   } 
   system("cls"); 
   printf("              output of RRWMF\n"); 
   printf("************************************************\n"); 
   prt(alg);   /*输出进程PCB信息*/ 
   while(ready!=NULL&&Ctime==ready->ArriTime){ 
	  NewInsert(); 
   } 
} 
/*****************************************************************************/ 
/*******************************优先级调度算法*******************************/ 
 
void priority(char alg) 
{ 
   while(run!=NULL)  /*当运行队列不空时，有进程正在运行*/ 
   { 
      run->cputime=run->cputime+1; 
      run->needtime=run->needtime-1; 
      run->prio=run->prio-3; /*每运行一次优先数降低3个单位*/ 
      if(run->needtime==0)  /*如所需时间为0将其插入完成队列*/ 
      { 
         run->next=finish; 
         finish=run; 
         run->state='F';  /*置状态为完成态*/ 
         run=NULL;  /*运行队列头指针为空*/ 
         if(ready!=NULL) /*如就绪队列不空*/ 
            firstin(); /*将就绪对列的第一个进程投入运行*/ 
      } 
      else /*没有运行完同时优先数不是最大，则将其变为就绪态插入到就绪队列*/ 
         if((ready!=NULL)&&(run->prioprio)) 
         { 
            run->state='W'; 
            insert1(run); 
            firstin(); /*将就绪队列的第一个进程投入运行*/ 
         } 
		system("cls"); 
        printf("              output of priority\n"); 
        printf("************************************************\n"); 
             
      prt(alg); /*输出进程PCB信息*/ 
   } 
} 
/*****************************************************************************/ 
/*******************************时间片轮转法*******************************/ 
 
void roundrun(char alg) 
{ 
   while(run!=NULL) 
   { 
      run->cputime=run->cputime+1; 
      run->needtime=run->needtime-1; 
      run->count=run->count+1; 
      if(run->needtime==0)/*运行完将其变为完成态，插入完成队列*/ 
      { 
         run->next=finish; 
         finish=run; 
         run->state='F'; 
         run=NULL; 
         if(ready!=NULL) 
            firstin(); /*就绪队列不空，将第一个进程投入运行*/ 
      } 
      else 
         if(run->count==run->round)  /*如果时间片到*/ 
         { 
            run->count=0;  /*计数器置0*/ 
            if(ready!=NULL) /*如就绪队列不空*/ 
            { 
               run->state='W'; /*将进程插入到就绪队列中等待轮转*/ 
               insert2(run); 
               firstin(); /*将就绪对列的第一个进程投入运行*/ 
            } 
         } 
      system("cls"); 
      printf("              output of round\n"); 
      printf("************************************************\n"); 
      prt(alg); /*输出进程信息*/ 
   } 
} 
/*****************************************************************************/ 
/******************************FCFS调度算法*******************************/ 
 
void  FCFS(char alg) 
{ 
   while(run!=NULL)  /*当运行队列不空时，有进程正在运行*/ 
   { 
      run->cputime=run->cputime+1; 
      run->needtime=run->needtime-1; 
      if(run->needtime==0)  /*如所需时间为0将其插入完成队列*/ 
      { 
         run->next=finish; 
         finish=run; 
         run->state='F';  /*置状态为完成态*/ 
         run=NULL;  /*运行队列头指针为空*/ 
         if(ready!=NULL) /*如就绪队列不空*/ 
            firstin(); /*将就绪对列的第一个进程投入运行*/ 
      } 
     
     system("cls"); 
      printf("              output of FCFS\n"); 
      printf("************************************************\n"); 
      prt(alg); /*输出进程信息*/ 
  
   } 
} 
/*****************************************************************************/ 
/******************************多级反馈轮转算法*******************************/ 
 
void RRWMF(char alg) 
{ 
	init(); 
    create4(alg); 
	Ctime=1; 
	if(ready!=NULL&&Ctime==ready->ArriTime)NewInsert(); 
	if(NewProcess!=NULL) 
        Nfirstin(); /*新创建进程队列不空，将第一个进程投入运行*/ 
	else if(TimeOver!=NULL) 
        Tfirstin(); /*时间片完进程队列不空，将第一个进程投入运行*/ 
 
	 while(run!=NULL||NewProcess!=NULL||TimeOver!=NULL||ready!=NULL){ 
		 	 
		   if(ready!=NULL&&Ctime==ready->ArriTime)NewInsert(); 
		     
			if(run!=NULL) 
			{ 
			 run->cputime=run->cputime+1; 
             run->needtime=run->needtime-1; 
             run->count=run->count+1; 
			 
             if(run->needtime==0)/*运行完将其变为完成态，插入完成队列*/ 
			 { 
                 FinishInsert(); 
			//	 if(ready!=NULL&&Ctime==ready->ArriTime)NewInsert();/////////////////////////// 
				 if(NewProcess!=NULL)                       
				      Nfirstin(); /*新创建进程队列不空，将第一个进程投入运行*/ 
			     else if(TimeOver!=NULL) 
                      Tfirstin(); /*时间片完进程队列不空，将第一个进程投入运行*/ 
			    
			 } 
             else if(run->count==run->round)  /*如果时间片到*/ 
			 { 
                run->count=0;  /*计数器置0*/ 
				Tinsert();      ///插入时间片完队列等待 
				if(NewProcess!=NULL) 
				      Nfirstin(); /*新创建进程队列不空，将第一个进程投入运行*/ 
			     else if(TimeOver!=NULL) 
                      Tfirstin(); /*时间片完进程队列不空，将第一个进程投入运行*/ 
			      
			 } 
			} 
			else{ 
			     if(NewProcess!=NULL)                       
				      Nfirstin(); /*新创建进程队列不空，将第一个进程投入运行*/ 
			     else if(TimeOver!=NULL) 
                      Tfirstin(); /*时间片完进程队列不空，将第一个进程投入运行*/ 
			     
			} 
			 system("cls"); 
             printf("              output of RRWMF\n"); 
             printf("************************************************\n"); 
             prt(alg); /*输出进程信息*/ 
			 Ctime=Ctime+1; 
	 } 
 
} 
/*****************************************************************************/ 
/******************************主函数*******************************/ 
 
void main() 
{ 
   char algo;  /*算法标记*/ 
   system("cls"); 
   printf("type the algorithm:P/R/F/M(priority/roundrobin/FCFS/RRWMF)\n"); 
   scanf("%c",&algo); /*输入字符确定算法*/ 
   printf("Enter process number\n"); 
   scanf("%d",&N); /*输入进程数*/ 
   if(algo=='P'||algo=='p') 
   { 
      create1(algo); /*优先数法*/ 
      priority(algo); 
   } 
   else 
      if(algo=='R'||algo=='r') 
      { 
         create2(algo); /*轮转法*/ 
         roundrun(algo); 
      } 
    else 
      if(algo=='F'||algo=='f') 
      { 
         create3(algo); /*FCFS法*/ 
         FCFS(algo); 
      } 
    else 
      if(algo=='M'||algo=='m') 
      { 
         init(); /*多级反馈轮转法法*/ 
         RRWMF(algo); 
      } 
}