華工2016春操作系統(tǒng)大作業(yè)銀行家死鎖避免算法模擬(含源

1、華南理工“計(jì)算機(jī)操作系統(tǒng)”課程設(shè)計(jì)大作業(yè)一、實(shí)驗(yàn)題目: 銀行家死鎖避免算法模擬二、實(shí)驗(yàn)?zāi)康模和ㄟ^本次實(shí)驗(yàn)掌握銀行家死鎖避免算法的基本思想。當(dāng)進(jìn)程提出資源申請時(shí)，能夠用該算法判斷是否拒絕進(jìn)程請求。三、實(shí)驗(yàn)內(nèi)容認(rèn)真閱讀教材（計(jì)算機(jī)操作系統(tǒng)（第三版），湯小丹，西安電子科技大學(xué)出版社）P108-P111頁3.6.3節(jié)銀行家算法的實(shí)現(xiàn)思想，理解該算法是如何能夠?qū)崿F(xiàn)死鎖避免的。編寫一個(gè)銀行家算法模擬程序用于處理進(jìn)程的資源申請。1。假設(shè)系統(tǒng)共有5類資源，分別以A、B、C、D、E來標(biāo)識，每類資源的初始數(shù)量全部為50。2。進(jìn)程可以通過程序界面隨時(shí)提交新的資源申請，提交的信息包括進(jìn)程名稱、對5類資源的最大需求數(shù)量

2、。3。每次當(dāng)有資源申請時(shí)，先輸出系統(tǒng)當(dāng)前狀態(tài)（5類資源當(dāng)前可用數(shù)量，每個(gè)進(jìn)程已分配的每類資源數(shù)量），再利用銀行家算法判斷是否該滿足進(jìn)程請求。如果可以分配，輸出給該進(jìn)程分配資源后的系統(tǒng)狀態(tài)，再輸出至少一個(gè)“安全序列”。四、實(shí)驗(yàn)要求：每人完成一份大作業(yè)實(shí)驗(yàn)報(bào)告。報(bào)告分設(shè)計(jì)思想、數(shù)據(jù)定義、處理流程、源程序、運(yùn)行結(jié)果截圖、設(shè)計(jì)體會(huì)等部分。1） 給出數(shù)據(jù)定義和詳細(xì)說明；2） 給出實(shí)現(xiàn)思想和設(shè)計(jì)流程；3） 調(diào)試完成源程序；4） 屏幕觀察運(yùn)行結(jié)果；5） 總結(jié)自己的設(shè)計(jì)體會(huì)；編程語言及操作系統(tǒng)平臺不限。五、提交內(nèi)容本大作業(yè)每個(gè)人必須單獨(dú)完成。最后需提交的內(nèi)容包括：源程序（關(guān)鍵代碼需要注釋說明）、可運(yùn)行程序、算

3、法思路及流程圖、心得體會(huì)。將以上內(nèi)容刻入光盤，光盤上寫明班級、學(xué)號、姓名信息，再將大作業(yè)要求、源程序及注釋、算法思路及流程圖、心得體會(huì)等打印出來。最后將打印稿及光盤統(tǒng)一交給網(wǎng)絡(luò)學(xué)院教務(wù)員。銀行家算法實(shí)現(xiàn)一 課程設(shè)計(jì)目的1. 加深對死鎖概念的理解。2. 能夠利用銀行家算法，有效避免死鎖的發(fā)生，或檢測死鎖的存在。二 課程設(shè)計(jì)摘要銀行家算法：我們可以把操作系統(tǒng)看作是銀行家，操作系統(tǒng)管理的資源相當(dāng)于銀行家管理的資金，進(jìn)程向操作系統(tǒng)請求分配資源相當(dāng)于用戶向銀行家貸款。操作系統(tǒng)按照銀行家制定的規(guī)則為進(jìn)程分配資源，當(dāng)進(jìn)程首次申請資源時(shí)，要測試該進(jìn)程對資源的最大需求量，如果系統(tǒng)現(xiàn)存的資源可以滿足它的最大需求量

4、則按當(dāng)前的申請量分配資源，否則就推遲分配。當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請資源時(shí)，先測試該進(jìn)程已占用的資源數(shù)與本次申請的資源數(shù)之和是否超過了該進(jìn)程對資源的最大需求量。若超過則拒絕分配資源，若沒有超過則再測試系統(tǒng)現(xiàn)存的資源能否滿足該進(jìn)程尚需的最大資源量，若能滿足則按當(dāng)前的申請量分配資源，否則也要推遲分配。三 開發(fā)環(huán)境系統(tǒng)軟件硬件環(huán)境軟件：Windows 7; VC+ 6.0硬件：CPU 2.40GHz;2G內(nèi)存四課程設(shè)計(jì)原理分析在多道程序系統(tǒng)中，雖可借助于多個(gè)進(jìn)程的并發(fā)執(zhí)行，來改善系統(tǒng)的資源利用率，提高系統(tǒng)的吞吐量，但可能發(fā)生一種危險(xiǎn)死鎖。所謂死鎖，是指多個(gè)進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)

