共享資源分配與銀行家算法課程設(shè)計(jì)

1、課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱 共享資源分配與銀行家算法 系（部） 信息工程系 專業(yè)班級 姓 名學(xué) 號指導(dǎo)教師 2010 年 6 月 28 日目 錄一、課程設(shè)計(jì)目的和意義3二、方案設(shè)計(jì)及開發(fā)過程31.課題設(shè)計(jì)背景32.算法描述33.數(shù)據(jù)結(jié)構(gòu)44.主要函數(shù)說明45.算法流程圖5三、調(diào)試記錄與分析四、運(yùn)行結(jié)果及說明61執(zhí)行結(jié)果 62結(jié)果分析7五、課程設(shè)計(jì)總結(jié)8參考資料8附錄8一、 課程設(shè)計(jì)目的和意義計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)學(xué)生學(xué)習(xí)完計(jì)算機(jī)操作系統(tǒng)課程后，進(jìn)行的一次全面的綜合訓(xùn)練，其目的在于加深催操作系統(tǒng)基礎(chǔ)理論和基本知識的理解，加強(qiáng)學(xué)生的動手能力. 銀行家算法是避免死鎖的一種重要方法。通過編寫一個模擬動態(tài)資

2、源分配的銀行家算法程序，進(jìn)一步深入理解死鎖、產(chǎn)生死鎖的必要條件、安全狀態(tài)等重要概念，并掌握避免死鎖的具體實(shí)施方法二、方案設(shè)計(jì)及開發(fā)過程1.課題設(shè)計(jì)背景銀行家算法又稱“資源分配拒絕”法，其基本思想是，系統(tǒng)中的所有進(jìn)程放入進(jìn)程集合，在安全狀態(tài)下系統(tǒng)受到進(jìn)程的請求后試探性的把資源分配給他，現(xiàn)在系統(tǒng)將剩下的資源和進(jìn)程集合中其他進(jìn)程還需要的資源數(shù)做比較，找出剩余資源能滿足最大需求量的進(jìn)程，從而保證進(jìn)程運(yùn)行完成后還回全部資源。這時系統(tǒng)將該進(jìn)程從進(jìn)程集合中將其清除。此時系統(tǒng)中的資源就更多了。反復(fù)執(zhí)行上面的步驟，最后檢查進(jìn)程的集合為空時就表明本次申請可行，系統(tǒng)處于安全狀態(tài)，可以實(shí)施本次分配，否則，只要進(jìn)程集合

3、非空，系統(tǒng)便處于不安全狀態(tài)，本次不能分配給他。請進(jìn)程等待2.算法描述1）如果Requesti 是進(jìn)程Pi的請求向量，如果Requesti，j=K,表示進(jìn)程Pi需要K個Rj類型的資源。當(dāng)Pi發(fā)出資源請求后，系統(tǒng)按下述步驟進(jìn)行檢查：如果Requestij<= Needi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。2）如果Requestij<=Availablej,便轉(zhuǎn)向步驟3，否則，表示尚無足夠資源，進(jìn)程Pi須等待。3）系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值：Availablej:=Availablej-Requestij;Allo

4、cationi,j:=Allocationi,j+Requestij;Needi,j:=Needi,j-Requestij;4)系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程pi等待。3.數(shù)據(jù)結(jié)構(gòu)1.可利用資源向量AVAILABLE。這是一個含有M個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目，其3初始值是系統(tǒng)中所配置的該類全部可哦那個資源的數(shù)目，其數(shù)值隨該類資源的分配和回收而動態(tài)的改變。2.最大需求矩陣MAX。這是一個M*N的矩陣，它定義了系統(tǒng)中N個進(jìn)程中的每

5、一個進(jìn)程對M類資源的最大需求。3.分配矩陣ALLOCATION。這也是一個M*N的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。4.需求矩陣NEED。這也是一個M*N的矩陣，用以表示每一個進(jìn)程尚需的各類資源數(shù)。5.NEEDR,W=MAXR,W-ALLOCATIONR,W4.主要函數(shù)說明主要的常量變量#define W 10 /最大進(jìn)程數(shù)W=10#define R 20 /最大資源總數(shù)R=20int AVAILABLER; /可利用資源向量int MAXWR; /最大需求矩陣int ALLOCATIONWR; /分配矩陣int NEEDWR; /需求矩陣int RequestR;

