在C语言中使用银行家算法预防死锁

什么是死锁

死锁是指在一个并发系统中，两个或以上的线程互相等待对方的资源而无限制地等待下去，使得进程无法继续运行而陷入一种“死循环”，形成死锁。

银行家算法

银行家算法是一种避免死锁的算法。它通过动态地分配资源，避免进程因竞争资源而发生死锁，并保证分配的资源不会导致系统不安全。

银行家算法的实现需要考虑以下信息：

• Available：当前可用的资源数目。
• Max：系统中每种资源的最大需求量。
• Allocation：系统中每种资源当前已分配的数量。
• Need：系统中每种资源还需要的数量。

死锁避免的步骤

使用银行家算法避免死锁可以分为以下步骤：

1. 初始化资源可用数量 Available，系统的所有进程以及它们的资源需求量 Max 和已分配资源数量 Allocation。
2. 检查系统是否处于安全状态，也就是系统是否有足够的资源满足后续进程的请求。如果是，则接受请求并更新资源分配情况；否则，拒绝请求，等待其他进程释放资源。
3. 继续进行死锁预防工作。每当分配或释放资源时，都要重新计算实际可用资源和各个进程还需要的资源数量，并尝试将之前因拒绝请求而被阻塞的进程重新考虑分配资源。

示例1：使用银行家算法避免死锁

假设系统中有5个进程，申请资源的顺序为 P1、P2、P3、P4、P5。分别显示它们对三类资源的最大需求量 Max 和已分配资源数量 Allocation 如下表所示。

进程	Allocation	Max	Need
P1	1 1 0	2 1 1	1 0 1 (Max-Allo)
P2	1 0 1	2 1 2	1 1 1
P3	1 0 0	1 2 0	0 2 0
P4	0 0 1	3 0 0	3 0 2
P5	0 0 1	2 0 1	2 0 0

此时可用资源数量 Available 为 1 2 0。

假设现在进程 P4 申请 1 0 0 资源，判断如下：

1. 检查系统是否处于安全状态，此时 Available 与 Need 比较结果如下：

进程	Need	Available	Work	Finish
P1	1 0 1	0 2 0	0 0 0	No
P2	1 1 0
P3	0 2 0
P4	3 0 2
P5	2 0 0

则 P2 或 P3 可以被分配资源，我们选择 P2，分配资源后，状态如下：

进程	Allocation	Need	Available	Work	Finish
P1	1 0 1	1 0 0	0 1 0	1 0 0	No
P2	1 1 1	1 0 1	1 1 0	0 1 0	Yes
P3	1 0 0	0 2 0	1 2 1	0 0 0	No
P4	0 0 1	3 0 1	1 2 1	0 0 1	No
P5	0 0 1	2 0 0	1 2 2	0 0 0	No

1. P4 的申请可以被满足，并更新 Allocation 和 Available 信息，状态如下：

进程	Allocation	Max	Need
P1	1 0 1	2 1 1	1 1 0
P2	1 1 1	2 1 2	1 0 1
P3	1 0 0	1 2 0	0 2 0
P4	0 0 2	3 0 0	3 0 0
P5	0 0 1	2 0 1	2 0 0
	1 1 4	10 5 8	5 3 9 (Max-Allo)

1. 继续进行死锁预防工作，更新各个进程需要的资源数量，状态如下：

进程	Allocation	Max	Need
P1	1 0 1	2 1 1	1 1 0
P2	1 1 1	2 1 2	1 0 1
P3	1 0 0	1 2 0	0 2 0
P4	0 0 2	3 0 0	3 0 0
P5	0 0 1	2 0 1	2 0 0

示例2：配合源代码使用银行家算法避免死锁

下面是一个基于 C 语言的简单死锁避免示例代码，使用了银行家算法的思想。它让两个线程按不同的顺序执行，增加了产生死锁的概率，验证了死锁验证的正确性。

#include<stdio.h>
#include<stdlib.h>

int available[10],max[10][10],allocation[10][10],need[10][10],flag[10],work[10];
int num_process,num_res;

int input_data() {
    int i,j;
    printf("Enter the number of processes: ");
    scanf("%d",&num_process);
    printf("Enter the number of types of resources: ");
    scanf("%d",&num_res);
    for(i=1;i<=num_process;i++){
        printf("Enter the allocation of process %d: ",i);
        for(j=1;j<=num_res;j++){
            scanf("%d",&allocation[i][j]);
        }
        flag[i]=0;
    }
    printf("\n");
    for(i=1;i<=num_process;i++){
        printf("\nEnter the Max Matrix for process %d : ",i);
        for(j=1;j<=num_res;j++){
            scanf("%d",&max[i][j]);
        }
    }
    printf("\n");
    printf("\nEnter the Available Resources : ");
    for(i=1;i<=num_res;i++){
        scanf("%d",&available[i]);
        work[i]=available[i];
    }
    printf("\n");
    return 0;
}

void calculate_need(){
    int i,j;
    for(i=1;i<=num_process;i++){
        for(j=1;j<=num_res;j++){
            need[i][j]=max[i][j]-allocation[i][j];
        }
    }
}

int check_availability(int j){
    int i;
    for(i=1;i<=num_res;i++){
        if (need[j][i]>work[i]){
            return 0;
        }
    }
    return 1;
}

int wait_or_exit(){
    int i,j,found,flag;
    for(i=1;i<=num_process;i++){
        if(flag[i]==0 && check_availability(i)){
            flag[i]=1;
            for(j=1;j<=num_res;j++){
                work[j]=work[j]+allocation[i][j];
            }
            break;
        }
    }
    if(i>num_process){
        return 0;
    }
    else{
        return 1;
    }
}

void detect_deadlock(){
    int i,j,found,flag;
    calculate_need();
    int process_allocated = 0;
    while(process_allocated<num_process){
        found = 0;
        for(i=1;i<=num_process;i++){
            if(flag[i]==0 && check_availability(i)){
                flag[i]=1;
                found = 1;
                printf("\nProcess %d is allocated resources ",i);
                for(j=1;j<=num_res;j++){
                    work[j]=work[j]+allocation[i][j];
                }
                process_allocated++;
            }
        }
        if(found==0){
            printf("\nSystem is not in safe state\n");
            return;
        }
    }
    printf("\nSystem is in safe state\n");
}

int main(){
    input_data();
    detect_deadlock();
    return 0;
}

这个代码输入了最大需求量、当前已分配数量和可用资源数量。它先计算出需要的资源数量，然后检查系统是否处于安全状态。如果不是，就需要等待其他资源释放。