時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法 C語(yǔ)言模擬實(shí)現(xiàn) 收藏

1、時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法 C語(yǔ)言模擬實(shí)現(xiàn) 收藏 一、目的和要求進(jìn)程調(diào)度是處理機(jī)管理的核心內(nèi)容。本實(shí)驗(yàn)要求用高級(jí)語(yǔ)言編寫模擬進(jìn)程調(diào)度程序，以便加深理解有關(guān)進(jìn)程控制快、進(jìn)程隊(duì)列等概念，并體會(huì)和了解優(yōu)先數(shù)算法和時(shí)間片輪轉(zhuǎn)算法的具體實(shí)施辦法。二、實(shí)驗(yàn)內(nèi)容1.設(shè)計(jì)進(jìn)程控制塊PCB的結(jié)構(gòu)，通常應(yīng)包括如下信息：進(jìn)程名、進(jìn)程優(yōu)先數(shù)（或輪轉(zhuǎn)時(shí)間片數(shù)）、進(jìn)程已占用的CPU時(shí)間、進(jìn)程到完成還需要的時(shí)間、進(jìn)程的狀態(tài)、當(dāng)前隊(duì)列指針等。  2.編寫兩種調(diào)度算法程序：優(yōu)先數(shù)調(diào)度算法程序循環(huán)輪轉(zhuǎn)調(diào)度算法程序3.按要求輸出結(jié)果。三、提示和說(shuō)明分別用兩種調(diào)度算法對(duì)伍個(gè)進(jìn)程進(jìn)行調(diào)度。每個(gè)進(jìn)程可有三種狀態(tài)；

2、執(zhí)行狀態(tài)（RUN）、就緒狀態(tài)（READY,包括等待狀態(tài)）和完成狀態(tài)（FINISH），并假定初始狀態(tài)為就緒狀態(tài)。（一）進(jìn)程控制塊結(jié)構(gòu)如下：      NAME進(jìn)程標(biāo)示符      PRIO/ROUND進(jìn)程優(yōu)先數(shù)/進(jìn)程每次輪轉(zhuǎn)的時(shí)間片數(shù)（設(shè)為常數(shù)2）      CPUTIME進(jìn)程累計(jì)占用CPU的時(shí)間片數(shù)      NEEDTIME進(jìn)程到完成還需要的時(shí)間片數(shù)

3、60;     STATE進(jìn)程狀態(tài)      NEXT鏈指針注：    1.為了便于處理，程序中進(jìn)程的的運(yùn)行時(shí)間以時(shí)間片為單位進(jìn)行計(jì)算；    2.各進(jìn)程的優(yōu)先數(shù)或輪轉(zhuǎn)時(shí)間片數(shù)，以及進(jìn)程運(yùn)行時(shí)間片數(shù)的初值，均由用戶在程序運(yùn)行時(shí)給定。（二）進(jìn)程的就緒態(tài)和等待態(tài)均為鏈表結(jié)構(gòu)，共有四個(gè)指針如下：      RUN當(dāng)前運(yùn)行進(jìn)程指針  &

4、#160;   READY就需隊(duì)列頭指針      TAIL就需隊(duì)列尾指針      FINISH完成隊(duì)列頭指針（三）程序說(shuō)明    1. 在優(yōu)先數(shù)算法中，進(jìn)程優(yōu)先數(shù)的初值設(shè)為：      50-NEEDTIME每執(zhí)行一次，優(yōu)先數(shù)減1，CPU時(shí)間片數(shù)加1，進(jìn)程還需要的時(shí)間片數(shù)減1。在輪轉(zhuǎn)法中，采用固定時(shí)間片單位（兩個(gè)時(shí)間片為一個(gè)單位），進(jìn)程每輪轉(zhuǎn)一

5、次，CPU時(shí)間片數(shù)加2，進(jìn)程還需要的時(shí)間片數(shù)減2，并退出CPU，排到就緒隊(duì)列尾，等待下一次調(diào)度。    2. 程序的模塊結(jié)構(gòu)提示如下：整個(gè)程序可由主程序和如下7個(gè)過(guò)程組成：（1）INSERT1在優(yōu)先數(shù)算法中，將尚未完成的PCB按優(yōu)先數(shù)順序插入到就緒隊(duì)列中；（2）INSERT2在輪轉(zhuǎn)法中，將執(zhí)行了一個(gè)時(shí)間片單位（為2），但尚未完成的進(jìn)程的PCB，插到就緒隊(duì)列的隊(duì)尾；（3）FIRSTIN調(diào)度就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行；（4）PRINT顯示每執(zhí)行一次后所有進(jìn)程的狀態(tài)及有關(guān)信息。（5）CREATE創(chuàng)建新進(jìn)程，并將它的PCB插入就緒隊(duì)列；（6）PRISCH按優(yōu)先

