操作系統(tǒng)課程設(shè)計之模擬通過銀行家算法避免死鎖

1、模擬通過銀行家算法避免死鎖一、 銀行家算法產(chǎn)生的背景及目的 1：在多道程序系統(tǒng)中，雖然節(jié)奏、雖然借助于多個進程的并發(fā)執(zhí)行來改善系統(tǒng)的利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險死鎖。，死鎖就是多個進程在運行過程中因爭奪資源而造成的一種僵局，當(dāng)進程處于這種僵局狀態(tài)時，如無外力作用，他們將無法再向前進行，如再把信號量作為同步工具時，多個Wait和Signal操作順序不當(dāng)，會產(chǎn)生進程死鎖。然而產(chǎn)生死鎖的必要條件有互斥條件，請求和保持條件，不剝奪條件和環(huán)路等待條件。在預(yù)防死鎖的幾種方法中，都施加了較強的限制條件，在避免死鎖的方法中，所施加的條件較弱，有可能獲得令人滿意的系統(tǒng)性能。在該方法中把系統(tǒng)的狀態(tài)

2、分為安全狀態(tài)和不安全狀態(tài)，只要能使系統(tǒng)都處于安全狀態(tài)，便可避免死鎖。2：實驗?zāi)康模鹤寣W(xué)生獨立的使用編程語言編寫和調(diào)試一個系統(tǒng)分配資源的簡單模擬程序，了解死鎖產(chǎn)生的原因及條件。采用銀行家算法及時避免死鎖的產(chǎn)生，進一步理解課堂上老師講的相關(guān)知識點。銀行家算法是從當(dāng)前狀態(tài)出發(fā)，逐個按安全序列檢查各客戶中誰能完成其工作，然后假定其完成工作且歸還全部貸款，再進而檢查下一個能完成工作的客戶。如果所有客戶都能完成工作，則找到一個安全序列，銀行家才是安全的。二：銀行家算法中的數(shù)據(jù)結(jié)構(gòu) 1：可利用資源向量Available。這是一個含有m個元素的數(shù)組，其中的每個元素代表一類可利用的資源數(shù)目，其初始值是系統(tǒng)中所配

3、置的該類全部可用資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)的改變。如果Availablej=k，z則表示系統(tǒng)中現(xiàn)有Rj類資源K 個。 2：最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Maxi,j=k，表示第i個進程需要第Rj類資源的最大數(shù)目k個.3: 分配矩陣Allocation,也是n*m的矩陣，若Allocationi,j=k,表示第i個進程已分配Rj類資源的數(shù)目為k個。 4：需求矩陣Need。也是一個n*m的矩陣，Needi,j=k,表示第i個進程還需Rj類資源k個。三、銀行家算法及安全性算法 1：銀行家算法設(shè)Request

4、i是進程Pi的請求向量，若Requestij=k;表示進程需要j類資源k個。當(dāng)Pi發(fā)出資源請求時，系統(tǒng)按下屬步驟進行檢查；(1) 如果Requestij<=Needij;便轉(zhuǎn)向步驟（2），否則認為出錯，因為它所需要的資源數(shù)已超過他所宣布的最大值。(2) 如果Requestij<=Availableij,便轉(zhuǎn)向步驟（3），否則認為尚無足夠資源，進程需等待。(3) 系統(tǒng)試探著把資源分配給進程，并修改下面數(shù)據(jù)結(jié)構(gòu)的數(shù)據(jù)Availableij=Availableij-Requestij;Allocationij=Allocationij+Requestij;Needij=Needij-Re

