2023年新版銀行家共享資源分配與銀行家算法實(shí)驗(yàn)報(bào)告

課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱共享資源分派與銀行家算法系(部)專業(yè)班級(jí)姓名學(xué)號(hào)指導(dǎo)教師?年月日 目錄一、課程設(shè)計(jì)目的和意義 3二、方案設(shè)計(jì)及開(kāi)發(fā)過(guò)程 31.課題設(shè)計(jì)背景 32.算法描述 ３3.數(shù)據(jù)結(jié)構(gòu)?44．重要函數(shù)說(shuō)明?45.算法流程圖?5三、調(diào)試記錄與分析四、運(yùn)營(yíng)結(jié)果及說(shuō)明 ６1.執(zhí)行結(jié)果 62.結(jié)果分析 ７五、課程設(shè)計(jì)總結(jié)?8一、程設(shè)計(jì)目的和意義計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生學(xué)習(xí)完《計(jì)算機(jī)操作系統(tǒng)》課程后，進(jìn)行的一次全面的綜合訓(xùn)練，其目的在于加深催操作系統(tǒng)基礎(chǔ)理論和基本知識(shí)的理解,加強(qiáng)學(xué)生的動(dòng)手能力．銀行家算法是避免死鎖的一種重要方法。通過(guò)編寫一個(gè)模擬動(dòng)態(tài)資源分派的銀行家算法程序，進(jìn)一步進(jìn)一步理解死鎖、產(chǎn)生死鎖的必要條件、安全狀態(tài)等重要概念，并掌握避免死鎖的具體實(shí)行方法二、方案設(shè)計(jì)及開(kāi)發(fā)過(guò)程

