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

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

3、進入進程調度循環后，每次按ctrl+f即動態創建一個過程，然后將該PCB插入就緒隊列中。按ctrl+q退出進程調度循環。10、在進程調度循環中，每次選擇優先級最大的就緒進程來執行。將其狀態從就緒變為運行，通過延時一段時間來模擬該進程執行一個時間片的過程，然后優先級減半，生命周期減一。設計圖形用戶界面GUI，在窗口中顯示該進程和其他所有進程的PCB內容。如果將該運行進程的生命周期不為0，則重新把它變為就緒狀態，插入就緒對列中；否則該進程執行完成，撤銷其PCB。以上為一次進程調度循環。四、程序主要流程圖：實驗源程序：#include #include #include typedef struct

4、 node /*進程節點信息*/ char name20; /*進程的名字*/ int prio; /*進程的優先級*/ int round; /*分配CPU的時間片*/ int cputime; /*CPU執行時間*/ int needtime; /*進程執行所需要的時間*/ char state; /*進程的狀態，W就緒態，R執行態，F完成態*/ int count; /*記錄執行的次數*/ struct node *next; /*鏈表指針*/ PCB; typedef struct Queue /*多級就緒隊列節點信息*/ PCB *LinkPCB; /*就緒隊列中的進程隊列指針*/

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

6、插入到完成隊列尾部*/ void InsertPrio(ReadyQueue *in); /*創建就緒隊列，規定優先數越小，優先級越低*/ void PrioCreate(); /*創建就緒隊列輸入函數*/ void GetFirst(ReadyQueue *queue); /*取得某一個就緒隊列中的隊頭進程*/ void InsertLast(PCB *in,ReadyQueue *queue); /*將進程插入到就緒隊列尾部*/ void ProcessCreate(); /*進程創建函數*/ void RoundRun(ReadyQueue *timechip); /*時間片輪轉調度算法

7、*/ void MultiDispatch(); /*多級調度算法，每次執行一個時間片*/ int main(void) PrioCreate(); /*創建就緒隊列*/ ProcessCreate();/*創建就緒進程隊列*/ MultiDispatch();/*算法開始*/ Output(); /*輸出最終的調度序列*/ return 0; void Output() /*進程信息輸出函數*/ ReadyQueue *print = Head; PCB *p; printf(進程名t優先級t輪數tcpu時間t需要時間t進程狀態t計數器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) /*將進程插入到完成隊列尾部*/ 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) /*創建就緒隊列，規定優先數越小，優先級越低*/ 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; else while(fst-next !=

11、NULL) /*移動指針查找第一個別它小的元素的位置進行插入*/ nxt = fst; fst = fst-next; if(fst -next = NULL) /*已經搜索到隊尾，則其優先級數最小，將其插入到隊尾即可*/ in -next = fst -next; fst -next = in; else /*插入到隊列中*/ nxt = in; in -next = fst; void PrioCreate() /*創建就緒隊列輸入函數*/ ReadyQueue *tmp; int i; printf(輸入就緒隊列的個數：n); scanf(%d,&ReadyNum); printf(輸入

12、每個就緒隊列的CPU時間片：n); for(i = 0;i round); /*輸入此就緒隊列中給每個進程所分配的CPU時間片*/ tmp -prio = 50 - tmp-round; /*設置其優先級，時間片越高，其優先級越低*/ tmp -LinkPCB = NULL; /*初始化其連接的進程隊列為空*/ tmp -next = NULL; InsertPrio(tmp); /*按照優先級從高到低，建立多個就緒隊列*/ void GetFirst(ReadyQueue *queue) /*取得某一個就緒隊列中的隊頭進程*/ 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) /*將進程插入到就緒隊列尾部*/ 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() /*進程創建函數*/ PCB *tmp; int i; printf(輸入進程的個數：n); scanf(%d,&num); printf(輸入進程名字和進程所需時間：n); for(i = 0;i name); getchar(); /*吸收回車符號*/ scanf(%d,&(tmp-needtime); tmp -cputime = 0; tmp -state =W; tmp -prio = 50 - tmp-needtime; /*設置其優先級，需要的時間越多，優先級越低*/

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

16、sh(run); flag = 0; else if(run-count = timechip -round)/*時間片用完*/ run-state = W; run-count = 0; /*計數器清零，為下次做準備*/ InsertLast(run,timechip); flag = 0; flag = 1; GetFirst(timechip); void MultiDispatch() /*多級調度算法，每次執行一個時間片*/ 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) /*進程執行完畢*/ run -state = F; InsertFinish(run); flag = 0; else if(run-count = run-round)/*時間片用完*/ run-state = W; run-count = 0; /*計數器清零，為下次做準備*/ if(point -next!=NULL)

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