中國計量學院現代科技學院《計算機操作系統》課程設計報告課程設計報告課程設計名稱共享資源分配與銀行家算法系（部）信息工程系專業班級姓名學號指導教師 2010年6月28日 目錄一、課程設計目的和意義 3二、方案設計及開發過程 31.課題設計背景 32.算法描述 33.數據結構 44.主要函數說明 45.算法流程圖 5三、調試記錄與分析四、運行結果及說明 61．執行結果 62．結果分析 7五、課程設計總結 8參考資料 8附錄 8課程設計目的和意義計算機科學與技術專業學生學習完《計算機操作系統》課程后，進行的一次全面的綜合訓練，其目的在于加深催操作系統基礎理論和基本知識的理解，加強學生的動手能力.銀行家算法是避免死鎖的一種重要方法。通過編寫一個模擬動態資源分配的銀行家算法程序，進一步深入理解死鎖、產生死鎖的必要條件、安全狀態等重要概念，并掌握避免死鎖的具體實施方法二、方案設計及開發過程

1.課題設計背景銀行家算法又稱“資源分配拒絕”法，其基本思想是，系統中的所有進程放入進程集合，在安全狀態下系統受到進程的請求后試探性的把資源分配給他，現在系統將剩下的資源和進程集合中其他進程還需要的資源數做比較，找出剩余資源能滿足最大需求量的進程，從而保證進程運行完成后還回全部資源。這時系統將該進程從進程集合中將其清除。此時系統中的資源就更多了。反復執行上面的步驟，最后檢查進程的集合為空時就表明本次申請可行，系統處于安全狀態，可以實施本次分配，否則，只要進程集合非空，系統便處于不安全狀態，本次不能分配給他。請進程等待2.算法描述1）如果Request[i]是進程Pi的請求向量，如果Request[i，j]=K,表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：

