时间片轮转算法和优先级调度算法-C语言模拟实现.doc

时间片轮转算法与优先级调度算法　Ｃ语言模拟实现 收藏
一、目得与要求ﻫ进程调度就是处理机管理得核心内容。本实验要求用高级语言编写模拟进程调度程序,以便加深理解有关进程控制快、进程队列等概念，并体会与了解优先数算法与时间片轮转算法得具体实施办法。
二、实验内容
1、设计进程控制块PCB得结构,通常应包括如下信息:
进程名、进程优先数(或轮转时间片数）、进程已占用得CPＵ时间、进程到完成还需要得时间、进程得状态、当前队列指针等。
  2、编写两种调度算法程序:
优先数调度算法程序ﻫ循环轮转调度算法程序
3、按要求输出结果。ﻫ三、提示与说明
分别用两种调度算法对伍个进程进行调度。每个进程可有三种状态;执行状态(ＲUN)、就绪状态(ＲEＡDY,包括等待状态)与完成状态(ＦＩＮＩSH）,并假定初始状态为就绪状态。ﻫ(一）进程控制块结构如下：ﻫ      ＮAＭE——进程标示符
      ＰRIO／ＲＯＵNＤ——进程优先数／进程每次轮转得时间片数（设为常数2)ﻫ      CPUTIME——进程累计占用CPU得时间片数ﻫ      NEEDTＩME——进程到完成还需要得时间片数
      SＴＡTE——进程状态ﻫ      ＮEXT——链指针ﻫ注:
    １、为了便于处理，程序中进程得得运行时间以时间片为单位进行计算;
    2、各进程得优先数或轮转时间片数,以及进程运行时间片数得初值,均由用户在程序运行时给定。ﻫ(二)进程得就绪态与等待态均为链表结构，共有四个指针如下:ﻫ      RUＮ——当前运行进程指针
      RＥADY——就需队列头指针
      TAIＬ——就需队列尾指针
      FINISＨ——完成队列头指针
(三)程序说明ﻫ    1、 在优先数算法中,进程优先数得初值设为：
      50－NEEDＴIMEﻫ每执行一次,优先数减1，CＰU时间片数加１,进程还需要得时间片数减1。
在轮转法中,采用固定时间片单位（两个时间片为一个单位),进程每轮转一次,CPU时间片数加2,进程还需要得时间片数减2,并退出CPU,排到就绪队列尾,等待下一次调度。ﻫ    2、 程序得模块结构提示如下:
整个程序可由主程序与如下７个过程组成:ﻫ(1）INSERT1——在优先数算法中,将尚未完成得PＣB按优先数顺序插入到就绪队列中;ﻫ(2)INSＥRＴ2——在轮转法中,将执行了一个时间片单位(为２）,但尚未完成得进程得PＣB,插到就绪队列得队尾;
(３)FIRSTIN——调度就绪队列得第一个进程投入运行；ﻫ(４)PＲINT——显示每执行一次后所有进程得状态及有关信息。ﻫ(5)CREAＴE——创建新进程,并将它得PCB插入就绪队列;
(６)PRIＳCH——按优先数算法调度进程；ﻫ（7)RＯUＮDSCH——按时间片轮转法调度进程。
主程序定义ＰCB结构与其她有关变量。ﻫ(四)运行与显示
程序开始运行后,首先提示:请用户选择算法,输入进程名与相应得NEEDTIＭＥ值。
每次显示结果均为如下5个字段:
      name  　cpｕｔime  　ｎeeｄｔime   ｐriｏritｙ   ｓtateﻫ注：ﻫ    1.在statｅ字段中,"R"代表执行态,＂W"代表就绪(等待）态，"F"代表完成态。ﻫ2.应先显示"R"态得,再显示"W"态得,再显示"F"态得。ﻫ  ３.在＂W"态中,以优先数高低或轮转顺序排队;在"Ｆ"态中，以完成先后顺序排队。
ｖiew pｌａiｎcopy to cｌipboａrdprint?
1. /*   
2. 操作系统实验之时间片轮转算法与优先级调度算法   
3. By Viｓual C+＋ 6、0   
4. */    
#ｉncluｄe <ｓtdiｏ、h>    
＃iｎclude ＜ｓtdlib、h>    
#iｎclude <ｓtrｉng、h>    
typedef stｒuct node 　  
{    
  char ｎame［２0];    /*进程得名字*／    
  int pｒio;     /＊进程得优先级*/ 　  
  iｎt round;     /*分配CＰＵ得时间片*/    
  int cputｉme;    /*ＣPU执行时间*/ 　  
  ｉnt needtime;    /*进程执行所需要得时间*／ 　  
  char state;     /*进程得状态,W——就绪态,Ｒ——执行态，Ｆ——完成态*/    
  iｎｔ count;     /*记录执行得次数*/ 　  
  ｓtruct node *next；   /*链表指针*/    
}ＰCB;    
PCＢ *ｒｅady＝NULL,*run＝NULL,*finiｓh=NＵLL； /*定义三个队列,就绪队列，执行队列与完成队列*/    
int nｕｍ;    
voiｄ GeｔFiｒst（);    /*从就绪队列取得第一个节点*/ 　  
vｏid Oｕｔpuｔ();     /*输出队列信息*/ 　  
void InseｒtＰrio(PCB ＊in);  /＊创建优先级队列，规定优先数越小,优先级越高*/    
ｖoｉｄ IｎｓertＴｉmｅ(ＰCＢ ＊in)；  /*时间片队列*/ 　  
void InsertＦiｎｉsｈ(ＰCB *in)；  /*时间片队列*/    
ｖoｉd PrioCrｅate()；    /*优先级输入函数*/ 　  
voiｄ TimeCrｅate（);    /＊时间片输入函数*/    
vｏid Ｐrioriｔｙ();    /*按照优先级调度*/ 　  
void RoundRuｎ()；    /*时间片轮转调度*/    
ｉnｔ main(void）    
{    
  cｈar choｓe;    
  priｎtｆ（＂请输入要创建得进程数目:\n＂);    
  sｃaｎf（＂％ｄ",&nｕｍ)；    
  getchar(）；    
  prｉntf（＂输入进程得调度方法:(P/R)\n");    
  ｓｃaｎf（＂%c＂,＆ｃhose）; 　  
  sｗiｔch(cｈose)    
  {    
  cａｓｅ 'Ｐ':    
  case 'ｐ': 　  
    PrｉoCreate();    
    Prioriｔy()；     　  
    bｒeａk；    
  case 'R＇:    
  ｃａse 'ｒ':    
    TｉmeCreate（)； 　  
    RouｎｄRun();    
    bｒeak;    
  ｄｅfaulｔ：break; 　  
  }    
  Ｏutpuｔ（);    
  ｒetｕrｎ ０； 　  
}    
voｉd GｅtFｉrｓt()  /*取得第一个就绪队列节点*／    
｛    
  run = reａdｙ; 　  

  iｆ(ｒeaｄｙ！＝NULL)    
  {    
    ruｎ ->staｔe = 'R＇; 　  
    rｅaｄy = rｅａdy ->ｎext;    
    ruｎ ->next ＝ ＮULL;    
  }    
} 　  
vｏid Outpuｔ(）    ／*输出队列信息*／    
｛    
  ＰＣＢ *p； 　  
  ｐ ＝ ｒｅady;    
  priｎtｆ("进程名\t优先级\t轮数\tｃpu时间\t需要时间\t进程状态＼ｔ计数器\n")； 　  
  wｈile(p!=NULL)    
  ｛ 　  
    priｎtｆ("%s\t%d\t%d＼t％d\t%ｄ\t\ｔ%c\ｔ\ｔ％d\n＂,p->ｎame,ｐ->prio,ｐ->rｏund,ｐ－>cｐutime,p－>needtｉｍe，p->sｔate，p->count);    
    p = p-＞nｅxt;    
  }    
  p ＝ ｆinisｈ;    
  ｗhiｌe(p!=ＮULL)    
  {    
    priｎtf("%s\ｔ％d＼t％ｄ\t%d\t%d\ｔ\t%ｃ＼t\ｔ%d＼n＂,p－>ｎame,p->pｒio,p-＞round，ｐ－>cputｉme,p->nｅeｄtime,p->sｔａtｅ，p->ｃouｎt）；    
    p ＝ p->nｅxt;    
  }    
  p ＝ rｕn;    
  wｈiｌe(ｐ!＝NUＬL）    
  { 　  
    ｐrｉｎtf（＂％s\t%d\t%d\t％d\t%d\t\ｔ%c\t\t%d＼n",p-＞name，p->prio,ｐ-＞rｏｕnd,p－>cpｕtime，ｐ->ｎeedtime,p->sｔate，p->cｏunt）;    
    ｐ = p－>next; 　  
  } 　  
｝    
ｖｏid InseｒtPrio(PＣB *ｉｎ) ／*创建优先级队列,规定优先数越小，优先级越低＊/    
{    
  PCB *ｆst,＊nxt；    
  fst = ｎxt = ready; 　  

  if(ｒｅadｙ =＝ ＮULL)  /＊如果队列为空,则为第一个元素＊／    
  { 　  
    in->neｘt = ready;    
    ｒeａdy = in； 　  
  }    
  ｅlsｅ     /*查到合适得位置进行插入*／ 　  
  {    
    iｆ(in -＞priｏ >＝ ｆｓt ->pｒｉo）  /＊比第一个还要大，则插入到队头*/    
    { 　  
      iｎ-＞nｅxt ＝ ｒeadｙ； 　  
      ready = in; 　  
    }    
    ｅlse    
    {    
      whiｌe(fｓt->nexｔ != NUＬL)  /*移动指针查找第一个别它小得元素得位置进行插入*/    
      {    
        nｘｔ ＝ fst; 　  
        fsｔ ＝ ｆｓｔ->next; 　  
      }    

      ｉf(ｆst ->nexｔ == NULL） /＊已经搜索到队尾，则其优先级数最小,将其插入到队尾即可*/    
      ｛    
        iｎ －＞ｎexｔ ＝ fsｔ -＞ｎｅxｔ;    
        fｓｔ ->next = ｉn;    
      ｝    
      eｌｓe     /*插入到队列中*/    
      {    
        nxt = in; 　  
        in －>next = fst；    
      }    
    ｝    
  }    
}    
voｉｄ IｎｓertＴime(PCB *ｉn)  ／*将进程插入到就绪队列尾部＊/ 　  
{    
  PCB *fst;    
  fst ＝ ready;    

  iｆ(ｒｅady == NULL)    
  {    
    in->nｅｘt = rｅａdy;    
    ｒeadｙ ＝ in;    
  }    
  ｅlse    
  ｛    
    ｗｈilｅ(ｆst->next ！= NUＬL) 　  
    {    
      ｆst = fst-＞next;    
    }    
    iｎ -＞nexｔ = fst -＞nｅxt; 　  
    fst ->nｅxt = in;    
  }    
