死锁算法：银行家算法和安全性算法

借鉴了一些文章，自己总结了一下

银行家算法

首先，算法的核心在于，每次进程申请资源时，都会进行一次试探性分配，若成功，则真实分配。

基本思想：

• 在每个新进程进入系统时，他必须声明在运行过程中，可能需要的每种资源类型的最大单元数目（数目不超过系统拥有的资源总量）。
• 当进程请求一组资源时，系统必须首先在确定是否有足够的资源分配给该进程。
• 若有，在进一步计算将这些资源分配给进程后，是否会使系统处于不安全状态。如果处于安全状态，才将资源分配给他；否则，让进程等待。

银行家算法中的数据结构

为实现银行家算法，在系统中必须要有这样四个数据结构，分别用来描述系统中可利用的资源，所有进程对资源的最大需求，系统中的资源分配，以及所有进程还需要资源的情况。

可利用资源 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