银行家算法

缘起

日常膜一下我们伟大的dijkstra先生~

银行家算法是著名的操作系统资源分配算法. 由图灵奖得主dijkstra先生在1965年为T.H.E系统设计的一种避免死锁产生的算法。死锁是什么?（好吧，只是为了科普~）

分析

既然银行家算法是为了避免操作系统为进程分配资源产生死锁而设计的算法(这是银行家算法的背景)，那么自然需要讲清楚什么是死锁. 死锁通俗来讲就是

1
2
3
4
你和妈妈陷入了僵局...
你:		"妈妈, 你不开电视让我看动画片, 我就不吃饭, 哼!"
妈妈:		"气死我了, 如果你不吃饭, 我就不给你开电视看动画片!"
结果是: 饭也没吃成，动画片也没看成（挨顿打是另话）

根据上面对死锁的描述，我们知道了死锁的几个必要条件

  1. 互斥条件

    每个资源只能一个进程占用. 不能两个进程同时使用该资源. 显然啊, 如果一个资源不是互斥的话，则死锁显然是不会在该资源上发生的.

  2. 请求和保持条件

    指进程已经保持至少一个资源，但又提出了新的资源请求，而该资源已被其它进程占有，此时请求进程 阻塞，但又对自己已获得的其它资源保持不放。

  3. 不剥夺条件

    指进程已获得的资源，在未使用完之前，不能被剥夺，只能在使用完时由自己释放。

  4. 环路等待条件

    指在发生死锁时，必然存在一个进程——资源的环形链，即进程集合{P1，P2，P3，···，Pn}中的P1正在等待一个P2占用的资源；P2正在等待P3占用的资源，……，Pn正在等待已被P1占用的资源。上面举的你和妈妈的例子中n=2

因为如果有死锁发生，那么上述四个条件必然成立. 所以运用数学中的逆否命题，你就知道该怎么尽可能避免死锁——即尽可能的使上面的四个条件不成立.

那么，银行家算法和死锁有什么关系呢? 银行家算法应对操作系统（银行你就理解为操作系统，客户你就理解为进程，客户申请贷款理解为进程向操作系统申请资源（可能是内存，可能是CPU时间片，可能是文件句柄,可能是套接字），客户申请贷款银行未必一次性给够，可能分期给你，同样，操作系统也未必进程来要多少就立马给多少，而可能是分批次给进程）.

回归正题——操作系统分配资源的时候什么情况下可能遇到死锁呢? 就是可能剩下的内存不够分配给任何一个进程了，但是要想有内存能回收的话，就一定要有进程执行完毕，但是要有进程能执行完毕，前面说了，进程需要的内存未必一次给够，如果不给够的话，进程无法执行完毕. 那么操作系统就处于死锁状态了——没有进程能执行完毕了（因为不能给够任何一个进程该进程剩下需要的资源）. 从而新来的进程也无法请求资源——操作系统假死.

那么银行家算法是怎么避免这样的事情发生的呢? 形象的说就是真正分配之前先预演一遍——如果当前进程存在不会发生死锁的执行序列（将所有进程执行完毕）的话（网上很多博客称之为安全序列），那么此次分配就是安全的. 就可以分配, 不然的话，就不分配——让此进程等待.

所以银行家算法其实就两个模块. 一个模（函）块（数）真实的分配资源，一个模（函）块（数）进行安全性校验.

这里的建模与网上大部分类似, 就是

1
2
3
4
5
M[i][j], 1<=i<=n, 1<=j<=m, 表示i号进程运行一开始声明自己最多需要j号资源的数量
Allocation[i][j],1<=i<=n, 1<=j<=m, 表示操作系统为i号进程已经分配了j号资源的数量
Available[i] 1<=i<=m 表示当前操作系统资源i拥有的数量
Need[i][j], 1<=i<=n, 1<=j<=m, 表示i号进程当前还需要j号资源的数量
Request[i][j] ,1<=i<=n, 1<=j<=m, 表示进程i此次申请资源j的数量

那么银行家算法的c++实现如下

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
#include "stdafx.h"

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define LOCAL

class Banker // 银行家操作系统, 注意, 程序涉及的数组全都不用0索引
{
public:
	Banker() // 初始化各项资源
	{
		memset(Allocation, 0, sizeof(Allocation)); // 一开始是没有分配任何资源的
		input();
	}

	~Banker(){}