6、/進(jìn)程請求向量void changdata(int k);/進(jìn)程請求資源數(shù)據(jù)改變int chksec(int s); /系統(tǒng)安全性的檢測主要模塊void inputdata()void showdata()void changdata(int k) void restoredata(int k) int chksec(int s) int chkmax(int s)5.算法流程圖三、調(diào)試記錄與分析調(diào)試通過,程序未出錯四、運(yùn)行結(jié)果及說明1. 執(zhí)行結(jié)果2. 結(jié)果分析銀行家算法就是當(dāng)接收到一個系統(tǒng)資源的分配后找到一個安全序列，使得進(jìn)程間不會發(fā)生死鎖，若發(fā)生死鎖則讓進(jìn)程等待。五、課程設(shè)計(jì)總結(jié)通過本次銀

7、行家算法實(shí)驗(yàn)，加深了我對銀行家算法的了解，掌握了如何利用銀行家算法避免死鎖。實(shí)驗(yàn)中遇到點(diǎn)問題，通過查閱資料、詢問老師順利解決。通過這次的實(shí)踐，使我的理論知識更加的牢固。參考資料1湯小丹、湯子瀛、哲鳳屏等，計(jì)算機(jī)操作系統(tǒng)（第三版），西安電子科技大學(xué)出版社，2007.8附錄程序源碼:#include<string.h>#include<iostream.h>#define FALSE 0 #define TRUE 1 #define W 10 /最大進(jìn)程數(shù)W=10#define R 20 /最大資源總數(shù)R=20int M ; int N ; int ALL_RESOURCE

8、W; int AVAILABLER; /可利用資源向量int MAXWR; /最大需求矩陣int ALLOCATIONWR; /分配矩陣int NEEDWR; /需求矩陣int RequestR; /進(jìn)程請求向量void inputdata(); /數(shù)據(jù)輸入void showdata(); /數(shù)據(jù)顯示void changdata(int k);/進(jìn)程請求資源數(shù)據(jù)改變void restoredata(int k); /數(shù)據(jù)恢復(fù)int chksec(int s); /系統(tǒng)安全性的檢測int chkmax(int s); /檢測最大需求void bank(); /檢測分配的資源是否合理void ma

9、in() int i,j;inputdata(); for(i=0;i<M;i+)j=chksec(i);if (j=0) break; if (i>=M) cout<<"錯誤提示：經(jīng)安全性檢查發(fā)現(xiàn)，系統(tǒng)的初始狀態(tài)不安全！n"<<endl;else cout<<"提示：經(jīng)安全性檢查發(fā)現(xiàn)，系統(tǒng)的初始狀態(tài)安全！"<<endl; bank(); void inputdata()int i=0,j=0,p; cout<<"請輸入總進(jìn)程數(shù):"<<endl;do

10、cin>>M;if (M>W) cout<<endl<<"總進(jìn)程數(shù)超過了程序允許的最大進(jìn)程數(shù)，請重新輸入:"<<endl; while (M>W); cout<<endl; cout<<"請輸入資源的種類數(shù):"<<endl;do cin>>N;if (N>R)cout<<endl<<"資源的種類數(shù)超過了程序允許的最大資源種類數(shù)，請重新輸入:"<<endl; while (N>R);

11、 cout<<endl; cout<<"請依次輸入各類資源的總數(shù)量，即設(shè)置向量all_resource:"<<endl;for(i=0;i<N;i+) cin>>ALL_RESOURCEi; cout<<endl; cout<<"請依次輸入各進(jìn)程所需要的最大資源數(shù)量，即設(shè)置矩陣max:"<<endl;for (i=0;i<M;i+) for (j=0;j<N;j+)do cin>>MAXij;if (MAXij>ALL_RESOURCE

12、j) cout<<endl<<"該最大資源數(shù)量超過了聲明的該資源總數(shù),請重新輸入:"<<endl; while (MAXij>ALL_RESOURCEj); cout<<endl; cout<<"請依次輸入各進(jìn)程已經(jīng)占據(jù)的各類資源數(shù)量，即設(shè)置矩陣allocation:"<<endl;for (i=0;i<M;i+) for (j=0;j<N;j+)docin>>ALLOCATIONij;if (ALLOCATIONij>MAXij)cout<

