時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法c語言模擬實現(xiàn)收藏培訓(xùn)講學(xué)

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

2、 每個進程可有三種狀態(tài)； 執(zhí)行狀態(tài)（ R UN）、就緒狀態(tài)（ READY, 包括等待狀態(tài)）和完成狀態(tài)（ FINISH ），并假定初始狀態(tài)為就緒狀態(tài)。（一）進程控制塊結(jié)構(gòu)如下：NAME 進程標示符PRIO/ROUND 進程優(yōu)先數(shù) /進程每次輪轉(zhuǎn)的時間片數(shù)（設(shè)為常數(shù)2）CPUTIME 進程累計占用 CPU 的時間片數(shù)NEEDTIME 進程到完成還需要的時間片數(shù)STATE 進程狀態(tài)NEXT 鏈指針注：1.為了便于處理，程序中進程的的運行時間以時間片為單位進行計算；2.各進程的優(yōu)先數(shù)或輪轉(zhuǎn)時間片數(shù)，以及進程運行時間片數(shù)的初值，均由用戶在程序運行時給定。（二）進程的就緒態(tài)和等待態(tài)均為鏈表結(jié)構(gòu)，共有四個指

3、針如下：只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除RUN 當(dāng)前運行進程指針READY 就需隊列頭指針TAIL 就需隊列尾指針FINISH 完成隊列頭指針（三）程序說明1. 在優(yōu)先數(shù)算法中，進程優(yōu)先數(shù)的初值設(shè)為：50-NEEDTIME每執(zhí)行一次，優(yōu)先數(shù)減1， CPU 時間片數(shù)加 1，進程還需要的時間片數(shù)減1。在輪轉(zhuǎn)法中，采用固定時間片單位 （兩個時間片為一個單位） ，進程每輪轉(zhuǎn)一次，CPU 時間片數(shù)加 2，進程還需要的時間片數(shù)減2，并退出 CPU，排到就緒隊列尾，等待下一次調(diào)度。2. 程序的模塊結(jié)構(gòu)提示如下：整個程序可由主程序和如下 7 個過程組成：（ 1）INSERT1 在優(yōu)先

4、數(shù)算法中， 將尚未完成的 PCB 按優(yōu)先數(shù)順序插入到就緒隊列中；（ 2） INSERT2 在輪轉(zhuǎn)法中，將執(zhí)行了一個時間片單位（為 2），但尚未完成的進程的 PCB，插到就緒隊列的隊尾；（ 3） FIRSTIN 調(diào)度就緒隊列的第一個進程投入運行；（ 4） PRINT 顯示每執(zhí)行一次后所有進程的狀態(tài)及有關(guān)信息。（ 5） CREATE 創(chuàng)建新進程，并將它的 PCB 插入就緒隊列；（ 6） PRISCH 按優(yōu)先數(shù)算法調(diào)度進程；（ 7） ROUNDSCH 按時間片輪轉(zhuǎn)法調(diào)度進程。主程序定義 PCB 結(jié)構(gòu)和其他有關(guān)變量。（四）運行和顯示程序開始運行后，首先提示：請用戶選擇算法，輸入進程名和相應(yīng)的NEEDT

5、IME 值。每次顯示結(jié)果均為如下5 個字段：namecputimeneedtimeprioritystate注：只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除1在 state字段中， "R" 代表執(zhí)行態(tài)， "W" 代表就緒（等待）態(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)順序排隊；在"F" 態(tài)中，以完成先后順序排隊。viewplainc

6、opytoclipboardprint?1. /*2. 操作系統(tǒng)實驗之時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法3. By Visual C+ 6.04. */#include <stdio.h>#include <stdlib.h>#include <string.h>typedef struct nodecharname20;/*進程的名字 */intprio; /*進程的優(yōu)先級 */intround;/*分配 CPU 的時間片 */intcputime;/*CPU執(zhí)行時間 */intneedtime; /*進程執(zhí)行所需要的時間 */charstate;/*進程的狀

7、態(tài)， W 就緒態(tài)，R 執(zhí)行態(tài)，F(xiàn) 完成態(tài) */intcount;/*記錄執(zhí)行的次數(shù) */struct node *next;/*鏈表指針 */PCB;PCB *ready=NULL,*run=NULL,*finish=NULL; /*定義三個隊列，就緒隊列，執(zhí)行隊列和完成隊列*/int num;void GetFirst();/*從就緒隊列取得第一個節(jié)點*/void Output();/*輸出隊列信息 */只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除void InsertPrio(PCB *in); /*創(chuàng)建優(yōu)先級隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越高*/void InsertTime

