7-1 银行家算法 -- 安全性检查 (20 分)(思路 + 详解 + 知识分析) 宝 你今天 AC 了吗

停更一周了，在这一周里，我每时每刻都在 想这我这 29 个粉丝，庆幸教师资格证终于结束了，贴心杰又可以天天更新博客了

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈，I am come back;

[](()二：题目：

====================================================================

输入 N 个进程(N<=100)，以及 M 类资源（M<=100），初始化各种资源的总数，T0 时刻资源的分配情况。判断 T0 时刻是否安全。例如： 假定系统中有 5 个进程{P0，P1，P2，P3，P4}和三类资源{A,B,C}，各种资源的数量分别为 10、5、7，在 T0 时刻的资源分配图如下：

输入格式:

第一行输入进程数量 N，第二行输入资源类数 M，第三行输入 M 类资源个类资源的总数，以下 N 行分别输入每个进程的名字，该进程对 M 类资源的最大需求以及已分配资源。

输出格式:

输出 T0 时刻系统的状态。若安全，输出“找到安全序列，处于安全状态。”否则，输出“找不到安全序列，处于不安全状态。”

输入样例:

在这里给出一组输入。例如：

5

3

10 5 7

P0 7 5 3 0 1 0

P1 3 2 2 2 0 0

P2 9 0 2 3 0 2

P3 2 2 2 2 1 1

P4 4 3 2 0 0 2

输出样例:

在这里给出相应的输出。例如：

name max allocation need available

P0 7 5 3 | 0 1 0 | 7 4 3 | 3 3 2

P1 3 2 2 | 2 0 0 | 1 2 2 |

P2 9 0 2 | 3 0 2 | 6 0 0 |

P3 2 2 2 | 2 1 1 | 0 1 1 |

P4 4 3 2 | 0 0 2 | 4 3 0 |

找到安全序列，处于安全状态。

[](()三：思路

===================================================================

思路:

1.首先我们进行安全性算法是为了预防死锁，再解释一下死锁 比如

1>:在系统中有两个进程 p1,p2 和两个资源 r1(扫描仪)，r2(刻录机)

p1 和 p2 都需要将扫描的文档通过刻录机刻录到 CD 盘上，

2>:进程 p1 先请求资源 r1 成功，进程 p2 请求资源 r2 成功，那么接下来，

p1 又申请了 r2 资源 p2 申请了 r1 资源，那么此时 p1 和 p2 都在等对方

释放资源那么就会发生死锁，两个进程都无法进行下去

2.那么安全性算法就是使系统在分配资源时候一直处在安全的状态（即不会发生死锁）

那么我们在分配资源的时候就有了算法，即最终分配给各个进程的资源，都不会影响到

整个系统的安全状态，这时会出现一个进程的执行序列

3.具体解释算法过程

1>:几个变量

Max:一个进程所需的最大资源量

Allocation:系统已经给其分配了多少资源

Need:这个进程还需要多少资源

Available:这个系统还剩多少资源

2>:刚开始设置 work = Available 将所有进程设置为 finish = false （相当于定义一个 flag）

3>:找一个进程满足下列的条件

finish = false

need <= work(需要的资源得比系统剩余的要少)

4>:如果 3>的条件满足的话，我们就需要

将 work += Allocation （每个进程执行完后需要释放资源）

finish = true (代表该进程完成)

返回步骤 3>继续寻找满足上诉条件的进程

5>:思考如何判定此时的系统状态是安全还是不安全的

安全:如果 3>的条件不满足 即此时的所有进程的 finsh = true 说明了所有的进程已经完成

不安全: 我们已经判断了所有的 finish = false 的进程，但是仍未找到满足条件的

need < work 那么可以判定此状态为 不安全的状态

4.处理数据

1>:这里我们选取的数据结构是结构体数组因为一个进程他对应好多属性，所以选取的是结构体

在结构体的属性当中 我们设置一个 max[] 和 allocation[] 目的是存放多个不同类型资源

2>:关于 node[i].a[j],node[i].b[j],node[i].c[j]的理解，就是 3 个二维数组 就是这样的

[](()四：先说坑

====================================================================

1.这个题无语了简直了真是，不，应该是 PTA 这个平台让我真的无语了，我定义了一个变量 cnt 但我并未初始化为 0 ，我在 DEV-C 中测试了好多数据其实也无妨正确结果，但是在 PTA 中提交一直显示答案错误，而且测试样例一直输出 找不到安全序列，真的一上午我真的想砸电脑，什么呀！！ 最后坚持不懈，不信邪，终于让我发现一个大毛病，原来在 PTA 上变量必须初始化，否则系统自动给你赋值一个很大数 ，但在 DEV-C 上却没有任何问题

2.这个题还需要的是无论 是否可以得到安全序列，其都必须将其系统中各个进程的状态输出来

[](()五：上码

===================================================================

/**

思路:1.首先我们进行安全性算法是为了预防死锁，再解释一下死锁 比如

1>:在系统中有两个进程 p1,p2 和两个资源 r1(扫描仪)，r2(刻录机)

p1 和 p2 都需要将扫描的文档通过刻录机刻录到 CD 盘上，

2>:进程 p1 先请求资源 r1 成功，进程 p2 请求资源 r2 成功，那么接下来，

p1 又申请了 r2 资源 p2 申请了 r1 资源，那么此时 p1 和 p2 都在等对方

释放资源那么就会发生死锁，两个进程都无法进行下去

2.那么安全性算法就是使系统在分配资源时候一直处在安全的状态（即不会发生死锁）

那么我们在分配资源的时候就有了算法，即最终分配给各个进程的资源，都不会影响到

整个系统的安全状态，这时会出现一个进程的执行序列

3.具体解释算法过程

1>:几个变量

Max:一个进程所需的最大资源量

Allocation:系统已经给其分配了多少资源

Need:这个进程还需要多少资源

Available:这个系统还剩多少资源

2>:刚开始设置 work = Available 将所有进程设置为 finish = false （相当于定义一个 flag）

3>:找一个进程满足下列的条件

finish = false

need <= work(需要的资源得比系统剩余的要少)

4>:如果 3>的条件满足的话，我们就需要

将 work += Allocation （每个进程执行完后需要释放资源）

finish = true (代表该进程完成)

返回步骤 3>继续寻找满足上诉条件的进程

5>:思考如何判定此时的系统状态是安全还是不安全的

安全:如果 3>的条件不满足 即此时的所有进程的 finsh = true 说明了所有的进程已经完成

不安全: 我们已经判断了所有的 finish = false 的进程，但是仍未找到满足条件的

need < work 那么可以判定此状态为 不安全的状态

，否则

那么就是说明该系统处在不安全的状态（即会发生死锁）

4.处理数据

1>:这里我们选取的数据结构是结构体数组因为一个进程他对应好多属性，所以选取的是结构体

在结构体的属性当中 我们设置一个 max[] 和 allocation[] 目的是存放多个不同类型资源

2>:关于 node[i].a[j],node[i].b[j],node[i].c[j]的理解，就是 3 个二维数组 就是这样的

*/

#include<bits/stdc++.h>

using namespace std;

struct Node{

string processName;//进程名

int a[100];//Max

int b[100];//allocation

int c[100];//need

bool finish;

}node[1000];

//关于重写 sort 方法中的两个参数 都表示是一个结构体（即我们需要用两个结构体当中的数据进行比较）

bool sort_c(Node node1,Node node2){

return node1.c[0] < node2.c[0];

}

int main(){

int N,M;

int cnt = 0;//用于记进程完成的个数

vector<int>v1;//存总的资源总量

vector<int>v2;//存 need 需要的资源

vector<int>v3;//记录最后需要输出的 Available

cin >> N >> M;

for(int i = 0; i < M; i++){

int resources;

cin >> resources;

v1.push_back(resources);

}

for(int i = 0; i < N; i++){

cin >> node[i].processName;

//输入 Max

for(int j = 0; j < M; j++){

cin >> node[i].a[j];

}

//输入 allocation

for(int j = 0; j < M; j++){

cin >> node[i].b[j];

v1[j] -= node[i].b[j];//这里是每次减去分配的资源 那么剩下的最后就是 available

}

//求取 need

for( 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 int j = 0; j < M; j++){

node[i].c[j] = node[i].a[j] - node[i].b[j];

}

node[i].finish = false;//将每个进程初始状态设为 false

}

for(int i = 0; i < M; i++){

v3.push_back(v1[i]);

}

// sort(node,node+N,sort_c);

//算法核心部分

for(int i = 0; i < N; i++){

int count = 0;

for(int j = 0; j < M; j++){

if(node[i].c[j] <= v1[j]){

count++;

}else{

break;//只要有一个不合适就 break 出去

}

}