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

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

2、的死鎖算法，具體算法如下表示：假設(shè)進程P提出請求Requesti，則銀行家算法按如下步驟進行判斷：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ù)原狀，進程進入等待狀態(tài)。根據(jù)以上銀行家算法步驟，可得出如下

3、圖所示流程圖:2.安全性檢查算法安全性檢查算法主要是根據(jù)銀行家算法進行資源分配后，檢查資源分配后的系統(tǒng)狀態(tài)是否處于安全狀態(tài)之中。具體算法如下所示:1) 設(shè)置兩個工作向量Work=Available，F(xiàn)inish=false；2) 從進程集合中找到一個滿足下述條件的進程；Finish=false;Need<=work;如果能夠找到該進程，則執(zhí)行3），否則，執(zhí)行4）；3) 假設(shè)上述找到的進程獲得資源，可順利執(zhí)行，直至完成，從而釋放資源。Work=Work+Allocation;Finish=true;Goto 2);4) 如果所有進程的Finish=true，則表示該系統(tǒng)安全，否則系統(tǒng)不安全

4、，請求被拒。5) 根據(jù)以上安全檢查算法步驟，可得出如下圖所示流程圖:主要數(shù)據(jù)結(jié)構(gòu)#include <iostream.h>/全局變量定義int Available100; /可利用資源數(shù)組int Max50100; /最大需求矩陣int Allocation50100; /分配矩陣int Need50100; /需求矩陣int Request50100; /M個進程還需要N類資源的資源量int Finish50;int p50;int m,n; /M個進程,N類資源主要代碼結(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<<"輸入進程的數(shù)目:n"cin>>m;cout<<"輸入資源的種類:n"cin>>n;cout<<"輸入每個進程最多所需的各類資源數(shù),按照"<

7、<m<<"x"<<n<<"矩陣輸入n"for (i=0;i<m;i+)for(j=0;j<n;j+)cin>>Maxij;cout<<"輸入每個進程已經(jīng)分配的各類資源數(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<<"個進程所擁有的第"<<j+1<<"個資源錯誤，請重新輸入:n"j-;continue;cout<<"請輸入各個資源現(xiàn)有的數(shù)目:n"for (i=0;i<n;i+)cin>>Availablei;Safe();while (1)cout<<"輸入要申請的資源的進程號：（第一個進程號為0，第二個進程號為1，依此類推）n&

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

10、;Needmii-=Requestmii;if (Safe()cout<<"同意分配請求n"elsecout<<"SORRY()你的請求被拒絕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<<"是否再次請求分配？是請按Y/y，否請按N/n"while (1)cin>>Flag;if (Flag='Y'|Flag='y'|Flag='N'|Flag='n')break;elsecout<<"請按要求重新輸入:n"continue;if (Flag='Y'|Flag='y')continue;else break;主要代碼段分析1. 在開始編寫程序時，由于相關(guān)參數(shù)由用戶自己進行輸入時，由于運用scanf和printf語句，造成程序長度很長，而且輸入子程序復(fù)雜度為O()，程序反應(yīng)速度也比較慢。后來改用cin