如果Requesti[j]<=Need[i,j]，便轉向步驟2；否則認為出錯，因為它所需要的資源數已超過它所宣布的最大值。2）如果Requesti[j]<=Available[j],便轉向步驟3，否則，表示尚無足夠資源，進程Pi須等待。3）系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值：Available[j]:=Available[j]-Requesti[j];Allocation[i,j]:=Allocation[i,j]+Requesti[j];Need[i,j]:=Need[i,j]-Requesti[j];4)系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程pi等待。3.數據結構1.可利用資源向量AVAILABLE。這是一個含有M個元素的數組，其中的每一個元素代表一類可利用的資源數目，其3初始值是系統中所配置的該類全部可哦那個資源的數目，其數值隨該類資源的分配和回收而動態的改變。2.最大需求矩陣MAX。這是一個M*N的矩陣，它定義了系統中N個進程中的每一個進程對M類資源的最大需求。3.分配矩陣ALLOCATION。這也是一個M*N的矩陣，它定義了系統中每一類資源當前已分配給每一進程的資源數。4.需求矩陣NEED。這也是一個M*N的矩陣，用以表示每一個進程尚需的各類資源數。5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W]4.主要函數說明主要的常量變量#defineW10//最大進程數W=10#defineR20//最大資源總數R=20intAVAILABLE[R];//可利用資源向量intMAX[W][R];//最大需求矩陣intALLOCATION[W][R];//分配矩陣intNEED[W][R];//需求矩陣intRequest[R];//進程請求向量voidchangdata(intk);//進程請求資源數據改變intchksec(ints);//系統安全性的檢測主要模塊voidinputdata()voidshowdata()voidchangdata(intk)voidrestoredata(intk)intchksec(ints)intchkmax(ints)5.算法流程圖三、調試記錄與分析調試通過,程序未出錯四、運行結果及說明執行結果結果分析銀行家算法就是當接收到一個系統資源的分配后找到一個安全序列，使得進程間不會發生死鎖，若發生死鎖則讓進程等待。五、課程設計總結通過本次銀行家算法實驗，加深了我對銀行家算法的了解，掌握了如何利用銀行家算法避免死鎖。實驗中遇到點問題，通過查閱資料、詢問老師順利解決。通過這次的實踐，使我的理論知識更加的牢固。參考資料[1]湯小丹、湯子瀛、哲鳳屏等，《計算機操作系統》（第三版），西安電子科技大學出版社，2007.8附錄程序源碼:#include<string.h>#include<iostream.h>#defineFALSE0#defineTRUE1#defineW10//最大進程數W=10#defineR20//最大資源總數R=20intM;intN;intALL_RESOURCE[W];intAVAILABLE[R];//可利用資源向量intMAX[W][R];//最大需求矩陣intALLOCATION[W][R];//分配矩陣intNEED[W][R];//需求矩陣intRequest[R];//進程請求向量voidinputdata();//數據輸入voidshowdata();//數據顯示voidchangdata(intk);//進程請求資源數據改變voidrestoredata(intk);//數據恢復intchksec(ints);//系統安全性的檢測intchkmax(ints);//檢測最大需求voidbank();//檢測分配的資源是否合理voidmain(){inti,j;inputdata();for(i=0;i<M;i++){ j=chksec(i); if(j==0)break;}if(i>=M)cout<<"錯誤提示：經安全性檢查發現，系統的初始狀態不安全！！！\n"<<endl;else{cout<<"提示：經安全性檢查發現，系統的初始狀態安全！"<<endl; bank();}}voidinputdata(){ inti=0,j=0,p;cout<<"請輸入總進程數:"<<endl;do{ cin>>M; if(M>W)cout<<endl<<"總進程數超過了程序允許的最大進程數，請重新輸入:"<<endl;}while(M>W);cout<<endl;cout<<"請輸入資源的種類數:"<<endl;do{cin>>N; if(N>R) cout<<endl<<"資源的種類數超過了程序允許的最大資源種類數，請重新輸入:"<<endl;}while(N>R);cout<<endl;cout<<"請依次輸入各類資源的總數量，即設置向量all_resource:"<<endl;for(i=0;i<N;i++) cin>>ALL_RESOURCE[i];cout<<endl;cout<<"請依次輸入各進程所需要的最大資源數量，即設置矩陣max:"<<endl;for(i=0;i<M;i++){for(j=0;j<N;j++){do{cin>>MAX[i][j];if(MAX[i][j]>ALL_RESOURCE[j])cout<<endl<<"該最大資源數量超過了聲明的該資源總數,請重新輸入:"<<endl;}while(MAX[i][j]>ALL_RESOURCE[j]);}}cout<<endl;cout<<"請依次輸入各進程已經占據的各類資源數量，即設置矩陣allocation:"<<endl;for(i=0;i<M;i++){ for(j=0;j<N;j++) { do{ cin>>ALLOCATION[i][j]; if(ALLOCATION[i][j]>MAX[i][j]) cout<<endl<<"已占有的資源數量超過了聲明的最大資源數量,請重新輸入:"<<endl; }while(ALLOCATION[i][j]>MAX[i][j]); }}cout<<endl;for(i=0;i<M;i++) for(j=0;j<N;j++) NEED[i][j]=MAX[i][j]-ALLOCATION[i][j];for(j=0;j<N;j++){ p=ALL_RESOURCE[j]; for(i=0;i<M;i++) {p=p-ALLOCATION[i][j];AVAILABLE[j]=p;if(AVAILABLE[j]<0) AVAILABLE[j]=0; }}}voidshowdata(){inti,j;cout<<"各種資源的總數量，即向量all_resource為:"<<endl;cout<<"";for(j=0;j<N;j++) cout<<"資源"<<j<<":"<<ALL_RESOURCE[j];cout<<endl<<endl;cout<<"當前系統中各類資源的可用數量，即向量available為:"<<endl;cout<<"";for(j=0;j<N;j++) cout<<"資源"<<j<<":"<<AVAILABLE[j];cout<<endl<<endl;cout<<"各進程還需要的資源數量，即矩陣need為:"<<endl<<endl;for(i=0;i<M;i++){cout<<"進程P"<<i<<":";for(j=0;j<N;j++) cout<<NEED[i][j]<<"";cout<<endl;}cout<<endl;cout<<"各進程已經得到的資源量，即矩陣allocation為:"<<endl<<endl;for(i=0;i<M;i++){ cout<<"進程P"<<i<<":"; for(j=0;j<N;j++) cout<<ALLOCATION[i][j]<<""; cout<<endl;}cout<<endl;}voidchangdata(intk){ intj; for(j=0;j<N;j++) { AVAILABLE[j]=AVAILABLE[j]-Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]+Request[j]; NEED[k][j]=NEED[k][j]-Request[j]; }}voidrestoredata(intk){ intj; for(j=0;j<N;j++) { AVAILABLE[j]=AVAILABLE[j]+Request[j]; ALLOCATION[k][j]=ALLOCATION[k][j]-Request[j]; NEED[k][j]=NEED[k][j]+Request[j]; }}intchksec(ints){ intWORK,FINISH[W];inti,j,k=0;for(i=0;i<M;i++) FINISH[i]=FALSE;for(j=0;j<N;j++) { WORK=AVAILABLE[j];i=s;do { if(FINISH[i]==FALSE&&NEED[i][j]<=WORK) { WORK=WORK+ALLOCATION[i][j]; FINISH[i]=TRUE; i=0; }else { i++; } }while(i<M);for(i=0;i<M;i++) if(FINISH[i]==FALSE) { return1; } }return0;}intchkmax(ints){intj,flag=0; for(j=0;j<N;j++) { if(MAX[s][j]==ALLOCATION[s][j]) {flag=1; AVAILABLE[j]=AVAILABLE[j]+MAX[s][j]; MAX[s][j]=0; } } returnflag;}c{inti=0,j=0;charflag='Y';while(flag=='Y'||flag=='y') {i=-1;while(i<0||i>=M) {cout<<"請輸入需申請資源的進程號（從P0到P"<<M-1<<"，否則重新輸入!）:";cout<<"p"; cin>>i;if(i<0||i>=M) cout<<"輸入的進程號不存在，重新輸入!"<<endl; } cout<<"請輸入進程P"<<i<<"申請的資源數:"<<endl; for(j=0;j<N;j++) { cout<<"資源"<<j<<":"; cin>>Request[j];if(Request[j]>NEED[i][j]) {cout<<"進程P"<<i<<"申請的資源數大于進程P"<<i<<"還需要"<<j<<"類資源的資源量!"; cout<<"申請不合理，出錯!請重新選擇!"<<endl<<endl; flag='N'; break; } else { if(Request[j]>AVAILABLE[j]) {cout<<"進程P"<<i<<"申請的資源數大于系統可用"<<j<<"類資源的資源量!"; cout<<"申請不合理，出錯!請重新選擇!"<<endl<<endl; flag='N'; break; } } } if(flag=='Y'||flag=='y') { changdata(i); if(chksec(i)) {cout<<endl; cout<<"該分配會導致系統不安全!!!本次資源申請不成功，不予分配!!!"<<endl; cout<<endl; restoredata(i); } else {cout<<endl; cout<<"經安全性檢查，系統安全，本次分配成功，且資源分配狀況如下所示："<<endl; cout<<endl; showdata(); if(chkmax(i)) {cout<<"在資源分配成功之后，由于該進程所需的某些資源的最大需求量已經滿足，"<<endl; cout<<"因此在進程結束后系統將回收這些資源！"<<endl;cout<<"在資源收回之后，各進程的資源需求和分配情況如下所示："<<endl; showdata(); } } } cout<<endl; cout<<"是否繼續銀行家算法演示,按'Y'或'y'鍵繼續,按'N'或'n'鍵退出演示:"; cin>>flag;}}附錄A：指導教師評語及成績指導教師評語： 成績評定：指導教師：年月日目錄TOC\o"1-2"\h\u253321總論 1311911.1項目概況 1317891.2建設單位概況 3162241.3項目提出的理由與過程 3311231.4可行性研究報告編制依據 4225921.5可行性研究報告編制原則 426521.6可行性研究范圍 5265791.7結論與建議 665262項目建設背景和必要性 9302042.1項目區基本狀況 9237942.2項目背景 11327472.3項目建設的必要性 11265903市場分析 14297233.1物流園區的發展概況 1479553.2市場供求現狀 1669963.3目標市場定位 17108883.4市場競爭力分析

