写在前面

在这漫长的人生旅途中，我们总会遇到荆棘，难以逾越。有人选择放弃，有人忍痛前行。虽然两者并无高下之分，但我还是希望自己能够选择后者，无畏艰险，至死不渝。

银行家算法的模拟与实现

(1) 进一步理解进程的并发执行。
(2) 加强对进程死锁的理解，理解安全状态与不安全状态的概念。
(3) 掌握使用银行家算法避免死锁问题。

  1. 基本概念

    • 死锁：多个进程在执行过程中，因为竞争资源会造成相互等待的局面。如果没有外力作用，这些进程将永远无法向前推进。此时称系统处于死锁状态或者系统产生了死锁。
    • 安全序列：系统按某种顺序并发进程，并使它们都能达到获得最大资源而顺序完成的序列为安全序列。
    • 安全状态：能找到安全序列的状态称为安全状态，安全状态不会导致死锁。
    • 不安全状态：在当前状态下不存在安全序列，则系统处于不安全状态。

  2. 银行家算法

    银行家算法顾名思义是来源于银行的借贷业务，一定数量的本金要满足多个客户的借贷周转，为了防止银行家资金无法周转而倒闭，对每一笔贷款，必须考察其是否能限期归还。在操作系统中研究资源分配策略时也有类似问题，系统中有限的资源要供多个进程使用，必须保证得到的资源的进程能在有限的时间内归还资源，以供其它进程使用资源。如果资源分配不当，就会发生进程循环等待资源，则进程都无法继续执行下去的死锁现象。

  3. 当一进程提出资源申请时，银行家算法执行下列步骤以决定是否向其分配资源：
    1）检查该进程所需要的资源是否已超过它所宣布的最大值。
    2）检查系统当前是否有足够资源满足该进程的请求。
    3）系统试探着将资源分配给该进程，得到一个新状态。
    4）执行安全性算法，若该新状态是安全的，则分配完成；若新状态是不安全的，则恢复原状态，阻塞该进程。

  4. 本实验的内容是要通过编写和调试一个模拟系统动态分配资源的银行家算法程序，有效地避免死锁发生。具体要求如下：
    （1） 初始化时让系统拥有一定的资源；
    （2） 用键盘输入的方式允许进程动态申请资源；
    （3） 如果试探分配后系统处于安全状态，则修改系统的资源分配情况，正式分配资源；
    （4） 如果试探分配后系统处于不安全状态，则提示不能满足请求，恢复原状态并阻塞该进程。

数据结构

进程个数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. 设置两个工作向量
    Work 记录系统当前可用资源量，初值为Available;
    finish 记录所有进程是否已被执行, 初值为长度为n，值均为False的向量。
  2. 从进程集合中找到一个满足下述条件的进程，
    finish == False;
    Need <= Work;
    如找到，执行3；否则，执行4。
  3. 假设进程获得资源，可顺利执行，直至完成，从而释放资源。
    Work += Allocation;
    Finish=True;
    执行2
  4. 如所有的进程finish= True，则表示安全；否则系统不安全。

算法流程图

图1

具体设计

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

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;
}

实现完整源码

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
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
#include <stdio.h>
#include <malloc.h>

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

int n;  //进程数
int m;  //资源类数
int *Available; //可使用资源向量
int **Max;  //最大需求矩阵
int **Allocation;    //分配矩阵
int **Need; //需求矩阵
bool safe = False;
typedef struct
{
    int id;
    int *req_src;
}Request;
Request* new_request;

void initial();  
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);
void show(int *a, int len);


int main()
{
    initial();
    request();
    process();
    return 0;
}

void show(int *a, int len)
{
    int i = 0;
    while(i<len)
    {
        printf(" %d",*(a+i));
        i++;
    }
   printf("\n");
}
 

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++;
    } 
}

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;
}

效果如图所示：

效果