#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct node
{
   char name[10];  /*進程標識符*/
   int prio;   /*進程優先數*/
   int round[3];  /*進程時間輪轉時間片*/
   int cputime; /*進程占用CPU時間*/
   int needtime; /*進程到完成還要的時間*/
   int count; /*計數器*/
   int curpri;
   char state; /*進程的狀態*/
   struct node *next; /*鏈指針*/
}PCB;
PCB *finish,*ready[3],*tail[3],*run; /*隊列指針*/

int M=3;//時間片級數 
/*將各級就緒隊列中的第一個進程投入運行*/
partfirstin(int i)
{
   run=ready[i];   /*就緒隊列頭指針賦值給運行頭指針*/
   run->state='R';   /*進程狀態變為運行態*/
   ready[i]=ready[i]->next;  /*就緒對列頭指針后移到下一進程*/
}

firstin()
{/*將就緒隊列中的第一個進程投入運行*/
	if(ready[0]!=NULL)  partfirstin(0);
	else if(ready[1]!=NULL) partfirstin(1);
	      else if(ready[2]!=NULL) partfirstin(2);
}
/*標題輸出函數*/
void prt1(char a)
{
   if(toupper(a)=='P') /*優先數法*/
      printf("  name     cputime  needtime  priority  state\n");
   else
      printf("  name     cputime  needtime   count   curpri      state\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/*輪轉法的輸出*/
      printf("  %-10s%-10d%-10d%-10d%-10d %-c\n",q->name,
       q->cputime,q->needtime,q->count,q->curpri,q->state);
}
/*輸出函數*/
void prt(char algo)
{
   PCB *p;
   prt1(algo);  /*輸出標題*/
   if(run!=NULL) /*如果運行指針不空*/
      prt2(algo,run); /*輸出當前正在運行的PCB*/
   p=ready[0];  /*輸出就緒隊列1的PCB*/
   while(p!=NULL)
   {
      prt2(algo,p);
      p=p->next;
   }
   p=ready[1];  /*輸出就緒隊列2的PCB*/
   while(p!=NULL)
   {
      prt2(algo,p);
      p=p->next;
   }
   p=ready[2];  /*輸出就緒隊列3的PCB*/
   while(p!=NULL)
   {
      prt2(algo,p);
      p=p->next;
   }
   p=finish;  /*輸出完成隊列的PCB*/
   while(p!=NULL)
   {
      prt2(algo,p);
      p=p->next;
   }
   getchar();  /*壓任意鍵繼續*/
}
/*優先數的插入算法*/
insert1(PCB *q)
{
   PCB *p1,*s,*r;
   int b;
   s=q;  /*待插入的PCB指針*/
   p1=ready[0]; /*就緒隊列頭指針*/
   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[0]=s;
   }
}
/*輪轉法插入函數*/
insert2(PCB *p2,int i)
{if(tail[i]!=NULL)
	{tail[i]->next=p2;  /*將新的PCB插入在當前就緒隊列的尾*/
     tail[i]=p2;
     p2->next=NULL;
	}
   else if(ready[i]==NULL)
			{p2->next=ready[i];
             ready[i]=p2;
			 tail[i]=p2;
			}
}
/*優先數創建初始PCB信息*/
void create1(char alg,int N)
{
   PCB *p;
   int i,time;
   char na[10];
   ready[0]=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[0]!=NULL) /*就緒隊列不空調用插入函數插入*/
         insert1(p);
      else
      {
         p->next=ready[0]; /*創建就緒隊列的第一個PCB*/
         ready[0]=p;
      }
   }
 //  clrscr();
   printf("          output of priority:\n");
   printf("************************************************\n");
   prt(alg);  /*輸出進程PCB信息*/
   run=ready[0]; /*將就緒隊列的第一個進程投入運行*/
   ready[0]=ready[0]->next;
   run->state='R';
}
/*輪轉法創建進程PCB*/
void create2(char alg,int N)
{
   PCB *p;
   int i,time;
   char na[10];
   ready[0]=NULL;
   ready[1]=NULL;
   ready[2]=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[0]=2;  /*時間片1*/
	  p->round[1]=4;  /*時間片2*/
	  p->round[2]=8;  /*時間片3*/
	  p->curpri=2;
      if(ready[0]!=NULL)
         insert2(p,0);
      else
      {
         p->next=ready[0];
         ready[0]=p;
         tail[0]=p;
      }
	  tail[1]=NULL;
	  tail[2]=NULL;
   }
 //  clrscr();
   printf("              output of round\n");
   printf("*************************************************************\n");
   prt(alg);   /*輸出進程PCB信息*/
   run=ready[0];  /*將就緒隊列的第一個進程投入運行*/
   ready[0]=ready[0]->next;
   run->state='R';
}