1.課題設(shè)計(jì)背景銀行家算法又稱“資源分派拒絕”法,其基本思想是,系統(tǒng)中的所有進(jìn)程放入進(jìn)程集合,在安全狀態(tài)下系統(tǒng)受到進(jìn)程的請(qǐng)求后試探性的把資源分派給他，現(xiàn)在系統(tǒng)將剩下的資源和進(jìn)程集合中其他進(jìn)程還需要的資源數(shù)做比較,找出剩余資源能滿足最大需求量的進(jìn)程,從而保證進(jìn)程運(yùn)營(yíng)完畢后還回所有資源。這時(shí)系統(tǒng)將該進(jìn)程從進(jìn)程集合中將其清除。此時(shí)系統(tǒng)中的資源就更多了。反復(fù)執(zhí)行上面的環(huán)節(jié),最后檢查進(jìn)程的集合為空時(shí)就表白本次申請(qǐng)可行,系統(tǒng)處在安全狀態(tài)，可以實(shí)行本次分派，否則，只要進(jìn)程集合非空,系統(tǒng)便處在不安全狀態(tài),本次不能分派給他。請(qǐng)進(jìn)程等待2.算法描述１)假如Ｒequest[i]是進(jìn)程Pｉ的請(qǐng)求向量，假如Requｅst［i,j]＝Ｋ,表達(dá)進(jìn)程Ｐi需要K個(gè)Rｊ類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述環(huán)節(jié)進(jìn)行檢查：?假如Reｑｕesti[ｊ]<=Need[i,j]，便轉(zhuǎn)向環(huán)節(jié)2；否則認(rèn)為犯錯(cuò),由于它所需要的資源數(shù)已超過(guò)它所宣布的最大值。2）假如Requestｉ[j]<＝Availabｌe[j］，便轉(zhuǎn)向環(huán)節(jié)３,否則，表達(dá)尚無(wú)足夠資源，進(jìn)程Ｐi須等待。3）系統(tǒng)試探著把資源分派給進(jìn)程Pi,并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值:Ａvailabｌe[j]:=Avａｉｌａｂle[j]-Reqｕｅstｉ[ｊ]；Alloｃａt(yī)ｉon[i,ｊ]:=Alｌocatｉon[i，j]+Requeｓti［j］；Neeｄ[ｉ,j]：=Ｎeed[i,j]-Ｒeｑueｓｔｉ［j］；4)系統(tǒng)執(zhí)行安全性算法,檢查本次資源分派后，系統(tǒng)是否處在安全狀態(tài)。若安全,才正式將資源分派給進(jìn)程Pi，以完畢本次分派;否則，將本次的試探分派作廢，恢復(fù)本來(lái)的資源分派狀態(tài)，讓進(jìn)程pｉ等待。３.數(shù)據(jù)結(jié)構(gòu)1.可運(yùn)用資源向量AＶAＩLＡBLE。這是一個(gè)具有M個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可運(yùn)用的資源數(shù)目,其3初始值是系統(tǒng)中所配置的該類所有可哦那個(gè)資源的數(shù)目,其數(shù)值隨該類資源的分派和回收而動(dòng)態(tài)的改變。2．最大需求矩陣MAX。這是一個(gè)Ｍ＊Ｎ的矩陣,它定義了系統(tǒng)中N個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)M類資源的最大需求。3.分派矩陣ＡLＬOＣＡTIOＮ。這也是一個(gè)Ｍ＊N的矩陣,它定義了系統(tǒng)中每一類資源當(dāng)前已分派給每一進(jìn)程的資源數(shù)。4．需求矩陣NEED。這也是一個(gè)M*N的矩陣,用以表達(dá)每一個(gè)進(jìn)程尚需的各類資源數(shù)。5．NＥEＤ[R,Ｗ]=MAＸ[R,W]-ＡLLOＣＡTIＯN[R,W]4.重要函數(shù)說(shuō)明重要的常量變量#defineW１０//最大進(jìn)程數(shù)W＝10#defineR２0//最大資源總數(shù)R=20ｉｎｔＡＶAＩLAＢLE[R］;／/可運(yùn)用資源向量inｔMAＸ[W][R]；//最大需求矩陣intAＬLOCATＩOＮ[W］[R];/／分派矩陣intＮEED[W][R］；//需求矩陣inｔReｑｕesｔ［R];/／進(jìn)程請(qǐng)求向量voｉdchangdata（intk)；//進(jìn)程請(qǐng)求資源數(shù)據(jù)改變ｉｎtchｋｓec(inｔs）;//系統(tǒng)安全性的檢測(cè)重要模塊vｏidinpｕｔdata()voidsｈｏwｄaｔa（)ｖoidchaｎgｄata(ｉnｔｋ)vｏiｄrｅstｏreｄatａ(intｋ）intchkｓｅc(intｓ)iｎtｃhkmax(ｉnts)5.算法流程圖三、調(diào)試記錄與分析調(diào)試通過(guò),程序未犯錯(cuò)四、運(yùn)營(yíng)結(jié)果及說(shuō)明執(zhí)行結(jié)果結(jié)果分析銀行家算法就是當(dāng)接受到一個(gè)系統(tǒng)資源的分派后找到一個(gè)安全序列,使得進(jìn)程間不會(huì)發(fā)生死鎖，若發(fā)生死鎖則讓進(jìn)程等待。五、課程設(shè)計(jì)總結(jié)通過(guò)本次銀行家算法實(shí)驗(yàn),加深了我對(duì)銀行家算法的了解，掌握了如何運(yùn)用銀行家算法避免死鎖。實(shí)驗(yàn)中碰到點(diǎn)問(wèn)題，通過(guò)查閱資料、詢問(wèn)老師順利解決。通過(guò)這次的實(shí)踐，使我的理論知識(shí)更加的牢固。附錄程序源碼:#inｃｌude<ｉostreaｍ＞usｉngnamespaｃestd;#ｄeｆinｅＦALSE０#ｄｅfｉneTＲUＥ1#ｄefinｅW10／/最大進(jìn)程數(shù)W=10#ｄeｆineＲ20//最大資源總數(shù)R=2０inｔM；intＮ；intALＬ＿RESＯUＲCE[W］;iｎtＡVAIＬAＢLE[R];/／可運(yùn)用資源向量intMAＸ[W][R];//最大需求矩陣iｎtＡＬLＯＣＡTＩOＮ[W][R];//分派矩陣intＮＥED[W][Ｒ];／／需求矩陣intReqｕeｓt[R］;//進(jìn)程請(qǐng)求向量voiｄinputdaｔa(）;/／數(shù)據(jù)輸入voiｄｓhoｗｄaｔa();//數(shù)據(jù)顯示voｉdcｈaｎgdata(iｎtk);//進(jìn)程請(qǐng)求資源數(shù)據(jù)改變ｖｏidreｓｔoreｄatａ(iｎtk)；//數(shù)據(jù)恢復(fù)intchksec(ｉntｓ);/／系統(tǒng)安全性的檢測(cè)iｎtcｈkmax(iｎts)；//檢測(cè)最大需求voiｄbanｋ(）;//檢測(cè)分派的資源是否合理intmain(){iｎti,j；inpuｔdata（）;／/安全性算法ｆｏr(i=0;i<M;i++）{?j=ｃhksec(ｉ);?ｉf(ｊ==0)bｒeak;｝iｆ(i＞=Ｍ)couｔ<<＂錯(cuò)誤提醒:經(jīng)安全性檢查發(fā)現(xiàn)，系統(tǒng)的初始狀態(tài)不安全！!!＼n"＜<endl；ｅlｓe{ｃoｕt<<＂提醒：經(jīng)安全性檢查發(fā)現(xiàn)，系統(tǒng)的初始狀態(tài)安全！"＜<enｄｌ;?bank（);}retuｒn0;}voidiｎputdata()//數(shù)據(jù)輸入{?inti=0,ｊ=0,p；ｃout＜＜"請(qǐng)輸入總進(jìn)程數(shù):"<<ｅndl;do{?ｃｉｎ>>Ｍ； if(M>W)coｕt<<endl<＜"總進(jìn)程數(shù)超過(guò)了程序允許的最大進(jìn)程數(shù),請(qǐng)重新輸入："<<endl;}whiｌe(M>W）;cout<<ｅｎdl;cout＜<"請(qǐng)輸入資源的種類數(shù):"<＜ｅndl；do{cin＞>N； if(N＞R)ｃouｔ＜<enｄl＜<"資源的種類數(shù)超過(guò)了程序允許的最大資源種類數(shù)，請(qǐng)重新輸入:＂＜<ｅｎdl;}ｗｈile(N>R);cout<<enｄl；ｃouｔ<<"請(qǐng)依次輸入各類資源的總數(shù)量,即設(shè)立向量all_resｏurｃe:＂<<eｎｄｌ;for(i＝0;i＜Ｎ;i＋+) cin＞＞ＡLL＿RESＯURＣE[i];cout<＜enｄl;couｔ＜<"請(qǐng)依次輸入各進(jìn)程所需要的最大資源數(shù)量，即設(shè)立矩陣max：＂<<endl;fｏr(ｉ=0;i<M;i++){foｒ(j=0;j<N;j＋＋）{ｄo｛cin＞>MAX[i][j］；if(ＭAX［ｉ］[ｊ]>ＡＬL＿ＲESOURCE[ｊ])ｃouｔ＜＜endl<<"該最大資源數(shù)量超過(guò)了聲明的該資源總數(shù),請(qǐng)重新輸入："＜＜endl;｝ｗhile（MAＸ[i][j]>ALL_REＳOＵRCE［ｊ]）;}｝cout<＜endｌ;cｏut＜<"請(qǐng)依次輸入各進(jìn)程已經(jīng)占據(jù)的各類資源數(shù)量，即設(shè)立矩陣alloｃａｔion:"<<enｄl;fｏｒ(i=0;ｉ＜M;i＋+）{ foｒ(j＝0;j<N;j++) {? ｄo{?ciｎ>＞ALLＯCAＴION［ｉ］[ｊ];?? if(ALＬOCＡTＩＯN[ｉ]［j]>MAX[i］[j]）? ??cout<＜endl<<＂已占有的資源數(shù)量超過(guò)了聲明的最大資源數(shù)量，請(qǐng)重新輸入:＂<<ｅndｌ; }while(ＡLLOＣATION[ｉ][ｊ］>MAX［ｉ][j])；?}}cout<<ｅｎdl；foｒ(i=0；ｉ<M；i++) foｒ(j=0;j＜Ｎ;ｊ＋+) NEED［i］［j]=MAX[i][j]-ＡLＬＯＣAＴIＯN[i]［j];fｏr（j=0;j＜N;j++）{ p＝ALL_RESOUＲCE［j］;?for(i=0；i<M;i++) ｛p=p-ALLＯCＡTＩＯN[ｉ]［ｊ］;AVAIＬAＢLE[j]=p;ｉｆ(AVＡILAＢLE[j]＜0） ? AVAＩLＡBLE[j]=0; ｝}}voiｄｓhowdａt(yī)a（)//銀行家算法｛ｉnｔi,j;ｃout＜<"各種資源的總數(shù)量，即向量ａll_resouｒcｅ為:"＜<ｅｎdｌ;cout<<"＂;ｆor(ｊ=0;ｊ<N；j＋+) cｏut<<"資源"<<j＜<":"<＜ALＬ＿RESOUＲＣＥ[ｊ];cout<<ｅnｄl<<eｎdｌ;couｔ<<"當(dāng)前系統(tǒng)中各類資源的可用數(shù)量，即向量available為:＂<<endｌ；coｕｔ<<"＂;foｒ(j＝０;j<N;j＋+）?coｕt<<"資源"<<j<<"："<<AVAILAＢLE[j］;coｕｔ<<endl<<ｅndl;cout<<"各進(jìn)程還需要的資源數(shù)量，即矩陣need為:＂<<ｅｎｄｌ<<endl;ｆoｒ(ｉ=0;i＜M；i++){ｃout＜<"進(jìn)程P"<<i<＜＂：";for(j＝０;j<Ｎ;j++)??ｃouｔ<<NＥED[ｉ][j]<＜"";couｔ＜<endl;｝coｕt＜<endｌ;couｔ<<＂各進(jìn)程已經(jīng)得到的資源量,即矩陣ａlloｃatioｎ為:"<<endl<<ｅndl;foｒ(ｉ=０;i<M；i++)｛?cｏuｔ<<"進(jìn)程P＂＜<i＜<":"; for(j=０；j<Ｎ;j++） ?cout<<ＡＬＬOCＡTION[ｉ][ｊ］<<"";?cout<＜eｎdl;｝ｃout<<endｌ;｝ｖoidｃhanｇdaｔa(ｉｎtｋ)／/進(jìn)程請(qǐng)求資源數(shù)據(jù)改變{ ｉｎｔj;?for(j=０;j<N;j＋＋) ｛ ＡVＡIＬＡＢLE[ｊ］=AVAIＬAＢLE[j]－Requesｔ[j];? ALLOＣATION[ｋ］[j］＝ALLOCATＩON[k][j］+Rｅｑｕest[j];??NEED[k][ｊ]=NEED[k]［j]-Request[ｊ]; }}vｏiｄrestoｒedata(ｉｎｔｋ）/／數(shù)據(jù)恢復(fù){?iｎｔｊ; ｆｏｒ(j=0;j＜N;j+＋)?{?AVAILABLＥ[ｊ]＝ＡＶAIＬABLE［ｊ］+Ｒｅquｅｓｔ［j］; ?ALLOCAＴIＯN[k]［j]=ALＬOCＡTION[k］[ｊ］-Reｑuesｔ［ｊ]; ＮEED[k][j］=NEＥD［ｋ]［j]+Ｒequｅst[j];?}}inｔchｋｓeｃ(iｎts)/／系統(tǒng)安全性的檢測(cè){?intWOＲK,FＩNISH［Ｗ］;inti,j,ｋ＝0;for（i=0；i<M;i+＋) FIＮIＳＨ[i]＝FALSＥ；ｆoｒ(ｊ＝0;j＜N;ｊ++) { ?WORＫ=AVＡILABLE[j]；ｉ=s;do {?if(ＦIＮISＨ[i］＝=FALＳE&＆NＥED[i][j］<＝WORＫ） {????ＷORK=WＯRK+ALLＯＣATＩＯN[i][ｊ］;? ＦINIＳH［i]=ＴＲＵE；?? ?ｉ=０;? ?}eｌse ?{ i++；?? } }whiｌe（i<M);for（ｉ=0;i<Ｍ;ｉ+＋)? ｉｆ(FＩNISH［ｉ]==FALSE) ? { rｅｔuｒn１；? ?} }ｒｅtuｒn０;｝inｔchkｍaｘ(ints）／/檢測(cè)最大需求{ｉnｔj,flａg=0; ｆｏr(ｊ＝0;j＜N;j＋+） ｛? if(ＭAＸ[s］[j]==ALLＯCATIＯN[s][ｊ]) {ｆlag=１;???AＶAIＬABLE[j］=ＡVＡILＡBLE[ｊ]＋MAＸ[ｓ][j］;???MＡX[ｓ][ｊ]＝0;??}?} retuｒnflａg;}ｖoidbank(){ｉnti＝0,ｊ=0;cｈaｒfｌag=＇Ｙ＇；whｉlｅ（fｌag=='Y'｜|flag＝＝'y＇) ｛i＝－1;while(i＜０||i>=M)?｛couｔ<<"請(qǐng)輸入需申請(qǐng)資源的進(jìn)程號(hào)(從P0到Ｐ"<＜M-1<<＂，否則重新輸入!):＂;couｔ＜<"p＂;? cin>＞i;if(i<0｜｜i>＝M) cout<<"輸入的進(jìn)程號(hào)不存在,重新輸入!＂＜<enｄl;?}?coｕt<＜"請(qǐng)輸入進(jìn)程P"<<i<<"申請(qǐng)的資源數(shù):＂<<endｌ;?foｒ(j=0；j<Ｎ;j++)?｛ ｃｏｕｔ<<"資源＂＜<j＜＜＂："；??ｃｉn>>Reqｕeｓt［j］;iｆ(Reｑuｅst[j]>NＥＥＤ［i]［j]） ?｛cｏut<<"進(jìn)程P＂＜<i<＜"申請(qǐng)的資源數(shù)大于進(jìn)程P"<＜i<<"還需要"<＜j<＜"類資源的資源量！"; ?cｏuｔ<<＂申請(qǐng)不合理,犯錯(cuò)！請(qǐng)重新選擇!"<＜endl<<endl;???flag＝'N'; ??bｒeak;??}? eｌsｅ ｛ if（Rｅqueｓt[j］>AＶAＩLABLE［ｊ])