銀行家算法

銀行家算法是一種最有代表性的避免死鎖的算法。在避免死鎖方法中允許進程動態地申請資源，但系統在進行資源分配之前，應先計算此次分配資源的安全性，若分配不會導致系統進入不安全狀態，則分配，否則等待。（破壞了環路等待條件）

實驗原理

數據結構

1）可利用資源向量Available
是個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目。如果Available［j］=K，則表示系統中現有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個，方能完成其任務。
Need［i,j］=Max［i,j］- Allocation［i,j］

int Allocation[11][101];//進程已獲得資源
int Max[11][101];//進程所需最大資源
int Available[11];//可分配資源
int Need[11][101];//進程所需資源
int Requesti[11];//資源請求
int Work[11];//工作向量
int link[11];//安全序列
int x,y;//x表進程數，y表資源種類

初始化

幫助用戶輸入已知變量的函數，構建銀行家算法的Max、Allocation、Need、Available矩陣，便于進行接下來的數據處理。

void init(){//初始化cout << "請輸入進程個數:" << endl;cin >> x;cout << "請輸入資源共有多少類:" << endl;cin >> y;cout << "請輸入每個進程所需要的各種資源的最大數目:" << endl;for (int i = 0; i < x; i++) {cout << "P" << i+1 << ":" ;for (int j = 0; j < y; j++) {cin >> Max[i][j];}}cout << "請輸入每個進程已分配的資源數量：" << endl;for(int i=0; i<x; i++){cout << "P" << i+1 << ":" ;for(int j=0; j<y; j++){cin >> Allocation[i][j];if(Allocation[i][j]>Max[i][j]){cout << "已分配資源數量大于進程所需的資源最大數目，請重新輸入" << endl;i--;}}}cout << "請輸入系統可分配的資源數:" << endl;for (int i = 0; i < y; i++) {cin >> Available[i];}for (int i = 0; i < x; i++) {//計算每一個進程尚需的各類資源數，Need矩陣for (int j = 0; j < y; j++) {Need[i][j] = Max[i][j] - Allocation[i][j];}}
}

輸出資源分配量

打印現在的矩陣狀態（Max、Allocation、Need、Available），方便用戶了解算法進行程度

void printSystemVariable(){//輸出資源分配量cout << "此時資源分配量如下：" << endl;cout << "進程  " << "   Max   " << "   Alloction " << "    Need  " << "    Available " << endl;for(int i=0;i<x;i++){//第i個進程cout << "P" << i+1 << "     " ;for(int j=0;j<y;j++){//第i個進程的Max矩陣信息cout << Max[i][j] << "    " ;}cout << "|  " ;for(int j=0;j<y;j++){//第i個進程的Allocation矩陣信息cout << Allocation[i][j] << "    " ;}cout << "|  " ;for(int j=0;j<y;j++){//第i個進程的Need矩陣信息cout << Need[i][j] << "    " ;}cout << "|  " ;if(i==0){for(int j=0;j<y;j++){//第i個進程的Available矩陣信息cout << Available[j] << "    " ;}}cout << endl ;}
}

安全性算法

1）設置兩個向量：
工作向量Work: 它表示系統可提供給進程繼續運行所需的各類資源數目，它含有m個元素，在執行安全算法開始時，Work=Available;
工作向量Finish: 它表示系統是否有足夠的資源分配給進程，使之運行完成。開始時先做Finish［i］=false; 當有足夠資源分配給進程時，再令Finish［i］=true。
2）從進程集合中找到一個能滿足下述條件的進程：
Finish［i］=false;
Need［i,j］≤Work［j］；
若找到，執行 (3)，否則，執行 (4)
3）當進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：
Work［j］=Work［i］+Allocation［i,j］;
Finish［i］=true;
go to step 2;
4）如果所有進程的Finish［i］=true都滿足，則表示系統處于安全狀態；否則，系統處于不安全狀態