5、程處于這種僵局狀態(tài)時(shí)，若無外力作用，它們都將無法再向前推進(jìn)。為保證系統(tǒng)中諸進(jìn)程的正常運(yùn)行，應(yīng)事先采取必要的措施，來預(yù)防死鎖。最有代表性的避免死鎖的方法，是Dijkstra的銀行家算法。死鎖：死鎖的產(chǎn)生，必須同時(shí)滿足四個(gè)條件，第一個(gè)為互斥條件，即一個(gè)資源每次只能由一個(gè)進(jìn)程占用；第二個(gè)為請求和保持條件，指進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請求，而該資源又被其他進(jìn)程占有，此時(shí)請求進(jìn)程阻塞，但又對自己已獲得的其他資源保持不放；第三個(gè)為非剝奪條件，即在出現(xiàn)死鎖的系統(tǒng)中一定有不可剝奪使用的資源；第四個(gè)為循環(huán)等待條件，系統(tǒng)中存在若干個(gè)循環(huán)等待的進(jìn)程，即其中每一個(gè)進(jìn)程分別等待它前一個(gè)進(jìn)程所持有的資

6、源。防止死鎖的機(jī)構(gòu)只能確保上述四個(gè)條件之一不出現(xiàn)，則系統(tǒng)就不會(huì)發(fā)生死鎖。銀行家算法原理： 銀行家算法是避免死鎖的一種重要方法，通過編寫一個(gè)簡單的銀行家算法程序，加深了解有關(guān)資源申請、避免死鎖等概念，并體會(huì)和了解死鎖和避免死鎖的具體實(shí)施方法。通過這個(gè)算法可以用來解決生活中的實(shí)際問題，如銀行貸款等。銀行家算法，顧名思義是來源于銀行的借貸業(yè)務(wù)，一定數(shù)量的本金要應(yīng)多個(gè)客戶的借貸周轉(zhuǎn)，為了防止銀行家資金無法周轉(zhuǎn)而倒閉，對每一筆貸款，必須考察其是否能限期歸還。在操作系統(tǒng)中研究資源分配策略時(shí)也有類似問題，系統(tǒng)中有限的資源要供多個(gè)進(jìn)程使用，必須保證得到的資源的進(jìn)程能在有限的時(shí)間內(nèi)歸還資源，以供其他進(jìn)程使用資源

7、。如果資源分配不得到就會(huì)發(fā)生進(jìn)程循環(huán)等待資源，則進(jìn)程都無法繼續(xù)執(zhí)行下去的死鎖現(xiàn)象。把一個(gè)進(jìn)程需要和已占有資源的情況記錄在進(jìn)程控制中，假定進(jìn)程控制塊PCB其中“狀態(tài)”有就緒態(tài)、等待態(tài)和完成態(tài)。當(dāng)進(jìn)程在處于等待態(tài)時(shí)，表示系統(tǒng)不能滿足該進(jìn)程當(dāng)前的資源申請?！百Y源需求總量”表示進(jìn)程在整個(gè)執(zhí)行過程中總共要申請的資源量。顯然，每個(gè)進(jìn)程的資源需求總量不能超過系統(tǒng)擁有的資源總數(shù), 銀行算法進(jìn)行資源分配可以避免死鎖.算法思想：將一定數(shù)量的資金供多個(gè)用戶周轉(zhuǎn)使用，當(dāng)用戶對資金的最大申請量不超過現(xiàn)存資金時(shí)可接納一個(gè)新客戶，客戶可以分期借款，但借款總數(shù)不能超過最大的申請量。銀行家對客戶的借款可以推遲支付，但是能夠使客

