#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef struct node
{
   char name[10];  /*進(jìn)程標(biāo)識(shí)符*/
   int prio;   /*進(jìn)程優(yōu)先數(shù)*/
   int round;  /*進(jìn)程時(shí)間輪轉(zhuǎn)時(shí)間片*/
   int cputime; /*進(jìn)程占用CPU時(shí)間*/
   int needtime; /*進(jìn)程到完成還要的時(shí)間*/
   int count;  /*計(jì)數(shù)器*/
   char state; /*進(jìn)程的狀態(tài)*/
   struct node *next; /*鏈指針*/
}PCB;
PCB *finish,*ready,*tail,*run; /*隊(duì)列指針*/
int N; /*進(jìn)程數(shù)*/
/*將就緒隊(duì)列中的第一個(gè)進(jìn)程投入運(yùn)行*/
firstin()
{
   run=ready;   /*就緒隊(duì)列頭指針賦值給運(yùn)行頭指針*/
   run->state='R';   /*進(jìn)程狀態(tài)變?yōu)檫\(yùn)行態(tài)*/
   ready=ready->next;  /*就緒對(duì)列頭指針后移到下一進(jìn)程*/
}
/*標(biāo)題輸出函數(shù)*/
void prt1(char a)
{
   if(toupper(a)=='P') /*優(yōu)先數(shù)法*/
      printf("  name     runtime  needtime  priority  state\n");
   else
      printf("  name     runtime  needtime   count   round     state\n");
}
/*進(jìn)程PCB輸出*/
void prt2(char a,PCB *q)
{
   if(toupper(a)=='P')  /*優(yōu)先數(shù)法的輸出*/
      printf("  %-10s%-10d%-10d%-10d %c\n",q->name,
       q->cputime,q->needtime,q->prio,q->state);
   else/*輪轉(zhuǎn)法的輸出*/
      printf("  %-10s%-10d%-10d%-10d%-10d %-c\n",q->name,
       q->cputime,q->needtime,q->count,q->round,q->state);
}
/*輸出函數(shù)*/
void prt(char algo)
{
   PCB *p;
   prt1(algo);  /*輸出標(biāo)題*/
   if(run!=NULL) /*如果運(yùn)行指針不空*/
      prt2(algo,run); /*輸出當(dāng)前正在運(yùn)行的PCB*/
   p=ready;  /*輸出就緒隊(duì)列PCB*/
   while(p!=NULL)
   {
      prt2(algo,p);
      p=p->next;
   }
   p=finish;  /*輸出完成隊(duì)列的PCB*/
   while(p!=NULL)
   {
      prt2(algo,p);
      p=p->next;
   }
   getch();  /*壓任意鍵繼續(xù)*/
}
/*優(yōu)先數(shù)的插入算法*/
insert1(PCB *q)
{
   PCB *p1,*s,*r;
   int b;
   s=q;  /*待插入的PCB指針*/
   p1=ready; /*就緒隊(duì)列頭指針*/
   r=p1; /*r做p1的前驅(qū)指針*/
   b=1;
   while((p1!=NULL)&&b)  /*根據(jù)優(yōu)先數(shù)確定插入位置*/
      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;  /*否則插入在就緒隊(duì)列的頭*/
      ready=s;
   }
}
/*輪轉(zhuǎn)法插入函數(shù)*/
insert2(PCB *p2)
{
   tail->next=p2;  /*將新的PCB插入在當(dāng)前就緒隊(duì)列的尾*/
   tail=p2;
   p2->next=NULL;
}
/*優(yōu)先數(shù)創(chuàng)建初始PCB信息*/
void create1(char alg)
{
   PCB *p;
   int i,time;
   char na[10];
   ready=NULL; /*就緒隊(duì)列頭指針*/
   finish=NULL;  /*完成隊(duì)列頭指針*/
   run=NULL; /*運(yùn)行隊(duì)列指針*/
   printf("Enter name and time of process\n"); /*輸入進(jìn)程標(biāo)識(shí)和所需時(shí)間創(chuàng)建PCB*/

   for(i=1;i<=N;i++)
   {
      p=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) /*就緒隊(duì)列不空調(diào)用插入函數(shù)插入*/
  insert1(p);
      else
      {
  p->next=ready; /*創(chuàng)建就緒隊(duì)列的第一個(gè)PCB*/
  ready=p;
      }
   }
   clrscr();
   printf("          output of priority:\n");
   printf("************************************************\n");
   prt(alg);  /*輸出進(jìn)程PCB信息*/
   run=ready; /*將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/
   ready=ready->next;
   run->state='R';
}


/*優(yōu)先數(shù)調(diào)度算法*/
priority(char alg)
{
   while(run!=NULL)  /*當(dāng)運(yùn)行隊(duì)列不空時(shí)，有進(jìn)程正在運(yùn)行*/
   {
      run->cputime=run->cputime+1;
      run->needtime=run->needtime-1;
      run->prio=run->prio-3; /*每運(yùn)行一次優(yōu)先數(shù)降低3個(gè)單位*/
      if(run->needtime==0)  /*如所需時(shí)間為0將其插入完成隊(duì)列*/
      {
  run->next=finish;
  finish=run;
  run->state='F';  /*置狀態(tài)為完成態(tài)*/
  run=NULL;  /*運(yùn)行隊(duì)列頭指針為空*/
  if(ready!=NULL) /*如就緒隊(duì)列不空*/
     firstin(); /*將就緒對(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/
      }
      else /*沒有運(yùn)行完同時(shí)優(yōu)先數(shù)不是最大，則將其變?yōu)榫途w態(tài)插入到就緒隊(duì)列*/
  if((ready!=NULL)&&(run->prio<ready->prio))
  {
     run->state='W';
     insert1(run);
     firstin(); /*將就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行*/
  }
      prt(alg); /*輸出進(jìn)程PCB信息*/
   }
}

/*主函數(shù)*/
main()
{
   clrscr();
   printf("Welcome to the priority algorithm!");
   printf("Enter process number\n");
   scanf("%d",&N); /*輸入進(jìn)程數(shù)*/
      create1('p'); /*優(yōu)先級(jí)法*/
      priority('p');
}