操作系統(tǒng)課程設(shè)計(jì)銀行家算法

操作系統(tǒng)課程設(shè)計(jì)報(bào)告小組成員指導(dǎo)教師吉林建筑大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院年月日銀行家算法

摘要本次的課程設(shè)計(jì)內(nèi)容是銀行家算法，在操作系統(tǒng)當(dāng)中，由于競(jìng)爭(zhēng)非剝奪性資源和進(jìn)程推進(jìn)的不當(dāng)，對(duì)系統(tǒng)的安全造成威脅，所以，銀行家算法就是為了避免對(duì)系統(tǒng)產(chǎn)生死鎖而存在的。銀行家算法包括對(duì)請(qǐng)求資源的試分配和對(duì)安全性的考量，當(dāng)系統(tǒng)的安全性不能夠滿足的時(shí)候，則對(duì)系統(tǒng)進(jìn)行保護(hù)。在編寫(xiě)銀行家算法的時(shí)候需要定義Need（需求矩陣），Allocation（分配矩陣），Max（最大需求矩陣）以及Available（可利用資源量）。在實(shí)現(xiàn)一系列的功能的時(shí)候使用的數(shù)組的結(jié)構(gòu)，便于進(jìn)行矩陣的加減運(yùn)算，可以提高程序的運(yùn)行效率。通過(guò)編寫(xiě)可以基本上實(shí)現(xiàn)銀行家算法所要達(dá)到的基本目的，在輸入正確的情況下能夠輸出正確的安全序列，在不安全的情況下可以做出提醒，并且恢復(fù)原有輸入數(shù)據(jù)。關(guān)鍵字：銀行家算法最大需求矩陣分配矩陣需求矩陣可利用資源量1緒論銀行家算法是操作系統(tǒng)當(dāng)中為避免鎖死的算法，并且是最具有代表性的避免鎖死的算法，能夠有效的在資源分配的過(guò)程中，對(duì)系統(tǒng)的安全性進(jìn)行檢測(cè)。整個(gè)算法的計(jì)算步驟為對(duì)輸入的數(shù)據(jù)進(jìn)行試分配，并對(duì)安全性進(jìn)行檢測(cè)，當(dāng)系統(tǒng)為安全的時(shí)，依照安全序列執(zhí)行程序，如果不安全則進(jìn)入阻塞狀態(tài)。銀行家算法的來(lái)源是在銀行中，客戶申請(qǐng)貸款的數(shù)量是有限的，每個(gè)客戶在第一次申請(qǐng)貸款時(shí)要聲明完成該項(xiàng)目所需的最大資金量，在滿足所有貸款要求時(shí)，客戶應(yīng)及時(shí)歸還。銀行家在客戶申請(qǐng)的貸款數(shù)量不超過(guò)自己擁有的最大值時(shí)，都應(yīng)盡量滿足客戶的需要。在這樣的描述中，銀行家就好比操作系統(tǒng)，資金就是資源，客戶就相當(dāng)于要申請(qǐng)資源的進(jìn)程在鋁免死鎖的方法中，所施加的簡(jiǎn)直條件比在預(yù)防死鎖的方法中限制條件要弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中，把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，就可避免死鎖的發(fā)生。所謂安全狀態(tài)與不安全狀態(tài)是指如果所有過(guò)程有可能完成執(zhí)行（終止），則一個(gè)狀態(tài)被認(rèn)為是安全的。由于系統(tǒng)無(wú)法知道什么時(shí)候一個(gè)過(guò)程將終止，或者之后它需要多少資源，系統(tǒng)假定所有進(jìn)程將最終試圖獲取其聲明的最大資源并在不久之后終止2需求分析2.1問(wèn)題描述：在多道程序系統(tǒng)中，雖然能夠借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來(lái)改善系統(tǒng)資源的利用率，提高系統(tǒng)的吞吐量，但是依然有風(fēng)險(xiǎn)存在，那就是一一鎖死。所謂鎖死是指，多個(gè)進(jìn)程在運(yùn)行中因爭(zhēng)奪資源而造成的一種僵局，當(dāng)進(jìn)程的這種僵持狀態(tài)時(shí)，若無(wú)外力作用，它們將無(wú)法再向前推進(jìn)。一組程序中，每個(gè)進(jìn)程都無(wú)限等待被該組進(jìn)程中的另一進(jìn)程所占有的資源，因而永遠(yuǎn)無(wú)法得到資源，這種現(xiàn)象就叫做進(jìn)程死鎖。2.2產(chǎn)生條件1、進(jìn)程間競(jìng)爭(zhēng)非剝奪性資源2、進(jìn)程保持申請(qǐng)3、資源的獨(dú)占，一個(gè)資源同一時(shí)刻只能分配給一個(gè)進(jìn)程4、進(jìn)程循環(huán)等待資源2.3運(yùn)行環(huán)境VisualC++6.02.4程序功能在該程序中應(yīng)該具有以下功能：1、從外界輸入進(jìn)程數(shù)，資源數(shù)以及完成銀行家算法的所需的各類資源數(shù)。2、當(dāng)輸入越界或者非法輸入時(shí)能夠提示錯(cuò)誤。3、當(dāng)進(jìn)程推進(jìn)處于不安全狀態(tài)時(shí)要能夠進(jìn)行提示處于不安全狀態(tài)，并且能夠恢復(fù)數(shù)據(jù)到初始狀態(tài)。當(dāng)請(qǐng)求資源量大于可利用資源數(shù)時(shí)要能夠進(jìn)行提醒，并且重新輸入。4、當(dāng)數(shù)據(jù)完成初始化時(shí)，要能夠輸出數(shù)據(jù)所對(duì)應(yīng)的矩陣。3概要設(shè)計(jì)3.1程序模塊本程序包括了四個(gè)基本模塊：主函數(shù)、試分配、安全性測(cè)試、數(shù)據(jù)的輸入與輸出。11主函主函數(shù)用于輸出系統(tǒng)的主要操作界面，以及調(diào)用其他的函數(shù)，完成銀行家算法。2試分配：對(duì)輸入的進(jìn)程的Max、AvailablesAllocation以及Request進(jìn)行分配，判斷是否可以正常分配。3安全性測(cè)試：當(dāng)試分配完成時(shí)，通過(guò)安全性測(cè)試來(lái)對(duì)系統(tǒng)的安全性進(jìn)行檢測(cè)，安全時(shí)輸出安全序列，不安全時(shí)進(jìn)行提醒，并且恢復(fù)到初始化時(shí)輸入的數(shù)據(jù)。3.2模塊之間關(guān)系主函數(shù)可以調(diào)用系統(tǒng)的所有函數(shù)，以及輸出功能界面，將試分配函數(shù)，安全性測(cè)試函數(shù)和輸入輸出函數(shù)定義在主函數(shù)當(dāng)中，在需要時(shí)通過(guò)相應(yīng)的選項(xiàng)進(jìn)行調(diào)用。而試分配與安全性測(cè)試是并列的兩個(gè)函數(shù)，存在執(zhí)行試分配后需對(duì)安全序列進(jìn)行判斷。輸入輸出函數(shù)，確定數(shù)值，并將相對(duì)應(yīng)的數(shù)據(jù)輸入到對(duì)應(yīng)的模塊，來(lái)進(jìn)行計(jì)算。3.3數(shù)據(jù)結(jié)構(gòu)程序當(dāng)中需要四種數(shù)據(jù)結(jié)構(gòu)。1、可利用資源矩陣(Available)＞當(dāng)Available[]=k時(shí)，這表示系統(tǒng)中有該類資源k個(gè)。2、最大需求矩陣(Max),當(dāng)Max[][]=k時(shí)，則表示進(jìn)程需要的資源為k個(gè)。3、分配矩陣(Allocation),當(dāng)Allocation□□二k時(shí)，則表示進(jìn)程當(dāng)前己被分得k個(gè)資源。4、需求矩陣(Need),當(dāng)Need[][]=k時(shí)，則表示進(jìn)程還需要k個(gè)資源才能夠完成。3.4算法思想操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請(qǐng)資源時(shí)，要測(cè)試該進(jìn)程對(duì)資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量則按當(dāng)前的申請(qǐng)量分配資源，否則就推退分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程己占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)了該進(jìn)程對(duì)資源的最大需求量。若超過(guò)則拒絕分配資源，若沒(méi)有超過(guò)則再測(cè)試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則也要推遲分配。4詳細(xì)設(shè)計(jì)4.1程序模塊劃分：4.1.1數(shù)據(jù)的初始化：根據(jù)提示輸入最大需求矩陣(Max),可利用資源量(Available),分配矩陣(Allocation)所需的數(shù)據(jù)。4.1.2輸出所對(duì)應(yīng)的矩陣：根據(jù)輸入的數(shù)據(jù)輸出對(duì)應(yīng)的矩陣，并且計(jì)算出需求矩陣(Need),將完整的算法需要的數(shù)據(jù)呈現(xiàn)給操作者。3試分配：根據(jù)操作者所輸入的進(jìn)程號(hào)己經(jīng)請(qǐng)求，對(duì)系統(tǒng)進(jìn)行時(shí)分配。4安全測(cè)試當(dāng)試分配完成時(shí)可進(jìn)行安全性測(cè)試，當(dāng)進(jìn)程間是安全的時(shí)候則可以輸出相應(yīng)的安全序列。如果錯(cuò)誤，則可以回到數(shù)據(jù)的初始化狀態(tài)。4.2數(shù)據(jù)判斷當(dāng)輸入的數(shù)據(jù)不符合規(guī)定時(shí)，可以對(duì)該數(shù)據(jù)進(jìn)行判斷，不符合條件重新輸入,例如：if(!(O<=in&&in<=t-l)),在程序中，用于判斷所輸入的進(jìn)程號(hào)是否滿足要求，如果不滿足要求通過(guò)該語(yǔ)句輸出“cout?〃該進(jìn)程不存在，重新輸入，/?endl;,,o4.3函數(shù)調(diào)用通過(guò)switch語(yǔ)句對(duì)所調(diào)用的函數(shù)進(jìn)行判斷。switch(choice)(case1:Input();break;//輸入相關(guān)數(shù)據(jù)函數(shù)case2：Print();break;//打印輸出相關(guān)數(shù)據(jù)表函數(shù)case3:cout<<，z請(qǐng)輸入有請(qǐng)求的進(jìn)程號(hào)："break：case4:checksafe(in);break;//安全性檢查case5:refenpei(in);break;//恢復(fù)數(shù)據(jù)}4.4程序流程圖5測(cè)試與分析5.1程序調(diào)試：1、在數(shù)據(jù)初始化當(dāng)中要考慮到輸入進(jìn)程數(shù)是否為負(fù)數(shù)，是否為字符。2、在安全性算法當(dāng)中要考慮到當(dāng)不安全時(shí)，數(shù)據(jù)能否恢復(fù)，是否可以重新進(jìn)行分配。當(dāng)輸入的Request大于Need或者大于Available的情況，當(dāng)大于是需要重新輸入。5.2程序測(cè)試：2.1輸入初始化:軻A咨源教:瞞入進(jìn)程教：斥艮行家算法「輸入腐需激據(jù)2二顯示矩辟=試分配=檢查安全性=恢復(fù)教據(jù)至U初始狀態(tài)2.2矩陣輸出

Pl—>P0—>P2——>P3進(jìn)入安全性檢測(cè)…安全序列：分配的序列二已誦過(guò)安全，性測(cè)試，開(kāi)始給第Pl—>P0—>P2——>P3進(jìn)程^Maxp。!3pl!6p2!3p3!4Allocation!：Need100!!222512!1101211!1103002：!4202342Auailable1115.2.4進(jìn)程不安全時(shí)請(qǐng)輸入有請(qǐng)求的進(jìn)程號(hào)=2愿輸入的旱PC2］進(jìn)程W求量為：103請(qǐng)輸人請(qǐng)求咨源的數(shù)目二101輸入成功，L執(zhí)行銀行家算試分配完成，該進(jìn)程需進(jìn)入安全性檢測(cè)試分配后系統(tǒng)不拿待傾復(fù)原來(lái)的數(shù)據(jù)已恢復(fù)初始狀態(tài)...輸入郵］是：101算曩進(jìn)行試分配，本次資源由請(qǐng)不成功"，Alloca,tionAua±lable6參考文獻(xiàn)湯小丹梁紅兵哲鳳屏湯子瀛，《計(jì)算機(jī)操作系統(tǒng)（第三版）》，西安：西安電子科技大學(xué)出版社王長(zhǎng)元李晉惠等編著，《軟件工程》，西安：西安地圖出版社孟慶昌等編著，《操作系統(tǒng)原理》，北京：機(jī)械工業(yè)出版社左萬(wàn)歷周長(zhǎng)林彭濤，《計(jì)算機(jī)操作系統(tǒng)教程（第三版）》，北京：高等教育出版社陳志泊王春玲孟偉，《面向?qū)ο蟮某绦蛟O(shè)計(jì)語(yǔ)言C++（第二版）》，北京：人民郵電出版社7附錄：源程序清單ttinclude<iostream.h>ttdefineM10〃資源類數(shù)#defineN50〃進(jìn)程數(shù)voidInput();〃用于輸入的函數(shù)voidPrint();〃用于打印輸出表格的函數(shù)voidtryfenpei(inti)://試分配函數(shù)voidchecksafe(intx);//安全檢測(cè)函數(shù)voidrefenpei(inti);//恢復(fù)數(shù)據(jù)函數(shù)//定義初始化數(shù)組intAvailable[M],Max[N][M],Allocation[N][M],NeedtN][M],Request[M];intc,t;//資源進(jìn)程intin;//用戶選擇的進(jìn)程號(hào)/**voidmain()(intchoice;charch=，Y';COUt?，Z輸入資源數(shù)：〃；cin>>c;COUt?，Z輸入進(jìn)程數(shù)：〃；cin>>t;do(if(ch==，Y'||ch==，y，)(cout?,，銀行家算法，，?endl;cout?z，l:輸入所需數(shù)據(jù)"《endl;cout<<z，2:顯示矩陣〃《endl;cout<<z，3:試分配〃《endl;cout<<，，4:檢查安全性〃《endl;cout?/z5:恢復(fù)數(shù)據(jù)到初始狀態(tài)〃《endl;cout〈<〃**********************"〈〈endl;COUt?Z，請(qǐng)選擇操作序號(hào)：〃；cin>>choice;switch(choice){case1:Input();//輸入相關(guān)數(shù)據(jù)函數(shù)break;case2:Print();//打印輸出相關(guān)數(shù)據(jù)表函數(shù)break;case3:cout?，z請(qǐng)輸入有請(qǐng)求的進(jìn)程號(hào):”;while(cin?in)(if(!(0<=in&&in<=t-l))(cout<<，,該進(jìn)程不存在，重新輸入，z<<endl:}elsebreak;}tryfenpei(in);//試分配break;case4:checksafe(in)://安全性檢查break;case5：refenpei(in);//恢復(fù)數(shù)據(jù)break;default:cout<<，?清(1-5)中選擇正確的操作序號(hào)!z，?endl;break;)cout?"要繼續(xù)進(jìn)行嗎?(y-是n否)〃;}elseif(ch='N'||ch==，n*)(cout<</z正在退出...，，<<endl;break;}else{cout<<〃輸入無(wú)效!重新輸入...，z<<endl:)}while(cin>>ch);}/*main函數(shù)結(jié)束*//*輸入函數(shù)*/voidInput()(intj,n,m;cout?,，輸入可利用資源:,z?endl;for(j=0;j<c;j++)(〃cout?"請(qǐng)輸入Available[〃<<j?"]:";while(cin?Available[j])(if(Available[j]<0)cout?，,輸入數(shù)字無(wú)效，請(qǐng)重新輸入，，?endl;elsebreak;}；}cout?，z輸入最大需求:,z?endl;for(n=0;n<t;n++)〃各個(gè)進(jìn)程循環(huán)輸入(for(m=0;m<c:m++)//c個(gè)類資源ABC循環(huán)輸入(while(cin>>Max[n][m]){if(Max[n][m]<0)cout?，z輸入數(shù)字無(wú)效，請(qǐng)重新輸入〃《endl;elsebreak;)；}}cout?，z輸入占有資源:，z?endl;for(n=0;n<t;n++)〃各個(gè)進(jìn)程循環(huán)輸入(for(m=0;m<c:m++)//c個(gè)類資源ABC循環(huán)輸入(while(cin>>Allocation[nJ[m])if(Allocation[n][m]<0)cout?，,輸入數(shù)字無(wú)效，請(qǐng)重新輸入，，?endl;elsebreak;NeedEn][m]=Max[n][m]-Allocation[n][m];})cout?，,初始化完成！..."?endl;}/*輸入函數(shù)結(jié)束*/