	bool allocate(int i, int j, int k) // 银行家算法的主模块——分配资源算法, 参数表示i号进程需要j号资源的数量为k, 因为这里主要展示银行家算法,所以没有对请求进行进一步的封装
	{
		if (k>Available[j] || k>Need[i][j]) // 首先进行当前资源检查, 如果不满足, 直接返回false
		{
			return false; // 如果操作系统剩下根本没有k的资源或者超出了当时i进程声称的对j资源的最大需求量
		}
		// 开始试探性的分配资源（预分配）
		assign_or_rollback(i,j,k,1);
		if (!safe())
		{
			assign_or_rollback(i,j,k, -1); // 因为会发生死锁, 所以回滚资源预分配
			return false;
		}
		return true;
	}

	void display() // 展示当前操作系统中各资源的数量
	{
		for (int i = 1; i<=n_resources; i++)
		{
			printf("%d ", Available[i]);
		}
		puts("");
	}
	
private:
	const static int RESOURCE_TYPE = 10; // 资源最多有十种
	const static int PROCESS_NUM = 10; // 最多支持10个进程并发
	int M[PROCESS_NUM][RESOURCE_TYPE]; // i号进程运行一开始声明自己最多需要j号资源的数量
	int Allocation[PROCESS_NUM][RESOURCE_TYPE]; // 二维数组, 表示操作系统已经为i号进程分配了j资源的数量
	int Need[PROCESS_NUM][RESOURCE_TYPE]; // 二维数组, 表示目前i进程对j资源的需求量
	int Available[RESOURCE_TYPE]; // 当前操作系统各种资源剩下的数量
	int counterpart[RESOURCE_TYPE]; // Available的副本
	int n_resources; //资源的实际种数
	int n_process; // 进程数量
	bool finish[PROCESS_NUM]; // 在模拟运行的过程中是否执行完毕了
	int safesequence[PROCESS_NUM]; // 安全序列(银行家算法执行的过程中每次调用safe进行检查的时候,如果可行的话, 要输出安全序列的)

	void input() // 输入系统
	{
		puts("输入资源数和进程数");
		scanf("%d%d", &n_resources, &n_process);
		puts("输入各个资源的初始值");
		for (int i = 1;i<=n_resources; i++)
		{
			scanf("%d", Available+i);
		}
		puts("输入各个进程对各个资源的最大需求量");
		for (int i = 1; i<=n_process; i++)
		{
			for (int j = 1; j<=n_resources; j++)
			{
				scanf("%d", M[i]+j);
				Need[i][j] = M[i][j];
			}
		}
	}

	void assign_or_rollback(int i, int j, int k, int flag) // （试探性地）分配资源或者回滚资源分配, flag为1表示分配, -1表示回滚资源
	{
		k*=flag;
		Allocation[i][j]+=k;
		Available[j]-=k;
		Need[i][j]-=k;
	}

	bool safe() // 判断此次分配是否会发生系统死锁, true表示不会, false表示会,这是银行家算法的核心——其实就是预演一遍进程的运行. 看看会不会死锁
	{
		memcpy(counterpart, Available, sizeof(Available)); // 首先准备副本资源(不要影响Available)
		memset(finish, 0, sizeof(finish)); // 重置finish
		int count = n_process; // 当前还剩下的未完成的进程
		// 其实这里dfs应该做一个优化——因为dfs的目的是找到一组安全序列就成. 所以采用贪心策略应该dfs之前进行适当的排序——例如按照need最小进行排序——这种贪心是符合直观的——尽可能快的让任务结束,好腾挪出空间来
		return dfs(0,count); // 因为程序不用零索引, 所以0表示一个不存在的进程
	}

	bool ok(int i) // 检查操作系统中当前剩余可用的资源是否能支撑进程i执行完毕, true表示可以，false表示不可以
	{
		for (int j=1; j<=n_resources;j++) // 检查各种资源是否足够
		{
			if (Need[i][j]>counterpart[j])
			{
				return false;
			}
		}
		return true;
	}

	void revoke(int i, int flag) // 回收进程i占用的各种资源
	{
		for (int j = 1; j<=n_resources; j++)
		{
			counterpart[j]+=Allocation[i][j]*flag;
		}
	}