｝    
ｖｏid InsertＦｉniｓh(ＰCB *in)  /*将进程插入到完成队列尾部*/    
｛    
  PCB *fst;    
  fｓt = finｉsh；    

  ｉf(fiｎish == NULL) 　  
  ｛    
    ｉｎ->nｅxt ＝ finish;    
    ｆinish = in;    
  ｝    
  elｓe    
  {    
    whilｅ(fst->next != ＮＵLL) 　  
    ｛ 　  
      ｆｓｔ = fsｔ->nｅxt; 　  
    ｝    
    ｉn ->ｎｅxt ＝ ｆst ->next; 　  
    fｓt ->neｘt = in; 　  
  }    
｝    
void ＰrioCreate() /＊优先级调度输入函数*／ 　  
｛ 　  
  PCB *tｍp;    
  int ｉ；    

  priｎtｆ("输入进程名字与进程所需时间：\n＂）;    
  fｏｒ(i ＝ 0；i < nuｍ; i+＋)    
  {    
    ｉf((tmp = （PCＢ ＊)malloc(ｓizｅｏf(PCB)）)＝＝NＵLL)    
    ｛    
      perror（"malloｃ");    
      exiｔ（1）;    
    }    
    scanｆ（"%s＂,tmp－＞naｍｅ）;    
    getchaｒ();    ／＊吸收回车符号*/ 　  
    scanf(＂%d",&(ｔmp->nｅedtime))；    
    tmｐ ->cputime = ０；    
    ｔｍp ->stａte ＝＇W'； 　  
    tmp ->pｒｉo = 50 － tｍp-＞ｎeedｔｉme;  /*设置其优先级,需要得时间越多,优先级越低*/ 　  
    tmp ->rｏuｎd = ０;    
    tmp －>counｔ = 0;    
    InsｅrtPrio(ｔｍp);      /*按照优先级从高到低，插入到就绪队列*/    
  }    
}    
voiｄ TimｅＣｒeatｅ() ／＊时间片输入函数＊/    
｛    
  ＰCＢ *ｔmp; 　  
  ｉnt i; 　  

  prｉnｔｆ("输入进程名字与进程时间片所需时间：＼ｎ");    
  for(ｉ = ０;i < nuｍ； ｉ＋+)    
  {    
    if((ｔmp = (PCB *)mａlloc(ｓizｅof(PCB)))==NＵLL）    
    {    
      perror("malloc"）;    
      exit(1)； 　  
    }    
    ｓcanf（＂％ｓ",ｔmｐ->ｎame)；    
    ｇeｔchar();    
    scanｆ(＂%d",&(tｍp->nｅedｔime));    
    tmp -＞cｐutime = 0； 　  
    tmp －>staｔe ＝'W'; 　  
    tmp ->ｐriｏ = 0；    
    ｔｍp -＞roｕｎd = 2;  ／*假设每个进程所分配得时间片就是2*／    
    tmp -＞counｔ = 0； 　  
    IｎsｅrtTｉmｅ（tｍp)；    
  } 　  
}    
void Ｐriorｉｔy()   /*按照优先级调度，每次执行一个时间片*/    
{    
  ｉnt flag = 1;    

  GetＦｉｒｓｔ();    
  whｉle(rｕn != NULＬ）  /＊当就绪队列不为空时，则调度进程如执行队列执行*/ 　  
  {    
    Ouｔput（)；  /*输出每次调度过程中各个节点得状态*/ 　  
    whiｌe（ｆlaｇ）    
    {    
      run－>ｐｒiｏ -= 3; /*优先级减去三*/ 　  
      run->ｃpuｔime+＋; /*CPU时间片加一＊／    
      run->ｎeeｄtｉme--;／*进程执行完成得剩余时间减一＊／    
      if(ｒｕn->needtime == 0)/*如果进程执行完毕,将进程状态置为F，将其插入到完成队列*/    
      {    
        ｒun ->ｓtａte = 'F'; 　  
        rｕn－＞ｃount++; /＊进程执行得次数加一*/ 　  
        InｓertFｉｎiｓh(ｒun);    
        ｆｌａg = 0; 　  
      }    
      ｅｌsｅ   ／＊将进程状态置为Ｗ,入就绪队列*／    
      ｛    
        rｕn->state = 'Ｗ＇;    
        run-＞count+＋； /*进程执行得次数加一＊／    
        IｎsertTｉme(rｕn）;    
        flａg = 0;    
      }    
    ｝    
    flａｇ ＝ １; 　  
    GetＦirｓt();    /＊继续取就绪队列队头进程进入执行队列*／    
  } 　  
}    
voｉd ＲoｕnｄRun()    /＊时间片轮转调度算法*／ 　  
{    

  int fｌag = 1；    

  GｅtFirｓt()；    
  ｗｈiｌe(ruｎ != NULＬ)    
  ｛ 　  
    Ｏutput();    
    wｈｉｌe(flaｇ)    
    { 　  
      ｒuｎ－＞ｃount＋＋;    
      rｕn->cputｉmｅ++;    
      run->neｅdｔime－-;    
      if(run－＞ｎeedtｉme ＝= 0) /*进程执行完毕*/    
      {    
        run ->ｓtaｔe = 'F'；    
        ＩnseｒtFinish(ｒun);    
        flag = 0;    
      ｝ 　  
      eｌｓｅ if（ｒuｎ->count == run－>rｏuｎd)/＊时间片用完＊／    
      { 　  
        rｕn->stａｔe = 'W';    
        run->ｃount ＝ 0;   /*计数器清零，为下次做准备*/ 　  
        InserｔTimｅ(rｕn);    
        ｆlag = ０； 　  
      ｝    
    }    
    ｆｌag = 1；    
    GetFｉrst();    
  }    
}