银行家算法（C语言实现）

发表于 | 分类于

简介

银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格·迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。

算法实现

数据结构

进程个数n
资源类数m
可利用资源向量Available
含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。如果Available[j]=K，则表示系统中现有Rj类资源K个。
最大需求矩阵Max
n×m的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。如果Max[i,j]=K，则表示进程i需要Rj类资源的最大数目为K。
分配矩阵Allocation
n×m的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。如果Allocation[i,j]=K，则表示进程i当前已分得Rj类资源的 数目为K。
需求矩阵Need
n×m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K，则表示进程i还需要Rj类资源K个，方能完成其任务。
Need[i,j]=Max[i,j]-Allocation[i,j]

算法原理

我们可以把操作系统看作是银行家，操作系统管理的资源相当于银行家管理的资金，进程向操作系统请求分配资源相当于用户向银行家贷款。
为保证资金的安全，银行家规定：
(1) 当一个顾客对资金的最大需求量不超过银行家现有的资金时就可接纳该顾客；
(2) 顾客可以分期贷款，但贷款的总数不能超过最大需求量；
(3) 当银行家现有的资金不能满足顾客尚需的贷款数额时，对顾客的贷款可推迟支付，但总能使顾客在有限的时间里得到贷款；
(4) 当顾客得到所需的全部资金后，一定能在有限的时间里归还所有的资金.
操作系统按照银行家制定的规则为进程分配资源，当进程首次申请资源时，要测试该进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量则按当前的申请量分配资源，否则就推迟分配。当进程在执行中继续申请资源时，先测试该进程本次申请的资源数是否超过了该资源所剩余的总量。若超过则拒绝分配资源，若能满足则按当前的申请量分配资源。

算法实现

初始化
由用户输入数据，分别对可利用资源向量矩阵AVAILABLE、最大需求矩阵MAX、分配矩阵ALLOCATION、需求矩阵NEED赋值。
银行家算法
在避免死锁的方法中，所施加的限制条件较弱，有可能获得令人满意的系统性能。在该方法中把系统的状态分为安全状态和不安全状态，只要能使系统始终都处于安全状态，便可以避免发生死锁。
银行家算法的基本思想是分配资源之前，判断系统是否是安全的；若是，才分配。它是最具有代表性的避免死锁的算法。
设编号为ID的进程提出请求new_request，定义（关于向量比较、运算的定义，代码实现部分给出，这里不再赘述）：
i=new_request->id为该进程的编号，
new_request->req_src为该进程此次所请求的资源向量，
则银行家算法按如下规则进行判断：
1.如果new_request->req_src <= Need[i] 则转2；否则，出错。
2..如果new_request->req_src <= Available[i]，则转3；否则，等待。
3.系统试探分配资源，修改相关数据：
Available[i] -= new_request->req_src ;
Allocation[i] += new_request->req_src;
Need[i] -= new_request->req_src;
4.系统执行安全性检查，如安全，则分配成立；否则试探险性分配作废，系统恢复原状，进程等待。
安全性检查算法
1.设置两个工作向量
Work 记录系统当前可用资源量，初值为Available;
finish 记录所有进程是否已被执行, 初值为长度为n，值均为False的向量。
2.从进程集合中找到一个满足下述条件的进程，
finish == False;
Need <= Work;
如找到，执行3；否则，执行4。
3.假设进程获得资源，可顺利执行，直至完成，从而释放资源。
Work += Allocation;
Finish=True;
执行2
4.如所有的进程finish= True，则表示安全；否则系统不安全。

代码实现（C语言）

首先，将需要的变量定义为全局变量

1
2
3
4
5
6
7
8
9
10
11
12
13
int n;  //进程数
int m;  //资源类数
int *Available; //可使用资源向量
int **Max;  //最大需求矩阵
int **Allocation;    //分配矩阵
int **Need; //需求矩阵
bool safe = False;
typedef struct
{
    int id;  //进程ID
    int *req_src;  //进程此次申请资源
}Request;
Request* new_request;

如上，用到了Bool型变量，因此要定义

1
2
3
#define True 1
#define False 0
typedef int bool;

下面列出了我们将要写的函数：

1
2
3
4
5
6
7
8
void initial();            //初始化n,m,Available等的函数  
void request();		//提出请求
void process();			//处理
bool safe_detect();		//安全性检测
/*向量运算函数*/
bool vector_compare(int *a, int *b, int len);		  
void vector_add(int *a, int *b, int len);
void vector_sub(int *a, int *b, int len);

