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

1、時(shí)間片輪轉(zhuǎn)算法和優(yōu)先級調(diào)度算法C 語言模擬實(shí)現(xiàn)收藏一、目的和要求進(jìn)程調(diào)度是處理機(jī)管理的核心內(nèi)容。本實(shí)驗(yàn)要求用高級語言編寫模擬進(jìn)程調(diào)度程序，以便加深理解有關(guān)進(jìn)程控制快、進(jìn)程隊(duì)列等概念，并體會和了解優(yōu)先數(shù)算法和時(shí)間片輪轉(zhuǎn)算法的具體實(shí)施辦法。二、實(shí)驗(yàn)內(nèi)容1 .設(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é)果。三、提示和說明分別用兩種調(diào)度算法對伍個(gè)進(jìn)程進(jìn)行調(diào)度。每個(gè)進(jìn)程可有三種狀態(tài)；執(zhí)行狀態(tài) （ RU

2、N）、就緒狀態(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)程指針READY 就需隊(duì)列

3、頭指針TAIL 就需隊(duì)列尾指針FINISH 完成隊(duì)列頭指針（三）程序說明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è)過程組成：（ 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)程；（ 7） ROUNDSCH 按時(shí)間片輪轉(zhuǎn)法調(diào)度進(jìn)程。主程序定義PCB 結(jié)構(gòu)和其他有關(guān)變量。（四）運(yùn)行和顯示程序開始運(yùn)行后，首先提示：請用戶選擇算法，輸入進(jìn)程名和相應(yīng)的NEEDTIME 值。每次顯示結(jié)果均為如下5 個(gè)字段：name cputime needtime priority state注：1在

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

6、t cputime; /*CPU 執(zhí)行時(shí)間*/int needtime; /* 進(jìn)程執(zhí)行所需要的時(shí)間*/char state; /* 進(jìn)程的狀態(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,*run=NULL,*finish=NULL; /*定義三個(gè)隊(duì)列，就緒隊(duì)列，執(zhí)行隊(duì)列和完成隊(duì)列*/int num;void GetFirst(); /* 從就緒隊(duì)列取得第一個(gè)節(jié)點(diǎn)*/void Output(); /* 輸出隊(duì)列信息*/3void InsertPrio(PCB

7、*in); /* 創(chuàng)建優(yōu)先級隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越高/void InsertTime(PCB *in); /*時(shí)間片隊(duì)列*/void InsertFinish(PCB *in); /*時(shí)間片隊(duì)列*/void PrioCreate(); /* 優(yōu)先級輸入函數(shù)*/void TimeCreate(); /* 時(shí)間片輸入函數(shù)*/void Priority(); /* 按照優(yōu)先級調(diào)度*/void RoundRun(); /* 時(shí)間片輪轉(zhuǎn)調(diào)度*/int main(void)char chose;printf( 請輸入要?jiǎng)?chuàng)建的進(jìn)程數(shù)目:n);scanf(%d,&num);getchar();prin

8、tf( 輸入進(jìn)程的調(diào)度方法：(P/R)n);scanf(%c,&chose);switch(chose)case P:case p:PrioCreate();Priority();break;case R:case r:TimeCreate();RoundRun();break;default:break;Output();return 0;void GetFirst() /* 取得第一個(gè)就緒隊(duì)列節(jié)點(diǎn)*/run = ready;if(ready!=NULL)run -state = R;ready = ready -next;run -next = NULL;void Output() /*

9、輸出隊(duì)列信息*/PCB *p;p = ready;printf( 進(jìn)程名 t 優(yōu)先級 t 輪數(shù) tcpu 時(shí)間 t 需要時(shí)間t 進(jìn)程狀態(tài)t 計(jì)數(shù)器 n);while(p!=NULL)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 = finish;while(p!=NULL)printf(%st%dt%dt%dt%dtt%ctt%dn,p-name,p-prio,p-round,p-cputime,p-needtime,p-state,

10、p-count);p = p-next;p = run;while(p!=NULL)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;void InsertPrio(PCB *in) /* 創(chuàng)建優(yōu)先級隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低/PCB *fst,*nxt;fst = nxt = ready;if(ready = NULL) /* 如果隊(duì)列為空，則為第一個(gè)元素*/in-next = ready;ready = in;else /* 查到合

11、適的位置進(jìn)行插入*/if(in -prio = fst -prio) /*比第一個(gè)還要大，則插入到隊(duì)頭*/in-next = ready;ready = in;7最新資料推薦elsewhile(fst-next != NULL) /*移動(dòng)指針查找第一個(gè)別它小的元素的位置進(jìn)行插入 */nxt = fst;fst = fst-next;if(fst -next = NULL) /*已經(jīng)搜索到隊(duì)尾，則其優(yōu)先級數(shù)最小，將其插入到隊(duì)尾即可*/in -next = fst -next;fst -next = in;else /* 插入到隊(duì)列中*/nxt = in;in -next = fst;void I

12、nsertTime(PCB *in) /* 將進(jìn)程插入到就緒隊(duì)列尾部*/PCB *fst;fst = ready;if(ready = NULL)in-next = ready;ready = in;)else(while(fst-next != NULL)(fst = fst-next;)in -next = fst -next;fst -next = in;)void lnsertFinish(PCB *in) /*將進(jìn)程插入到完成隊(duì)列尾部*/(PCB *fst;fst = finish;if(finish = NULL)(in-next = finish;finish = in;)els

13、e(while(fst-next != NULL)(fst = fst-next;) in -next = fst -next;9fst -next = in;void PrioCreate() /* 優(yōu)先級調(diào)度輸入函數(shù)*/PCB *tmp;int i;printf( 輸入進(jìn)程名字和進(jìn)程所需時(shí)間：n);for(i = 0;i name);getchar(); /* 吸收回車符號*/scanf(%d,&(tmp-needtime);tmp -cputime = 0;tmp -state =W;tmp -prio = 50 - tmp-needtime; /*設(shè)置其優(yōu)先級，需要的時(shí)間越多，優(yōu)先級越

14、低*/tmp -round = 0;tmp -count = 0;InsertPrio(tmp); /* 按照優(yōu)先級從高到低，插入到就緒隊(duì)列*/void TimeCreate() /* 時(shí)間片輸入函數(shù)*/PCB *tmp;int i;printf( 輸入進(jìn)程名字和進(jìn)程時(shí)間片所需時(shí)間：n);for(i = 0;i name);getchar();scanf(%d,&(tmp-needtime);tmp -cputime = 0;tmp -state =W;tmp -prio = 0;tmp -round = 2; /* 假設(shè)每個(gè)進(jìn)程所分配的時(shí)間片是2*/tmp -count = 0;Insert

15、Time(tmp);void Priority() /* 按照優(yōu)先級調(diào)度，每次執(zhí)行一個(gè)時(shí)間片*/int flag = 1;GetFirst();while(run != NULL) /* 當(dāng)就緒隊(duì)列不為空時(shí)，則調(diào)度進(jìn)程如執(zhí)行隊(duì)列執(zhí)行/11最新資料推薦OutputQ; /*輸出每次調(diào)度過程中各個(gè)節(jié)點(diǎn)的狀態(tài)*/while(flag)run-prio -= 3; /*優(yōu)先級減去三*/run-cputime+; /*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ì)列*/)void RoundRunQ /*時(shí)間片輪轉(zhuǎn)調(diào)度算法 */int flag = 1;GetFirst();while(run != NULL)Output();wh