6、數(shù)算法調(diào)度進(jìn)程；（7）ROUNDSCH按時(shí)間片輪轉(zhuǎn)法調(diào)度進(jìn)程。主程序定義PCB結(jié)構(gòu)和其他有關(guān)變量。（四）運(yùn)行和顯示程序開始運(yùn)行后，首先提示：請(qǐng)用戶選擇算法，輸入進(jìn)程名和相應(yīng)的NEEDTIME值。每次顯示結(jié)果均為如下5個(gè)字段：      name   cputime   needtime   priority   state注：    1在state字段中，"R"代表執(zhí)行態(tài)，"W"

7、;代表就緒（等待）態(tài)，"F"代表完成態(tài)。2應(yīng)先顯示"R"態(tài)的，再顯示"W"態(tài)的，再顯示"F"態(tài)的。  3在"W"態(tài)中，以優(yōu)先數(shù)高低或輪轉(zhuǎn)順序排隊(duì)；在"F"態(tài)中，以完成先后順序排隊(duì)。view plaincopy to clipboardprint?1. /*   2. 操作系統(tǒng)實(shí)驗(yàn)之時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法   3. By Visual C+ 6.0   4. *

8、/    #include <stdio.h>    #include <stdlib.h>    #include <string.h>    typedef struct node          char name20;    /*進(jìn)程的名字*/ 

9、;     int prio;     /*進(jìn)程的優(yōu)先級(jí)*/      int round;     /*分配CPU的時(shí)間片*/      int cputime;    /*CPU執(zhí)行時(shí)間*/      int needtime

10、;    /*進(jìn)程執(zhí)行所需要的時(shí)間*/      char state;     /*進(jìn)程的狀態(tài)，W就緒態(tài)，R執(zhí)行態(tài)，F(xiàn)完成態(tài)*/      int count;     /*記錄執(zhí)行的次數(shù)*/      struct node *next;  &#

11、160;/*鏈表指針*/    PCB;    PCB *ready=NULL,*run=NULL,*finish=NULL; /*定義三個(gè)隊(duì)列，就緒隊(duì)列，執(zhí)行隊(duì)列和完成隊(duì)列*/    int num;    void GetFirst();    /*從就緒隊(duì)列取得第一個(gè)節(jié)點(diǎn)*/    void Output();   

12、60; /*輸出隊(duì)列信息*/    void InsertPrio(PCB *in);  /*創(chuàng)建優(yōu)先級(jí)隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級(jí)越高*/    void InsertTime(PCB *in);  /*時(shí)間片隊(duì)列*/    void InsertFinish(PCB *in);  /*時(shí)間片隊(duì)列*/    void PrioCreat

13、e();    /*優(yōu)先級(jí)輸入函數(shù)*/    void TimeCreate();    /*時(shí)間片輸入函數(shù)*/    void Priority();    /*按照優(yōu)先級(jí)調(diào)度*/    void RoundRun();    /*時(shí)間片輪轉(zhuǎn)調(diào)度*/    int main(v

14、oid)          char chose;      printf("請(qǐng)輸入要?jiǎng)?chuàng)建的進(jìn)程數(shù)目:n");      scanf("%d",&num);      getchar();      printf("輸入進(jìn)程的調(diào)度方法：(P/R)n&q

15、uot;);      scanf("%c",&chose);      switch(chose)            case 'P':      case 'p':        PrioCr

16、eate();        Priority();            break;      case 'R':      case 'r':        TimeCreate();

17、0;       RoundRun();        break;      default:break;            Output();      return 0;        vo

18、id GetFirst()  /*取得第一個(gè)就緒隊(duì)列節(jié)點(diǎn)*/          run = ready;            if(ready!=NULL)              run ->state = 

19、'R'        ready = ready ->next;        run ->next = NULL;              void Output()    /*輸出隊(duì)列信息*/ 

20、        PCB *p;      p = ready;      printf("進(jìn)程名t優(yōu)先級(jí)t輪數(shù)tcpu時(shí)間t需要時(shí)間t進(jìn)程狀態(tài)t計(jì)數(shù)器n");      while(p!=NULL)            

21、0; printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);        p = p->next;            p = finish; 

22、60;   while(p!=NULL)              printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);        p = p-&

23、gt;next;            p = run;      while(p!=NULL)              printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p-

24、>needtime,p->state,p->count);        p = p->next;              void InsertPrio(PCB *in) /*創(chuàng)建優(yōu)先級(jí)隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級(jí)越低*/          PCB *

25、fst,*nxt;      fst = nxt = ready;            if(ready = NULL)  /*如果隊(duì)列為空，則為第一個(gè)元素*/              in->next = ready;