bool chesksafe(){//安全性算法for (int i = 0; i < y; i++) {Work[i] = Available[i];}bool Finish[7];//工作向量int mark = x;//避免改變x的值所設的變量int temp = 0;//滿足需求資源少于剩余資源這一條件的資源數int flag = 0;//進行資源分配的次數while (mark--) {//求安全序列的操作最多進行進程數次for(int i=0;i<x;++i){//判定第i個進程if(Finish[i]==true){continue;}for (int j = 0; j < y; j++) {if(Need[i][j]<=Work[j]){//計算該進程需求資源少于剩余資源的資源數temp++;}}if(temp==y){//全部資源都滿足需求資源少于剩余資源for (int j = 0; j < y; j++) {//獲得分配給該資源的資源數Work[j]+=Allocation[i][j];}Finish[i]=true;flag++;//進行一次資源分配link[flag]=i+1;//將進行資源分配的進程依次放入隊列}temp=0;//更新滿足分配資源條件的資源數}}if(flag==x){//如果沒有進行進程數次資源分配，說明不是安全序列cout << "系統處于安全狀態，安全序列為：" << endl;for (int i = 1; i <= x; i++) {cout << "P" << link[i] << " " ;}cout << endl;return true;}else{cout << "系統處于不安全狀態" << endl;return false;}
}

銀行家算法

設Requesti是進程Pi的請求向量，如果Requesti［j］=K，表示進程Pi需要K個Rj類型的資源。當Pi發出資源請求后，系統按下述步驟進行檢查：
(1)如果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］;
系統執行安全性算法，檢查此次資源分配后，系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復原來的資源分配狀態，讓進程Pi等待。

  string an;//存儲是否請求分配的用戶指令bool flag = false;//用于跳出兩層循環的標志while(1){cout << "是否請求分配？（'y'or'Y'表是，'n'or'N'表否） " ;cin>>an;if(an[0]!='Y'&&an[0]!='y'){break;}int num;cout << "請輸入請求資源的進程號（如：P1則輸入1）： " << endl;cin >> num;num -= 1;//進程從1開始計數但各個數組下標從0開始計數cout << "輸入進程請求的資源數" << endl;for (int i = 0; i < y; i++) {cin >> Requesti[i];}for (int i = 0; i < y; i++) {if(Requesti[i]>Need[num][i]){cout << "所需要的資源數已超過所宣布最大值Max" << endl;flag = true;break;}if(Requesti[i]>Available[i]){cout << "尚無足夠資源" << endl;flag = true;break;}Available[i]-=Requesti[i];Allocation[num][i]+=Requesti[i];Need[num][i]-=Requesti[i];}if (flag){//當任意資源請求出現問題時，跳出兩層循環flag = false;//更新標志continue;//執行下一次循環}int temp = 0;//滿足Max值的Allocation值的個數if(chesksafe()){//安全,完成本次分配for (int i = 0; i < y; i++) {if(Allocation[num][i]>=Max[num][i]){temp++;}}if (temp == y) {/*如果1個進程分配資源后，每個資源已獲得值都大于等于所需最大值則更新Available、Allocation和Need矩陣*/for (int i = 0; i < y; i++) {Available[i]+=Allocation[num][i];//可分配資源獲得該進程已獲得的資源數Allocation[num][i]=0;//清空該進程已獲得的資源數Need[num][i]=0;//清空該進程尚需的各類資源數}}cout << "分配成功" << endl;printSystemVariable();}else{//不安全,撤銷之前的操作cout << "分配失敗" << endl;for (int i = 0; i < y; i++) {Available[i]+=Requesti[i];Need[num][i]+=Requesti[i];Allocation[num][i]-=Requesti[i];}printSystemVariable();}}

完整代碼

