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

2、態（RUN）、就緒狀態（READY包括等待狀態）和完成狀態（FINISH），并假定 初始狀態為就緒狀態。（一）進程控制塊結構如下：NAME 進程標示符PRIO/ROUND 進程優先數/進程每次輪轉的時間片數 （設為常數2）CPUTIME 進程累計占用CPU的時間片數STATE進程狀態NEXT 鏈指針注：1. 為了便于處理，程序中進程的的運行時間以時間片為單位進行計算 ；2. 各進程的優先數或輪轉時間片數，以及進程運行時間片數的初值，均由用 戶在程序運行時給定。（二）進程的就緒態和等待態均為鏈表結構，共有四個指針如下：RUN 當前運行進程指針READY 就需隊列頭指針TAIL 就需隊列尾指針FI

3、NISH 完成隊列頭指針（三）程序說明1. 在優先數算法中，進程優先數的初值設為：50-NEEDTIME每執行一次，優先數減1，CPU時間片數加1，進程還需要的時間片數減1。 在輪轉法中，采用固定時間片單位（兩個時間片為一個單位），進程每輪轉一 次，CPU時間片數加2，進程還需要的時間片數減2，并退出CPU，排到就緒隊 列尾，等待下一次調度。2. 程序的模塊結構提示如下：整個程序可由主程序和如下7個過程組成：（1）INSERT1在優先數算法中，將尚未完成的PCB按優先數順序插入到就緒隊列中;（2） INSERT2在輪轉法中，將執行了一個時間片單位（為2）,但尚未完 成的進程的PCB,插到就緒隊

4、列的隊尾；（3）FIRSTIN調度就緒隊列的第一個進程投入運行 ；（4） PRINT顯示每執行一次后所有進程的狀態及有關信息。（5） CREATE創建新進程，并將它的PCB插入就緒隊列；（6） PRISCH按優先數算法調度進程；（7）ROUNDSCH 按時間片輪轉法調度進程。主程序定義PCB結構和其他有關變量。（四）運行和顯示程序開始運行后，首先提示：請用戶選擇算法，輸入進程名和相應的NEEDTIM E值。每次顯示結果均為如下5個字段：n amecputimen eedtimepriority state注：1 .在state字段中，"R"代表執行態，"W&quo

5、t;代表就緒（等待）態，"F"代表完 成態。2.應先顯示"R"態的，再顯示"W"態的，再顯示"F"態的。3 .在"W"態中，以優先數高低或輪轉順序排隊；在"F"態中，以完成先后順序 排隊。view pla in copy to clipboardpri nt?2. 操作系統實驗之時間片輪轉算法和優先級調度算法3. By Visual C+ 6.04. */#i nclude <stdio.h>#i nclude <stdlib.h>#in clude

6、<stri ng.h>typedef struct nodechar name20; /*進程的名字 */int prio; /* 進程的優先級*/int round; /* 分配CPU的時間片*/int cputime; /*CPU 執行時間 */int needtime; /*進程執行所需要的時間*/char state; /* 進程的狀態，W就緒態，R執行態，F完成態*/int count; /*記錄執行的次數*/struct node *next; /*鏈表指針 */PCB;PCB *ready=NULL,*run=NULL,*finish=NULL; /*定義三個隊列，就

7、緒隊列，執行隊列和完成隊列*/int num;void GetFirst(); /*從就緒隊列取得第一個節點*/void Output。；/*輸出隊列信息*/void InsertPrio(PCB *in); /* 創建優先級隊列，規定優先數越小，優先級越高*/void InsertTime(PCB *in); /* 時間片隊列 */void InsertFinish(PCB *in); /* 時間片隊列 */void PrioCreate(); /*優先級輸入函數*/void TimeCreate(); /*時間片輸入函數*/void Priority。； /*按照優先級調度*/void R