26、        ready = in;            else     /*查到合適的位置進(jìn)行插入*/              if(in ->prio >= fst ->

27、prio)  /*比第一個(gè)還要大，則插入到隊(duì)頭*/                  in->next = ready;          ready = in;            

28、;    else                  while(fst->next != NULL)  /*移動(dòng)指針查找第一個(gè)別它小的元素的位置進(jìn)行插入*/                  

29、    nxt = fst;            fst = fst->next;                             &

30、#160;if(fst ->next = NULL) /*已經(jīng)搜索到隊(duì)尾，則其優(yōu)先級(jí)數(shù)最小，將其插入到隊(duì)尾即可*/                      in ->next = fst ->next;         

31、   fst ->next = in;                    else     /*插入到隊(duì)列中*/                 &#

32、160;    nxt = in;            in ->next = fst;                            

33、0;   void InsertTime(PCB *in)  /*將進(jìn)程插入到就緒隊(duì)列尾部*/          PCB *fst;      fst = ready;            if(ready = NULL)    

34、;          in->next = ready;        ready = in;            else              while(fst-

35、>next != NULL)                  fst = fst->next;                in ->next = fst ->next;  

36、0;     fst ->next = in;              void InsertFinish(PCB *in)  /*將進(jìn)程插入到完成隊(duì)列尾部*/          PCB *fst;      fst

37、60;= finish;            if(finish = NULL)              in->next = finish;        finish = in;     

38、;       else              while(fst->next != NULL)                  fst = fst->next;    &

39、#160;           in ->next = fst ->next;        fst ->next = in;              void PrioCreate() /*優(yōu)先級(jí)調(diào)度輸入函數(shù)

40、*/          PCB *tmp;      int i;            printf("輸入進(jìn)程名字和進(jìn)程所需時(shí)間：n");      for(i = 0;i < num; i+)   

41、           if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)                  perror("malloc");          exit

42、(1);                scanf("%s",tmp->name);        getchar();    /*吸收回車符號(hào)*/        scanf("%d",&(tmp->needtime);

43、        tmp ->cputime = 0;        tmp ->state ='W'        tmp ->prio = 50 - tmp->needtime;  /*設(shè)置其優(yōu)先級(jí)，需要的時(shí)間越多，優(yōu)先級(jí)越低*

44、/        tmp ->round = 0;        tmp ->count = 0;        InsertPrio(tmp);      /*按照優(yōu)先級(jí)從高到低，插入到就緒隊(duì)列*/     

45、0;        void TimeCreate() /*時(shí)間片輸入函數(shù)*/          PCB *tmp;      int i;            printf("輸入進(jìn)程名字和進(jìn)程時(shí)間片所需時(shí)間：n");   &

46、#160;  for(i = 0;i < num; i+)              if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)                  perror

47、("malloc");          exit(1);                scanf("%s",tmp->name);        getchar();        

48、;scanf("%d",&(tmp->needtime);        tmp ->cputime = 0;        tmp ->state ='W'        tmp ->prio = 0;    

49、    tmp ->round = 2;  /*假設(shè)每個(gè)進(jìn)程所分配的時(shí)間片是2*/        tmp ->count = 0;        InsertTime(tmp);              void&#

50、160;Priority()   /*按照優(yōu)先級(jí)調(diào)度，每次執(zhí)行一個(gè)時(shí)間片*/          int flag = 1;            GetFirst();      while(run != NULL)  /*當(dāng)就緒隊(duì)列不為空時(shí)，則調(diào)度進(jìn)程如執(zhí)行隊(duì)列執(zhí)行*

51、/              Output();  /*輸出每次調(diào)度過(guò)程中各個(gè)節(jié)點(diǎn)的狀態(tài)*/        while(flag)                  run->prio -= 3;

52、0;/*優(yōu)先級(jí)減去三*/          run->cputime+; /*CPU時(shí)間片加一*/          run->needtime-;/*進(jìn)程執(zhí)行完成的剩余時(shí)間減一*/          if(run->needtime = 0)/*如果進(jìn)程執(zhí)行完畢，將進(jìn)程狀態(tài)置為F

53、，將其插入到完成隊(duì)列*/                      run ->state = 'F'            run->count+; /*進(jìn)程執(zhí)行的次數(shù)加一*/    

54、60;       InsertFinish(run);            flag = 0;                    else   /*將進(jìn)程狀態(tài)置為W，入就緒隊(duì)列*/&

55、#160;                     run->state = 'W'            run->count+; /*進(jìn)程執(zhí)行的次數(shù)加一*/       

56、0;    InsertTime(run);            flag = 0;                          flag = 1;        GetFirst();    /*繼續(xù)取就緒隊(duì)列隊(duì)頭進(jìn)程進(jìn)入執(zhí)行隊(duì)列*/              void RoundRun()    /*時(shí)間片輪轉(zhuǎn)調(diào)度算法*/