1.設計目的與要求

1.1設計目的

????????了解銀行家算法中使用的數據結構和求安全序列算法，并進一步加深對避免死鎖算法及其實現過程的理解。

1.2設計要求

????????通過編寫和調試一個系統動態分配資源的簡單模擬程序，觀察死鎖產生的條件，并采用適當的算法，有效地防止和避免死鎖的發生。

2.設計思想及系統平臺

2.1設計思想

????????基本思想分為兩個模塊，一是銀行家算法模塊，二是安全性檢查模塊。當有進程申請資源時，先檢查系統是否能夠滿足進程的請求，此時程序進入安全性檢查模塊，如果安全就分配，不安全就拒絕申請。

????????本算法的數據結構：

? ? ? ? 1）可利用資源向量Available。這是一個含有m個元素的數組，其中的每一個元素代表一類可利用的資源數目。

? ? ? ? 2）最大需求矩陣Max。這是一個n×m的矩陣，定義了系統中n個進程中的每一個進程對m類資源的最大需求。

? ? ? ? 3）分配矩陣Allocation。這也是一個n×m的矩陣，定義了系統中每一類資源當前已分配給每一進程的資源數。

? ? ? ? 4）需求矩陣Need。這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數。

????????由數學知識可知，Need[i,j]=Max[i,j]-Allocation[i,j]。

2.2系統平臺及使用語言

????????CodeBlocks，C++

3.詳細算法描述

1）初始化函數Init()

????????用戶輸入數據，初始化可利用資源向量矩陣AVAILABLE、最大需求矩陣MAX、分配矩陣ALLOCATION、需求矩陣NEED。

2）銀行家算法Order()

????????當進程Pi發出資源請求后，系統按以下步驟進行檢查：

????????①如果Request[i,j]<=Need[i,j]，便轉向步驟②；否則出錯，因為它請求的資源數已超過它的需求最大值。

????????②如果Request[i,j]<=Available[j]，便轉向步驟③；否則，表示當前資源不足，Pi須等待

????????③系統試探著把資源分配給進程Pi，并修改下面數據結構中的數值：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]

????????④系統執行安全性算法，檢查此次資源分配后系統是否處于安全狀態。若安全，才正式將資源分配給進程Pi；否則，恢復原來的資源分配狀態，讓進程Pi等待。

3）安全性檢查算法Safecheck()

????????①設置兩個向量：工作向量Work，表示系統可提供給進程繼續運行所需的各類資源數目，初始化Work=Available；Finish，表示系統是否有足夠的資源分配給進程，初始化Finish[i]=false；當有足夠資源分配給進程時，再令Finish[i]=true。

????????②從進程集合中找到一個能滿足下述條件的進程：Finish[i]=false；Need[i,j]≤Work[j]；若找到，執行步驟③，否則，執行步驟④。

????????③假設進程Pi獲得資源后，可順利執行，直至完成，并釋放出分配給它的資源，故應執行：Work[j]= Work[j]+Allocation[i,j]；Finish[i]=true；go to step ②

????????④如果所有進程的Finish[i]=true都滿足，則表示系統處于安全狀態；否則，系統處于不安全狀態。

4.源代碼