8、戶在有限的時(shí)間內(nèi)得到借款，客戶得到所有的借款后能在有限的時(shí)間內(nèi)歸還。用銀行家算法分配資源時(shí)，測試進(jìn)程對資源的最大需求量，若現(xiàn)存資源能滿足最大需求就滿足當(dāng)前進(jìn)程的申請，否則推遲分配，這樣能夠保證至少有一個(gè)進(jìn)程可以得到所需的全部資源而執(zhí)行到結(jié)束，然后歸還資源，若OS能保證所有進(jìn)程在有限的時(shí)間內(nèi)得到所需資源則稱系統(tǒng)處于安全狀態(tài)。5. 算法實(shí)現(xiàn)1. 程序流程圖：2. 2. 算法描述： 銀行家算法的設(shè)計(jì)思想是：當(dāng)用戶申請一組資源時(shí)，系統(tǒng)必須做出判斷；如果把這些資源分出去，系統(tǒng)是否還處于安全裝他。若是，就可以分出這些資源；否則，該申請暫不能滿足。3. 數(shù)據(jù)結(jié)構(gòu)描述：（n表示系統(tǒng)中進(jìn)程的數(shù)目，m表

9、示資源的分類數(shù)。）3.1. Available是一個(gè)長度為m的向量，它表示每類資源可用的數(shù)量。Available j=k，表示rj類資源可用的數(shù)量為k。3.2.Max是一個(gè)n×m矩陣，它表示每個(gè)進(jìn)程對資源的最大需求。Max i，j=k，表示進(jìn)程pi至多可以申請k個(gè)rj類資源單位。3.3. Allocation是一個(gè)n×m矩陣，它表示當(dāng)前分給每個(gè)進(jìn)程的資源數(shù)目。Allocation i，j=k，表示進(jìn)程pi當(dāng)前分到k個(gè)rj類資源。3.4. Need是一個(gè)n×m矩陣，它表示每個(gè)進(jìn)程還缺少多少資源。Needi，j=k，表示進(jìn)程pi尚需k個(gè)rj類資源才能完成其任務(wù)。顯然N

10、eedi，j= Max i，j- Allocation i，j。這些數(shù)據(jù)結(jié)構(gòu)的大小和數(shù)值隨時(shí)間推移而改變。4. 系統(tǒng)所執(zhí)行的安全性算法描述如下：4.1.設(shè)置2個(gè)向量：工作向量Work：它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work = Available。Finishi ：它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之完成運(yùn)行。開始時(shí)先做Finishi=true。4.2.從進(jìn)程集合中找到一個(gè)滿足下述條件的進(jìn)程：Finishi=flase；Needi,jWorkj；若找到，則執(zhí)行步驟3，否則，執(zhí)行步驟4。4.3.當(dāng)進(jìn)程pi獲得資源后，可順利執(zhí)行，直至

11、完成，并釋放分配給它的資源。4.4.如果所有進(jìn)程的Finishi=true都滿足。則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 六.程序源代碼#include<iostream>#include<string>#include<stdio.h>using namespace std;#define False 0#define True 1int Max100100=0;/各進(jìn)程所需各類資源的最大需求int Avaliable100=0;/系統(tǒng)可用資源char name100=0;/資源的名稱int Allocation100100=0;/系

12、統(tǒng)已分配資源int Need100100=0;/還需要資源int Request100=0;/請求資源向量int temp100=0;/存放安全序列int Work100=0;/存放系統(tǒng)可提供資源int M=100;/作業(yè)的最大數(shù)為100int N=100;/資源的最大數(shù)為100void showdata()/顯示資源矩陣 int i,j; cout<<"系統(tǒng)目前可用的資源Avaliable:"<<endl; for(i=0;i<N;i+) cout<<namei<<" " cout<<e

13、ndl; for (j=0;j<N;j+) cout<<Avaliablej<<" "/輸出分配資源 cout<<endl; cout<<" Max Allocation Need"<<endl; cout<<"進(jìn)程名 " for(j=0;j<3;j+) for(i=0;i<N;i+) cout<<namei<<" " cout<<" " cout<<endl

14、; for(i=0;i<M;i+) cout<<" "<<i<<" " for(j=0;j<N;j+) cout<<Maxij<<" " cout<<" " for(j=0;j<N;j+) cout<<Allocationij<<" " cout<<" " for(j=0;j<N;j+) cout<<Needij<<&qu

15、ot; " cout<<endl; int changdata(int i)/進(jìn)行資源分配 int j;for (j=0;j<M;j+) Avaliablej=Avaliablej-Requestj; Allocationij=Allocationij+Requestj; Needij=Needij-Requestj;return 1;int safe()/安全性算法int i,k=0,m,apply,Finish100=0;int j;int flag=0;Work0=Avaliable0;Work1=Avaliable1;Work2=Avaliable2;for

