操作系統(tǒng)銀行家算法.doc

操作系統(tǒng) 銀行家算法操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)繕?biāo)1. 理解銀行家算法。2. 掌握進(jìn)程安全性檢查的方法及資源分配的方法。3. 加深了解有關(guān)資源申請、避免死鎖等概念。4. 體會和了解死鎖和避免死鎖的具體實(shí)施方法。實(shí)驗(yàn)要求編寫和調(diào)試一個(gè)系統(tǒng)動態(tài)分配資源的簡單模擬程序，觀察死鎖產(chǎn)生的條件，并采用銀行家算法，有效的防止和避免死鎖的發(fā)生。設(shè)計(jì)思路1.銀行家算法在避免死鎖的方法中，如果施加的限制條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖?；舅枷霝椋涸诜峙滟Y源之前，判斷系統(tǒng)是否是安全的；若安全，才分配。它是最具代表性的死鎖算法，具體算法如下表示：假設(shè)進(jìn)程P提出請求Requesti，則銀行家算法按如下步驟進(jìn)行判斷：1) 如果Requesti =Needi，則轉(zhuǎn)向2）；否則出錯。2) 如果Requesti =Availablei，則轉(zhuǎn)向3）；否則出錯。3) 系統(tǒng)試探分配相關(guān)資源，修改相關(guān)數(shù)據(jù)：Availablei=Availablei-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;4) 系統(tǒng)執(zhí)行安全性檢查，如安全，則分配成立；否則試探性分配資源作廢，系統(tǒng)恢復(fù)原狀，進(jìn)程進(jìn)入等待狀態(tài)。根據(jù)以上銀行家算法步驟，可得出如下圖所示流程圖:2.安全性檢查算法安全性檢查算法主要是根據(jù)銀行家算法進(jìn)行資源分配后，檢查資源分配后的系統(tǒng)狀態(tài)是否處于安全狀態(tài)之中。具體算法如下所示:1) 設(shè)置兩個(gè)工作向量Work=Available，F(xiàn)inish=false；2) 從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程；Finish=false;Need=work;如果能夠找到該進(jìn)程，則執(zhí)行3），否則，執(zhí)行4）；3) 假設(shè)上述找到的進(jìn)程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work=Work+Allocation;Finish=true;Goto 2);4) 如果所有進(jìn)程的Finish=true，則表示該系統(tǒng)安全，否則系統(tǒng)不安全，請求被拒。5) 根據(jù)以上安全檢查算法步驟，可得出如下圖所示流程圖:主要數(shù)據(jù)結(jié)構(gòu)#include /全局變量定義int Available100; /可利用資源數(shù)組int Max50100; /最大需求矩陣int Allocation50100; /分配矩陣int Need50100; /需求矩陣int Request50100; /M個(gè)進(jìn)程還需要N類資源的資源量int Finish50;int p50;int m,n; /M個(gè)進(jìn)程,N類資源主要代碼結(jié)構(gòu)/安全性算法int Safe() int i,j,l=0;int Work100; /可利用資源數(shù)組for (i=0;in;i+)Worki=Availablei;for (i=0;im;i+)Finishi=0;for (i=0;im;i+)if (Finishi=1)continue;elsefor (j=0;jWorkj)break;if (j=n)Finishi=1;for(int k=0;kn;k+)Workk+=Allocationik;pl+=i;i=-1;else continue;if (l=m)cout系統(tǒng)是安全的n;cout系統(tǒng)安全序列是:n;for (i=0;il;i+)coutpi;if (i!=l-1)cout;coutn;return 1;/銀行家算法int main()int i,j,mi;coutm;coutn;cout輸入每個(gè)進(jìn)程最多所需的各類資源數(shù),按照mxn矩陣輸入n;for (i=0;im;i+)for(j=0;jMaxij;cout輸入每個(gè)進(jìn)程已經(jīng)分配的各類資源數(shù),按照mxn矩陣輸入n;for (i=0;im;i+)for(j=0;jAllocationij;Needij=Maxij-Allocationij;if (Needij0)cout你輸入的第i+1個(gè)進(jìn)程所擁有的第j+1個(gè)資源錯誤，請重新輸入:n;j-;continue;cout請輸入各個(gè)資源現(xiàn)有的數(shù)目:n;for (i=0;iAvailablei;Safe();while (1)coutmi;cout輸入進(jìn)程所請求的各個(gè)資源的數(shù)量n;for (i=0;iNeedmii)coutAvailablei)cout所請求資源數(shù)超過系統(tǒng)所有的資源數(shù)！n;return 0;for (i=0;in;i+)Availablei-=Requestmii;Allocationmii+=Requestmii;Needmii-=Requestmii;if (Safe()cout同意分配請求n;elsecoutSORRY()你的請求被拒絕n;for (i=0;in;i+)Availablei+=Requestmii;Allocationmii-=Requestmii;Needmii+=Requestmii;for (i=0;im;i+) Finishi=0;char Flag; /標(biāo)志位coutFlag;if (Flag=Y|Flag=y|Flag=N|Flag=n)break;elsecout請按要求重新輸入:n;continue;if (Flag=Y|Flag=y)continue;else break;主要代碼段分析1. 在開始編寫程序時(shí)，由于相關(guān)參數(shù)由用戶自己進(jìn)行輸入時(shí)，由于運(yùn)用scanf和printf語句，造成程序長度很長，而且輸入子程序復(fù)雜度為O(n2)，程序反應(yīng)速度也比較慢。后來改用cin和cout函數(shù)程序長度大大縮短。2. 由于程序的可重復(fù)使用的方便性，采取設(shè)立標(biāo)志位Flag，由用