模擬通過銀行家算法避免死鎖銀行家算法產生的背景及目的1：在多道程序系統中，雖然借助于多個進程的并發執行來改善系統的運用率，提高系統的吞吐量，但也許發生一種危險—死鎖。死鎖就是多個進程在運營過程中因爭奪資源而導致的一種僵局，當進程處在這種僵局狀態時，如無外力作用，他們將無法再向前進行，如再把信號量作為同步工具時，多個Wait和Signal操作順序不妥，會產生進程死鎖。然而產生死鎖的必要條件有互斥條件，請求和保持條件，不剝奪條件和環路等待條件。在防止死鎖的幾種方法中，都施加了較強的限制條件，在避免死鎖的方法中，所施加的條件較弱，有也許獲得令人滿意的系統性能。在該方法中把系統的狀態分為安全狀態和不安全狀態，只要能使系統都處在安全狀態，便可避免死鎖。2：實驗目的：讓學生獨立的使用編程語言編寫和調試一個系統分派資源的簡樸模擬程序，了解死鎖產生的因素及條件。采用銀行家算法及時避免死鎖的產生，進一步理解課堂上老師講的相關知識點。銀行家算法是從當前狀態出發，逐個按安全序列檢查各客戶中誰能完畢其工作，然后假定其完畢工作且歸還所有貸款，再進而檢查下一個能完畢工作的客戶。假如所有客戶都能完畢工作，則找到一個安全序列，銀行家才是安全的。二：銀行家算法中的數據結構1：可運用資源向量Available。這是一個具有m個元素的數組，其中的每個元素代表一類可運用的資源數目，其初始值是系統中所配置的該類所有可用資源的數目，其數值隨該類資源的分派和回收而動態的改變。假如Available[j]=k，z則表達系統中現有Rj類資源K個。2：最大需求矩陣Max。這是一個n*m的矩陣，它定義了系統中n個進程中的每一個進程對m類資源的最大需求。假如Max[i,j]=k，表達第i個進程需要第Rj類資源的最大數目k個.3:分派矩陣Allocation,也是n*m的矩陣，若Allocation[i,j]=k,表達第i個進程已分派Rj類資源的數目為k個。4：需求矩陣Need。也是一個n*m的矩陣，Need[i,j]=k,表達第i個進程還需Rj類資源k個。三、銀行家算法及安全性算法1：銀行家算法設Request[i]是進程Pi的請求向量，若Request[i][j]=k;表達進程需要j類資源k個。當Pi發出資源請求時，系統按下屬環節進行檢查；假如Request[i][j]<=Need[i][j];便轉向環節（2），否則認為犯錯，由于它所需要的資源數已超過他所宣布的最大值。假如Request[i][j]<=Available[i][j],便轉向環節（3），否則認為尚無足夠資源，進程需等待。系統試探著把資源分派給進程，并修改下面數據結構的數據Available[i][j]=Available[i][j]-Request[i][j];Allocation[i][j]=Allocation[i][j]+Request[i][j];Need[i][j]=Need[i][j]-Request[i][j];系統執行安全性算法，檢查本次資源分派后系統是否處在安全狀態。若安全，才正式將資源分派給進程Pi，已完畢本次分派。否則，將本次的試探分派作廢，回復本來的資源分派狀態，將進程Pi等待。2：安全性算法設立兩個向量；1：工作向量Work，表達系統可提供應進程運營所需的各類資源數目，它具有m個元素，初始時Work=Available2：Finish,表達系統是否有足夠的資源分派給進程，使之運營完畢。開始時先做Finish[i]=true從進程中找到一個能滿需下屬條件的進程1；Finish[i]=false；2：Need[i][j]<=Work[j];若找到執行環節（3），否則執行環節（4）當進程Pi順利獲得資源后，直至完畢，并釋放分派給它的資源，執行：Work[j]=Work[j]+Allocation[i][j];Finish[i]=true;Gotostep(2);假如所有的進程Finish[i]都滿足，則表達系統處在安全狀態，否則，處在不安全狀態。四、模塊設計與分析及整體功能概述模塊設計與分析：整個銀行家算法分為初始化函數Init（），安全性算法函數safe（），銀行家算法函數bank（）三部分。初始化函數生成開始時刻系統中的進程和資源情況，安全性算法判斷當某進程申請資源時，系統能否處在安全狀態。在本實驗中，若系統處在安全狀態，便生成一個安全進程序列（安全序列也許有多個）。銀行家算法函數bank（）負責整體的檢查與異常判斷。整體功能概述：死鎖會引起系統陷入僵局，操作系統必須防止此現象的發生。本實驗通過一個動態分派資源的模擬程序，更清楚的理解死鎖產生的因素和條件。Dijkstra的銀行家算法是最有代表性的避免死鎖的方法。運營程序時用戶設定系統中進程和可運用資源的種類數目。輸入各進程的可運用資源Available，最大需求MAX，已分派資源Allocation，需求資源Need，之后各系統發出資源請求Request，運用實驗中的安全性算法判斷能否產生一個安全性隊列，若能，則給該進程分派成功，否則，不予分派。五、流程圖設計六、源代碼及調試分析#include<iostream.h>#defineMAXm50//定義最大進程數#defineMAXn100//定義最大資源數intMAX[MAXm][MAXn];//最大需求矩陣intAllocation[MAXm][MAXn];//已分派矩陣intAvailable[MAXn];//可用資源數組intNeed[MAXm][MAXn];//需求矩陣intRequest[MAXm][MAXn];//請求矩陣intFinish[MAXm];//存儲完畢資源分派的進程intSequence[MAXm];//模擬的資源分派序列intWork[MAXn];//系統是否有足夠的資源分派給進程intm,n;//m個進程,n個資源#defineFalse0#defineTrue1voidinput();//數據輸入函數intsafealg();//安全性算法函數voidbanker();//銀行家算法函數voidmain(){input();safealg();banker();}//*************初始化算法***************voidinput(){ inti,j;//************自定義進程數目與資源種類******************* cout<<"***********************************\n"; cout<<"*運用銀行家算法避免死鎖*\n"; cout<<"**\n"; cout<<"************************************\n"; cout<<"請輸入進程的數目:"; cin>>m; cout<<"請輸入資源的種類:"; cin>>n; //*****輸入每個進程對每種資源的最大需求、已經獲得的數量、每種類型資源的數目 cout<<"各進程資源最大需求(Max),按照"<<m<<"x"<<n<<"矩陣輸入:\n"; for(i=0;i<m;i++) { cout<<"P"<<i<<":"; for(j=0;j<n;j++){ cin>>MAX[i][j]; if(j==n) cout<<"資源種類數匹配出現錯誤！";//當資源配置的種類數大于預先輸入的數值時，犯錯 } } cout<<"各進程當前獲得資源(Allocation),按照"<<m<<"x"<<n<<"矩陣輸入"<<endl; for(i=0;i<m;i++) { cout<<"P"<<i<<":"; for(j=0;j<n;j++) { cin>>Allocation[i][j]; if(j==n) cout<<"資源種類數匹配出現錯誤！";//當資源配置的種類數大于預先輸入的數值時，犯錯 Need[i][j]=MAX[i][j]-Allocation[i][j];//需求數等于最大需求減去已經分派數 } } cout<<"系統可用資源(Available):"<<endl; for(j=0;j<n;j++) { cin>>Available[j];//輸入各種資源的可運用數 } cout<<"當前時刻的進程分派情況如圖：\n"; cout<<"進程號-"<<"MAX----"<<"Allocation---"<<"Need--"<<"Available---\n";//顯示各進程的資源情況for(i=0;i<m;i++) { cout<<"P"<<i<<":"; for(j=0;j<n;j++) cout<<""<<MAX[i][j];for(j=0;j<n;j++) cout<<""<<Allocation[i][j]; cout<<""; for(j=0;j<n;j++) cout<<""<<Need[i][j]; for(j=0;j<n;j++) cout<<""<<Available[j]; cout<<endl;//回車換行 }}//*****************銀行家算法，為進程分派資源***********//voidbanker(){ inti,j; intchoice;while(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<<"請輸入進程申請的資源(Request):"<<endl; for(j=0;j<n;j++) cin>>Request[i][j]; //**********銀行家算法進行檢查*************// for(j=0;j<n;j++) { if(Request[i][j]>Need[i][j]) { cout<<"申請的資源大于它需要的資源數,請重新輸入!\n";//資源申請不合理 continue; } if(Request[i][j]>Available[j]) { //資源申請數目大于可運用數，無法分派，得等待 cout<<"當前系統可用資源不夠，請等待!"<<endl; continue; } } for(j=0;j<n;j++)//資源申請得到允許時，變換各個資源數 { Available[j]=Available[j]-Request[i][j];//可用資源減少 Allocation[i][j]=Allocation[i][j]+Request[i][j];//所得資源增長 Need[i][j]=Need[i][j]-Request[i][j];//仍需資源減少 } if(safealg()<0)//安全性算法的返回值 { cout<<"分派不成功，請等待！"; for(j=0;j<n;j++)//把資源恢復成分派之前的狀態 { Available[j]=Available[j]+Request[i][j]; Allocation[i][j]=Allocation[i][j]-Request[i][j]; Need[i][j]=Need[i][j]+Request[i][j]; } for(i=0;i<m;i++) { Finish[i]=False;//沒有足夠的資源分派給該進程 } }//if(safealg()<0) else { cout<<"批準分派請求!"<<endl; for(j=0;j<n;j++) Work[j]=Available[j];cout<<"進程號-"<<"--Work----"<<"Need---"<<"Allocation---"<<"Work+Allocation--" <<"Finish--"<<endl;for(i=0;i<m;i++)//按模擬分派序列進行分派 { cout<<"進程P"<<Sequence[i]<<":"; for(j=0;j<n;j++) cout<<Work[j]<<""; cout<<""; for(j=0;j<n;j++) cout<<Need[Sequence[i]][j]<<""; cout<<""; for(j=0;j<n;j++) cout<<Allocation[Sequence[i]][j]<<""; cout<<""; for(j=0;j<n;j++) cout<<Allocation[Sequence[i]][j]+Work[j]<<""; cout<<"";cout<<Finish[Sequence[i]]<<"";//完畢該進程 for(j=0;j<n;j++) Work[j]=Allocation[Sequence[i]][j]+Work[j];//回收該進程所分派的資源 cout<<endl; } }//if(safealg()>=0) }//if(choice=1) elseif(choice==2)//離開———— break; elsecout<<"請輸入1或2!";//只認可1或2 }//while(1)}//*********安全性算法************//intsafealg(){ inti,j,k,l=0; //intWork[MAXn];//工作組 //記錄序列 for(i=0;i<n;i++) Work[i]=Available[i];//工作分派初始化為系統可用資源 for(i=0;i<m;i++)//掃描所有進程，預設所有進程不能運營 { Finish[i]=False; } for(i=0;i<m;i++) {// if(Finish[i]==True) { continue; } else//對于未運營的進程，進行如下解決 {/// for(j=0;j<n;j++)//找到一個滿足Finish[i]=false且Need[i][j]<=Work[j]的進程 { if(Need[i][j]>Work[j])//由于部分資源得不到滿足，進程i無法運營 { break; } } if(j==n)//進程各類資源所有得到滿足 { Finish[i]=True; for(k=0;k<n;k++)//進程i正常運營后，釋放其占有的資源 { Work[k]+=Allocation[i][k];//工作分派加上可用資源 } Sequence[l++]=i;//模擬資源分派序列生成 i=-1;//重新掃描所有進程從i=0開始 } else {//某一資源得不到滿足 continue;//試探下一個進程 } }// if(l==m)//都試探完畢 { cout<<"系統安