Deadlock algorithm ： Banker algorithm and security algorithm

Learn from some articles , I have summed up

Banker Algorithm

First , The core of the algorithm is , Every time a process requests resources , There will be a tentative allocation , If successful , Then the real distribution .

The basic idea ：

• When each new process enters the system , He must declare that during the operation , The maximum number of units per resource type that may be required （ The number does not exceed the total resources owned by the system ）.
• When a process requests a set of resources , The system must first determine whether there are enough resources allocated to the process .
• If you have any , After further calculation, allocate these resources to the process , Whether the system will be in an unsafe state . If in a safe state , To allocate resources to him ; otherwise , Let the process wait .

The data structure in banker's algorithm

To implement the banker's algorithm , There must be four data structures in the system , They are used to describe Available resources in the system , all The greatest demand of the process for resources , Resource allocation in the system , as well as All processes also need resources .

Available resources Available： This is a containing m Array of elements , Each of these elements represents a kind of available resources . Its initial value is the number of all available resources configured by the system . If Available[j] = k, It means that there is Rj Class resources k individual .

Maximum demand matrix Max： This is a nm Matrix . It defines... In the system n Processes, each pair m The biggest demand of class resources . If Max[i,j] = K, It means process i need Rj The maximum number of class resources is K.

Distribution matrix Allocation： This is also a nm matrix , It defines the resources currently allocated to each type of process by each type of resource in the system . If Allocation[i.j]= K, It means process i Have been divided into Rj The number of class resources is K.

Demand matrix Need： All current processes still need resources

m Matrix , It is used to indicate the number of various resources required by each process , If Need[i,j]=K, It means process i It also needs to be K individual Rj Class resources can complete the task .

The relationship between the above three matrices is as follows ：Need[i, j] = Max[i, j] - Allocation[i, j].

name
Available resource vector	int Available[m]	m For resource types
Maximum demand matrix	int Max [n][m]	n For the number of processes
Distribution matrix	int Allocation[n][m]
We also need a resource matrix	int need[i][j]=Max[i][j]- Allocation[i][j]
Number of resources applied	int Request [m]	Will always update , Temporary storage application
Work vector	int Work[m] int Finish[n]

Algorithm steps

1. initialization

2. Process request resources

（1） Data loading Request

（2） Input legitimacy judgment

If the total application exceeds the previously stated maximum , False report . If the application exceeds the currently available , The block .

3. Exploratory distribution

for(int i=0;i<m;i++)
{
    
    available[i] -= request[i];
    allocation[index][i] += request[i];
    need[index][i] -= request[i];
}

4. Safety inspection

Call the security algorithm , If the current state is safe , Then it will be officially allocated . otherwise , Rollback state , Block the process .

Security algorithm

data structure

Work vector Work, It represents the number of resources that can be provided to the process to continue running , It contains m Elements , At the beginning of executing the security algorithm ,Work = Available;

Finish, It indicates whether the system has enough resources to allocate to the process , Make it work . Start with Finish[i] = false. When there are enough resources allocated to the process , Re order FInish[i] = false;

Algorithmic thought

a. Find a process from the process collection that meets the following conditions ：

Finish[i] = false;
Need[i,j]<=Work[j];
 If you find the execution step  b, Otherwise, carry out the steps  c;

b. When a process Pi After obtaining resources , Can be executed smoothly , Until completion , And release its resources . So it should be carried out ：

Work[j] = Work[j] + Allocation[i,j];
Finish[j] =true;
 Return to the execution step  a

c. If all processes are Finish[i] = true All satisfied with , It means that the system is in a safe state ; otherwise , The system is in an unsafe state .

to update ： Complete implementation code

//
// 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];
//  Optional , It is mainly used for initialization at the beginning 
    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];
        }
    }
//  Data initialization 
    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){
    
//  Input inspection and pre allocation 
    if(!preAllocate(cond))return false;

//  Safety inspection after pre distribution 
    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){
    
    //  Apply for inspection 
    for(int i=0; i<cond->m; i++){
    
        if(cond->available[i] < cond->request[i] //  Is there any space left to allocate 
           ||
           cond->need[cond->cur][i] < cond->request[i]) //  Judge whether it is a legal application 
        {
    
            printf("invalid request, allocation fail\n");
            return false;
        }
    }
    //  Pre allocation 
    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);
//  The first is to find an unfinished process , Allocate all resources to it 
    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