void createnew(char alg,int N)
{
   PCB *p;
   int i,time;
   char na[10];
   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[0]=2;  /*時間片1*/
	  p->round[1]=4;  /*時間片2*/
	  p->round[2]=8;  /*時間片3*/
	  p->curpri=2;
      if(ready[0]!=NULL)
         insert2(p,0);
      else
      {
         p->next=ready[0];
         ready[0]=p;
         tail[0]=p;
      }
   }
 //  clrscr();
   printf("              output of round\n");
   printf("*************************************************************\n");
   prt(alg);   /*輸出進程PCB信息*/
   run=ready[0];  /*將就緒隊列的第一個進程投入運行*/
   ready[0]=ready[0]->next;
   run->state='R';
}
/*優先數調度算法*/
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[0]!=NULL) /*如就緒隊列不空*/
            firstin(); /*將就緒對列的第一個進程投入運行*/
      }
      else /*沒有運行完同時優先數不是最大，則將其變為就緒態插入到就緒隊列*/
         if((ready[0]!=NULL)&&(run->prio<ready[0]->prio))
         {
            run->state='W';
            insert1(run);
            firstin(); /*將就緒隊列的第一個進程投入運行*/
         }
      prt(alg); /*輸出進程PCB信息*/
   }
}
/*時間片輪轉法*/
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

		  for(int i=0;i<M;i++)
			  if((run->curpri==2-i)&&(run->count==run->round[i])) 
				 /*如果該級的時間片到*/
				{
				  run->count=0;  /*計數器置0*/
				  if(i+1<M) /*如就緒隊列不空*/
				  { 
					run->curpri=run->curpri-1;
				    run->state='W'; /*將進程插入到就緒隊列中等待輪轉*/
                    insert2(run,i+1);
                    firstin(); /*將就緒對列的第一個進程投入運行*/
				  }
				  else if(i+1==M)
						{run->curpri=0;
			             run->state='w';
						 insert2(run,2);
						 firstin();
						}
				}
      prt(alg); /*輸出進程信息*/
	  printf("If you want to enter new process,please type 'y'\n");
	  char np;
	  int n;
	  scanf("%c",&np);
	  if(np=='y'||np=='Y')
	  {
		  if(run->curpri=0) {insert2(run,0);run->state='w';}
		  else if(run->curpri=1) {insert2(run,1);run->state='w';}
		        else {insert2(run,2);run->state='w';}
		  printf("Enter new process number\n");
		  scanf("%d",&n);
		  createnew(alg,n);
	  }
   }
}
/*主函數*/
main()
{
   char algo;  /*算法標記*/
   int N; /*進程數*/
  // clrscr();
   printf("type the algorithm:P/R(priority/roundrobin)\n");
   scanf("%c",&algo); /*輸入字符確定算法*/
   printf("Enter process number\n");
   scanf("%d",&N);
   if(algo=='P'||algo=='p')
   {
      create1(algo,N); /*優先數法*/
      priority(algo);
   }
   else
      if(algo=='R'||algo=='r')
      {
         create2(algo,N); /*輪轉法*/
         roundrun(algo);
      }
}