/*輸出函數(shù)*/voidPrint()inti,j;???????*|，z<<endl:cout?，z*****|z/<<endl;cout?，z進(jìn)程Max|AllocationNeedAvailable|z/<<endl;cout?，/******|，，<<endl;for(i=0;i<t;i++)■]?.]■■>■]■?1—I?]■^?x■]??]■■X■X*■]?^?x■]?^?x?1?wx■X?1?^?x■]?cout<<,，|p，/<<i<<，/|for(j=0;j<c;j++)cout<<Max[i][j]?z/〃；}cout<<"|";for(j=0;j<c;j++)(cout<<Allocation[i][j]<<〃}cout<<"I”;for(j=0;j<c;j++)(cout<<Need[i][j]<<，z〃；}cout<<"|";if(i==0)(for(j=0;j<c;j++){cout<<Available[j]<</z}cout<<〃|〃；}if(i>0)(COUt<<，ZI"；cout<<endl;}????????????????輸出函數(shù)結(jié)束*/inti;cout?，,您輸入的是〃《〃p[〃<Xn<X〃]〃《〃進(jìn)程，z?endl;cout?，,該進(jìn)程需求量為：〃；for(i=0;i<c;i++)cout<<Need[n][i]<</z”;cout<<endl;cout?，/請(qǐng)輸入請(qǐng)求資源的數(shù)目：〃；for(i=0;i<c;i++)(while(cin>>Request[i])(if(Request[i]<0){cout<<，/!!輸入的數(shù)字無(wú)效.，z<<endl;)elseif(Request[i]>Need[n][i]){cout<<〃!!超出進(jìn)程需求量，，?endl?endl;)elseif(Request[i]>Available[i])(cout?，z!!系統(tǒng)沒(méi)有足夠的可用資源量滿足進(jìn)程需要，z?endl?endl;)elsebreak;))cout<<，,輸入成功，輸入的是："；for(intf=0;f<c;f++)cout<<Request[f]<</z";cout<<endl;cout?，,執(zhí)行銀行家算法，進(jìn)行試分配...，，?endl;for(f=0;f<c:f++)(Available[f]=Available[f]-Request[f]:Allocationin][f]=Allocation[n][f]+Request[f]:NeedEn][f]=NeedLn][f]-Request[f];}cout<<z，試分配完成!z/<<endl:}/*試分配函數(shù)結(jié)束*//*安全檢測(cè)函數(shù)*/voidchecksafe(intx)(cout?,，進(jìn)入安全性檢測(cè)..."?endl;inti,m,apply,j,k=0,flag=0;intWork[M],temp[N];boolFinish[N];〃t為進(jìn)程數(shù)for(i=0;i<c;++i)(Work[i]=Available[i];}for(i=0;i<t;i++)(Finishli]=false;}for(i=0;i<t;i++)(apply=0;for(j=0;j<c;j++)(if(false==Finish[i]&&Need[i][j]<=Work[j]){apply++;〃標(biāo)