	bool dfs(int i, int j) // i是当前运行完毕的进程，此次dfs的目的是决定下一次要运行的进程, j是当前尚未完成的进程数量
	{
		if (!j) // 如果找到了
		{
			printf("安全序列: ");
			for (int i = n_process; i; i--) // 打印出一种安全序列
			{
				printf("%d ", safesequence[i]);
			}
			puts("");
			return true;
		}
		for (int i = 1; i<=n_process; i++) // 否则就要扩展状态了
		{
			if (finish[i]) // 如果已经完成了, 就算了
			{
				continue;
			}
			if (ok(i)) // 如果第i个进程能执行完毕
			{
				revoke(i,1); // 回收进程i占用的资源
				finish[i] = true;
				safesequence[j] = i; // 改变状态
				if (dfs(i,j-1))
				{
					return true;
				}
				finish[i] = false; // 改回来
				revoke(i, -1);
			}
		}
		return false; // 最终没找到任何一种安全序列,即死锁发生.
	}
};

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	Banker banker;
	int i,j,k; // (i,j,k)构成一次请求——i进程请求j资源的数量为k
	puts("操作系统初始化完毕, 开始接受资源请求!");
	while(~scanf("%d%d%d", &i,&j,&k))
	{
		printf("%d号进程申请%d号资源的数量为%d\n", i,j,k);
		if (banker.allocate(i,j,k))
		{
			puts("资源分配成功!当前操作系统中各个资源剩余数量如下");
		}
		else
		{
			puts("资源分配失败!可能资源不足亦或是系统有死锁风险!请等待其余进程结束再申请资源!当前操作系统中各个资源剩余数量如下");
		}
		banker.display();
	}
	return 0;
}
/*
测试数据
3 5
10 5 7
7 5 3
3 2 2
9 0 2
2 2 2
4 3 3
1 2 1
2 1 2
3 1 3
3 3 2
4 1 2
4 2 1
4 3 1
5 3 2
2 1 1
2 3 2
5 1 3
5 2 3
1 2 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
输入资源数和进程数
输入各个资源的初始值
输入各个进程对各个资源的最大需求量
操作系统初始化完毕, 开始接受资源请求!
1号进程申请2号资源的数量为1
安全序列: 1 2 3 4 5
资源分配成功!当前操作系统中各个资源剩余数量如下
10 4 7
2号进程申请1号资源的数量为2
安全序列: 1 2 3 4 5
资源分配成功!当前操作系统中各个资源剩余数量如下
8 4 7
3号进程申请1号资源的数量为3
安全序列: 2 1 3 4 5
资源分配成功!当前操作系统中各个资源剩余数量如下
5 4 7
3号进程申请3号资源的数量为2
安全序列: 2 1 3 4 5
资源分配成功!当前操作系统中各个资源剩余数量如下
5 4 5
4号进程申请1号资源的数量为2
安全序列: 2 4 1 3 5
资源分配成功!当前操作系统中各个资源剩余数量如下
3 4 5
4号进程申请2号资源的数量为1
安全序列: 2 4 1 3 5
资源分配成功!当前操作系统中各个资源剩余数量如下
3 3 5
4号进程申请3号资源的数量为1
安全序列: 2 4 1 3 5
资源分配成功!当前操作系统中各个资源剩余数量如下
3 3 4
5号进程申请3号资源的数量为2
安全序列: 2 4 1 3 5
资源分配成功!当前操作系统中各个资源剩余数量如下
3 3 2
2号进程申请1号资源的数量为1
安全序列: 2 4 1 3 5
资源分配成功!当前操作系统中各个资源剩余数量如下
2 3 2
2号进程申请3号资源的数量为2
安全序列: 2 4 1 3 5
资源分配成功!当前操作系统中各个资源剩余数量如下
2 3 0
5号进程申请1号资源的数量为3
资源分配失败!可能资源不足亦或是系统有死锁风险!请等待其余进程结束再申请资源!当前操作系统中各个资源剩余数量如下
2 3 0
5号进程申请2号资源的数量为3
资源分配失败!可能资源不足亦或是系统有死锁风险!请等待其余进程结束再申请资源!当前操作系统中各个资源剩余数量如下
2 3 0
1号进程申请2号资源的数量为2
资源分配失败!可能资源不足亦或是系统有死锁风险!请等待其余进程结束再申请资源!当前操作系统中各个资源剩余数量如下
2 3 0
请按任意键继续. . .

银行家算法一个最大的弱点就在于——每个进程需要在运行开始之前就预估自己需要的各种资源数量并给出上限. 注意，对于银行家算法而言，这是必须要给出的. 不然safe算法是无法进行的（safe算法是模拟会不会发生死锁，里面用到的ok函数中用到了Need, 如果我不知道你需要的上限，我咋知道Need是多少?）. 这其实对于大部分操作系统而言其实是做不到的. 所以银行家算法其实并不实用. 但是它的思想在人类思想史的星空中依旧熠熠生辉. 致敬伟大的dijkstra!

参考

【1】https://blog.csdn.net/weixin_39478524/article/details/80604876

【2】https://blog.csdn.net/qq_34777600/article/details/79509425