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

實(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)度的過程。3、加深理解多級(jí)反饋隊(duì)列進(jìn)程調(diào)度算法。二、實(shí)驗(yàn)內(nèi)容：1、采用一種熟悉的語言，編制程序，最好采用C/C++，界面設(shè)計(jì)可采用其它自己喜歡的語言。2、采用多級(jí)反饋隊(duì)列進(jìn)程調(diào)度算法進(jìn)行進(jìn)程調(diào)度。3、每個(gè)進(jìn)程對應(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)建一個(gè)PCB，各個(gè)進(jìn)程的pid都是唯一的，pid時(shí)在1到100范圍的一個(gè)整數(shù)?？梢詣?chuàng)建一個(gè)下標(biāo)為1到100的布爾數(shù)組，“真”表示下標(biāo)對應(yīng)的進(jìn)程號(hào)是空閑的，“假”表示下標(biāo)對應(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ù)的過程，要求動(dòng)態(tài)創(chuàng)建進(jìn)程。進(jìn)入進(jìn)程調(diào)度循環(huán)后，每次按ctrl+f即動(dòng)態(tài)創(chuàng)建一個(gè)過程，然后將該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)程來執(zhí)行。將其狀態(tài)從就緒變?yōu)檫\(yùn)行，通過延時(shí)一段時(shí)間來模擬該進(jìn)程執(zhí)行一個(gè)時(shí)間片的過程，然后優(yōu)先級(jí)減半，生命周期減一。設(shè)計(jì)圖形用戶界面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)建就緒隊(duì)列輸入函數(shù)*/{ReadyQueue*tmp;inti;printf("輸入就緒隊(duì)列的個(gè)數(shù)：\n");scanf("%d",&ReadyNum);printf("輸入每個(gè)就緒隊(duì)列的CPU時(shí)間片：\n");for(i=0;i<ReadyNum;i++){if((tmp=(ReadyQueue*)malloc(sizeof(ReadyQueue)))==NULL){perror("malloc");exit(1);}scanf("%d",&(tmp->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ì)列*/}}voidGetFirst(ReadyQueue*queue)/*取得某一個(gè)就緒隊(duì)列中的隊(duì)頭進(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)程插入到就緒隊(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->next=fst->next;fst->next=in;}}voidProcessCreate()/*進(jìn)程創(chuàng)建函數(shù)*/{PCB*tmp;inti;printf("輸入進(jìn)程的個(gè)數(shù)：\n");scanf("%d",&num);printf("輸入進(jìn)程名字和進(jìn)程所需時(shí)間：\n");for(i=0;i<num;i++){if((tmp=(PCB*)malloc(sizeof(PCB)))==NULL){perror("malloc");exit(1);}scanf("%s",tmp->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í)越低*/tmp->round=Head->round;tmp->count=0;InsertLast(tmp,Head);/*按照優(yōu)先級(jí)從高到低，插入到就緒隊(duì)列*/}}voidRoundRun(ReadyQueue*timechip)/*時(shí)間片輪轉(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)/*時(shí)間片用完*/{run->state='W';run->count=0;/*計(jì)數(shù)器清零，為下次做準(zhǔn)備*/InsertLast(run,timechip);flag=0;}}flag=1;GetFirst(timechip);}}voidMultiDispatch()/*多級(jí)調(diào)度算法，每次執(zhí)行一個(gè)時(shí)間片*/{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)/*時(shí)間片用完*/{run->state='W';run->count=0;/*計(jì)數(shù)器清零，為下次做準(zhǔn)備*/if(point->next!=NULL){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)中遇到的問題和實(shí)驗(yàn)中的重點(diǎn)1.使用C++對于多級(jí)反饋模擬過程進(jìn)行描述，需要對計(jì)數(shù)器KillTimer();ONTIMER();進(jìn)行設(shè)計(jì)。通過在計(jì)數(shù)器中對函數(shù)run()設(shè)計(jì)并在ONTIMER()中對run函數(shù)調(diào)用從而完成多級(jí)反饋隊(duì)列運(yùn)行的模擬。在變成過程中要對ONTIMER手動(dòng)映射