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

1、時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法-C語言模擬實現(xiàn)-收藏時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法C語言模擬實現(xiàn)收藏一、目的和要求進程調(diào)度是處理機管理的核心內(nèi)容。本實驗要求用高級語言編寫模擬進程調(diào)度程序，以便加深理解有關(guān)進程控制快、進程隊列等概念，并體會和了解優(yōu)先數(shù)算法和時間片輪轉(zhuǎn)算法的具體實施辦法。二、實驗內(nèi)容i設(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)（RUN）、就緒狀態(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)，共有四個指針如下：RUN當(dāng)前運行進程指

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

4、為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)度進程；I(7) ROUNDSCH按時間片輪轉(zhuǎn)法調(diào)度進程。主程序定義PCB結(jié)構(gòu)和其他有關(guān)變量。(四)運行和顯示程序開始運行后，首先提示：請用戶選擇算法，輸入進程名和相應(yīng)的NEEDTIME值。每次顯示結(jié)果均為如下5個字段：namecputimeneedtimeprioritystate注：1.在state字段中，"R”代表執(zhí)行

5、態(tài)，"W"代表就緒（等待）態(tài)，"F”代表完I成態(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)中，以完成先后順序排隊。viewplaincopytoclipboardprint?I1. /*2. 操作系統(tǒng)實驗之時間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法3. ByVisualC+6.04. */I#include<stdio.h>#include<stdlib.h>#include

6、<string.h>typedefstructnodecharname20;/*進程的名字*/intprio;/*進程的優(yōu)先級*/intround;/*分配CPU的時間片*/intcputime;/*CPU執(zhí)行時間*/intneedtime;/*進程執(zhí)行所需要的時間*/charstate;/*進程的狀態(tài))W就緒態(tài)，R執(zhí)行態(tài)，F(xiàn)完成態(tài)*/intcount;/*記錄執(zhí)行的次數(shù)*/structnode*next;/*鏈表指針*/PCB;PCB*ready=NULL,*run=NULL,*finish=NULL;/*定義三個隊列，就緒隊列，執(zhí)行隊列和完成隊列*/intnum;voidGet

7、First();/*從就緒隊列取得第一個節(jié)點*/voidOutput();/*輸出隊列信息*/voidInsertPrio(PCB*in);/*創(chuàng)建優(yōu)先級隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越高*/voidInsertTime(PCB*in);/*時間片隊列*/voidInsertFinish(PCB*in);/*時間片隊列*/優(yōu)先級輸入時間片輸入按照優(yōu)先級調(diào)度時間片輪轉(zhuǎn)調(diào)voidPrioCreate();/*函數(shù)*/voidTimeCreate();/*函數(shù)*/voidPriority。；/*/voidRoundRun();/*度*/intmain(void)charchose;printf(&qu

8、ot;請輸入要創(chuàng)建的進程數(shù)目：n)；scanf("%d”,&num);printf("輸入進程的調(diào)度方法：n")；scanf("%c”,&chose);switch(chose)case'P':case'p':PrioCreate();Priority。；break;case'R':case'r':TimeCreate();RoundRun();break;defaultbreak;Output();return0;voidGetFirst()/*取得第一個就緒隊列節(jié)點*/r

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

10、->next;p=finish;while(p!=NULL)t%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)t%dtt%ctt%dn",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;voidIns

11、ertPrio(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->prio)/*比第一個還要大，則插入到隊頭*/in->next=ready;ready=in;elsewhile(fst->next!=NULL)/*移動指針查找第一個別它小的元素的位置進行插入*/nxt=fst;fst=fst->nex

12、t;if(fst->next=NULL)/*已經(jīng)搜索到隊尾，則其優(yōu)先級數(shù)最小，將其插入到隊尾即可*/in->next=fst->next;fst->next=in;else/*插入到隊列中*/nxt=in;in->next=fst;voidInsertTime(PCB*in)/*將進程插入到就緒隊列尾部*/PCB*fst;fst=ready;if(ready=NULL)in->next=ready;ready=in;elsewhile(fst->next!=NULL)fst=fst->next;in->next=fst->next;f

13、st->next=in;voidInsertFinish(PCB*in)/*將進程插入到完成隊列尾部*/PCB*fst;fst=finish;if(finish=NULL)in->next=finish;finish=in;elsewhile(fst->next!=NULL)fst=fst->next;in->next=fst->next;fst->next=in;voidPrioCreate()/*優(yōu)先級調(diào)度輸入函數(shù)*/PCB*tmp;inti;printf("輸入進程名字和進程所需時間：n")；for(i=0;i<num;

14、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->round=0;tmp->count=

15、0;InsertPrio(tmp);/*按照優(yōu)先級從高到低，插入到就緒隊列*/voidTimeCreate()/*時間片輸入函數(shù)*/PCB*tmp;inti;printf("輸入進程名字和進程時間片所需時間：n");for(i=0;i<num;i+)if(tmp=(PCB*)malloc(sizeof(PCB)=NULL)perror("malloc");exit(1);scanf("%s",tmp->name);getchar();scanf("%d”,&(tmp->needtime);tmp-&

16、gt;cputime=0;tmp->state='W'tmp->prio=0;tmp->round=2;/*假設(shè)每個進程所分配的時間片是2*/tmp->count=0;InsertTime(tmp);voidPriority。/*按照優(yōu)先級調(diào)度，每次執(zhí)行一個時間片*/intflag=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+;

17、/*CPU時間片加一*/run->needtime-;/*進程執(zhí)行完成的剩余時間減一*/if(run->needtime=0)/*如果進程執(zhí)行完畢，將進程狀態(tài)置為F,將其插入到完成隊列*/run->state='F'run->count+;/*進程執(zhí)行的次數(shù)加一*/InsertFinish(run);flag=0；else/*將進程狀態(tài)置為W,入就緒隊列*/run->state='W'run->count+;/*進程執(zhí)行的次數(shù)加一*/InsertTime(run);flag=0；flag=1；GetFirst();/*繼續(xù)取就緒隊列隊頭進程進入執(zhí)行隊列*/voidRoundRun()/*時間片輪轉(zhuǎn)調(diào)度算法*/intflag=1;GetFirst();while(run!=NULL)Output();while(flag)r