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

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

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

3、針READY就需隊(duì)列頭指針TAIL就需隊(duì)列尾指針FINISH完成隊(duì)列頭指針(三)程序說(shuō)明1 .在優(yōu)先數(shù)算法中，進(jìn)程優(yōu)先數(shù)的初值設(shè)為：50-NEEDTIME每執(zhí)行一次，優(yōu)先數(shù)減1,CPU時(shí)間片數(shù)加1,進(jìn)程還需要的時(shí)間片數(shù)減1。在輪轉(zhuǎn)法中，采用固定時(shí)間片單位(兩個(gè)時(shí)間片為一個(gè)單位)，進(jìn)程每輪轉(zhuǎn)一次，CPU時(shí)間片數(shù)加2,進(jìn)程還需要的時(shí)間片數(shù)減2,并退出CPU,排到就緒隊(duì)列尾，等待下一次調(diào)度。2 .程序的模塊結(jié)構(gòu)提示如下：整個(gè)程序可由主程序和如下7個(gè)過(guò)程組成：(1) INSERT1在優(yōu)先數(shù)算法中，將尚未完成的PCB按優(yōu)先數(shù)順序插入到就緒隊(duì)列中；(2) INSERT2在輪轉(zhuǎn)法中，將執(zhí)行了一個(gè)時(shí)間片單位(

4、為2),但尚未完成的進(jìn)程的PCB,插到就緒隊(duì)列的隊(duì)尾；(3) FIRSTIN調(diào)度就緒隊(duì)列的第一個(gè)進(jìn)程投入運(yùn)行；(4) PRINT顯示每執(zhí)行一次后所有進(jìn)程的狀態(tài)及有關(guān)信息。(5) CREATE創(chuàng)建新進(jìn)程，并將它的PCB插入就緒隊(duì)列；(6) PRISCH按優(yōu)先數(shù)算法調(diào)度進(jìn)程；I(7) ROUNDSCH按時(shí)間片輪轉(zhuǎn)法調(diào)度進(jìn)程。主程序定義PCB結(jié)構(gòu)和其他有關(guān)變量。(四)運(yùn)行和顯示程序開(kāi)始運(yùn)行后，首先提示：請(qǐng)用戶選擇算法，輸入進(jìn)程名和相應(yīng)的NEEDTIME值。每次顯示結(jié)果均為如下5個(gè)字段：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)順序排隊(duì)；在"F"態(tài)中，以完成先后順序排隊(duì)。viewplaincopytoclipboardprint?I1. /*2. 操作系統(tǒng)實(shí)驗(yàn)之時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級(jí)調(diào)度算法3. ByVisualC+6.04. */I#include<stdio.h>#include<stdlib.h>#include

6、<string.h>typedefstructnodecharname20;/*進(jìn)程的名字*/intprio;/*進(jìn)程的優(yōu)先級(jí)*/intround;/*分配CPU的時(shí)間片*/intcputime;/*CPU執(zhí)行時(shí)間*/intneedtime;/*進(jìn)程執(zhí)行所需要的時(shí)間*/charstate;/*進(jìn)程的狀態(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;/*定義三個(gè)隊(duì)列，就緒隊(duì)列，執(zhí)行隊(duì)列和完成隊(duì)列*/intnum;voidGet

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

8、ot;請(qǐng)輸入要?jiǎng)?chuàng)建的進(jìn)程數(shù)目：n)；scanf("%d”,&num);printf("輸入進(jìn)程的調(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()/*取得第一個(gè)就緒隊(duì)列節(jié)點(diǎn)*/r

9、un=ready;if(ready!=NULL)run->state='R'ready=ready->next;run->next=NULL;voidOutput()/*輸出隊(duì)列信息*/PCB*p;p=ready;printf("進(jìn)程名t優(yōu)先級(jí)t輪數(shù)tcpu時(shí)間t需要時(shí)間t進(jìn)程狀態(tài)t計(jì)數(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)先級(jí)隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級(jí)越低*/PCB*fst,*nxt;fst=nxt=ready;if(ready=NULL)/*如果隊(duì)列為空，則為第一個(gè)元素*/in->next=ready;ready=in;else/*查到合適的位置進(jìn)行插入*/if(in->prio>=fst->prio)/*比第一個(gè)還要大，則插入到隊(duì)頭*/in->next=ready;ready=in;elsewhile(fst->next!=NULL)/*移動(dòng)指針查找第一個(gè)別它小的元素的位置進(jìn)行插入*/nxt=fst;fst=fst->nex

12、t;if(fst->next=NULL)/*已經(jīng)搜索到隊(duì)尾，則其優(yōu)先級(jí)數(shù)最小，將其插入到隊(duì)尾即可*/in->next=fst->next;fst->next=in;else/*插入到隊(duì)列中*/nxt=in;in->next=fst;voidInsertTime(PCB*in)/*將進(jìn)程插入到就緒隊(duì)列尾部*/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)/*將進(jìn)程插入到完成隊(duì)列尾部*/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)先級(jí)調(diào)度輸入函數(shù)*/PCB*tmp;inti;printf("輸入進(jìn)程名字和進(jìn)程所需時(shí)間：n")；for(i=0;i<num;

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

15、0;InsertPrio(tmp);/*按照優(yōu)先級(jí)從高到低，插入到就緒隊(duì)列*/voidTimeCreate()/*時(shí)間片輸入函數(shù)*/PCB*tmp;inti;printf("輸入進(jìn)程名字和進(jìn)程時(shí)間片所需時(shí)間：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è)每個(gè)進(jìn)程所分配的時(shí)間片是2*/tmp->count=0;InsertTime(tmp);voidPriority。/*按照優(yōu)先級(jí)調(diào)度，每次執(zhí)行一個(gè)時(shí)間片*/intflag=1;GetFirst();while(run!=NULL)/*當(dāng)就緒隊(duì)列不為空時(shí)，則調(diào)度進(jìn)程如執(zhí)行隊(duì)列執(zhí)行*/Output();/*輸出每次調(diào)度過(guò)程中各個(gè)節(jié)點(diǎn)的狀態(tài)*/while(flag)run->prio-=3;/*優(yōu)先級(jí)減去三*/run->cputime+;

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