多級(jí)反饋隊(duì)列_實(shí)驗(yàn)_操作系統(tǒng)

1、實(shí)驗(yàn)名稱：多級(jí)反饋隊(duì)列調(diào)度 09091201丁奎榮一、實(shí)驗(yàn)?zāi)康模?、綜合應(yīng)用下列知識(shí)點(diǎn)設(shè)計(jì)并實(shí)現(xiàn)操作系統(tǒng)的進(jìn)程調(diào)度，進(jìn)程狀態(tài)轉(zhuǎn)換，多組級(jí)反饋隊(duì)列進(jìn)程調(diào)度算法。2、加深理解操作系統(tǒng)進(jìn)程調(diào)度的過(guò)程。3、加深理解多級(jí)反饋隊(duì)列進(jìn)程調(diào)度算法。二、實(shí)驗(yàn)內(nèi)容：1、采用一種熟悉的語(yǔ)言，編制程序，最好采用C/C+，界面設(shè)計(jì)可采用其它自己喜歡的語(yǔ)言。2、采用多級(jí)反饋隊(duì)列進(jìn)程調(diào)度算法進(jìn)行進(jìn)程調(diào)度。3、每個(gè)進(jìn)程對(duì)應(yīng)一個(gè)PCB。在PCB中包括進(jìn)程標(biāo)識(shí)符pid、進(jìn)程的狀態(tài)標(biāo)志status、進(jìn)程優(yōu)先級(jí)priority、進(jìn)程的隊(duì)列指針next和表示進(jìn)程生命周期的數(shù)據(jù)項(xiàng)life（在實(shí)際系統(tǒng)中不包括該項(xiàng)）。4、創(chuàng)建進(jìn)程時(shí)即創(chuàng)建一

2、個(gè)PCB，各個(gè)進(jìn)程的pid都是唯一的，pid時(shí)在1到100范圍的一個(gè)整數(shù)?？梢詣?chuàng)建一個(gè)下標(biāo)為1到100的布爾數(shù)組，“真”表示下標(biāo)對(duì)應(yīng)的進(jìn)程號(hào)是空閑的，“假”表示下標(biāo)對(duì)應(yīng)的進(jìn)程號(hào)已分配給某個(gè)進(jìn)程。5、進(jìn)程狀態(tài)status的取值為“就緒ready”或“運(yùn)行run”，剛創(chuàng)建時(shí)，狀態(tài)為“ready”。被進(jìn)程調(diào)度程序選中后變?yōu)椤皉un”。6、進(jìn)程優(yōu)先級(jí)priority是0到49范圍內(nèi)的一個(gè)隨機(jī)整數(shù)。7、生命周期life是1到5范圍內(nèi)的一個(gè)隨機(jī)整數(shù)。8、初始化時(shí)，創(chuàng)建一個(gè)鄰接表，包含50各就緒隊(duì)列，各就緒隊(duì)列的進(jìn)程優(yōu)先級(jí)priority分別是0到49。9、為了模擬用戶動(dòng)態(tài)提交任務(wù)的過(guò)程，要求動(dòng)態(tài)創(chuàng)建進(jìn)程。

3、進(jìn)入進(jìn)程調(diào)度循環(huán)后，每次按ctrl+f即動(dòng)態(tài)創(chuàng)建一個(gè)過(guò)程，然后將該P(yáng)CB插入就緒隊(duì)列中。按ctrl+q退出進(jìn)程調(diào)度循環(huán)。10、在進(jìn)程調(diào)度循環(huán)中，每次選擇優(yōu)先級(jí)最大的就緒進(jìn)程來(lái)執(zhí)行。將其狀態(tài)從就緒變?yōu)檫\(yùn)行，通過(guò)延時(shí)一段時(shí)間來(lái)模擬該進(jìn)程執(zhí)行一個(gè)時(shí)間片的過(guò)程，然后優(yōu)先級(jí)減半，生命周期減一。設(shè)計(jì)圖形用戶界面GUI，在窗口中顯示該進(jìn)程和其他所有進(jìn)程的PCB內(nèi)容。如果將該運(yùn)行進(jìn)程的生命周期不為0，則重新把它變?yōu)榫途w狀態(tài)，插入就緒對(duì)列中；否則該進(jìn)程執(zhí)行完成，撤銷其PCB。以上為一次進(jìn)程調(diào)度循環(huán)。四、程序主要流程圖：實(shí)驗(yàn)源程序：#include #include #include typedef struct

