死鎖-銀行家算法實驗報告

./實驗目的銀行家算法是避免死鎖的一種重要方法。通過編寫一個模擬動態(tài)資源分配的銀行家算法程序,進一步深入理解死鎖、產(chǎn)生死鎖的必要條件、安全狀態(tài)等重要概念,并掌握避免死鎖的具體實施方法二、實驗要求根據(jù)銀行家算法的基本思想,編寫和調(diào)試一個實現(xiàn)動態(tài)資源分配的模擬程序,并能夠有效地防止和避免死鎖的發(fā)生。設計思想說明設計銀行家算法是為了避免死鎖三、實驗方法內(nèi)容算法設計思路銀行家算法又稱"資源分配拒絕"法,其基本思想是,系統(tǒng)中的所有進程放入進程集合,在安全狀態(tài)下系統(tǒng)受到進程的請求后試探性的把資源分配給他,現(xiàn)在系統(tǒng)將剩下的資源和進程集合中其他進程還需要的資源數(shù)做比較,找出剩余資源能滿足最大需求量的進程,從而保證進程運行完成后還回全部資源。這時系統(tǒng)將該進程從進程集合中將其清除。此時系統(tǒng)中的資源就更多了。反復執(zhí)行上面的步驟,最后檢查進程的集合為空時就表明本次申請可行,系統(tǒng)處于安全狀態(tài),可以實施本次分配,否則,只要進程集合非空,系統(tǒng)便處于不安全狀態(tài),本次不能分配給他。請進程等待算法流程圖算法中用到的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)的說明1.可利用資源向量AVAILABLE。這是一個含有M個元素的數(shù)組,其中的每一個元素代表一類可利用的資源數(shù)目,其3初始值是系統(tǒng)中所配置的該類全部可哦那個資源的數(shù)目,其數(shù)值隨該類資源的分配和回收而動態(tài)的改變。2.最大需求矩陣MAX。這是一個M*N的矩陣,它定義了系統(tǒng)中N個進程中的每一個進程對M類資源的最大需求。3.分配矩陣ALLOCATION。這也是一個M*N的矩陣,它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。4.需求矩陣NEED。這也是一個M*N的矩陣,用以表示每一個進程尚需的各類資源數(shù)。5.NEED[R,W]=MAX[R,W]-ALLOCATION[R,W]主要的常量變量#defineW10//最大進程數(shù)W=10#defineR20//最大資源總數(shù)R=20intAVAILABLE[R];//可利用資源向量intMAX[W][R];//最大需求矩陣intALLOCATION[W][R];//分配矩陣intNEED[W][R];//需求矩陣intRequest[R];//進程請求向量voidchangdata<intk>;//進程請求資源數(shù)據(jù)改變intchksec<ints>;//系統(tǒng)安全性的檢測主要模塊voidinputdata<>voidshowdata<>voidchangdata<intk>voidrestoredata<intk>intchksec<ints>intchkmax<ints>四、實驗代碼#include<string.h>#include<iostream.h>#defineFALSE0#defineTRUE1#defineW10//最大進程數(shù)W=10#defineR20//最大資源總數(shù)R=20intM;intN;intALL_RESOURCE[W];intAVAILABLE[R];//可利用資源向量intMAX[W][R];//最大需求矩陣intALLOCATION[W][R];//分配矩陣intNEED[W][R];//需求矩陣intRequest[R];//進程請求向量voidinputdata<>;//數(shù)據(jù)輸入voidshowdata<>;//數(shù)據(jù)顯示voidchangdata<intk>;//進程請求資源數(shù)據(jù)改變voidrestoredata<intk>;//數(shù)據(jù)恢復intchksec<ints>;//系統(tǒng)安全性的檢測intchkmax<ints>;//檢測最大需求voidbank<>;//檢測分配的資源是否合理.voidmain<>{inti,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<>;}}voidinputdata<>{ inti=0,j=0,p;cout<<"請輸入總進程數(shù):"<<endl;do{ cin>>M;if<M>W>cout<<endl<<"總進程數(shù)超過了程序允許的最大進程數(shù),請重新輸入:"<<endl;}while<M>W>;cout<<endl;cout<<"請輸入資源的種類數(shù):"<<endl;do{cin>>N;if<N>R> cout<<endl<<"資源的種類數(shù)超過了程序允許的最大資源種類數(shù),請重新輸入:"<<endl;}while<N>R>;cout<<endl;cout<<"請依次輸入各類資源的總數(shù)量,即設置向量all_resource:"<<endl;for<i=0;i<N;i++> cin>>ALL_RESOURCE[i];cout<<endl;cout<<"請依次輸入各進程所需要的最大資源數(shù)量,即設置矩陣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<<"該最大資源數(shù)量超過了聲明的該資源總數(shù),請重新輸入:"<<endl;}while<MAX[i][j]>ALL_RESOURCE[j]>;}}cout<<endl;cout<<"請依次輸入各進程已經(jīng)占據(jù)的各類資源數(shù)量,即設置矩陣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<<"已占有的資源數(shù)量超過了聲明的最大資源數(shù)量,請重新輸入:"<<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<<"各種資源的總數(shù)量,即向量all_resource為:"<<endl;cout<<"";for<j=0;j<N;j++> cout<<"資源"<<j<<":"<<ALL_RESOURCE[j];cout<<endl<<endl;cout<<"當前系統(tǒng)中各類資源的可用數(shù)量,即向量available為:"<<endl;cout<<"";for<j=0;j<N;j++> cout<<"資源"<<j<<":"<<AVAILABLE[j];cout<<endl<<endl;cout<<"各進程還需要的資源數(shù)量,即矩陣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<<"各進程已經(jīng)得到的資源量,即矩陣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<<"申請的資源數(shù):"<<endl;for<j=0;j<N;j++> { cout<<"資源"<<j<<":"; cin>>Request[j];if<Request[j]>NEED[i][j]> {cout<<"進程P"<<i<<"申請的資源數(shù)大于進程P"<<i<<"還需要"<<j<<"類資源的資源量!"; cout<<"申請不合理,出錯!請重新選擇!"<<endl<<endl; flag='N';break; }else { if<Request[j]>AVAILABLE[j]> {cout<<"進程P"<<i<<"申請的資源數(shù)大于系統(tǒng)可用"<<j<<"類資源的資源量!"; cout<<"申請不合理,出錯!請重新選擇!"<<endl<<endl; flag='N';break; } } } if<flag=='Y'||flag=='y'> { changdata<i>;if<chksec<i>> {cout<<endl; cout<<"該分配會導致系統(tǒng)不安全!!!本次資源申請不成功