5、questij;(4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進程Pi，已完成此次分配。否則，將本次的試探分配作廢，回復(fù)原來的資源分配狀態(tài)，將進程Pi等待。2：安全性算法（1） 設(shè)置兩個向量； 1：工作向量Work，表示系統(tǒng)可提供給進程運行所需的各類資源數(shù)目，它含有m個元素，初始時Work=Available 2：Finish ,表示系統(tǒng)是否有足夠的資源分配給進程，使之運行完成。開始時先做Finishi=true（2） 從進程中找到一個能滿需下屬條件的進程1；Finishi=false；2：Needij<=Workj;若找到執(zhí)行步驟（3），

6、否則執(zhí)行步驟（4）（3） 當(dāng)進程Pi順利獲得資源后，直至完成，并釋放分配給它的資源，執(zhí)行： Workj=Workj+Allocationij; Finishi=true; Go to step (2);(5) 如果所有的進程Finishi都滿足，則表示系統(tǒng)處于安全狀態(tài)，否則，處于不安全狀態(tài)。四、模塊設(shè)計與分析及整體功能概述模塊設(shè)計與分析： 整個銀行家算法分為初始化函數(shù)Init（），安全性算法函數(shù) safe（），銀行家算法函數(shù)bank（）三部分。初始化函數(shù)生成開始時刻系統(tǒng)中的進程和資源情況，安全性算法判斷當(dāng)某進程申請資源時，系統(tǒng)能否處于安全狀態(tài)。在本實驗中，若系統(tǒng)處于安全狀態(tài)，便生成一個安全進程

7、序列（安全序列可能有多個）。銀行家算法函數(shù)bank（）負責(zé)整體的檢查與異常判斷。整體功能概述：死鎖會引起系統(tǒng)陷入僵局，操作系統(tǒng)必須防止此現(xiàn)象的發(fā)生。本實驗通過一個動態(tài)分配資源的模擬程序，更清楚的理解死鎖產(chǎn)生的原因和條件。Dijkstra的銀行家算法是最有代表性的避免死鎖的方法。運行程序時用戶設(shè)定系統(tǒng)中進程和可利用資源的種類數(shù)目。輸入各進程的可利用資源Available，最大需求MAX，已分配資源Allocation ，需求資源Need，之后各系統(tǒng)發(fā)出資源請求Request，利用實驗中的安全性算法判斷能否產(chǎn)生一個安全性隊列，若能，則給該進程分配成功，否則，不予分配。五、流程圖設(shè)計 六、源代碼及調(diào)

8、試分析 #include<iostream.h>#define MAXm 50 / 定義最大進程數(shù)#define MAXn 100 /定義最大資源數(shù)int MAXMAXmMAXn; /最大需求矩陣int AllocationMAXmMAXn; /已分配矩陣int AvailableMAXn; /可用資源數(shù)組int NeedMAXmMAXn; /需求矩陣int RequestMAXmMAXn; /請求矩陣int FinishMAXm; /存儲完成資源分配的進程int SequenceMAXm; /模擬的資源分配序列int WorkMAXn; /系統(tǒng)是否有足夠的資源分配給進程int m

9、,n; /m個進程,n個資源#define False 0#define True 1void input(); /數(shù)據(jù)輸入函數(shù)int safealg(); /安全性算法函數(shù)void banker(); /銀行家算法函數(shù)void main()input();safealg();banker();/*初始化算法*void input() int i,j; /*自定義進程數(shù)目與資源種類*cout<<"*n"cout<<"*利用銀行家算法避免死鎖*n" cout<<"* *n"cout<<&q

10、uot;*n"cout<<"請輸入進程的數(shù)目:"cin>>m;cout<<"請輸入資源的種類:"cin>>n;/*輸入每個進程對每種資源的最大需求、已經(jīng)獲得的數(shù)量、每種類型資源的數(shù)目cout<<"各進程資源最大需求(Max),按照"<<m<<"x"<<n<<"矩陣輸入:n"for(i=0;i<m;i+) cout<<"P"<<i&

11、lt;<":" for(j=0;j<n;j+) cin>>MAXij; if(j=n)cout<<"資源種類數(shù)匹配出現(xiàn)錯誤！"/當(dāng)資源配置的種類數(shù)大于預(yù)先輸入的數(shù)值時，出錯cout<<"各進程當(dāng)前獲得資源(Allocation),按照"<<m<<"x"<<n<<"矩陣輸入"<<endl;for(i=0;i<m;i+) cout<<"P"<<

12、i<<":"for(j=0;j<n;j+)cin>>Allocationij;if(j=n)cout<<"資源種類數(shù)匹配出現(xiàn)錯誤！"/當(dāng)資源配置的種類數(shù)大于預(yù)先輸入的數(shù)值時，出錯Needij=MAXij-Allocationij;/需求數(shù)等于最大需求減去已經(jīng)分配數(shù) cout<<"系統(tǒng)可用資源(Available):"<<endl;for(j=0;j<n;j+) cin>>Availablej;/輸入各種資源的可利用數(shù)cout<<"

13、當(dāng)前時刻的進程分配情況如圖：n"cout<<"進程號-"<<"MAX-"<<"Allocation-"<<"Need-"<<"Available-n"/顯示各進程的資源情況 for(i=0;i<m;i+) cout<<"P"<<i<<": " for(j=0;j<n;j+) cout<<" "<<

14、MAXij; for(j=0;j<n;j+) cout<<" "<<Allocationij; cout<<" " for(j=0;j<n;j+) cout<<" "<<Needij; for(j=0;j<n;j+) cout<<" "<<Availablej; cout<<endl;/回車換行/*銀行家算法，為進程分配資源*/void banker() int i,j; int choice; whi

15、le(1) cout<<endl; cout<<"輸入要進行的操作(1:分配資源 2:離開) :" /用戶選擇 cin>>choice; if(choice=1) /分配資源 cout<<"從P0到P"<<m-1<<"之間選擇要分配資源的進程號:n"cin>>i; if(i>=m) cout<<"無此進程號!請重新輸入:n" cin>>i;/重新輸入進程號 cout<<"請輸入進程

16、申請的資源(Request):"<<endl;for(j=0;j<n;j+)cin>>Requestij; /*銀行家算法進行檢查*/ for(j=0;j<n;j+)if(Requestij>Needij)cout<<"申請的資源大于它需要的資源數(shù),請重新輸入!n"/資源申請不合理continue; if(Requestij>Availablej)/資源申請數(shù)目大于可利用數(shù)，無法分配，得等待cout<<"當(dāng)前系統(tǒng)可用資源不夠，請等待!"<<endl;contin

17、ue; for(j=0;j<n;j+)/資源申請得到允許時，變換各個資源數(shù) Availablej=Availablej-Requestij; /可用資源減少 Allocationij=Allocationij+Requestij;/所得資源增加 Needij=Needij-Requestij; /仍需資源減少if(safealg()<0)/安全性算法的返回值cout<<"分配不成功，請等待！"for (j=0;j<n;j+) /把資源恢復(fù)成分配之前的狀態(tài) Availablej=Availablej+Requestij; Allocationij

18、=Allocationij-Requestij; Needij=Needij+Requestij; for(i=0;i<m;i+) Finishi=False;/沒有足夠的資源分配給該進程/if(safealg()<0) else cout<<"同意分配請求!"<<endl; for(j=0;j<n;j+) Workj=Availablej; cout<<"進程號-"<<"-Work-"<<"Need-"<<"All

19、ocation-"<<"Work+Allocation-" <<"Finish-"<<endl; for(i=0;i<m;i+)/按模擬分配序列進行分配 cout<<"進程P"<<Sequencei<<": " for(j=0;j<n;j+)cout<<Workj<<" " cout<<" "for(j=0;j<n;j+)cout<&l

20、t;NeedSequenceij<<" "cout<<" "for(j=0;j<n;j+)cout<<AllocationSequenceij<<" "cout<<" "for(j=0;j<n;j+)cout<<AllocationSequenceij+Workj<<" "cout<<" " cout<<FinishSequencei<<&quo

21、t; "/完成該進程for(j=0;j<n;j+)Workj=AllocationSequenceij+Workj;/回收該進程所分配的資源cout<<endl; /if(safealg()>=0)/if(choice=1)else if(choice=2) /離開break; else cout<<"請輸入1或2!"/只認可1或2/while(1)/*安全性算法 */int safealg() int i,j,k,l=0; /int WorkMAXn; /工作組 /記錄序列 for(i=0;i<n;i+) Worki=A

22、vailablei; /工作分配初始化為系統(tǒng)可用資源 for(i=0;i<m;i+) /掃描所有進程，預(yù)設(shè)所有進程不能運行 Finishi=False; for(i=0;i<m;i+) /if(Finishi=True) continue; else /對于未運行的進程，進行如下處理 / for(j=0;j<n;j+)/找到一個滿足Finishi=false且Needij<=Workj的進程 if(Needij>Workj)/由于部分資源得不到滿足，進程i無法運行break; if(j=n)/進程各類資源全部得到滿足 Finishi=True; for(k=0;k<n;k+)/進程i正常運行后，釋放其占有的資源 Workk+=Allocationik; /工作分配加上可用資源 Sequencel+=i; /模擬資源分配序列生成 i=-1; /重新掃描所有進程從i=0開始 else /某一資源得不到滿足continue; /試探下一個進程 /if(l=m)/都試探完畢cout<<"系統(tǒng)安全!"<<endl; cout<<"安全序列："for(i=0;i<l;i+) /輸出安全序列cout&l