時間片輪轉算法和優(yōu)先級調度算法 C語言模擬實現 收藏

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

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

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

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

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

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

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

8、4. */    #include <stdio.h>    #include <stdlib.h>    #include <string.h>    typedef struct node          char name20;    /*進程的名字*/&

9、#160;     int prio;     /*進程的優(yōu)先級*/      int round;     /*分配CPU的時間片*/      int cputime;    /*CPU執(zhí)行時間*/      int need

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

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

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

13、reate();    /*優(yōu)先級輸入函數*/    void TimeCreate();    /*時間片輸入函數*/    void Priority();    /*按照優(yōu)先級調度*/    void RoundRun();    /*時間片輪轉調度*/    int ma

14、in(void)          char chose;      printf("請輸入要創(chuàng)建的進程數目:n");      scanf("%d",&num);      getchar();      printf("輸入進程的調度方法：(P/R

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

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

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

18、0;void GetFirst()  /*取得第一個就緒隊列節(jié)點*/          run = ready;            if(ready!=NULL)              run ->state =&#

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

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

21、  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、     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 = 

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

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

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

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

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

28、#160;    else                  while(fst->next != NULL)  /*移動指針查找第一個別它小的元素的位置進行插入*/                 &#

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

30、60; if(fst ->next = NULL) /*已經搜索到隊尾，則其優(yōu)先級數最小，將其插入到隊尾即可*/                      in ->next = fst ->next;        &#

31、160;   fst ->next = in;                    else     /*插入到隊列中*/                

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

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

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

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

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

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

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

39、60;            in ->next = fst ->next;        fst ->next = in;              void PrioCreate() /*優(yōu)先級調度

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

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

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

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

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

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

46、60;   for(i = 0;i < num; i+)              if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)                  pe

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

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

49、160;    tmp ->round = 2;  /*假設每個進程所分配的時間片是2*/        tmp ->count = 0;        InsertTime(tmp);              vo

50、id Priority()   /*按照優(yōu)先級調度，每次執(zhí)行一個時間片*/          int flag = 1;            GetFirst();      while(run != NULL)  /*當就緒隊列不為空時，則調度進程如執(zhí)行隊

51、列執(zhí)行*/              Output();  /*輸出每次調度過程中各個節(jié)點的狀態(tài)*/        while(flag)                  run->prio -= 3;

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

53、態(tài)置為F，將其插入到完成隊列*/                      run ->state = 'F'            run->count+; /*進程執(zhí)行的次數加一*/    

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

55、列*/                      run->state = 'W'            run->count+; /*進程執(zhí)行的次數加一*/       

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