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

1、操作系統(tǒng) 銀行家算法操作系統(tǒng)實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)繕?biāo)1. 理解銀行家算法。2. 掌握進(jìn)程安全性檢查的方法及資源分配的方法。3. 加深了解有關(guān)資源申請(qǐng)、避免死鎖等概念。4. 體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。實(shí)驗(yàn)要求編寫(xiě)和調(diào)試一個(gè)系統(tǒng)動(dòng)態(tài)分配資源的簡(jiǎn)單模擬程序，觀察死鎖產(chǎn)生的條件，并采用銀行家算法，有效的防止和避免死鎖的發(fā)生。設(shè)計(jì)思路1.銀行家算法在避免死鎖的方法中，如果施加的限制條件較弱，有可能獲得令人滿(mǎn)意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)始終都處于安全狀態(tài)，便可以避免發(fā)生死鎖?；舅枷霝椋涸诜峙滟Y源之前，判斷系統(tǒng)是否是安全的；若安全，才分配。它是最具代表性

2、的死鎖算法，具體算法如下表示：假設(shè)進(jìn)程P提出請(qǐng)求Requesti，則銀行家算法按如下步驟進(jìn)行判斷：1) 如果Requesti <=Needi，則轉(zhuǎn)向2）；否則出錯(cuò)。2) 如果Requesti <=Availablei，則轉(zhuǎn)向3）；否則出錯(cuò)。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ù)以上銀行家算法步驟，可得出如下

3、圖所示流程圖:2.安全性檢查算法安全性檢查算法主要是根據(jù)銀行家算法進(jìn)行資源分配后，檢查資源分配后的系統(tǒng)狀態(tài)是否處于安全狀態(tài)之中。具體算法如下所示:1) 設(shè)置兩個(gè)工作向量Work=Available，F(xiàn)inish=false；2) 從進(jìn)程集合中找到一個(gè)滿(mǎn)足下述條件的進(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)不安全

4、，請(qǐng)求被拒。5) 根據(jù)以上安全檢查算法步驟，可得出如下圖所示流程圖:主要數(shù)據(jù)結(jié)構(gòu)#include <iostream.h>/全局變量定義int Available100; /可利用資源數(shù)組int Max50100; /最大需求矩陣int Allocation50100; /分配矩陣int Need50100; /需求矩陣int Request50100; /M個(gè)進(jìn)程還需要N類(lèi)資源的資源量int Finish50;int p50;int m,n; /M個(gè)進(jìn)程,N類(lèi)資源主要代碼結(jié)構(gòu)/安全性算法int Safe() int i,j,l=0;int Work100; /可利用資源數(shù)組for

5、 (i=0;i<n;i+)Worki=Availablei;for (i=0;i<m;i+)Finishi=0;for (i=0;i<m;i+)if (Finishi=1)continue;elsefor (j=0;j<n;j+)if (Needij>Workj)break;if (j=n)Finishi=1;for(int k=0;k<n;k+)Workk+=Allocationik;pl+=i;i=-1;else continue;if (l=m)cout<<"系統(tǒng)是安全的"<<'n'cout&

6、lt;<"系統(tǒng)安全序列是:n"for (i=0;i<l;i+)cout<<pi;if (i!=l-1)cout<<"->"cout<<'n'return 1;/銀行家算法int main()int i,j,mi;cout<<"輸入進(jìn)程的數(shù)目:n"cin>>m;cout<<"輸入資源的種類(lèi):n"cin>>n;cout<<"輸入每個(gè)進(jìn)程最多所需的各類(lèi)資源數(shù),按照"<

7、<m<<"x"<<n<<"矩陣輸入n"for (i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;cout<<"輸入每個(gè)進(jìn)程已經(jīng)分配的各類(lèi)資源數(shù),按照"<<m<<"x"<<n<<"矩陣輸入n"for (i=0;i<m;i+)for(j=0;j<n;j+)cin>>Allocationij;Needij=Maxij-Alloc

8、ationij;if (Needij<0)cout<<"你輸入的第"<<i+1<<"個(gè)進(jìn)程所擁有的第"<<j+1<<"個(gè)資源錯(cuò)誤，請(qǐng)重新輸入:n"j-;continue;cout<<"請(qǐng)輸入各個(gè)資源現(xiàn)有的數(shù)目:n"for (i=0;i<n;i+)cin>>Availablei;Safe();while (1)cout<<"輸入要申請(qǐng)的資源的進(jìn)程號(hào)：（第一個(gè)進(jìn)程號(hào)為0，第二個(gè)進(jìn)程號(hào)為1，依此類(lèi)推）n&

9、quot;cin>>mi;cout<<"輸入進(jìn)程所請(qǐng)求的各個(gè)資源的數(shù)量n"for (i=0;i<n;i+)if (Requestmii>Needmii)cout<<"所請(qǐng)求資源數(shù)超過(guò)進(jìn)程的需求量！n"return 0;if (Requestmii>Availablei)cout<<"所請(qǐng)求資源數(shù)超過(guò)系統(tǒng)所有的資源數(shù)！n"return 0;for (i=0;i<n;i+)Availablei-=Requestmii;Allocationmii+=Requestmii

10、;Needmii-=Requestmii;if (Safe()cout<<"同意分配請(qǐng)求n"elsecout<<"SORRY()你的請(qǐng)求被拒絕n"for (i=0;i<n;i+)Availablei+=Requestmii;Allocationmii-=Requestmii;Needmii+=Requestmii;for (i=0;i<m;i+) Finishi=0;char Flag; /標(biāo)志位cout<<"是否再次請(qǐng)求分配？是請(qǐng)按Y/y，否請(qǐng)按N/n"while (1)cin>>Flag;if (Flag='Y'|Flag='y'|Flag='N'|Flag='n')break;elsecout<<"請(qǐng)按要求重新輸入:n"continue;if (Flag='Y'|Flag='y')continue;else break;主要代碼段分析1. 在開(kāi)始編寫(xiě)程序時(shí)，由于相關(guān)參數(shù)由用戶(hù)自己進(jìn)行輸入時(shí)，由于運(yùn)用scanf和printf語(yǔ)句，造成程序長(zhǎng)度很長(zhǎng)，而且輸入子程序復(fù)雜度為O()，程序反應(yīng)速度也比較慢。后來(lái)改用cin