死锁算法：银行家算法和安全性算法
借鉴了一些文章，自己总结了一下
银行家算法
首先，算法的核心在于，每次进程申请资源时，都会进行一次试探性分配，若成功，则真实分配。
基本思想：
- 在每个新进程进入系统时，他必须声明在运行过程中，可能需要的每种资源类型的最大单元数目（数目不超过系统拥有的资源总量）。
- 当进程请求一组资源时，系统必须首先在确定是否有足够的资源分配给该进程。
- 若有，在进一步计算将这些资源分配给进程后，是否会使系统处于不安全状态。如果处于安全状态，才将资源分配给他；否则，让进程等待。
银行家算法中的数据结构
为实现银行家算法，在系统中必须要有这样四个数据结构，分别用来描述系统中可利用的资源，所有进程对资源的最大需求，系统中的资源分配，以及所有进程还需要资源的情况。
可利用资源 Available：这是一个含有 m 个元素的数组，其中每一个元素代表一类可利用的资源情况。其初始值是系统所配置的全部可用资源的数目。 如果Available[j] = k，则表示系统中现有 Rj 类资源 k 个。
最大需求矩阵 Max：这是一个 nm 的矩阵。它定义了系统中 n 个进程每一个对 m 类资源的最大需求。如果Max[i,j] = K，则表示进程i需要 Rj 类资源的最大数目为 K。
分配矩阵 Allocation：这也是一个 nm 矩阵，它定义了系统中每一类资源当前已分配给每一类进程的资源。如果Allocation[i.j]= K，则表示进程 i 已分得 Rj 类资源的数目为 K。
需求矩阵 Need：当前所有进程还需要的资源
m 的矩阵，用来表示每一个进程尚需的各类资源数，如果Need[i,j]=K，则表示进程 i 还需要 K 个 Rj 类资源才能完成任务。
上述三个矩阵之间存在如下关系：Need[i, j] = Max[i, j] - Allocation[i, j]。
| 名称 |
|
|
| 可利用资源向量 |
int Available[m] |
m为资源种类 |
| 最大需求矩阵 |
int Max [n][m] |
n为进程的数量 |
| 分配矩阵 |
int Allocation[n][m] |
|
| 还需资源矩阵 |
int need[i][j]=Max[i][j]- Allocation[i][j] |
|
| 申请资源数量 |
int Request [m] |
会一直更新，暂存申请 |
| 工作向量 |
int Work[m] int Finish[n] |
|
算法步骤
1.初始化
2.进程申请资源
（1）数据装入Request
（2）输入合法性判断
如果合计申请超出了之前声明的最大，则报错。如果申请超过了目前可用，则阻塞。
3.试探性分配
for(int i=0;i<m;i++)
{
available[i] -= request[i];
allocation[index][i] += request[i];
need[index][i] -= request[i];
}
4.安全检验
调用安全性算法，如果当前状态时安全的，则正式进行分配。否则，回滚状态，阻塞该进程。
安全性算法
数据结构
工作向量 Work，它表示可以提供给进程继续运行所需要的各类的资源数目，它含有 m 个元素，在执行安全算法开始时，Work = Available；
Finish，它表示系统是否有足够的资源分配给进程，使之运行完成。开始先做Finish[i] = false。当有足够资源分配给进程时，再令 FInish[i] = false;
算法思想
a.从进程集合中找到一个满足下述条件的进程：
Finish[i] = false;
Need[i,j]<=Work[j];
如果找到执行步骤 b，否则执行步骤 c；
b.当进程 Pi 获得资源后，可顺利执行，直到完成，并释放它的资源。故应执行：
Work[j] = Work[j] + Allocation[i,j];
Finish[j] =true;
返回执行步骤 a
c.如果所有进程的 Finish[i] = true 都满足，则表示系统处于安全状态；否则，系统处于不安全状态。
更新：完全的实现代码
//
// Created by Zza on 2022/4/15.
//
#ifndef DATASTRUCTUREIMPLEMENTINGC_BANKERRESOURCEDISPATCH_H
#define DATASTRUCTUREIMPLEMENTINGC_BANKERRESOURCEDISPATCH_H
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
//#include <pthread.h>
// init count of resource type
#define M 3
// init count of process
#define N 2
typedef struct Condition{
int available[M];
// 可选的，主要是在开始的时候初始化用
int max[N][M];
int need[N][M];
int allocation[N][M];
volatile int request[M];
int cur;
int n;
int m;
} Condition, *pCond;
//int need[i][j] = Max[i][j]- Allocation[i][j]
#define ACT_TIMES 10
typedef struct Actions{
int processId;
int request[M];
}Actions, *acts;
// global var
//static Condition CurCond;
bool InitCond(pCond cond);
bool DisplayCurCond(pCond cond);
// Banker actions
bool UpdateCond(pCond, acts);
bool BankerEvaluate(pCond);
bool preAllocate(pCond);
bool RollBack(pCond);
bool Commit(pCond);
//======================================================================================================================
// safety method
typedef struct SafetyWork{
int work[M];
bool finished[N];
} sfWork;
bool SafetyCertification(pCond cond);
bool sfWorkInit(sfWork*, pCond);
bool FindAndAlloc(sfWork* jud, pCond cond);
bool EndPhaseJudge(sfWork* jud, pCond cond);
//======================================================================================================================
#ifndef MAIN_FUNC
#define MAIN_FUNC
void test_main(){
Condition cond;
InitCond(&cond);
cond.available[0] = 2;
cond.available[1] = 4;
cond.available[2] = 3;
Actions reqs[] = {
{0,{2,0,0}},
{1,{0,1,1}},
{1,{2,1,2}},
{1,{0,1,0}},
{-1,{2,1,0}},
};
acts req = reqs;
while (req->processId >= 0){
DisplayCurCond(&cond);
UpdateCond(&cond,req);
BankerEvaluate(&cond);
printf("---------\n");
req++;
}
}
#endif
//======================================================================================================================
bool InitCond(pCond cond){
cond->cur = 0;
cond->n = N;
cond->m = M;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
cond->allocation[i][j] = 0;
cond->max[i][j] = 2;
cond->need[i][j] = cond->max[i][j] - cond->allocation[i][j];
cond->available[j]+=cond->max[i][j];
}
}
// 数据初始化
return 1;
}
bool DisplayCurCond(pCond cond){
printf("avail: ");
for(int j=0;j<cond->m;j++){
printf("%d\t",cond->available[j]);
}
printf("\n");
return 1;
}
//======================================================================================================================
bool BankerEvaluate(pCond cond){
// 输入检验与预分配
if(!preAllocate(cond))return false;
// 预分配后安全性检验
if(SafetyCertification(cond)){
Commit(cond);
printf("allocation success!\n");
} else{
printf("unsafe request, refuse, alloc fail.\n");
RollBack(cond);
return false;
}
return true;
}
bool preAllocate(pCond cond){
// 申请检验
for(int i=0; i<cond->m; i++){
if(cond->available[i] < cond->request[i] // 是否有剩余的空间给予分配
||
cond->need[cond->cur][i] < cond->request[i]) // 判断是否是合法的申请
{
printf("invalid request, allocation fail\n");
return false;
}
}
// 预分配
for(int i=0; i<M; i++){
cond->allocation[cond->cur][i] += cond->request[i];
cond->need[cond->cur][i] -= cond->request[i];
}
return true;
}
bool UpdateCond(pCond cond, acts act){
cond->cur = act->processId;
printf("get request of %d:\n",act->processId);
for(int i=0; i<M; i++){
printf("%d\t",act->request[i]);
cond->request[i] = act->request[i];
}
printf("\n");
return 1;
}
bool RollBack(pCond cond){
for(int i=0; i<M; i++){
cond->allocation[cond->cur][i] -= cond->request[i];
cond->need[cond->cur][i] += cond->request[i];
}
return 1;
}
bool Commit(pCond cond){
for(int i=0; i<M; i++){
cond->available[i] -= cond->request[i];
}
return true;
}
//======================================================================================================================
// safety method
bool SafetyCertification(pCond cond){
sfWork jud;
sfWorkInit(&jud, cond);
// 首先是找到一个没有完成的进程，把资源全部分配给它
while (FindAndAlloc(&jud, cond));
return EndPhaseJudge(&jud,cond);
}
bool sfWorkInit(sfWork* jud, pCond cond){
for(int i=0;i<M;i++){
jud->work[i] = cond->available[i];
}
for(int i=0;i<cond->n;i++){
jud->finished[i] = false;
}
return 1;
}
bool FindAndAlloc(sfWork* jud, pCond cond){
for(int i=0, j; i<cond->n; i++){
if(!jud->finished[i]){
for(j=0; j<M && cond->need[i][j] < jud->work[j]; j++);
if(j == M){
for(j=0; j<M; j++) { jud->work[j] += cond->allocation[i][j]; }
jud->finished[i] = true;
return 1;
}
}
}
return 0;
}
bool EndPhaseJudge(sfWork* jud, pCond cond){
for(int i=0, j; i<cond->n; i++){
if(!jud->finished[i]){
return false;
}
}
return true;
}
#endif //DATASTRUCTUREIMPLEMENTINGC_BANKERRESOURCEDISPATCH_H