#include <iostream>
#include <vector>
using namespace std;
#define MAX 20
int n_process;//表示進程的個數
int n_resource;//表示資源的個數
int Resource[MAX];//表示資源的總數
int Max[MAX][MAX];//表示進程對每類資源的最大需求量
int Allocation[MAX][MAX];//表示系統給進程已分配每類資源的數目
int Need[MAX][MAX];//表示進程還需各類資源數目
int Available[MAX];//表示系統當前剩下的資源
int Work[MAX];//表示安全性檢查的中間變量
bool Finish[MAX];//表示資源是否被安全性檢查過
vector<int> Safeorder;//表示安全序列
void Menu()
{cout << "------------銀行家算法----------------" << endl;cout << "*          1.初始化數據              *" << endl;cout << "*          2.申請資源                *" << endl;cout << "*          3.顯示資源分配情況        *" << endl;cout << "*          4.退出                    *" << endl;cout << "--------------------------------------" << endl;cout << "請選擇：";
}
//檢查初始化數值是否合理
void checkInit()
{if (n_resource)for (int i = 0; i < n_process; i++){for (int j = 0; j < n_resource; j++){if (Max[i][j] < 0){cout << "Max[" << i << "][" << j << "]輸入值小于0！" << endl;}if (Allocation[i][j] < 0){cout << "Allocation[" << i << "][" << j << "]輸入值小于0！" << endl;}if (Allocation[i][j]>Max[i][j]){cout << "Allocation[" << i << "][" << j << "]的值大于Max[" << i << "][" << j << "]輸入值" << endl;}}}for (int i = 0; i < n_resource; i++){if (Available[i]<0){cout << "Available[" << i << "]的值小于0！" << endl;}}cout << "檢查完畢，輸入無誤！" << endl;
}
//初始化進程和資源
int Init()
{if (n_resource != 0 && n_process != 0){cout << "已經初始化過了！" << endl;return 1;}cout << "請分別輸入資源個數和進程個數，中間用空格隔開：" << endl;cin >> n_resource >> n_process;cout << "請輸入各個資源的總擁有量：" << endl;for (int i = 0; i < n_resource; i++){cin >> Resource[i];}for (int i = 0; i < n_process; i++){cout << "P" << i << "對各個資源的最大需求量：" << endl;for (int j = 0; j < n_resource; j++){cin >> Max[i][j];}cout << "P" << i << "各個資源已分配量：" << endl;for (int j = 0; j < n_resource; j++){cin >> Allocation[i][j];}for (int j = 0; j < n_resource; j++){Need[i][j] = Max[i][j] - Allocation[i][j];}}for (int i = 0; i < n_resource; i++){int sum[MAX] = { 0 };for (int j = 0; j < n_process; j++){switch(i){case 0:case 1:case 2:sum[i] += Allocation[j][i];break;}}Available[i] = Resource[i] - sum[i];}checkInit();return 1;
}
//安全性檢查
bool Safecheck()
{//清空原來的安全序列Safeorder.clear();//Work初始化為Availablefor (int i = 0; i < n_resource; i++){Work[i] = Available[i];}//還沒開始檢查，設置標志為falsefor (int i = 0; i < n_process; i++){Finish[i] = false;}//開始安全性檢查int count = 0;for (int k = 0; k < n_process; k++){for (int i = 0; i < n_process; i++){if (Finish[i] == false){count = 0;for (int j = 0; j < n_resource; j++){if (Need[i][j] <= Work[j])count++;}//如果進程所需的各個資源數都沒有超過系統現有的對應資源數if (count == n_resource){for (int j = 0; j < n_resource; j++){//將Work賦值為 第i個進程各個已分配資源數＋系統現有的對應資源數Work[j] = Work[j] + Allocation[i][j];}Finish[i] = true;Safeorder.push_back(i);//加入到安全序列}}}}count = 0;//安全的進程數for (int i = 0; i < n_process; i++){if (Finish[i] == true)count++;}if (count == n_process)return true;elsereturn false;
}
//請求進程
int Order()
{int n = -1; //請求資源的進程號int *Request = new int[n_resource];//表示請求的各個資源數量cout << "請輸入你要請求的進程號：";cin >> n;cout << "請輸入你要請求各個資源的數量，中間用空格隔開：" << endl;for (int i = 0; i< n_resource; i++){cin >> Request[i];}//開始判斷//請求量大于該進程的最大需求量，出錯for (int i = 0; i < n_resource; i++){if (Need[n][i] < Request[i]){cout << "輸入錯誤，請求量不能比該進程的最大需求量還大！" << endl;return 1;}}//請求量大于當前空閑資源量，出錯for (int i = 0; i < n_resource; i++){if (Available[i] < Request[i]){cout << "拒絕，當前空閑資源不夠！" << endl;return 1;}}//請求量合理，試圖分配資源給請求進程，并做安全性檢查for (int i = 0; i < n_resource; i++){Available[i] -= Request[i];Allocation[n][i] += Request[i];Need[n][i] -= Request[i];}//安全性檢查bool Is_safe=Safecheck();if (Is_safe == true){cout << "系統已經分配資源給P" << n << "進程了！" << endl;cout << "其中一個安全序列為：" << endl;for (int i = 0; i < Safeorder.size(); i++){cout << "P" << Safeorder.at(i) << "->";}cout << "End" << endl ;}//不安全，恢復試分配之前的現場else{cout << "不能分配資源，否則系統會處于不安全狀態！" << endl;for (int i = 0; i < n_resource; i++){Available[i] += Request[i];Allocation[n][i] -= Request[i];Need[n][i] += Request[i];}}return 1;
}
//顯示資源分配情況
void Display()
{cout << endl;cout << "進程 \t Max \t Allocation\tNeed\tAvailable" << endl;for (int i = 0; i < n_process; i++){cout << " P" << i << " \t";for (int j = 0; j < n_resource; j++){cout << Max[i][j] << " ";}cout << "\t   ";for (int j = 0; j < n_resource; j++){cout << Allocation[i][j] << " ";}cout << "\t";for (int j = 0; j < n_resource; j++){cout << Need[i][j] << " ";}cout << "\t  ";for (int j = 0; i==0&&j < n_resource; j++){cout << Available[j] << " ";}cout << endl;}cout << endl;
}int main()
{int choose = 0;while (1){Menu();cin >> choose;switch (choose){case 1:Init();break;case 2:Order();break;case 3:Display();break;case 4:cout << "系統已退出！";return 1;default:cout << "輸錯了，重輸" << endl;break;}}
}

?實驗報告：https://download.csdn.net/download/sjhdxpz/88212618