8、(PCB *in); /*時間片隊列*/void InsertFinish(PCB *in); /*時間片隊列*/void PrioCreate();/*優(yōu)先級輸入函數(shù)*/void TimeCreate();/*時間片輸入函數(shù)*/void Priority();/*按照優(yōu)先級調(diào)度*/void RoundRun();/*時間片輪轉(zhuǎn)調(diào)度*/intmain(void)charchose;printf("請輸入要創(chuàng)建的進程數(shù)目:n");scanf("%d",&num);getchar();printf("輸入進程的調(diào)度方法：(P/R)n&quo

9、t;);scanf("%c",&chose);switch(chose)case 'P':case 'p':PrioCreate();Priority();break;case 'R':case 'r':TimeCreate();RoundRun();break;default:break;只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除Output();return 0;void GetFirst() /*取得第一個就緒隊列節(jié)點*/run = ready;if(ready!=NULL)run

10、 ->state = 'R'ready = ready ->next;run ->next = NULL;void Output()/*輸出隊列信息 */PCB *p;p = ready;printf("進程名 t 優(yōu)先級 t 輪數(shù) tcpu時間 t 需要時間 t 進程狀態(tài) t計數(shù)器 n");while(p!=NULL)printf("%st%dt%dt%dt%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p->needtime,p->

11、state,p->count);p = p->next;p = finish;while(p!=NULL)只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除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 = run;while(p!=NULL)printf("%st%dt%dt%dt%dtt%ctt%dn",p

12、->name,p->prio,p ->round,p->cputime,p->needtime,p->state,p->count);p = p->next;void InsertPrio(PCB *in) /*創(chuàng)建優(yōu)先級隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/PCB *fst,*nxt;fst = nxt = ready;if(ready = NULL) /*如果隊列為空，則為第一個元素*/in->next = ready;ready = in;else/*查到合適的位置進行插入*/if(in ->prio >= fst ->

13、;prio) /*比第一個還要大，則插入到隊頭*/in->next = ready;ready = in;只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除elsewhile(fst->next != NULL) /*移動指針查找第一個別它小的元素的位置進行插入 */nxt = fst;fst = fst->next;if(fst ->next = NULL) /*已經(jīng)搜索到隊尾，則其優(yōu)先級數(shù)最小，將其插入到隊尾即可 */in ->next = fst ->next;fst ->next = in;else/*插入到隊列中 */nxt = in

14、;in ->next = fst;void InsertTime(PCB *in) /*將進程插入到就緒隊列尾部*/PCB *fst;fst = ready;if(ready = NULL)只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除in->next = ready;ready = in;elsewhile(fst->next != NULL)fst = fst->next;in ->next = fst ->next;fst ->next = in;void InsertFinish(PCB *in) /*將進程插入到完成隊列尾部*/P

15、CB *fst;fst = finish;if(finish = NULL)in->next = finish;finish = in;elsewhile(fst->next != NULL)fst = fst->next;in ->next = fst ->next;只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除fst ->next = in;void PrioCreate() /*優(yōu)先級調(diào)度輸入函數(shù)*/PCB *tmp;inti;printf("輸入進程名字和進程所需時間：n");for(i = 0;i < num;

16、 i+)if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);scanf("%s",tmp->name);getchar(); /* 吸收回車符號 scanf("%d",&(tmp->needtime); tmp ->cputime = 0; tmp ->state ='W'*/tmp ->prio = 50 - tmp->needtime; /*設(shè)置其優(yōu)先級，需要的時間越多，優(yōu)先級越低 */tmp

17、->round = 0;tmp ->count = 0;InsertPrio(tmp);/*按照優(yōu)先級從高到低，插入到就緒隊列*/void TimeCreate() /*時間片輸入函數(shù)*/只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除PCB *tmp;inti;printf("輸入進程名字和進程時間片所需時間：n");for(i = 0;i < num; i+)if(tmp = (PCB *)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);scanf("%s&quo

18、t;,tmp->name);getchar();scanf("%d",&(tmp->needtime);tmp ->cputime = 0;tmp ->state ='W'tmp ->prio = 0;tmp ->round = 2; /*假設(shè)每個進程所分配的時間片是2*/tmp ->count = 0;InsertTime(tmp);void Priority()/*按照優(yōu)先級調(diào)度，每次執(zhí)行一個時間片*/intflag = 1;GetFirst();while(run != NULL) /*當(dāng)就緒隊列不為空時，則調(diào)度進程如執(zhí)行隊列執(zhí)行*/只供學(xué)習(xí)與交流此文檔僅供收集于網(wǎng)絡(luò)，如有侵權(quán)請聯(lián)系網(wǎng)站刪除Output(); /*輸出每次調(diào)度過程中各個節(jié)點的狀態(tài)*/while(flag)run->prio -= 3; /*優(yōu)先級減去三*/run->cputime+; /*CPU時間片加一*/run->needtime-;/*進程執(zhí)行完成的剩余時間減一*/if(run->needtime = 0)/*如果進程執(zhí)行完畢，將進程狀態(tài)置為F，將其插入到完成隊列*/run ->state = '