银行家算法 C++描述

银行家算法 C++描述

银行家算法 C++描述

银行家算法

操作系统——银行家算法

实现代码

main.cpp

#include "BankerAlgorithm.h"int main() {int n, m;scanf("%d%d", &n, &m);vector<vector<int> > max(n, vector<int>(m));vector<vector<int> > allocation(n, vector<int>(m));vector<int> available(m);for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {scanf("%d", &max[i][j]);}}for (int i = 0; i < n; ++i) {for (int j = 0; j < m; ++j) {scanf("%d", &allocation[i][j]);}}for (int i = 0; i < m; ++i) {scanf("%d", &available[i]);}BankerAlgorithm bankerAlgorithm(max, allocation, available);int process;while (~scanf("%d", &process) && process >= 0) {vector<int> request(m);for (int i = 0; i < request.size(); ++i) {scanf("%d", &request[i]);}bankerAlgorithm.request(process, request);}return 0;
}

BankerAlgorithm.h

#include <bits/stdc++.h>
using namespace std;
#ifndef BANKERALGORITHM_BANKERALGORITHM_H
#define BANKERALGORITHM_BANKERALGORITHM_Hclass BankerAlgorithm {
private:vector<vector<int> > max;vector<vector<int> > allocation;vector<vector<int> > need;vector<int> available;vector<bool> finished;vector<int> safeSequence;vector<int> allocate(vector<int> systemResources, vector<int> neededResources);vector<int> release(vector<int> systemResources, vector<int> releaseResources);bool finish(vector<int>& needResources);bool allFinish();bool isAvailable(vector<int>& requestResources);bool safeStatusCheck();
public:BankerAlgorithm(vector<vector<int> > max, vector<vector<int> > allocation, vector<int> available);void request(int process, vector<int> requestResources);
};#endif //BANKERALGORITHM_BANKERALGORITHM_H

BankerAlgorithm.cpp

#include "BankerAlgorithm.h"vector<int> BankerAlgorithm::allocate(vector<int> systemResources, vector<int> neededResources) {for (int i = 0; i < systemResources.size(); ++i) {systemResources[i] -= neededResources[i];}return systemResources;
}vector<int> BankerAlgorithm::release(vector<int> systemResources, vector<int> releaseResources) {for (int i = 0; i < systemResources.size(); ++i) {systemResources[i] += releaseResources[i];}return systemResources;
}BankerAlgorithm::BankerAlgorithm(vector<vector<int> > max, vector<vector<int> > allocation, vector<int> available) {this->max = max;this->allocation = allocation;this->need.resize(max.size());this->finished.resize(max[0].size());this->available.resize(available.size());for (int i = 0; i < max.size(); ++i) {this->need[i] = allocate(max[i], allocation[i]);}for (int i = 0; i < finished.size(); ++i) {finished[i] = false;}for (int i = 0; i < finished.size(); ++i) {this->available[i] = available[i];}}bool BankerAlgorithm::isAvailable(vector<int>& requestResources) {for (int i = 0; i < available.size(); ++i) {if (available[i] < requestResources[i]) {return false;}}return true;
}void BankerAlgorithm::request(int process, vector<int> requestResources) {if (!isAvailable(requestResources)) {printf("Available resource is not enough, rejected allocation request!\n");return;}available = allocate(available, requestResources);allocation[process] = release(allocation[process], requestResources);need[process] = allocate(need[process], requestResources);if (safeStatusCheck()) {printf("Allocation succeed!\n");} else {printf("Entering unsafe status, rejected allocation request!\n");}
}bool BankerAlgorithm::safeStatusCheck() {int count = 0;for (int i = 0; i < need.size(); ++i) {count += isAvailable(need[i]) ? 0 : 1;}if (count == available.size()) {return false;}bool safe = false;for (int i = 0; i < need.size() && !safe; ++i) {if (isAvailable(need[i]) && !finished[i]) {available = release(available, allocation[i]);finished[i] = true;safeSequence.push_back(i);if (allFinish()) {safe = true;printf("Safe Sequence: \n");for (int j = 0; j < safeSequence.size(); ++j) {printf("P%d ", safeSequence[j]);}printf("\n");} else {safe = safeStatusCheck();}safeSequence.pop_back();finished[i] = false;available = allocate(available, allocation[i]);}}return safe;
}bool BankerAlgorithm::finish(vector<int>& needResources) {for (int i = 0; i < needResources.size(); ++i) {if (needResources[i] == 0) {return false;}}return true;
}bool BankerAlgorithm::allFinish() {for (int i = 0; i < finished.size(); ++i) {if (!finished[i]) {return false;}}return true;
}

测试数据

4 4
0 0 1 2
1 7 5 0
2 3 5 6
0 6 5 6
0 0 1 2
1 0 0 0
1 3 5 4
0 0 1 4
1 5 2 0
1
0 4 2 0

测试结果

Safe Sequence:
P0 P2 P1 P3
Allocation succeed!

最后

• 由于博主水平有限，不免有疏漏之处，欢迎读者随时批评指正，以免造成不必要的误解！