設(shè)計(jì)1進(jìn)程調(diào)度算法的模擬

1、設(shè)計(jì)1進(jìn)程調(diào)度算法的模擬一、設(shè)計(jì)目的1、通過(guò)編程實(shí)現(xiàn)進(jìn)程調(diào)度算法的模擬，了解進(jìn)程調(diào)度的過(guò)程，理解進(jìn)程調(diào)度各方法的特點(diǎn)。二、設(shè)計(jì)要求1用語(yǔ)言來(lái)實(shí)現(xiàn)對(duì)n個(gè)進(jìn)程采用不同調(diào)度算法的進(jìn)程調(diào)度。2每個(gè)用來(lái)標(biāo)識(shí)進(jìn)程的進(jìn)程控制塊PCB用結(jié)構(gòu)來(lái)描述，包括以下字段：進(jìn)程優(yōu)先數(shù)ID，其中0為閑逛進(jìn)程，用戶進(jìn)程的標(biāo)識(shí)數(shù)為1,2,3。進(jìn)程優(yōu)先級(jí)Priority，閑逛進(jìn)程(idle)的優(yōu)先級(jí)為0,用戶進(jìn)程的優(yōu)先級(jí)大于0，且隨機(jī)產(chǎn)生，優(yōu)先數(shù)越大，優(yōu)先級(jí)越高。進(jìn)程占用的CPU時(shí)間CPUtime,進(jìn)程每運(yùn)行一次，累計(jì)值等于4。(4)進(jìn)程總共需要運(yùn)行時(shí)間Alltime，利用隨機(jī)函數(shù)產(chǎn)生。(5)進(jìn)程狀態(tài)，0：就緒態(tài)；1：運(yùn)行態(tài)；2

2、：阻塞態(tài)。(6)隊(duì)列指針next，用來(lái)將多個(gè)進(jìn)程控制塊PCB鏈接為隊(duì)列。3優(yōu)先數(shù)改變的原則(1)進(jìn)程在就緒隊(duì)列中每呆一個(gè)時(shí)間片，優(yōu)先數(shù)增加1。2)進(jìn)程每運(yùn)行一個(gè)時(shí)間片，優(yōu)先數(shù)減34.在調(diào)度前，系統(tǒng)中擁有的進(jìn)程數(shù)PCB_number由鍵盤輸入，經(jīng)初始化后，所有的進(jìn)程控制塊PCB鏈接成就緒隊(duì)列。三、設(shè)計(jì)說(shuō)明開始初始化PCB，輸入進(jìn)程信息FCFS算法，按照進(jìn)程先后順序輸出SJS算法，按照ALLTIME從小到大依次輸出優(yōu)先級(jí)算法，按照優(yōu)先從大到小輸出，進(jìn)程執(zhí)行依次P-3,就緒隊(duì)列中的進(jìn)程P+1RR算法，按照時(shí)間片依次執(zhí)行進(jìn)程，ALLTIME=4.結(jié)束1FCFS模塊1.1功能對(duì)于先到達(dá)的進(jìn)程優(yōu)先分配CP

3、U，按照先來(lái)先服務(wù)的原則依次執(zhí)行各進(jìn)程。數(shù)據(jù)結(jié)構(gòu)typedefstructPCBintID;/進(jìn)程優(yōu)先數(shù),用于標(biāo)示不同的進(jìn)程intPriority;/進(jìn)程優(yōu)先級(jí)intCPUTime;進(jìn)程占用的CPU時(shí)間CPUtime，進(jìn)程每運(yùn)行一次，累計(jì)值等于4intALLTime;/進(jìn)程總共需要運(yùn)行時(shí)間AlltimeintStatus;/用于表示進(jìn)程狀態(tài)，0：就緒態(tài)；1：運(yùn)行態(tài)；2：阻塞態(tài)PCB;算法voidFCFS()Node*p=head-next;while(p!=NULL)cout執(zhí)行進(jìn)程data.lD;p=p-next;coutendl;cout所有進(jìn)程都執(zhí)行完成next!=NULL)pmin=h