首先给出几个向量运算函数的定义：
定义a和b为两个等长向量,
a >= b 表示 a 中的每个元素都大于相应位置上的 b 的元素；
a += b 表示 a 中的每个元素增加相应位置上的 b 的元素的值；
a -= b 表示 a 中的每个元素都大于相应位置上的 b 的元素的值；
例：
a = [1,2,3];
b = [1,1,1];
则
a >= b;
a += b; //a=[2,3,4]
a -= b; //a=[0,1,2]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
bool vector_compare(int *a, int *b, int len)    // If vector a >= vector b, return True
{
    int i = 0;
    while(i<len)
    {
        if(*(a+i)<*(b+i))
            return False;
        i++;
    }
    return True;
}
void vector_add(int *a, int *b, int len) //vector a += vector b
{
    int i = 0;
    while(i<len)
    {
        *(a+i) += *(b+i);
        i++;
    } 
}
void vector_sub(int *a, int *b, int len) //vector a -= vector b
{
    int i = 0;
    while(i<len)
    {
        *(a+i) -= *(b+i);
        i++;
    } 
}

下面按算法步骤给出 initial(), request(), process(), safe_request()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
void initial()
{
    int i;
    int j;
    printf("请输入进程数:\n");
    scanf("%d",&n);
    printf("请输入资源类数:\n");
    scanf("%d",&m);    
    printf("请输入可使用资源向量:\n");
    Available = (int*)malloc(sizeof(int)*m);
    for(i=0; i<m; i++)
        scanf("%d",&Available[i]);
    printf("请输入最大需求矩阵:\n");
    Max = (int**)malloc(sizeof(int*)*n);
    for(i=0; i<n; i++)
    {
        Max[i] = (int*)malloc(sizeof(int)*m);
        for(j=0; j<m; j++)
            scanf("%d",&Max[i][j]);
    }
    printf("请输入分配矩阵:\n");
    Allocation = (int**)malloc(sizeof(int*)*n);
    for(i=0; i<n; i++)
    {
        Allocation[i] = (int*)malloc(sizeof(int)*m);
        for(j=0; j<m; j++)
            scanf("%d",&Allocation[i][j]);
    }
    Need = (int**)malloc(sizeof(int*)*n);
    for(i=0;i<n;i++)
    {
        Need[i] = (int *)malloc(sizeof(int)*m);
        for(j=0;j<m;j++)
            Need[i][j] = Max[i][j] - Allocation[i][j];
    }
}
void request()
{
    int i,id;
    new_request = (Request*)malloc(sizeof(Request));
    new_request->req_src = (int*)malloc(sizeof(int)*m);
    printf("请输入进程的ID\n");
    scanf("%d",&id);
    new_request->id = id - 1;
    printf("请输入进程申请资源向量\n");
    for(i=0; i<m; i++)
        scanf("%d",&new_request->req_src[i]);
}
void process()
{
    int i = new_request->id;
    if(vector_compare(Need[i],new_request->req_src,m))
        {
            if(vector_compare(Available,new_request->req_src,m))
            {
                vector_sub(Available,new_request->req_src,m);
                vector_add(Allocation[i],new_request->req_src,m);
                vector_sub(Need[i],new_request->req_src,m);
                safe_detect();
            }
            else
            {
                printf("程序所申请资源大于系统当前所剩资源，推迟执行!\n");  
                return;
            }
                              
        }
    else
    {
        printf("程序所申请资源大于该程序所需资源，无法执行!\n"); 
        return;
    }    
    if(safe)
    {
        printf("系统安全,进程可以执行!\n");
        return;
    }
    else
    {
        printf("系统不安全,进程无法执行!\n");
        vector_add(Available,new_request->req_src,m);
        vector_sub(Allocation[i],new_request->req_src,m);
        vector_add(Need[i],new_request->req_src,m);
        return;
    }
        
}
bool safe_detect()
{
    int *work = Available;
    bool *finish = (bool*)malloc(sizeof(bool)*n);
    int i;
    //初始化finish
    for(i=0; i<n; i++)
        finish[i] = False;
    
    for(i=0; i<n; i++)
    {
        if(finish[i]==False&&vector_compare(work,Need[i],m))
        {
            printf("尝试执行第%d进程\n",i+1);
            vector_add(work,Allocation[i],m);   //尝试执行该进程，释放资源
            finish[i] = True;
            i = -1;  //尝试分配后，从头查找是否还有可以执行的进程，考虑到i++，故此处为-1
        }
    }
    
    for(i=0; i<n; i++)
        if(finish[i]==False)
            break;
    if(i==n)
        safe = True;
    else
        safe = False;
}

最后

完整源码见这里