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

1、時間片輪轉(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)、肖前隊列指針等。2. 編寫兩種調(diào)度算法程序：優(yōu)先數(shù)調(diào)度算法程序循環(huán)輪轉(zhuǎn)調(diào)度算法程序3. 按要求輸岀結(jié)果。三、提示和說明分別用兩種調(diào)度算法對伍個進程進行調(diào)度。每個進程可有三種狀態(tài)；執(zhí)行狀態(tài)（R UN）、

2、就緒狀態(tài)（READY,包括等待狀態(tài)）和完成狀態(tài)（FINISH）,并假定初 始狀態(tài)為就緒狀態(tài)。（一）進程控制塊結(jié)構(gòu)如下：NAME一一進程標(biāo)示符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)，共有四個指針如下：RUN一一當(dāng)前運行進程指針READY就需隊列頭指

3、針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）INSERT 1-在優(yōu)先數(shù)算法中，將尚未完成的PCB按優(yōu)先數(shù)順療:插入到就緒隊列中；（2）INSERT2在輪轉(zhuǎn)法中，將執(zhí)行了一個時間片單位（為2）,但尚未

4、完成的進程的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)的NEEDTIME值。每次顯示結(jié)果均為如下5個字段：name cputime needtime piioiity state注:1. 在state字段中,”R代表執(zhí)行態(tài)，”W

5、”代表就緒(等待)態(tài)，”F代表完成態(tài)。2. 應(yīng)先顯示,R態(tài)的,再顯示”W”態(tài)的，再顯示態(tài)的。3. 在態(tài)中，以優(yōu)先數(shù)拓低或輪轉(zhuǎn)順序排隊；在”F”態(tài)中，以完成先后順序 排隊。view plaincopy to clipboardprint?1. /*2. 操作系統(tǒng)實驗之時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法3. By Visual C+ 6.04. */#include #include #include typedef struct nodechar name20;/*進程的名字*/int prio;/*進程的優(yōu)先級*/int round; /*分配CPU的時間片*/int cputime; /*CPU

6、 執(zhí)行時間*/int needtime; /*進程執(zhí)行所需要的時間*/char state;/*進程的狀態(tài)，W一就緒態(tài)，R執(zhí)行態(tài)，F(xiàn)一一完成態(tài)*/int count;/*記錄執(zhí)行的次數(shù)*/struct node *next; /*鏈表指針*/PCB;PCB *ready=NULL,*ruNULL,*finish=NULL; /*泄義三個隊列，就緒隊列,執(zhí)行隊列和完成隊列*/int num;void GetFirst(); /*從就緒隊列取得第一個節(jié)點*/void Output();/*輸出隊列信息*/void InsertPrio(PCB *in); /*創(chuàng)建優(yōu)先級隊列，規(guī)左優(yōu)先數(shù)越小，優(yōu)先級

7、越髙*void InsertTime(PCB *in); /*時間片隊列*/ void InsertFinish(PCB *in); /*時間片隊列*/ void PrioCreate();/*優(yōu)先級輸入函數(shù)*/void TimeCreate();/*時間片輸入函數(shù)*/void Priority();/*按照優(yōu)先級調(diào)度*/void RoundRun(); /*時間片輪轉(zhuǎn)訓(xùn)度*/ int main (void)char chose;printfCiS輸入要創(chuàng)建的進程數(shù)目:n“)；scanf(%dz&num);getchar();printf(“輸入進程的調(diào)度方法:(P/R)nH); scan f

8、(”c 律 &chose);switch(chose)case P:case 0:PrioCreate();Priority();break;case R:case：TimeCreate();RoundRun();break;default:break;Output();return 0;void GetFirst() /*取得第一個就緒隊列節(jié)點*/un = dy;if(ready! = NULL)run -state = R：ready = ready -next;run -next = NULL;void Output() /*輸出隊列信息*/PCB *p;p = ready;printf

9、(”進程名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-namezp-prio,p-roundzp-cputimezp-n eedtimezp-state,p-co un t);p = p-n ext;p = fin ish;while(p!=NULL)printf(,%st%dt%dt%dt%dtt%ctt%dn,zp-namezp-prio,p- round,p-cputimezp-n eedtime,p-state,p-co un t);p = p- next;p = run;w

10、hile(p!=NULL)printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-priozp-rou nd,p-cputime,p-n eedtime,p-state,p-co un t);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-n ext = ready;ready = in;else/*査到合適的位置進行插入*7if(in -prio = fs

11、t -prio) /*比第一個還要大,則插入到隊頭*/in- next = ready;ready = in;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;in next = fst;void InsertTime(PCB *in) /*將進程插入到就緒隊列尾部*

12、/PCB *fst;fst = ready;if (ready = NULL)in- next = ready;ready = in;elsewhile(fst-next != NULL)fst = fst-n ext;in -next = fst ext;fst next = in;void InsertFinish(PCB *in) /*將進程插入到完成隊列尾部*/PCB *fst;fst = finish;if(finish = NULL)in-n ext = fin ish; finish = in;else while(fst-next != NULL)fst = fst-next;

13、in -next = fst -next;fst -next = in;void PrioCreate() /*優(yōu)先級調(diào)度輸入函數(shù)*/PCB *tmp;int i;print輸入進程名字和進程所需時間:n);for(i = 0;i name);getchar(); /*吸收回車符號*/scan f(%d,&(tmp-n eedtime);tmp -cputime = 0;tmp -state =W;tmp -prio = 50 - tmp-needtime; /*設(shè)置其優(yōu)先級,需要的時間越多,優(yōu)先級越低*/tmp -round = 0;tmp -count = 0;InsertPrio(tmp

14、);/*按照優(yōu)先級從高到低，插入到就緒隊列*/void TimeCreate() /*時間片輸入函數(shù)*/PCB *tmp;int i;printf(”輸入進程名字和進程時間片所需時間：n)；for(i = 0;i name);getchar();scanfCd,&(tmp- needtime);tmp -cputime = 0;tmp -statetmp -prio = 0;tmp -round = 2; /*假設(shè)每個進程所分配的時間片是2*/tmp -count = 0;In sertTime(tmp);void Priority() /*按照優(yōu)先級調(diào)度，每次執(zhí)行一個時間片*/int fla

15、g = 1;GetFirst();while(run != NULL) /*當(dāng)就緒隊列不為空時，則調(diào)度進程如執(zhí)行隊列執(zhí)行*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 = F;run-count+; /*進程執(zhí)行的次數(shù)加一*/In sertFi nish(un);flag = 0;else /*將進程狀態(tài)豊為W,入就緒隊列*/run-state = W;run-count+; /*進程執(zhí)行的次數(shù)加一*/InsertTime(run);flag = 0;flag = 1;GetFirst(); /*繼續(xù)取就緒隊列隊頭進程進入執(zhí)行隊列*7void RoundRun() /*時間片輪轉(zhuǎn)調(diào)度算法*/int flag = 1;GetFirst();while(run != NULL)Output();while(flag