4、 node /*進(jìn)程節(jié)點(diǎn)信息*/ char name20; /*進(jìn)程的名字*/ int prio; /*進(jìn)程的優(yōu)先級(jí)*/ int round; /*分配CPU的時(shí)間片*/ int 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; typedef struct Queue /*多級(jí)就緒隊(duì)列節(jié)點(diǎn)信息*/ PCB *LinkPCB; /*就緒隊(duì)列中的進(jìn)程隊(duì)列指針*/

5、int prio; /*本就緒隊(duì)列的優(yōu)先級(jí)*/ int round; /*本就緒隊(duì)列所分配的時(shí)間片*/ struct Queue *next; /*指向下一個(gè)就緒隊(duì)列的鏈表指針*/ ReadyQueue; PCB *run=NULL,*finish=NULL; /*定義三個(gè)隊(duì)列，就緒隊(duì)列，執(zhí)行隊(duì)列和完成隊(duì)列*/ ReadyQueue *Head = NULL; /*定義第一個(gè)就緒隊(duì)列*/ int num; /*進(jìn)程個(gè)數(shù)*/ int ReadyNum; /*就緒隊(duì)列個(gè)數(shù)*/ void Output(); /*進(jìn)程信息輸出函數(shù)*/ void InsertFinish(PCB *in); /*將進(jìn)程

6、插入到完成隊(duì)列尾部*/ void InsertPrio(ReadyQueue *in); /*創(chuàng)建就緒隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級(jí)越低*/ void PrioCreate(); /*創(chuàng)建就緒隊(duì)列輸入函數(shù)*/ void GetFirst(ReadyQueue *queue); /*取得某一個(gè)就緒隊(duì)列中的隊(duì)頭進(jìn)程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*將進(jìn)程插入到就緒隊(duì)列尾部*/ void ProcessCreate(); /*進(jìn)程創(chuàng)建函數(shù)*/ void RoundRun(ReadyQueue *timechip); /*時(shí)間片輪轉(zhuǎn)調(diào)度算法

7、*/ void MultiDispatch(); /*多級(jí)調(diào)度算法，每次執(zhí)行一個(gè)時(shí)間片*/ int main(void) PrioCreate(); /*創(chuàng)建就緒隊(duì)列*/ ProcessCreate();/*創(chuàng)建就緒進(jìn)程隊(duì)列*/ MultiDispatch();/*算法開(kāi)始*/ Output(); /*輸出最終的調(diào)度序列*/ return 0; void Output() /*進(jìn)程信息輸出函數(shù)*/ ReadyQueue *print = Head; PCB *p; printf(進(jìn)程名t優(yōu)先級(jí)t輪數(shù)tcpu時(shí)間t需要時(shí)間t進(jìn)程狀態(tài)t計(jì)數(shù)器n); while(print) if(print -L

8、inkPCB != NULL) p=print -LinkPCB; while(p) 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; print = print-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,p-count); p = p-next; p

9、= 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 InsertFinish(PCB *in) /*將進(jìn)程插入到完成隊(duì)列尾部*/ PCB *fst; fst = finish; if(finish = NULL) in-next = finish; finish = in; else while(fst-next != NULL) fst = fst-next; in -next = f

