文章目錄

• • 銀行家算法
  • 實驗原理
  • • 銀行家算法中的數據結構
    • 銀行家算法
    • 安全性算法
  • 完整代碼
  • 測試
  • • 測試代碼
    • 測試數據
    • 測試結果

---

銀行家算法

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

---

實驗原理

銀行家算法中的數據結構

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］

這里我用到的數據結構成員變量

std::vector<std::string> _ResouceName; //資源名std::vector<int> _available; //系統可利用的各類資源數目std::vector< std::vector<int >> _max; //每一個進程對各種資源的最大需求std::vector< std::vector<int >> _allocation; //系統中每一類資源當前已分配給每一進程的資源數std::vector< std::vector<int >> _need; //每一個進程尚需的各類資源數std::vector<int> _Security; //安全序列size_t _processNum; //進程數size_t _resouceNum; //資源數

---

銀行家算法

設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等待。

bool CheckRequest(size_t pid, std::vector<int> request){//檢查資源請求是否合理for (size_t i = 0; i < _resouceNum; i++){//需求資源數已經超過最大值if (request[i] > _need[pid][i]){std::cout << "需求資源數已經超過最大值" << std::endl;return false;}//尚無足夠資源if (request[i] > _available[i]){std::cout << "尚無足夠資源，進程等待" << std::endl;return false;} }//嘗試分配資源給進程，看看此次分配后系統是否處于安全狀態for (size_t i = 0; i < _resouceNum; i++){_available[i] -= request[i];_allocation[pid][i] += request[i];_need[pid][i] -= request[i];}//檢查分配后系統是否安全if (CheckSafe() == true){//分配后系統安全，正式分配std::cout << "本次資源" << pid << "分配成功" << std::endl;OutPut();return true;}else{//分配后不安全，分配失效，資源恢復std::cout << "本次資源分配后系統不安全，分配作廢" << std::endl;for (size_t i = 0; i < _resouceNum; i++){_available[i] += request[i];_allocation[pid][i] -= request[i];_need[pid][i] += request[i];}OutPut();return false;}}

---

安全性算法

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 CheckSafe(){std::vector<int> work(_available); //表示系統可提供給進程繼續運行所需的各類資源數目std::vector<bool> finish(_processNum, false); //表示系統是否有足夠的資源分配給該進程while (1){size_t i = 0;//檢查是否全部都處于安全狀態for (i = 0; i < _processNum; i++){if(finish[i] == false)break;}//如果全都處于安全狀態，則說明此時系統也處于安全狀態if (i == _processNum){std::cout << "系統此時安全" << std::endl;return true;}for (i = 0; i < _processNum; i++){//如果這個進程已經執行過，則跳過if (finish[i] == true){continue;}//標志當前進程分配資源后是否安全bool flag = true;for (size_t j = 0; j < _resouceNum; j++){//如果某一項資源不夠分配，則說明當前進程不能執行，繼續判斷后面的if (_need[i][j] > work[j]){flag = false;break;}}if (flag == true){std::cout << "執行進程" << i << " ,系統可利用資源更新" << std::endl;//加入安全序列中_Security.push_back(i);//調用進程運行，并且釋放進程所占資源for (size_t j = 0; j < _resouceNum; j++){work[j] += _allocation[i][j];finish[i] = true;std::cout << "可用資源"<< _ResouceName[j] << "更新為: " << work[j] << std::endl;}break;//調用完后進入下一輪查找安全進程}}//如果進程全部遍歷完也沒有任何一個執行，則說明此時無法分配，不安全if (i == _processNum){std::cout << "系統此時不安全" << std::endl;return false;} }}

---

完整代碼

#include<iostream> #include<string> #include<vector>class Banker { public:friend Banker* Input(); //輸入函數 std::vector<std::string> _ResouceName; //資源名Banker(std::vector<std::string> ResouceName, std::vector<int> available, std::vector< std::vector<int >> max, std::vector< std::vector<int >> allocation): _ResouceName(ResouceName), _available(available), _max(max), _allocation(allocation), _need(_max.size(), std::vector<int>(_max[0].size(), 0)), _processNum(_max.size()), _resouceNum(_max[0].size()){//計算出需要的資源數for (size_t i = 0; i < _processNum; i++){ for (size_t j = 0; j < _resouceNum; j++){_need[i][j] = _max[i][j] - _allocation[i][j];}}}//封裝給外界獲取數量的接口int ResouceNum() const{return _resouceNum;}int ProcessNum() const{return _processNum;}//輸出安全序列void printSecurity(){std::cout << "--------------" << std::endl;std::cout << "安全序列為: " ;for (auto it : _Security){std::cout << it << std::ends;}std::cout << "--------------" << std::endl;std::cout << std::endl;}//輸出函數void OutPut(){std::cout << "*************************************" << std::endl;std::cout << "當前進程數:" << _processNum << " 當前資源種類數量:" << _resouceNum << std::endl;for (size_t i = 0; i < _resouceNum; i++){std::cout << "資源" << _ResouceName[i] << "可用數量為: " << _available[i] << std::endl;}std::cout << "--------------" << std::endl;for (size_t i = 0; i < _processNum; i++){std::cout << "進程" << i << std::endl;for (size_t j = 0; j < _resouceNum; j++){std::cout << "資源" << _ResouceName[j] << " 最大需求數量為: " << _max[i][j] << " 當前分配數量為: " << _allocation[i][j] << " 剩余需求數量為: " << _need[i][j] << std::endl;}}std::cout << "*************************************" << std::endl;}//銀行家算法核心，判斷請求算法bool CheckRequest(size_t pid, std::vector<int> request){//檢查資源請求是否合理for (size_t i = 0; i < _resouceNum; i++){//需求資源數已經超過最大值if (request[i] > _need[pid][i]){std::cout << "需求資源數已經超過最大值" << std::endl;return false;}//尚無足夠資源if (request[i] > _available[i]){std::cout << "尚無足夠資源，進程等待" << std::endl;return false;} }//嘗試分配資源給進程，看看此次分配后系統是否處于安全狀態for (size_t i = 0; i < _resouceNum; i++){_available[i] -= request[i];_allocation[pid][i] += request[i];_need[pid][i] -= request[i];}//檢查分配后系統是否安全if (CheckSafe() == true){//分配后系統安全，正式分配std::cout << "本次資源" << pid << "分配成功" << std::endl;OutPut();return true;}else{//分配后不安全，分配失效，資源恢復std::cout << "本次資源分配后系統不安全，分配作廢" << std::endl;for (size_t i = 0; i < _resouceNum; i++){_available[i] += request[i];_allocation[pid][i] -= request[i];_need[pid][i] += request[i];}OutPut();return false;}}//安全性算法bool CheckSafe(){std::vector<int> work(_available); //表示系統可提供給進程繼續運行所需的各類資源數目std::vector<bool> finish(_processNum, false); //表示系統是否有足夠的資源分配給該進程while (1){size_t i = 0;//檢查是否全部都處于安全狀態for (i = 0; i < _processNum; i++){if(finish[i] == false)break;}//如果全都處于安全狀態，則說明此時系統也處于安全狀態if (i == _processNum){std::cout << "系統此時安全" << std::endl;return true;}for (i = 0; i < _processNum; i++){//如果這個進程已經執行過，則跳過if (finish[i] == true){continue;}//標志當前進程分配資源后是否安全bool flag = true;for (size_t j = 0; j < _resouceNum; j++){//如果某一項資源不夠分配，則說明當前進程不能執行，繼續判斷后面的if (_need[i][j] > work[j]){flag = false;break;}}if (flag == true){std::cout << "執行進程" << i << " ,系統可利用資源更新" << std::endl;//加入安全序列中_Security.push_back(i);//調用進程運行，并且釋放進程所占資源for (size_t j = 0; j < _resouceNum; j++){work[j] += _allocation[i][j];finish[i] = true;std::cout << "可用資源"<< _ResouceName[j] << "更新為: " << work[j] << std::endl;}break;//調用完后進入下一輪查找安全進程}}//如果進程全部遍歷完也沒有任何一個執行，則說明此時無法分配，不安全if (i == _processNum){std::cout << "系統此時不安全" << std::endl;return false;} }}private:std::vector<int> _available; //系統可利用的各類資源數目std::vector< std::vector<int >> _max; //每一個進程對各種資源的最大需求std::vector< std::vector<int >> _allocation; //系統中每一類資源當前已分配給每一進程的資源數std::vector< std::vector<int >> _need; //每一個進程尚需的各類資源數std::vector<int> _Security; //安全序列size_t _processNum; //進程數size_t _resouceNum; //資源數 };//輸入函數 Banker* Input() {size_t processNum, resouceNum;std::cout << "請輸入進程數量:" << std::endl;std::cin >> processNum;std::cout << "請輸入資源種類數量:" << std::endl;std::cin >> resouceNum;std::vector<std::string> ResouceName(resouceNum);std::vector<int> available(resouceNum);std::vector< std::vector<int >> max(processNum, std::vector<int>(resouceNum, 0));std::vector< std::vector<int >> allocation(processNum, std::vector<int>(resouceNum, 0));std::cout << "請輸入資源名:" << std::endl;for (size_t i = 0; i < resouceNum; i++){std::cin >> ResouceName[i];}std::cout << "請輸入系統中該資源空閑數量:" << std::endl;for (size_t i = 0; i < resouceNum; i++){std::cin >> available[i];}for (size_t i = 0; i < processNum; i++){std::cout << "請輸入進程" << i << "中資源的最大需求量:" << std::endl;for (size_t j = 0; j < resouceNum; j++){ std::cin >> max[i][j];}}for (size_t i = 0; i < processNum; i++){std::cout << "請輸入進程" << i << "中資源的已分配數量:" << std::endl;for (size_t j = 0; j < resouceNum; j++){ std::cin >> allocation[i][j];}}std::cout << "資源輸入完畢" << std::endl;std::cout << "--------------" << std::endl;Banker* banker = new Banker(ResouceName, available, max, allocation);return banker; }

測試

測試代碼

#include"Banker.hpp" using namespace std;void test() {int flag = 0;Banker* backup = Input();bool result;while (1){Banker banker = *backup;cout << "--------------------" << endl;cout << "1.判斷當前系統狀態" << endl;cout << "2.申請資源" << endl;cout << "0.退出" << endl;cout << "--------------------" << endl;cin >> flag;switch (flag){case 1:{result = banker.CheckSafe();break;}case 2:{size_t pid;vector<int> request(banker.ResouceNum(), 0);cout << "請輸入發起請求的進程號:" << endl;cin >> pid;cout << "請輸入請求的資源的數量:" << endl;for (size_t i = 0; i < request.size(); i++){cin >> request[i];}result = banker.CheckRequest(pid, request);break;}case 0:exit(0);default:cout << "請輸入正確選項" << endl;continue;}if (result == true){cout << "資源分配成功, 系統此時安全" << endl;banker.printSecurity();}else{cout << "資源分配失敗，此時不安全" << endl;}} }int main() {test(); }

---

測試數據

這里的測試數據就拿教材上的一個習題

---

測試結果

可以看到，結果完全正確。

總結

以上是生活随笔為你收集整理的操作系统 ：银行家算法的实现（C++）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。