多級反饋隊列-實驗-操作系統(tǒng)

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

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

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

4、def struct node/*進程節(jié)點信息*/char name20:/*進程的名字*/int prio；/*進程的優(yōu)先級*/int round； /*分配CPU的時間片*/int cputime； /*CPU 執(zhí)行時間*/int needt ime;/*進程執(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；typedef struct Queue /*多級就緒隊列節(jié)點信息*/PCB *LinkPCB； 就緒隊列中的進程隊列指針*/int pri

5、o；/*本就緒隊列的優(yōu)先級*/int round；/*本就緒隊列所分配的時間片*/struct Queue *next； /*指向下一個就緒隊列的鏈表指針*/ReadyQueue；PCB *run=NULL,*finish=NULL； /*定義三個隊列，就緒隊列，執(zhí)行隊列和完成隊列*/ReadyQueue *Head = NULL； /*定義第一個就緒隊列*/int num；/*進程個數(shù)*/i nt Ready Num；/*就緒隊列個數(shù)*/void Output()；/*進程信息輸出函數(shù)*/void InsertFinish(PCB *in):/*將進程插入到完成隊列尾部*/void Inse

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

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

8、p)pr i nt f(n%st%dt%dt%dt%dtt%ctt%dnM.p-name.p-pr i o,p-round,p-cputime,p -needtime,p-state,p-count)；p = p-next；print = print-next；p = finish；wh訂e(p!=NULL)printf(，%st%dt%dt%dt%dtt%ctt%dn,p-name.p-prio,p-round p-cputimetp -needt ime,p-state,p-count)；p = p-next；p = run；wh訂e(p!=NULL)(printf(，%st%dt%dt%

9、dt%dtt%ctt%dnM,p-name,p-pr i o,p-round,p-cputime,p -needt ime,p-state,p-count)；p = p-next；void InsertFinish(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；void InsertPrio(Ready

10、Queue *in) 創(chuàng)建就緒隊列，規(guī)定優(yōu)先數(shù)越小，優(yōu)先級越低*/ReadyQueue *fst.nxt；fst = nxt = Head；if (Head = NULL)/*如果沒有隊列，則為笫一個元素*/in-next = Head；Head = in；else/*查到合適的位置進行插入*/(if (in -prio = fst -prio) /*比第一個還要大，則插入到隊頭*/in-next = Head；Head = in；elsewhile(fst-next != NULL) /*移動指針查找第一個別它小的元素的位置進行插入*/nxt = fst；fst = fst-next；if(

11、fst -next = NULL) /*已經(jīng)搜索到隊尾，則其優(yōu)先級數(shù)最小，將其插入到隊尾即 可*/in -next = fst 一next；fst -next = in；else/*插入到隊列中*/nxt = in；in -next = fst；void PrioCreate() /創(chuàng)建就緒隊列輸入函數(shù)*/ReadyQueue *tmp；int i;printfC輸入就緒隊列的個數(shù)：n)；scanf(n%d,&ReadyNum);printf (輸入每個就緒隊列的CPU時間片：n)；for(i = 0；i round):/*輸入此就緒隊列中給每個進程所分配的CPU時間片*/tmp -prio

12、= 50 - tmp-round； /*設置其優(yōu)先級，時間片越高，其優(yōu)先級越低*/ tmp -LinkPCB = NULL；/*初始化其連接的進程隊列為空*/tmp -next = NULL；InsertPrio(tmp)；/*按照優(yōu)先級從高到低，建立多個就緒隊列*/void GetFirst (ReadyQueue *queue)/*取得某一個就緒隊列中的隊頭進程*/run = queue -LinkPCB；if(queue -LinkPCB != NULL)(run -state = R；queue -LinkPCB = queue -LinkPCB -next；run -next = N

13、ULL；void InsertLast (PCB *in. ReadyQueue *queue) /*將進程插入到就緒隊列尾部*/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 -next = fst -next；fst -next = in；void ProcessCreate () /水進程創(chuàng)建函數(shù)*/PCB *tmp；int i:printfC輸入進程的

14、個數(shù):n);scanf(M%d&num)；printfC輸入進程名字和進程所需時間:n)；for(i = 0；i name)；getcharO ；/*吸收回車符號*/scanf (%d.&(tmp-needtime)；tmp -cputime = 0；tmp -state =1W * ；tmp -prio = 50 - tmp-needtime； /*設置其優(yōu)先級，需要的時間越多，優(yōu)先級越低*/tmp -round = Head 一)round；tmp -count = 0；InsertLast (tmp, Head) ；/*按照優(yōu)先級從高到低，插入到就緒隊列*/vo id RoundRun

15、(ReadyQueue *t imech i p)/*時間片輪轉(zhuǎn)調(diào)度算法*/int flag = 1;GetFirst(timechip)；wh訂e(run != NULL)while(flag)run-count+；run-cputime+；run-needtime；if(run-needtime = 0)進程執(zhí)行完畢*/run -state = F；InsertFinish(run)；flag = 0；else if(run-count = timechip -round)/*時間片用完*/run-state = W；run-count = 0；/*計數(shù)器清零，為下次做準備*/Insert

16、Last(run,timechip)；flag = 0；flag = 1;GetFirst(timechip):void MultiDispatchO/*多級調(diào)度算法，每次執(zhí)行一個時間片*/int flag = 1;int k = 0；ReadyQueue *point；point = Head；GetFirst(point)；wh訂e(run != NULL)Output()；if(Head -LinkPCB!二NULL)point = Head:while(flag)run-count+；run-cputime+；run-needtime；if (run-needt ime = 0) /*

17、進程執(zhí)行完畢*/run -state = F；InsertFinish(run)；flag = 0；else if(run-count = run-round)/*時間片用完*/run-state = * Wf；run-count = 0；/*計數(shù)器清零，為下次做準備*/if(point -next!二NULL)run -round = point-next -round； /設置其時間片是下一個就緒隊列的時間片*/InsertLast (run, point-next) ； /*將進程插入到下一個就緒隊列中*/flag = 0；elseRoundRun (point)；/*如果為最后一個就緒隊列就調(diào)用時間片輪轉(zhuǎn)算法*/break；+k；if(k = 3)ProcessCreateO ；flag = 1;if(point -LinkPCB = NULL)/*就緒隊列指針下移*/point =point-next；if(point -next =NULL)RoundRun(point)；break；GetFirst(point)；五、實驗中遇到的問題和實驗中的重點1使用C+對于多級反饋模擬過程進行描述，需要對計數(shù)器 KillTimer()；ONTIMER();進行設計。通過在計數(shù)器中對函數(shù)run()設計并在 ONTIMER(