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

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

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

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

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

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

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

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

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

9、個(gè)進(jìn)程,n個(gè)資源#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; /*自定義進(jìn)程數(shù)目與資源種類(lèi)*cout<<"*n"cout<<"*利用銀行家算法避免死鎖*n" cout<<"* *n"cout<<"*n

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

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

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

13、程分配情況如圖：n"cout<<"進(jìn)程號(hào)-"<<"MAX-"<<"Allocation-"<<"Need-"<<"Available-n"/顯示各進(jìn)程的資源情況 for(i=0;i<m;i+) cout<<"P"<<i<<": " for(j=0;j<n;j+) cout<<" "<<MAXij;

14、 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;/回車(chē)換行/*銀行家算法，為進(jìn)程分配資源*/void banker() int i,j; int choice; while(1)

15、cout<<endl; cout<<"輸入要進(jìn)行的操作(1:分配資源 2:離開(kāi)) :" /用戶(hù)選擇 cin>>choice; if(choice=1) /分配資源 cout<<"從P0到P"<<m-1<<"之間選擇要分配資源的進(jìn)程號(hào):n"cin>>i; if(i>=m) cout<<"無(wú)此進(jìn)程號(hào)!請(qǐng)重新輸入:n" cin>>i;/重新輸入進(jìn)程號(hào) cout<<"請(qǐng)輸入進(jìn)程申請(qǐng)的資源(

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

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

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

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

20、Sequenceij<<" "cout<<" "for(j=0;j<n;j+)cout<<AllocationSequenceij<<" "cout<<" "for(j=0;j<n;j+)cout<<AllocationSequenceij+Workj<<" "cout<<" " cout<<FinishSequencei<<" &qu

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

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