17160544項目選址和建設條件 1950564.1選址原則 1969314.2項目選址 19544.3場址所在位置現狀 19297334.4建設條件 20123545主要功能和建設規模 22282555.1主要功能 22281835.2建設規模及內容 26195696工程建設方案 27137726.1設計依據 27219396.2物流空間布局的要求 27262516.3空間布局原則 2853886.4總體布局 2936766.5工程建設方案 30235856.6給水工程 33115596.7排水工程 3553126.8電力工程 38288986.9供熱工程 46314656.10電訊工程 47153607工藝技術和設備方案 51276227.1物流技術方案 5142607.2制冷工藝技術方案 6769868節能方案分析 7336228.1節能依據 73176248.2能耗指標分析 73235218.3主要耗能指標計算 74272888.4節能措施和節能效果分析 76295509環境影響評價 83267939.1設計依據 8335089.2環境影響評價應堅持的原則 83134559.3項目位置環境現狀 84208539.4項目建設與運營對環境的影響 8430919.5項目建設期環境保護措施 8459489.6項目運行期環境保護措施 861431110安全與消防 873017710.1安全措施 872680010.2消防 88921011組織機構和人力資源配置 921053611.1施工組織機構 922404211.2基建項目部的主要職責 923031711.3運營管理 931573811.4人員來源、要求及培訓 942246412工程進度安排 96591412.1建設工期 962284512.2工程實施進度安排