8、oundRun(); /*時間片輪轉調度*/int main(-void)char chose;printf(”請輸入要創建的進程數目:n");sca nf("%d",&n um);getchar();printf("輸入進程的調度方法：(P/R)n");sca nf("%c",&chose);switch(chose)case 'P':case 'p':PrioCreate();Priority();break;case 'R': case 'r

9、9;:TimeCreate();Rou ndRu n();break;default:break;Output。；return 0;void GetFirst() /*取得第一個就緒隊列節點*/run = ready;if(ready!=NULL)run ->state = 'R'ready = ready ->n ext;run ->next = NULL;void Output() /*輸出隊列信息*/PCB *p;p = ready;printf("進程名t優先級t輪數tcpu 時間t需要時間t進程狀態t計數器n”)；while(p!=NULL

10、)prin tf("%st%dt%dt%dt%dtt%ctt%dn",p-> name,p->prio,p->roun d,p->cputime,p->n eedtime,p->state,p->co un t);p = p_>n ext;p = fin ish;while(p!=NULL)prin tf("%st%dt%dt%dt%dtt%ctt%dn",p-> name,p->prio,p->roun d,p->cputime,p->n eedtime,p->stat

11、e,p->co un t);p = p_>n ext;p = run;while(p!=NULL)prin tf("%st%dt%dt%dt%dtt%ctt%dn",p-> name,p->prio,p->roun d,p->cputime,p->n eedtime,p->state,p->co un t);p = p_>n ext;void InsertPrio(PCB *in) /*創建優先級隊列，規定優先數越小，優先級越低*/PCB *fst,* nxt;fst = nxt = ready;if(ready

12、= NULL) /*如果隊列為空，則為第一個元素*/in->n ext = ready;ready = in;else /*查到合適的位置進行插入*/if(in ->prio >= fst ->prio) /*比第一個還要大，則插入到隊頭*/in->next = ready;ready = in;elsewhile(fst- >n ext != NULL) /* 移動指針查找第一個別它小的元素的位置進行插 入*/nxt = fst;fst = fst->n ext;if(fst ->next = NULL)/*已經搜索到隊尾，則其優先級數最小，將

13、其插入到隊尾即可*/in ->n ext = fst ->n ext;fst ->n ext = in;else /* 插入到隊列中*/nxt = in;in ->n ext = fst;void In sertTime(PCB *in) /*將進程插入到就緒隊列尾部*/PCB *fst;fst = ready;if(ready = NULL)in->n ext = ready;ready = in;elsewhile(fst-> next != NULL)fst = fst- >n ext;in ->n ext = fst ->n ext

14、;fst ->next = in;void In sertFi ni sh(PCB *in) /*將進程插入到完成隊列尾部*/PCB *fst;fst = fini sh;if(fi nish = NULL)in->n ext = fini sh;finish = in;elsewhile(fst-> next != NULL)fst = fst- >n ext;in ->n ext = fst ->n ext;fst ->next = in;void PrioCreate() /*優先級調度輸入函數*/PCB *tmp;int i;printf(”輸

15、入進程名字和進程所需時間：n");for(i = 0;i < num; i+)if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);sca nf("%s",tmp->n ame);getchar(); /*吸收回車符號*/scan f("%d",&( tmp-> needtime);tmp ->cputime = 0;tmp ->state =W;tmp ->prio = 50 - tmp->need

16、time; /*設置其優先級，需要的時間越多，優先級越低*/tmp ->round = 0;tmp ->co unt = 0;InsertPrio(tmp); /* 按照優先級從高到低，插入到就緒隊列*/void TimeCreate()/*時間片輸入函數*/PCB *tmp;int i;printf(”輸入進程名字和進程時間片所需時間：n");for(i = 0;i < num; i+)if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);sca nf("%s

17、",tmp->n ame);getchar();scan f("%d",&( tmp-> needtime);tmp ->cputime = 0;tmp ->state =W;tmp ->prio = 0;tmp ->rou nd = 2; /*假設每個進程所分配的時間片是tmp ->co unt = 0;In sertTime(tmp);void Priority。/*按照優先級調度，每次執行一個時間片*/int flag = 1;GetFirst();while(run != NULL) /* 當就緒隊列不為空

18、時，則調度進程如執行隊列執行*/Output(); /*輸出每次調度過程中各個節點的狀態*/while(flag)run->prio -= 3; /*優先級減去三*/run->cputime+; /*CPU 時間片加一 */run-> needtime-;/*進程執行完成的剩余時間減一*/if(run->needtime = 0)/*如果進程執行完畢，將進程狀態置為 F,將其插入到完成隊列*/run ->state = 'F'run->cou nt+; /*進程執行的次數加一 */In sertF ini sh(r un);flag = 0;else /*將進程狀態置為 W,入就緒隊列*/run->state = W;run->cou nt+; /*進程執行的次數加一 */In sertTime(ru n);flag = 0;flag = 1;GetFirst(); /*繼續取就緒隊列隊頭進程進入執行隊列*/void Rou ndRu n() /*時間片輪轉調度算法 */int flag = 1;GetFirst();while(ru n != NULL)Output();while(flag)