目的：
熟悉银行家算法，加深死锁有关概念的理解。
内容：
编制银行家算法通用程序，并检测思考题中所给状态的安全性。
要求：
- 下列状态是否安全？(三个进程共享12个同类资源)
进程 已分配资源数 最大需求数
1 1 4 (状态a)
2 4 4
3 5 8
1 1 4
2 4 6 (状态b)
3 6 8
- 考虑下列系统状态
分配矩阵 最大需求矩阵 可用资源矩阵
0 0 1 2 0 0 1 2 1 5 2 0
1 0 0 0 1 7 5 0
1 3 5 4 2 3 5 6
0 6 3 2 0 6 5 2
0 0 1 4 0 6 5 6
问系统是否安全？若安全就给出所有的安全序列。若进程2请求(0420)，可否立即分配？
#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
#include <cstdio>using namespace std;
#define N 500typedef vector<int> Vi;
Vi Available;//可利用资源向量
Vi Max[N];//最大需求矩阵
Vi Allocation[N];//分配矩阵
Vi Need[N];//每一个进程尚需的各类资源数 = Max-Allocationint n,m;
int k;
Vi Request;//进程k的请求向量void Out(const Vi t[N]) {for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++)cout << t[i][j] << " ";puts("");}
}void Out(Vi &t) {for (int It : t)cout << It << " ";puts("");
}void init() {cin >> n >> m; //n个进程，m种资源//输入一行可利用资源向量for (int i = 0,x; i < m; i++) {cin >> x;Available.emplace_back(x);}//输入n*m分配矩阵for (int i = 0; i < n; i++)for (int j = 0,x; j < m; j++) {cin >> x;Allocation[i].emplace_back(x);}//输入n*m最大需求矩阵for (int i = 0; i < n; i++)for (int j = 0,x; j < m; j++) {cin >> x;Max[i].emplace_back(x);}for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)Need[i].emplace_back(Max[i][j]-Allocation[i][j]);cin >> k;k = k-1; // 本程序进程编号从0开始for (int i = 0,x; i < m; i++) {cin >> x;Request.emplace_back(x);}puts("Need:");Out(Need);}void dfs(int t,Vi &Work,Vi &Finish,vector<Vi> &ans,Vi q) {//cout << "T:"<<t<<"\n";if (t == n) {ans.emplace_back(q);return;}for (int i = 0; i < n; i++)if (!Finish[i]) {bool ok = true;for (int j = 0; j < m; j++)if (Need[i][j] > Work[j]) ok = false;if (!ok) continue;for (int j = 0; j < m; j++) Work[j] += Allocation[i][j];q.emplace_back(i);Finish[i] = 1;dfs(t+1,Work,Finish,ans,q);Finish[i] = 0;q.pop_back();for (int j = 0; j < m; j++)Work[j] -= Allocation[i][j];}
}bool solve() {for (int i = 0; i < m; i++)if (Request[i] > Max[k][i]) {puts("所需要的资源数已超过它所宣布的最大值");return false;}for (int i = 0; i < m; i++)if (Request[i] > Available[i]) {puts("表示尚无足够资源");return false;}for (int i = 0; i < m; i++) {Available[i] -= Request[i];Allocation[k][i] += Request[i];Need[k][i] -= Request[i];}Vi Work(Available); //它表示系统可提供给进程继续运行所需的各类资源数目Vi Finish(n,0); //它表示系统是否有足够的资源分配给进程，使之运行完成vector<Vi> ans;//记录所有安全序列
//puts("Work"); Out(Work);
//puts("Finish"); Out(Finish);dfs(0,Work,Finish,ans,Vi());//安全测试if (ans.size()) {//输出所有安全序列printf("有%d个安全序列:\n",ans.size());for (auto Vet : ans) {for (int It : Vet)cout << It+1 << " ";puts("");}return true;}cout<<"不可分配";return false;
}int main() {init();solve();return 0;
}/*
第一题
3 121
4
54
4
81 0 //如果只是判断是否安全，相当于程序1申请0个资源两个安全序列
2 1 3
2 3 1
~~~~~~~~~~~~~~~~
3 111
4
64
6
81 0
不安全第二题5 41 5 2 00 0 1 2
1 0 0 0
1 3 5 4
0 6 3 2
0 0 1 40 0 1 2
1 7 5 0
2 3 5 6
0 6 5 2
0 6 5 61
0 0 0 0
安全2
0 4 2 0
进程2请求(0420)，可以立即分配
*/