13、<endl<<"已占有的資源數(shù)量超過了聲明的最大資源數(shù)量,請重新輸入:"<<endl; while (ALLOCATIONij>MAXij); cout<<endl; for (i=0;i<M;i+)for(j=0;j<N;j+) NEEDij=MAXij-ALLOCATIONij; for (j=0;j<N;j+) p=ALL_RESOURCEj;for (i=0;i<M;i+) p=p-ALLOCATIONij; AVAILABLEj=p;if(AVAILABLEj<0) AVAILABLEj

14、=0; void showdata() int i,j; cout<<"各種資源的總數(shù)量，即向量all_resource為:"<<endl; cout<<" " for (j=0;j<N;j+) cout<<" 資源"<<j<<": "<<ALL_RESOURCEj; cout<<endl<<endl; cout<<"當(dāng)前系統(tǒng)中各類資源的可用數(shù)量，即向量available為:&qu

15、ot;<<endl; cout<<" " for (j=0;j<N;j+) cout<<" 資源"<<j<<": "<<AVAILABLEj; cout<<endl<<endl; cout<<"各進(jìn)程還需要的資源數(shù)量，即矩陣need為:"<<endl<<endl; for (i=0;i<M;i+) cout<<"進(jìn)程P"<<i&l

16、t;<": " for (j=0;j<N;j+) cout<<NEEDij<<" " cout<<endl; cout<<endl; cout<<"各進(jìn)程已經(jīng)得到的資源量，即矩陣allocation為: "<<endl<<endl; for (i=0;i<M;i+) cout<<"進(jìn)程P"<<i<<": "for (j=0;j<N;j+) cout<

17、;<ALLOCATIONij<<" " cout<<endl; cout<<endl; void changdata(int k) int j; for (j=0;j<N;j+) AVAILABLEj=AVAILABLEj-Requestj; ALLOCATIONkj=ALLOCATIONkj+Requestj; NEEDkj=NEEDkj-Requestj;void restoredata(int k) int j; for (j=0;j<N;j+) AVAILABLEj=AVAILABLEj+Requestj; AL

18、LOCATIONkj=ALLOCATIONkj-Requestj; NEEDkj=NEEDkj+Requestj;int chksec(int s) int WORK,FINISHW; int i,j,k=0; for(i=0;i<M;i+)FINISHi=FALSE; for(j=0;j<N;j+) WORK=AVAILABLEj; i=s; doif(FINISHi=FALSE&&NEEDij<=WORK)WORK=WORK+ALLOCATIONij; FINISHi=TRUE; i=0; else i+; while(i<M);for(i=0;i&

19、lt;M;i+) if(FINISHi=FALSE) return 1; return 0; int chkmax(int s) int j,flag=0;for(j=0;j<N;j+) if (MAXsj=ALLOCATIONsj) flag=1;AVAILABLEj=AVAILABLEj+MAXsj;MAXsj=0;return flag;cint i=0,j=0; char flag='Y' while(flag='Y'|flag='y') i=-1; while(i<0|i>=M) cout<<"請

20、輸入需申請資源的進(jìn)程號（從P0到P"<<M-1<<"，否則重新輸入!）:" cout<<"p" cin>>i; if(i<0|i>=M) cout<<"輸入的進(jìn)程號不存在，重新輸入!"<<endl; cout<<"請輸入進(jìn)程P"<<i<<"申請的資源數(shù):"<<endl; for (j=0;j<N;j+) cout<<" 資源&q

21、uot;<<j<<": " cin>>Requestj;if(Requestj>NEEDij) cout<<"進(jìn)程P"<<i<<"申請的資源數(shù)大于進(jìn)程P"<<i<<"還需要"<<j<<"類資源的資源量!" cout<<"申請不合理，出錯!請重新選擇!"<<endl<<endl; flag='N' break; else if(Requestj>AVAILABLEj) cout<<"進(jìn)程P"<<i<<"申請的資源數(shù)大于系統(tǒng)可用"<<j<<"類資源的資源量!" cout<<"申請不合理，出錯!請重新選擇!"<<endl&