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

2、的死鎖算法，具體算法如下表示：假設進程P提出請求Requesti，則銀行家算法按如下步驟進行判斷：1) 如果Requesti <=Needi，則轉向2）；否則出錯。2) 如果Requesti <=Availablei，則轉向3）；否則出錯。3) 系統試探分配相關資源，修改相關數據：Availablei=Availablei-Requesti;Allocationi=Allocationi+Requesti;Needi=Needi-Requesti;4) 系統執(zhí)行安全性檢查，如安全，則分配成立；否則試探性分配資源作廢，系統恢復原狀，進程進入等待狀態(tài)。根據以上銀行家算法步驟，可得出如下

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

4、，請求被拒。5) 根據以上安全檢查算法步驟，可得出如下圖所示流程圖:主要數據結構#include <iostream.h>/全局變量定義int Available100; /可利用資源數組int Max50100; /最大需求矩陣int Allocation50100; /分配矩陣int Need50100; /需求矩陣int Request50100; /M個進程還需要N類資源的資源量int Finish50;int p50;int m,n; /M個進程,N類資源主要代碼結構/安全性算法int Safe() int i,j,l=0;int Work100; /可利用資源數組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<<"系統是安全的"<<'n'cout&

6、lt;<"系統安全序列是: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<<"輸入進程的數目:n"cin>>m;cout<<"輸入資源的種類:n"cin>>n;cout<<"輸入每個進程最多所需的各類資源數,按照"<

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

9、quot;cin>>mi;cout<<"輸入進程所請求的各個資源的數量n"for (i=0;i<n;i+)if (Requestmii>Needmii)cout<<"所請求資源數超過進程的需求量！n"return 0;if (Requestmii>Availablei)cout<<"所請求資源數超過系統所有的資源數！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; /標志位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. 在開始編寫程序時，由于相關參數由用戶自己進行輸入時，由于運用scanf和printf語句，造成程序長度很長，而且輸入子程序復雜度為O(n2)，程序反應速度也比較慢。后來改用cin