16、(i=0;i<M;i+) apply=0; for(j=0;j<N;j+) if (Finishi=False&&Needij<=Workj) apply+; if(apply=N) for(m=0;m<N;m+) Workm=Workm+Allocationim;/變分配數(shù) Finishi=True; tempk=i; i=-1; k+; flag+; for(i=0;i<M;i+) if(Finishi=False) cout<<"系統(tǒng)不安全"<<endl;/不成功系統(tǒng)不安全 return -1; c

17、out<<"系統(tǒng)是安全的!"<<endl;/如果安全，輸出成功 cout<<"分配的序列:"for(i=0;i<M;i+)/輸出運(yùn)行進(jìn)程數(shù)組 cout<<tempi; if(i<M-1) cout<<"->" cout<<endl; return 0;void share()/利用銀行家算法對申請資源對進(jìn)行判定char ch;int i=0,j=0;ch='y'cout<<"請輸入要求分配的資源進(jìn)程號(0-&

18、quot;<<M-1<<"):" cin>>i;/輸入須申請的資源號cout<<"請輸入進(jìn)程 "<<i<<" 申請的資源:"<<endl;for(j=0;j<N;j+) cout<<namej<<":" cin>>Requestj;/輸入需要申請的資源 for (j=0;j<N;j+) if(Requestj>Needij)/判斷申請是否大于需求，若大于則出錯(cuò) cout<&

19、lt;"進(jìn)程 "<<i<<"申請的資源大于它需要的資源" cout<<" 分配不合理，不予分配！"<<endl; ch='n' break; else if(Requestj>Avaliablej)/判斷申請是否大于當(dāng)前資源，若大于則 /出錯(cuò) cout<<"進(jìn)程"<<i<<"申請的資源大于系統(tǒng)現(xiàn)在可利用的資源" cout<<" 分配出錯(cuò)，不予分配!"<&

20、lt;endl; ch='n' break; if(ch='y') changdata(i);/根據(jù)進(jìn)程需求量變換資源 showdata();/根據(jù)進(jìn)程需求量顯示變換后的資源 safe();/根據(jù)進(jìn)程需求量進(jìn)行銀行家算法判斷 void addresources()/添加資源 int n,flag;cout<<"請輸入需要添加資源種類的數(shù)量:"cin>>n;flag=N;N=N+n;for(int i=0;i<n;i+) cout<<"名稱:" cin>>nameflag

21、; cout<<"數(shù)量:" cin>>Avaliableflag+;showdata();safe();void changeresources()/修改資源函數(shù)cout<<"系統(tǒng)目前可用的資源Avaliable:"<<endl; for(int i=0;i<N;i+) cout<<namei<<":"<<Avaliablei<<endl;cout<<"輸入系統(tǒng)可用資源Avaliable:"<&l

22、t;endl;cin>>Avaliable0>>Avaliable1>>Avaliable2;cout<<"經(jīng)修改后的系統(tǒng)可用資源為"<<endl;for (int k=0;k<N;k+) cout<<namek<<":"<<Avaliablek<<endl;showdata();safe();void delresources()/刪除資源char ming;int i,flag=1;cout<<"請輸入需要?jiǎng)h除的資源

23、名稱："do cin>>ming;for(i=0;i<N;i+) if(ming=namei) flag=0; break; if(i=N) cout<<"該資源名稱不存在，請重新輸入："while(flag);for(int j=i;j<N-1;j+) namej=namej+1; Avaliablej=Avaliablej+1; N=N-1;showdata();safe();void addprocess()/添加作業(yè) int flag=M;M=M+1;cout<<"請輸入該作業(yè)的最大需求量Max&q

24、uot;<<endl;for(int i=0;i<N;i+) cout<<namei<<":" cin>>Maxflagi; Needflagi=Maxflagi-Allocationflagi;showdata();safe();int main()/主函數(shù)<m<<"*"<<n<<"矩陣)Max:"<<endl;for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>Maxij;do

25、flag=0; cout<<"請輸入各進(jìn)程已經(jīng)申請的資源量("<<m<<"*"<<n<<"矩陣)Allocation:"<<endl; for(i=0;i<m;i+) for(j=0;j<n;j+) cin>>Allocationij; if(Allocationij>Maxij) flag=1; Needij=Maxij-Allocationij; if(flag) cout<<"申請的資源大于最大需求量，請重

26、新輸入!n"while(flag); showdata();/顯示各種資源 safe();/用銀行家算法判定系統(tǒng)是否安全 while(choice) cout<<"*銀行家算法演示*"<<endl; cout<<" 1:增加資源 "<<endl; cout<<" 2:刪除資源 "<<endl; cout<<" 3:修改資源 "<<endl; cout<<" 4:分配資源 "<<endl;