4、ead2-next;for(p=head2-next;p!=NULL;p=p-next)if(pmin-data.ALLTimep-data.ALLTime)pmin=p;cout執(zhí)行剩余區(qū)間長(zhǎng)度最短的進(jìn)程endldata.ID;for(p=head2;p!=NULL;p=p-next)if(p-next=pmin)p-next=p-next-next;free(pmin);printf(n);printf(所有進(jìn)程都執(zhí)行完成。nn);3SearchMaxPRI模塊功能按照優(yōu)先級(jí)從高到低依次執(zhí)行程序數(shù)據(jù)結(jié)構(gòu)p返回優(yōu)先級(jí)最大進(jìn)程；p返回優(yōu)先級(jí)最大進(jìn)程；q0指向q的前一個(gè)進(jìn)程，便于刪除進(jìn)程；q用于

5、遍歷鏈表算法voidSearchMaxPRI(intm)Node*p=head-next;Node*q=head-next;Node*q0=head;while(q!=NULL)if(q-data.ALLTime=0)cout進(jìn)程已執(zhí)行完成endldata.ID;n-;q0-next=q0-next-next;free(q);q=q0-next;elseif(q-data.Priorityp-data.Priority)p=q;q0=q0-next;q=q-next;if(n0)action(p);按照輪轉(zhuǎn)的次序分配給每個(gè)程序一定的時(shí)間執(zhí)行，執(zhí)行完成后執(zhí)行后面的進(jìn)程，依次循環(huán)執(zhí)行直到所有進(jìn)程執(zhí)

6、行完成。數(shù)據(jù)結(jié)構(gòu)算法voidRR(intm)Node*p;while(head1-next!=NULL)p=head1-next;Node*prep=head1;Node*q;while(p!=NULL)cout執(zhí)行進(jìn)程一個(gè)時(shí)間片data.ID;for(q=head1;q-next!=NULL;q=q-next)if(q-next=p)p-data.ALLTime-=4;p-data.CPUTime+=4;if(p-data.ALLTime=0)cout進(jìn)程已執(zhí)行完成dataD;prep-next=prep-next-next;free(p);p=prep-next;elseprep=prep

7、-next;p=p-next;coutendl;cout進(jìn)入下一次輪轉(zhuǎn)endl;coutvv所有進(jìn)程都執(zhí)行完成endl;四、運(yùn)行結(jié)果及分析廣-i花左EziCodeBjocLjincheng3iircheng尼xe調(diào)eImgii一/T-,1413遲調(diào)eImgii一/T-,1413遲,rfefe逆索的ES矩籍蔓雯艮調(diào)一；-r:亠藺Icllcl值區(qū)區(qū)區(qū)sffs請(qǐng)鞘入丟紳進(jìn)程數(shù)，進(jìn)程GFUrii-wALlTiiiKStilus1507021M4H31Q7G成-JL片片In_0-一、n抑L一井工工MB-TJrl-悝J入有ProccasrcbLumcl0CoxB)1cxccu1;iuri；ixnc21G.

8、Byd3Freisan屮keyLutuiratliiuc-L該程序?qū)崿F(xiàn)了進(jìn)程調(diào)度的四種不同調(diào)度算法下的調(diào)度順序的輸出情況。五、總結(jié)通過(guò)該程序的實(shí)現(xiàn)，對(duì)進(jìn)程的調(diào)度有了更多的了解，對(duì)于不同的系統(tǒng)和系統(tǒng)目標(biāo)，通常采用不同的調(diào)度算法。有的算法適用于為數(shù)眾多的短作業(yè)調(diào)度，有的算法為系統(tǒng)合理的響應(yīng)時(shí)間提供了保證。調(diào)度算法的選擇的合適和否很重要。源代碼：#include#include#include#include#include#defineTRUE1#defineFALSE0#defineOK1typedefstructPCBintID;intPriority;intCPUTime;intALLTim