#include <iostream>
using namespace std;int Allocation[11][101];//進程已獲得資源
int Max[11][101];//進程所需最大資源
int Available[11];//可分配資源
int Need[11][101];//進程所需資源
int Requesti[11];//資源請求
int Work[11];//工作向量
int link[11];//安全序列
int x,y;//x表進程數，y表資源種類void init();//初始化
void printSystemVariable();//輸出資源分配量
bool chesksafe();//安全性算法int main(int argc, char const *argv[]) {init();printSystemVariable();if(!chesksafe()){return 0;}string an;//存儲是否請求分配的用戶指令bool flag = false;//用于跳出兩層循環的標志while(1){cout << "是否請求分配？（'y'or'Y'表是，'n'or'N'表否） " ;cin>>an;if(an[0]!='Y'&&an[0]!='y'){break;}int num;cout << "請輸入請求資源的進程號（如：P1則輸入1）： " << endl;cin >> num;num -= 1;//進程從1開始計數但各個數組下標從0開始計數cout << "輸入進程請求的資源數" << endl;for (int i = 0; i < y; i++) {cin >> Requesti[i];}for (int i = 0; i < y; i++) {if(Requesti[i]>Need[num][i]){cout << "所需要的資源數已超過所宣布最大值Max" << endl;flag = true;break;}if(Requesti[i]>Available[i]){cout << "尚無足夠資源" << endl;flag = true;break;}Available[i]-=Requesti[i];Allocation[num][i]+=Requesti[i];Need[num][i]-=Requesti[i];}if (flag){//當任意資源請求出現問題時，跳出兩層循環flag = false;//更新標志continue;//執行下一次循環}int temp = 0;//滿足Max值的Allocation值的個數if(chesksafe()){//安全,完成本次分配for (int i = 0; i < y; i++) {if(Allocation[num][i]>=Max[num][i]){temp++;}}if (temp == y) {/*如果1個進程分配資源后，每個資源已獲得值都大于等于所需最大值則更新Available、Allocation和Need矩陣*/for (int i = 0; i < y; i++) {Available[i]+=Allocation[num][i];//可分配資源獲得該進程已獲得的資源數Allocation[num][i]=0;//清空該進程已獲得的資源數Need[num][i]=0;//清空該進程尚需的各類資源數}}cout << "分配成功" << endl;printSystemVariable();}else{//不安全,撤銷之前的操作cout << "分配失敗,撤銷本次操作" << endl;for (int i = 0; i < y; i++) {Available[i]+=Requesti[i];Need[num][i]+=Requesti[i];Allocation[num][i]-=Requesti[i];}printSystemVariable();}}return 0;
}void init(){//初始化cout << "請輸入進程個數:" << endl;cin >> x;cout << "請輸入資源共有多少類:" << endl;cin >> y;cout << "請輸入每個進程所需要的各種資源的最大數目:" << endl;for (int i = 0; i < x; i++) {cout << "P" << i+1 << ":" ;for (int j = 0; j < y; j++) {cin >> Max[i][j];}}cout << "請輸入每個進程已分配的資源數量：" << endl;for(int i=0; i<x; i++){cout << "P" << i+1 << ":" ;for(int j=0; j<y; j++){cin >> Allocation[i][j];if(Allocation[i][j]>Max[i][j]){cout << "已分配資源數量大于進程所需的資源最大數目，請重新輸入" << endl;i--;}}}cout << "請輸入系統可分配的資源數:" << endl;for (int i = 0; i < y; i++) {cin >> Available[i];}for (int i = 0; i < x; i++) {//計算每一個進程尚需的各類資源數，Need矩陣for (int j = 0; j < y; j++) {Need[i][j] = Max[i][j] - Allocation[i][j];}}
}void printSystemVariable(){//輸出資源分配量cout << "此時資源分配量如下：" << endl;cout << "進程  " << "   Max   " << "   Alloction " << "    Need  " << "    Available " << endl;for(int i=0;i<x;i++){//第i個進程cout << "P" << i+1 << "     " ;for(int j=0;j<y;j++){//第i個進程的Max矩陣信息cout << Max[i][j] << "    " ;}cout << "|  " ;for(int j=0;j<y;j++){//第i個進程的Allocation矩陣信息cout << Allocation[i][j] << "    " ;}cout << "|  " ;for(int j=0;j<y;j++){//第i個進程的Need矩陣信息cout << Need[i][j] << "    " ;}cout << "|  " ;if(i==0){for(int j=0;j<y;j++){//第i個進程的Available矩陣信息cout << Available[j] << "    " ;}}cout << endl ;}
}bool chesksafe(){//安全性算法for (int i = 0; i < y; i++) {Work[i] = Available[i];}bool Finish[7];//工作向量int mark = x;//避免改變x的值所設的變量int temp = 0;//滿足需求資源少于剩余資源這一條件的資源數int flag = 0;//進行資源分配的次數while (mark--) {//求安全序列的操作最多進行進程數次for(int i=0;i<x;++i){//判定第i個進程if(Finish[i]==true){continue;}for (int j = 0; j < y; j++) {if(Need[i][j]<=Work[j]){//計算該進程需求資源少于剩余資源的資源數temp++;}}if(temp==y){//全部資源都滿足需求資源少于剩余資源for (int j = 0; j < y; j++) {//獲得分配給該資源的資源數Work[j]+=Allocation[i][j];}Finish[i]=true;flag++;//進行一次資源分配link[flag]=i+1;//將進行資源分配的進程依次放入隊列}temp=0;//更新滿足分配資源條件的資源數}}if(flag==x){//如果沒有進行進程數次資源分配，說明不是安全序列cout << "系統處于安全狀態，安全序列為：" << endl;for (int i = 1; i <= x; i++) {cout << "P" << link[i] << " " ;}cout << endl;return true;}else{cout << "系統處于不安全狀態" << endl;return false;}
}