10、st -next; fst -next = in; void InsertPrio(ReadyQueue *in) /*創(chuàng)建就緒隊(duì)列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級(jí)越低*/ ReadyQueue *fst,*nxt; fst = nxt = Head; if(Head = NULL) /*如果沒(méi)有隊(duì)列，則為第一個(gè)元素*/ in-next = Head; Head = in; else /*查到合適的位置進(jìn)行插入*/ if(in -prio = fst -prio) /*比第一個(gè)還要大，則插入到隊(duì)頭*/ in-next = Head; Head = in; else while(fst-next !=

11、NULL) /*移動(dòng)指針查找第一個(gè)別它小的元素的位置進(jìn)行插入*/ nxt = fst; fst = fst-next; 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; void PrioCreate() /*創(chuàng)建就緒隊(duì)列輸入函數(shù)*/ ReadyQueue *tmp; int i; printf(輸入就緒隊(duì)列的個(gè)數(shù)：n); scanf(%d,&ReadyNum); printf(輸入

12、每個(gè)就緒隊(duì)列的CPU時(shí)間片：n); for(i = 0;i round); /*輸入此就緒隊(duì)列中給每個(gè)進(jìn)程所分配的CPU時(shí)間片*/ tmp -prio = 50 - tmp-round; /*設(shè)置其優(yōu)先級(jí)，時(shí)間片越高，其優(yōu)先級(jí)越低*/ tmp -LinkPCB = NULL; /*初始化其連接的進(jìn)程隊(duì)列為空*/ tmp -next = NULL; InsertPrio(tmp); /*按照優(yōu)先級(jí)從高到低，建立多個(gè)就緒隊(duì)列*/ void GetFirst(ReadyQueue *queue) /*取得某一個(gè)就緒隊(duì)列中的隊(duì)頭進(jìn)程*/ run = queue -LinkPCB; if(queue -

13、LinkPCB != NULL) run -state = R; queue -LinkPCB = queue -LinkPCB -next; run -next = NULL; void InsertLast(PCB *in,ReadyQueue *queue) /*將進(jìn)程插入到就緒隊(duì)列尾部*/ PCB *fst; fst = queue-LinkPCB; if( queue-LinkPCB = NULL) in-next = queue-LinkPCB; queue-LinkPCB = in; else while(fst-next != NULL) fst = fst-next; in

14、-next = fst -next; fst -next = in; void ProcessCreate() /*進(jìn)程創(chuàng)建函數(shù)*/ PCB *tmp; int i; printf(輸入進(jìn)程的個(gè)數(shù)：n); scanf(%d,&num); printf(輸入進(jìn)程名字和進(jìn)程所需時(shí)間：n); for(i = 0;i 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í)越低*/

15、tmp -round = Head -round; tmp -count = 0; InsertLast(tmp,Head); /*按照優(yōu)先級(jí)從高到低，插入到就緒隊(duì)列*/ void RoundRun(ReadyQueue *timechip) /*時(shí)間片輪轉(zhuǎn)調(diào)度算法*/ int flag = 1; GetFirst(timechip); while(run != NULL) while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) /*進(jìn)程執(zhí)行完畢*/ run -state = F; InsertFini

16、sh(run); flag = 0; else if(run-count = timechip -round)/*時(shí)間片用完*/ run-state = W; run-count = 0; /*計(jì)數(shù)器清零，為下次做準(zhǔn)備*/ InsertLast(run,timechip); flag = 0; flag = 1; GetFirst(timechip); void MultiDispatch() /*多級(jí)調(diào)度算法，每次執(zhí)行一個(gè)時(shí)間片*/ int flag = 1; int k = 0; ReadyQueue *point; point = Head; GetFirst(point); while

17、(run != NULL) Output(); if(Head -LinkPCB!=NULL) point = Head; while(flag) run-count+; run-cputime+; run-needtime-; if(run-needtime = 0) /*進(jìn)程執(zhí)行完畢*/ run -state = F; InsertFinish(run); flag = 0; else if(run-count = run-round)/*時(shí)間片用完*/ run-state = W; run-count = 0; /*計(jì)數(shù)器清零，為下次做準(zhǔn)備*/ if(point -next!=NULL)

18、 run -round = point-next -round;/*設(shè)置其時(shí)間片是下一個(gè)就緒隊(duì)列的時(shí)間片*/ InsertLast(run,point-next); /*將進(jìn)程插入到下一個(gè)就緒隊(duì)列中*/ flag = 0; else RoundRun(point); /*如果為最后一個(gè)就緒隊(duì)列就調(diào)用時(shí)間片輪轉(zhuǎn)算法*/ break; +k; if(k = 3) ProcessCreate(); flag = 1; if(point -LinkPCB = NULL)/*就緒隊(duì)列指針下移*/ point =point-next; if(point -next =NULL) RoundRun(point); break; GetFirst(point); 五、實(shí)驗(yàn)中遇到的問(wèn)題和實(shí)驗(yàn)中的重點(diǎn)1.使用C+對(duì)于多級(jí)反饋模擬過(guò)程進(jìn)行描述，需要對(duì)計(jì)數(shù)器KillTimer();ONTIMER();進(jìn)行設(shè)計(jì)。通過(guò)在計(jì)數(shù)器中對(duì)函數(shù)run(