算法笔记—安全状态（银行家算法）、思考致富的博客-

题目描述

操作系统中，进程调度是一个非常重要的问题。每个进程都需要一定的资源才能顺利执行，进程执行过程中使用的资源在进程结束时都会释放。不同的资源分配策略会对系统的运行效率产生很大的影响，甚至可能导致死锁。

现某系统中现有n个进程和m种资源。每个进程开始时得到部分资源，但不足以使得进程顺利执行，还需要得到其它资源才能执行。已知该系统中各类可用资源的总量，给定已知的进程及其资源分配和需求情况，你能帮忙检查这些进程能够顺利执行吗？

输入数据：

输入数据有若干组，每组输入数据的第一行包含两个正整数n，m（0<n≤50000，0<m≤l00），表示当前系统中进程的总数和资源的种类。随后的m行中，每行有n个整数，为各个进程得到的资源数。之后的m行中，每行也有n个整数，表示进程还需要的资源数。之后的一行中包含m个整数，为系统中当前可用资源的数量。保证所有的整数值小于或等于10°。

输出数据：

对每组输入数据，在单独的行中输出结果。若所有进程均能顺利完成，输出Yes，否则输出No。

样例输入：

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

样例输出：

Yes No 

解题思路：
使用银行家算法来实现。
如果不太清楚银行家算法的具体过程，可以参考下面的链接。
操作系统—银行家算法

下面为实现代码：

/*  * @Description: 银行家算法  * @Author: sikaozhifu  * @Date: 2020-06-12 14:33:49  * @LastEditTime: 2020-06-12 15:41:03  * @LastEditors: Please set LastEditors  */ #include<iostream> #include<vector> #include<string> #include<algorithm> using namespace std; int n,m;//n 表示进程总数，m 表示资源种类数 //Max 表示最大需求数 //Allocation 表示已经分配的资源数 //Need 表示还需要分配的资源数 //表示系统可用的资源数 int **Max,**Allocation,**Need,*Available; //Work 动态存储当前Available的值 //Finish 表示当前进程是否为安全序列之一 int *Work,*Finish; vector<int> result; //判断是否为安全序列 bool check(){     Work = new int[m]; for(int i = 0;i < m;i++){         Work[i] = Available[i]; }     Finish = new int[n]; fill(Finish,Finish + n, 0); for(int k = 0;k < n;k++){//n 个进程需要遍历n次 for(int i = 0;i < n;i++){ if (Finish[i] == 0) { //判断需求数是否满足当前可用资源数 int count = 0; for(int j = 0;j < m;j++){ if(Need[i][j] <= Work[j]){                         count++; } } if(count == m){ //表示满足当前需求数 for(int j = 0;j < m;j++){ //更新当前的可用资源数                         Work[j] += Allocation[i][j]; }                     Finish[i] = 1;                     result.push_back(i); break; } } } } for(int i = 0;i < m;i++){ if(Finish[i] == 0){ return false; } } return true; } int main(){     cin >> n >> m;     Max = (int **)new int* [n];     Allocation = (int **)new int* [n];     Need = (int **)new int* [n]; for(int i = 0;i < n;i++){         Max[i] = new int[m];         Allocation[i] = new int[m];         Need[i] = new int[m]; }     Available = new int[m]; for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){             cin >> Allocation[j][i]; } } for(int i = 0;i < m;i++){ for(int j = 0;j < n;j++){             cin >> Need[j][i]; } } for(int i = 0;i < m; i++){         cin >> Available[i]; } if(check()){         cout << "Yes" << endl; }else{         cout << "No" << endl; } system("pause"); return 0; }