9、e;intStatus;PCB;typedefPCBDt;typedefstructNodeDtdata;structNode*next;Node;Node*head=(Node*)malloc(sizeof(Node);Node*head1=(Node*)malloc(sizeof(Node);Node*head2=(Node*)malloc(sizeof(Node);intn;voidcreate(intn)inti=1;srand(int)time(0);head-next=NULL;Node*q=head;cout優(yōu)先數(shù)優(yōu)先級(jí)CPUTimeAllTimeStatusendl;while

10、(idata.ID=i;p-data.CPUTime=0;p-data.Status=0;p-data.Priority=rand()%10+1;p-data.ALLTime=rand()%8+1;coutdata.IDdata.Prioritydata.CPUTimedata.CPUTimedata.ALLTimedata.Statusnext=NULL;q-next=p;q=q-next;i+;Node*p0=head1;head1-next=NULL;for(q=head-next;q!=NULL;q=q-next)Node*r=(Node*)malloc(sizeof(Node);r-

11、data.ID=q-data.ID;r-data.CPUTime=q-data.CPUTime;r-data.Status=q-data.Status;r-data.Priority=q-data.Priority;r-data.ALLTime=q-data.ALLTime;p0-next=r;r-next=NULL;p0=p0-next;Node*p1=head2;head2-next=NULL;for(q=head-next;q!=NULL;q=q-next)Node*k=(Node*)malloc(sizeof(Node);k-data.ID=q-data.ID;k-data.CPUTi

12、me=q-data.CPUTime;k-data.Status=q-data.Status;k-data.Priority=q-data.Priority;k-data.ALLTime=q-data.ALLTime;p1-next=k;k-next=NULL;p1=p1-next;voidFCFS()Node*p=head-next;while(p!=NULL)cout執(zhí)行進(jìn)程data.lD;p=p-next;coutendl;cout所有進(jìn)程都執(zhí)行完成next!=NULL)pmin=head2-next;for(p=head2-next;p!=NULL;p=p-next)if(pmin-da

13、ta.ALLTimep-data.ALLTime)pmin=p;coutvv執(zhí)行剩余區(qū)間長(zhǎng)度最短的進(jìn)程vvendlvvpmin-data.ID;for(p=head2;p!=NULL;p=p-next)if(p-next=pmin)p-next=p-next-next;free(pmin);coutendl;coutvv所有進(jìn)程都執(zhí)行完成next;while(q!=NULL)coutdata.lDv執(zhí)行一個(gè)時(shí)間片的進(jìn)程data.Priority=q-data.Priority+1;elseq-data.Priority=q-data.Priority-3;if(q-data.ALLTime4)

14、q-data.ALLTime-=4;elseq-data.ALLTime=0;q-data.Status=1;q=q-next;voidSearchMaxPRl(intm)Node*p=head-next;Node*q=head-next;Node*q0=head;while(q!=NULL)if(q-data.ALLTime=0)coutdata.ID進(jìn)程已執(zhí)行完成next=q0-next-next;free(q);q=q0-next;elseif(q-data.Priorityp-data.Priority)p=q;q0=q0-next;q=q-next;if(n0)action(p);v

15、oidRR(intm)Node*p;while(head1-next!=NULL)p=head1-next;Node*prep=head1;Node*q;while(p!=NULL)coutdata.ID執(zhí)行進(jìn)程一個(gè)時(shí)間片next!=NULL;q=q-next)if(q-next=p)p-data.ALLTime-=4;p-data.CPUTime+=4;if(p-data.ALLTime=0)coutdata.ID進(jìn)程已執(zhí)行完成next=prep-next-next;free(p);p=prep-next;elseprep=prep-next;p=p-next;coutendl;cout進(jìn)入

16、下一次輪轉(zhuǎn)endl;cout所有進(jìn)程都執(zhí)行完成endl;intmain()cout請(qǐng)輸入系統(tǒng)進(jìn)程數(shù)：n;intm=n;if(n=0)cout此時(shí)沒有就緒進(jìn)程endl;elsecreate(n);coutendl;cout先來(lái)先服務(wù)調(diào)度endl;FCFS();coutendl;cout最短作業(yè)優(yōu)先調(diào)度endl;SJF();coutendl;coutvv優(yōu)先權(quán)的分時(shí)調(diào)度next!=NULL)SearchMaxPRI(m);cout所有進(jìn)程都執(zhí)行完成endl;coutendl;cout輪轉(zhuǎn)法調(diào)度endl;RR(m);設(shè)計(jì)2模擬銀行家算法一、設(shè)計(jì)目的1通過(guò)對(duì)銀行家算法的模擬，理解銀行家算法的實(shí)現(xiàn)過(guò)程，

17、了解系統(tǒng)解決死鎖的方法二、設(shè)計(jì)要求1、編程序模擬銀行家算法2、能體現(xiàn)算法的全過(guò)程三、設(shè)計(jì)說(shuō)明1.bank模塊功能利用銀行家算法，給系統(tǒng)分配資源，避免死鎖。數(shù)據(jù)結(jié)構(gòu)TypedefstructRESOURCEintavailableR;/系統(tǒng)可用資源數(shù)intallocationWR;/M個(gè)進(jìn)程已經(jīng)得到N類資源的資源量intneedWR;/M個(gè)進(jìn)程還需要N類資源的資源量intrequestR;/請(qǐng)求資源個(gè)數(shù)RESOURCE算法inti=0,j=0;charchoice=Y;while(choice=Y|choice=y)i=-1;while(i=M)coutendli;if(i=M)cout進(jìn)程號(hào)不

18、存在，重新輸入!endl;cout請(qǐng)輸入進(jìn)程i申請(qǐng)各類資源的數(shù)量:endl;for(j=0;jrequestj;if(requestjneedij)coutvvendlvv進(jìn)程i申請(qǐng)的資源數(shù)大于進(jìn)程i還需要j類資源的數(shù)量!;cout若繼續(xù)執(zhí)行系統(tǒng)將處于不安全狀態(tài)!availablej)coutendl進(jìn)程i申請(qǐng)的資源數(shù)大于系統(tǒng)可用VVjVV類資源的數(shù)量!；cout繼續(xù)執(zhí)行系統(tǒng)將處于不安全狀態(tài)!endl;choice=N;break;if(choice=Y|choice=y)distribute(i);if(check()restore(i);print();elseprint();elseco

19、utendl;coutchoice;2.check模塊2.1功能檢查資源分配后系統(tǒng)是否處于安全狀態(tài)。2.2數(shù)據(jù)結(jié)構(gòu)TypedefstructRESOURCEintavailableR;/系統(tǒng)可用資源數(shù)intallocationWR;/M個(gè)進(jìn)程已經(jīng)得到N類資源的資源量intneedWR;/M個(gè)進(jìn)程還需要N類資源的資源量intrequestR;/請(qǐng)求資源個(gè)數(shù)RESOURCE算法intworkR,finishW;inti,j;for(j=0;jN;j+)workj=availablej;for(i=0;iM;i+)finishi=FALSE;for(i=0;iM;i+)for(j=0;jN;j+)i

20、f(finishi=FALSE&needij=workj)workj=worki+allocationij;finishi=TRUE;for(i=0;iM;i+)if(finishi=FALSE)coutendl;cout系統(tǒng)不安全!資源申請(qǐng)失敗!endl;coutendl;return1;elsecout系統(tǒng)安全，分配成功!endl;return0;四、運(yùn)行結(jié)果及分析resourccAt*C30urccB入各涯兔己經(jīng)占據(jù)的各矣資涕的僉魚:1H巨吉鐘資浜可利用數(shù)和資師欽S資原丄：5令原2:g行二二|益=二-.：行匹：底抑人蜜遁翠；甲iWJS.=2M：劇阿7加爐：9申家耳決演示4耳?2muju占

21、衣資謁迪討了聲明的赤L需汛ip?軒輸人311Igg|一|回ngla進(jìn)專輸人詡請(qǐng)芻去資務(wù)橄豪分配成功？誨注欽7涼“8暮矍初備源可刑用數(shù)晏負(fù)湧欽5資51：4簾沖2：6各說(shuō)程話鑄要的資源數(shù)野reaourccArcsourceBrcaourccCCXw124rmtutdThr、T*進(jìn)迸送5re&uurceC11tR號(hào)卡善爭(zhēng)的資源數(shù)気=L閔.；講稈0丘請(qǐng)柱P竊褲單應(yīng)壬潔貞s企資IrJT的腫1r:s-_retidutcrC.已專丹當(dāng)?shù)那⑵kri!suljruERexiJuircrHPz亡吃曲ireturned杠oceciitfiaritJtt4.4Ia?w*skfniijiSytommit.iibuh通過(guò)

22、實(shí)驗(yàn)結(jié)果可知銀行家算法中，當(dāng)進(jìn)程申請(qǐng)的資源大于聲明所需的最大資源或者大于系統(tǒng)當(dāng)前可用的資源時(shí)，系統(tǒng)將處于不安全狀態(tài)，資源分配失敗，從而防止了死鎖的產(chǎn)生。五、總結(jié)通過(guò)該算法的模擬可知銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進(jìn)程動(dòng)態(tài)地申請(qǐng)資源，但系統(tǒng)在進(jìn)行資源分配之前，應(yīng)先計(jì)算此次分配資源的安全性，若分配不會(huì)導(dǎo)致系統(tǒng)進(jìn)入不安全狀態(tài)，則分配，否則等待。為實(shí)現(xiàn)銀行家算法，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。源代碼:#include#include#include#defineFALSE0#defineTRUE1#defineW10#defineR10intallresourceW;int

23、maxWR;intavailableR;intallocationWR;intneedWR;intrequestR;intM;intN;voidprint()inti,j;coutvv各種資源總量:endl;coutvv資源vvjvv:vvallresourcejvvendl;coutvv目前各種資源可利用數(shù)量:endl;for(j=0;jN;j+)coutvv資源vvjvv：vvavailablejvvendl;coutvv各進(jìn)程還需要的資源數(shù)量:endlvvendl;coutvvresourceAvvresourceBvvresourceCvvendl;for(i=0;ivM;i+)cou

24、tvv進(jìn)程vvivv：;for(j=0;jvN;j+)coutvvneedijvv;coutvvendl;coutvv各進(jìn)程已經(jīng)得到的資源量：vvendlvvendl;coutvvresourceAvvresourceBvvresourceCvvendl;for(i=0;ivM;i+)for(j=0;jN;j+)coutallocationijcoutendl;voiddistribute(intl)/分配資源intj;for(j=0;jN;j+)availablej=availablej-requestj;allocationlj=allocationlj+requestj;needlj=n

25、eedlj-requestj;voidrestore(intl)/恢復(fù)資源intj;availablej=availablej+requestj;allocationlj=allocationlj-requestj;needlj=needlj+requestj;intcheck()intworkR,finishW;inti,j;for(j=0;jN;j+)workj=availablej;for(i=0;iM;i+)finishi=FALSE;for(i=0;iM;i+)for(j=0;jN;j+)if(finishi=FALSE&needij=workj)workj=worki+alloca

26、tionij;finishi=TRUE;for(i=0;iM;i+)if(finishi=FALSE)coutendl;cout系統(tǒng)不安全!資源申請(qǐng)失敗!endl;coutendl;return1;elsecout系統(tǒng)安全，分配成功!endl;return0;voidbank()inti=0,j=0;charchoice=Y;while(choice=Y|choice=y)i=-1;while(i=M)coutendli;if(i=M)cout進(jìn)程號(hào)不存在，重新輸入!endl;cout請(qǐng)輸入進(jìn)程i申請(qǐng)各類資源的數(shù)量:endl;for(j=0;jrequestj;if(requestjneedi

27、j)coutendl進(jìn)程i申請(qǐng)的資源數(shù)大于進(jìn)程i還需要j類資源的數(shù)量!;cout若繼續(xù)執(zhí)行系統(tǒng)將處于不安全狀態(tài)!availablej)coutendl進(jìn)程i申請(qǐng)的資源數(shù)大于系統(tǒng)可用j類資源的數(shù)量!;cout繼續(xù)執(zhí)行系統(tǒng)將處于不安全狀態(tài)!endl;choice=N;break;if(choice=Y|choice=y)distribute(i);if(check()restore(i);print();elseprint();elsecoutendl;Y/Ncoutchoice;intmain()vvendl；：vvendl；inti=0,j=0,p;coutt銀行家算法演示coutendlM;

28、coutN;coutvv請(qǐng)輸入各類資源總數(shù)：；for(i=0;iallresourcei；coutvv輸入各進(jìn)程所需要的各類資源的最大數(shù)量for(i=0；imaxij；if(maxijallresourcej)coutendl占有資源超過(guò)了聲明的該資源總數(shù),請(qǐng)重新輸入allresourcej);coutvv輸入各進(jìn)程已經(jīng)占據(jù)的各類資源的數(shù)量:endl;for(i=0;iM;i+)for(j=0;jallocationij;if(allocationijmaxij)coutvvendlvv占有資源超過(guò)了聲明的最大資源，請(qǐng)重新輸入maxij);for(j=0;jN;j+)p=allresourcej;for(i=0;iM;i+)p=p-allocationij;availablej=p;if(availablej0)availablej=0;for(i=0;iM;i+)for(j=0;jN;j+)needij=maxij-allocationij;print();bank();磁盤調(diào)度算法磁盤調(diào)度算法設(shè)計(jì)3一、設(shè)計(jì)目的1、通過(guò)對(duì)磁盤調(diào)度算法的實(shí)現(xiàn)，了解磁盤調(diào)度的算法已經(jīng)其尋道時(shí)間、設(shè)計(jì)要求編程序?qū)崿F(xiàn)下述磁盤調(diào)度算法，并求出每種算法的平均尋道長(zhǎng)度1先來(lái)先服務(wù)算法