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

實(shí)驗(yàn)名稱：多級反饋隊列調(diào)度09091201丁奎榮一、實(shí)驗(yàn)?zāi)康模?、綜合應(yīng)用下列知識點(diǎn)設(shè)計并實(shí)現(xiàn)操作系統(tǒng)的進(jìn)程調(diào)度，進(jìn)程狀態(tài)轉(zhuǎn)換，多組級反饋隊列進(jìn)程調(diào)度算法。2、加深理解操作系統(tǒng)進(jìn)程調(diào)度的過程。3、加深理解多級反饋隊列進(jìn)程調(diào)度算法。二、實(shí)驗(yàn)內(nèi)容：1、采用一種熟悉的語言，編制程序，最好采用C/C++，界面設(shè)計可采用其它自己喜歡的語言。2、采用多級反饋隊列進(jìn)程調(diào)度算法進(jìn)行進(jìn)程調(diào)度。3、每個進(jìn)程對應(yīng)一個PCB。在PCB中包括進(jìn)程標(biāo)識符pid、進(jìn)程的狀態(tài)標(biāo)志status、進(jìn)程優(yōu)先級priority、進(jìn)程的隊列指針next和表示進(jìn)程生命周期的數(shù)據(jù)項life（在實(shí)際系統(tǒng)中不包括該項）。4、創(chuàng)建進(jìn)程時即創(chuàng)建一個PCB，各個進(jìn)程的pid都是唯一的，pid時在1到100范圍的一個整數(shù)。可以創(chuàng)建一個下標(biāo)為1到100的布爾數(shù)組，“真”表示下標(biāo)對應(yīng)的進(jìn)程號是空閑的，“假”表示下標(biāo)對應(yīng)的進(jìn)程號已分配給某個進(jìn)程。5、進(jìn)程狀態(tài)status的取值為“就緒ready”或“運(yùn)行run”，剛創(chuàng)建時，狀態(tài)為“ready”。被進(jìn)程調(diào)度程序選中后變?yōu)椤皉un”。6、進(jìn)程優(yōu)先級priority是0到49范圍內(nèi)的一個隨機(jī)整數(shù)。7、生命周期life是1到5范圍內(nèi)的一個隨機(jī)整數(shù)。8、初始化時，創(chuàng)建一個鄰接表，包含50各就緒隊列，各就緒隊列的進(jìn)程優(yōu)先級priority分別是0到49。9、為了模擬用戶動態(tài)提交任務(wù)的過程，要求動態(tài)創(chuàng)建進(jìn)程。進(jìn)入進(jìn)程調(diào)度循環(huán)后，每次按ctrl+f即動態(tài)創(chuàng)建一個過程，然后將該P(yáng)CB插入就緒隊列中。按ctrl+q退出進(jìn)程調(diào)度循環(huán)。10、在進(jìn)程調(diào)度循環(huán)中，每次選擇優(yōu)先級最大的就緒進(jìn)程來執(zhí)行。將其狀態(tài)從就緒變?yōu)檫\(yùn)行，通過延時一段時間來模擬該進(jìn)程執(zhí)行一個時間片的過程，然后優(yōu)先級減半，生命周期減一。設(shè)計圖形用戶界面GUI，在窗口中顯示該進(jìn)程和其他所有進(jìn)程的PCB內(nèi)容。如果將該運(yùn)行進(jìn)程的生命周期不為0，則重新把它變?yōu)榫途w狀態(tài)，插入就緒對列中；否則該進(jìn)程執(zhí)行完成，撤銷其PCB。以上為一次進(jìn)程調(diào)度循環(huán)。四、程序主要流程圖：實(shí)驗(yàn)源程序：#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode/*進(jìn)程節(jié)點(diǎn)信息*/{}}}voidPrioCreate()/*創(chuàng)建就緒隊列輸入函數(shù)*/{ReadyQueue*tmp;inti;printf("輸入就緒隊列的個數(shù)：\n");scanf("%d",&ReadyNum);printf("輸入每個就緒隊列的CPU時間片：\n");for(i=0;i<ReadyNum;i++){if((tmp=(ReadyQueue*)malloc(sizeof(ReadyQueue)))==NULL){perror("malloc");exit(1);}scanf("%d",&(tmp->round));/*輸入此就緒隊列中給每個進(jìn)程所分配的CPU時間片*/tmp->prio=50-tmp->round;/*設(shè)置其優(yōu)先級，時間片越高，其優(yōu)先級越低*/tmp->LinkPCB=NULL;/*初始化其連接的進(jìn)程隊列為空*/tmp->next=NULL;InsertPrio(tmp);/*按照優(yōu)先級從高到低，建立多個就緒隊列*/}}voidGetFirst(ReadyQueue*queue)/*取得某一個就緒隊列中的隊頭進(jìn)程*/{run=queue->LinkPCB;if(queue->LinkPCB!=NULL){run->state='R';queue->LinkPCB=queue->LinkPCB->next;run->next=NULL;}}voidInsertLast(PCB*in,ReadyQueue*queue)/*將進(jìn)程插入到就緒隊列尾部*/{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;}}voidProcessCreate()/*進(jìn)程創(chuàng)建函數(shù)*/{PCB*tmp;inti;printf("輸入進(jìn)程的個數(shù)：\n");scanf("%d",&num);printf("輸入進(jìn)程名字和進(jìn)程所需時間：\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->cputime=0;tmp->state='W';tmp->prio=50-tmp->needtime;/*設(shè)置其優(yōu)先級，需要的時間越多，優(yōu)先級越低*/tmp->round=Head->round;tmp->count=0;InsertLast(tmp,Head);/*按照優(yōu)先級從高到低，插入到就緒隊列*/}}voidRoundRun(ReadyQueue*timechip)/*時間片輪轉(zhuǎn)調(diào)度算法*/{intflag=1;GetFirst(timechip);while(run!=NULL){while(flag){run->count++;run->cputime++;run->needtime--;if(run->needtime==0)/*進(jìn)程執(zhí)行完畢*/{run->state='F';InsertFinish(run);flag=0;}elseif(run->count==timechip->round)/*時間片用完*/{run->state='W';run->count=0;/*計數(shù)器清零，為下次做準(zhǔn)備*/InsertLast(run,timechip);flag=0;}}flag=1;GetFirst(timechip);}}voidMultiDispatch()/*多級調(diào)度算法，每次執(zhí)行一個時間片*/{intflag=1;intk=0;ReadyQueue*point;point=Head;GetFirst(point);while(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;}elseif(run->count==run->round)/*時間片用完*/{run->state='W';run->count=0;/*計數(shù)器清零，為下次做準(zhǔn)備*/if(point->next!=NULL){run->round=point->next->round;/*設(shè)置其時間片是下一個就緒隊列的時間片*/InsertLast(run,point->next);/*將進(jìn)程插入到下一個就緒隊列中*/flag=0;}else{RoundRun(point);/*如果為最后一個就緒隊列就調(diào)用時間片輪轉(zhuǎn)算法*/break;}}++k;if(k==3){ProcessCreate();}}flag=1;if(point->LinkPCB==NULL)/*就緒隊列指針下移*/point=point->next;if(point->next==NULL){RoundRun(point);break;}GetFirst(point);}}五、實(shí)驗(yàn)中遇到的問題和實(shí)驗(yàn)中的重點(diǎn)1.使用C++對于多級反饋模擬過程進(jìn)行描述，需要對計數(shù)器KillTimer();ONTIMER();進(jìn)行設(shè)計。通過在計數(shù)器中對函數(shù)run()設(shè)計并在ONTIMER()中對run函數(shù)調(diào)用從而完成多級反饋隊列運(yùn)行的模擬。在變成過程中要對ONTIMER手動映射