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

银行家算法是一种资源分配和避免死锁的算法，在执行 “s-state “检查以寻找潜在活动并确定是否应允许继续分配之前，模拟所有资源的预定最大可能量的资源分配。

为什么银行家的算法被称为

银行家的算法之所以有这样的标题，是因为它被运用于银行业，以确定是否授权向个人提供贷款。假设一家银行有n个账户持有人，每个人的个人余额为S。当有人要求贷款时，银行首先从其拥有的资金总额中扣除贷款金额，只有当余额超过S时才会批准贷款。之所以这样做，是因为如果每个账户持有人都来取钱，银行就能简单地做到。换句话说，银行绝不会以妨碍其满足所有客户要求的方式安排其资金。银行会努力在任何时候都保持安全。

银行家的算法是用以下数据结构实现的。

设n为系统中进程的数量，m为资源种类的数量。

可用的。

这个大小为’m’的1-d数组列出了当前可用的每一类资源的数量。
如果Available[j] = Rj，则有’k’个资源类型的实例。

最大。

系统中每个进程的最大需求由一个大小为’n*m’的二维数组指定。
如果Max[i, j] = k，则进程Pi最多可以请求’k’个资源类型Rj的实例。

分配。

当前分配给每个进程的每种资源的数量由一个大小为’n*m’的二维数组指定。
进程由Allocation[i, j] = k表示，Pi此时已经获得了’k’个资源类型的实例。Rj

需要。

每个进程的剩余资源需求显示在一个大小为’n*m’的二维数组中。
进程用Need[i, j] = k表示。现在，Pi需要 “k “个资源类型的实例。Rj
Allocation[i, j] – Maximum[i, j] = Need[i, j)

现在分配给进程Pi的资源由Allocationi标识，而进程Pi为了完成工作可能还需要的额外资源则由Needi标识。

安全算法和资源请求算法构成了银行家的算法。

安全的算法

以下是对确定系统是否处于安全状态的方法的描述。

1) 假设Work和Finish是两个向量，每个向量的长度为m和n。
初始化。Work = Available
当i=1, 2, 3, 4...n时，Finish[i]为假。
2) 找到一个I，使其同时 
a) Finish[i] = false 
b) Needi <= Work 
如果这样的I不存在，则转到步骤(4)
3) Work = Work + Allocation[i)
完成[i] = true 
转到第(2)步
4) 如果每一个i的Finish[i] = true
那么系统就处于安全状态。

资源请求的算法

让Requesti代表进程Pi的请求阵列。进程Pi请求K个资源类型Rj的实例，用Requesti [j] = k表示。当进程Pi提出资源请求时，会发生以下事情。

1) 如果Requesti >= Needi，则进入第2步；否则，报告一个错误条件，因为该过程提出的要求超过了它所能处理的范围。
2) 如果Requesti <= Accessible，则进入步骤（3）；否则，Pi将不得不等待，因为资源不可用。
3) 改变状态，使系统看起来已经给了Pi所需的资源。
请求-可用=可用
Allocationi = Allocationi + Requesti
Needi = Needi - Requesti

以下是银行家的算法的执行情况

// Banker's Algorithm
#include
int main()
{
    // P0 , P1 , P2 , P3 , P4 are the Process names here
    int n , m , i , j , k;
    n = 5; // Number of processes
    m = 3; // Number of resources
    int alloc[ 5 ] [ 3 ] = { { 0 , 1 , 0 }, // P0 // Allocation Matrix
                        { 2 , 0 , 0 } , // P1
                        { 3 , 0 , 2 } , // P2
                        { 2 , 1 , 1 } , // P3
                        { 0 , 0 , 2 } } ; // P4
    int max[ 5 ] [ 3 ] = { { 7 , 5 , 3 } , // P0 // MAX Matrix
                    { 3 , 2 , 2 } , // P1
                    { 9 , 0 , 2 } , // P2
                    { 2 , 2 , 2 } , // P3
                    { 4 , 3 , 3 } } ; // P4
    int avail[3] = { 3 , 3 , 2 } ; // Available Resources
    int f[n] , ans[n] , ind = 0 ;
    for (k = 0; k < n; k++) {
        f[k] = 0;
    }
    int need[n][m];
    for (i = 0; i < n; i++) {
        for (j = 0; j < m; j++)
            need[i][j] = max[i][j] - alloc[i][j] ;
    }
    int y = 0;
    for (k = 0; k < 5; k++){
        for (i = 0; i < n; i++){
            if (f[i] == 0){
                int flag = 0;
                for (j = 0; j < m; j++) {
                    if(need[i][j] > avail[j]){
                        flag = 1;
                        break;
                    }
                }
                if ( flag == 0 ) {
                    ans[ind++] = i;
                    for (y = 0; y < m; y++)
                        avail[y] += alloc[i][y] ;
                    f[i] = 1;
                }
            }
        }
    }
    int flag = 1; 
    for(int i=0;i " , ans[i]);
    printf(" P%d ", ans[n - 1]);
    }
    return(0);
}

输出

Following is the SAFE Sequence
 P1 -> P3 -> P4 -> P0 -> P2
........................................................
Process execute din 1.33 seconds
Press any key to continue.