0
00:00:00,000 --> 00:00:07,240


1
00:00:07,320 --> 00:00:10,680
下面我们来讨论银行家算法

2
00:00:10,720 --> 00:00:15,680
银行家算法是一种死锁避免的方法

3
00:00:15,720 --> 00:00:17,360
它指的是说

4
00:00:17,400 --> 00:00:22,400
我们以银行贷款分配的策略为基础

5
00:00:22,440 --> 00:00:26,240
通过判断系统是否处于安全状态

6
00:00:26,280 --> 00:00:31,720
来确定我这一次的资源分配是否同意

7
00:00:31,760 --> 00:00:36,320
这里借用的银行贷款分配策略是这样的

8
00:00:36,360 --> 00:00:38,640
客户在申请贷款的时候

9
00:00:38,680 --> 00:00:40,320
那你必须告诉银行

10
00:00:40,360 --> 00:00:43,360
你最大的资金申请量是多少

11
00:00:43,400 --> 00:00:46,920
并且保证在你的项目执行完毕之后

12
00:00:46,960 --> 00:00:49,160
能及时归还贷款

13
00:00:49,200 --> 00:00:51,520
对于我们操作系统里的

14
00:00:51,560 --> 00:00:55,360
银行家算法也是有类似的要求的

15
00:00:55,400 --> 00:00:57,280
从银行这个角度来说

16
00:00:57,320 --> 00:01:01,120
它只要保证用户贷款的数量

17
00:01:01,160 --> 00:01:03,600
不超过银行的最大值

18
00:01:03,640 --> 00:01:06,640
那么这银行就应该尽可能的

19
00:01:06,680 --> 00:01:08,320
满足客户的需求

20
00:01:08,360 --> 00:01:10,680
也就是说银行手里头没钱不行

21
00:01:10,720 --> 00:01:12,760
有钱不把它借给客户

22
00:01:12,800 --> 00:01:14,800
实际上它的利用效率也是很低的

23
00:01:14,840 --> 00:01:16,400
那这个比喻呢

24
00:01:16,440 --> 00:01:19,440
我们可以这样来进行对应

25
00:01:19,480 --> 00:01:21,960
银行家对应着我们这是操作系统

26
00:01:22,000 --> 00:01:23,280
银行家要来判断

27
00:01:23,320 --> 00:01:25,560
我借出去这笔钱行是不行

28
00:01:25,600 --> 00:01:26,520
安全不安全

29
00:01:26,560 --> 00:01:28,200
操作系统需要来判断

30
00:01:28,240 --> 00:01:30,880
我这个资源分配出去是否安全

31
00:01:30,920 --> 00:01:33,920
那银行家借的是资金

32
00:01:33,960 --> 00:01:35,120
这是它的资源

33
00:01:35,160 --> 00:01:36,840
对于我们操作系统来说

34
00:01:36,880 --> 00:01:38,480
我的CPU内存

35
00:01:38,520 --> 00:01:39,840
这是我的资源

36
00:01:39,880 --> 00:01:42,120
银行家应对的是客户

37
00:01:42,160 --> 00:01:43,680
而操作系统应对的

38
00:01:43,720 --> 00:01:48,120
是申请资源的线程或者是进程

39
00:01:48,160 --> 00:01:50,640
具体怎么做呢

40
00:01:50,680 --> 00:01:52,760
首先它要对系统的状态

41
00:01:52,800 --> 00:01:54,720
有一系列的记录

42
00:01:54,760 --> 00:01:56,800
你比如说在我们这里头

43
00:01:56,840 --> 00:02:00,240
假定系统里的线程数目是N

44
00:02:00,280 --> 00:02:02,600
然后资源的种类是M

45
00:02:02,640 --> 00:02:05,120
这时候呢 它们有一个矩阵

46
00:02:05,160 --> 00:02:06,560
M乘N的矩阵

47
00:02:06,600 --> 00:02:08,800
表示每一个线程

48
00:02:08,840 --> 00:02:12,880
它需要申请的每一类资源的总数

49
00:02:12,920 --> 00:02:14,320
那有了这个数字之后呢

50
00:02:14,360 --> 00:02:15,640
这里的一行

51
00:02:15,680 --> 00:02:17,920
那肯定是小于我系统里

52
00:02:17,960 --> 00:02:20,560
所拥有的所有资源的总量

53
00:02:20,600 --> 00:02:22,520
这是一个最基本的限制

54
00:02:22,560 --> 00:02:25,920
第二个是说我系统里的剩余资源

55
00:02:25,960 --> 00:02:28,680
这地方是一个长度为M的向量

56
00:02:28,720 --> 00:02:31,200
也就相当于系统里有M总资源

57
00:02:31,240 --> 00:02:33,480
每一种资源当前还剩多少

58
00:02:33,520 --> 00:02:36,840
再有一个是分配矩阵

59
00:02:36,880 --> 00:02:39,200
这里描述是已经分配给

60
00:02:39,240 --> 00:02:43,280
每一个线程的各类资源的数目

61
00:02:43,320 --> 00:02:46,600
以便能够知道它和总量之间

62
00:02:46,640 --> 00:02:48,280
到底是个什么样的关系

63
00:02:48,320 --> 00:02:49,080
已经分配出去

64
00:02:49,120 --> 00:02:50,480
不能大于每个进程

65
00:02:50,520 --> 00:02:53,240
在起头的时候声称的总量

66
00:02:53,280 --> 00:02:57,080
再有一个就是还有一个未来需要的量

67
00:02:57,120 --> 00:02:59,080
这也是一个M乘N的矩阵

68
00:02:59,120 --> 00:03:02,960
每一个线程它还需要M类的资源里的

69
00:03:03,000 --> 00:03:06,200
每一种各需要多少 那从这

70
00:03:06,240 --> 00:03:08,960
这几个向量和矩阵之间

71
00:03:09,000 --> 00:03:10,680
有这样一个关系

72
00:03:10,720 --> 00:03:13,440
最大的和未来需求的

73
00:03:13,480 --> 00:03:15,960
和已经分配的它们构成一个等式

74
00:03:16,000 --> 00:03:17,840
未来需要的等于最大的

75
00:03:17,880 --> 00:03:19,920
减去你已经分配的

76
00:03:19,960 --> 00:03:23,080
这是银行家算法在运行过程当中

77
00:03:23,120 --> 00:03:24,760
需要维护的信息

78
00:03:24,800 --> 00:03:26,280
也就是说它需要知道

79
00:03:26,320 --> 00:03:29,040
我现在总共有多少资源

80
00:03:29,080 --> 00:03:30,800
哪些已经分配出去了

81
00:03:30,840 --> 00:03:32,360
哪些还是空闲的

82
00:03:32,400 --> 00:03:34,080
这是它必须掌握的 否则的话

83
00:03:34,120 --> 00:03:38,240
它没有办法判断到底是否处于安全

84
00:03:38,280 --> 00:03:41,440
然后在这里就有一个安全的判断算法

85
00:03:41,480 --> 00:03:43,720
这里头呢 它的做法是说

86
00:03:43,760 --> 00:03:48,240
我们把现在可用的资源复制一下

87
00:03:48,280 --> 00:03:50,880
作为我当前进行判断的一个工作场所

88
00:03:50,920 --> 00:03:52,600
然后就看在这个状态下

89
00:03:52,640 --> 00:03:55,320
是不是我可以满足

90
00:03:55,360 --> 00:03:58,640
当前已经分配过资源的这些线程

91
00:03:58,680 --> 00:04:00,200
它的总的需求

92
00:04:00,240 --> 00:04:01,080
如果能满足

93
00:04:01,120 --> 00:04:02,680
表示我当前这种状态下

94
00:04:02,720 --> 00:04:05,680
可以把所有已经分配出去的资源

95
00:04:05,720 --> 00:04:08,520
最后在用户用完之后能够回收回来

96
00:04:08,560 --> 00:04:09,760
如果不是这样的话

97
00:04:09,800 --> 00:04:12,360
它就是不安全的 那在这呢

98
00:04:12,400 --> 00:04:15,120
每一个线程有一个状态

99
00:04:15,160 --> 00:04:17,600
false表示当前还没有运行完

100
00:04:17,640 --> 00:04:20,480
如何来判断当前是否安全呢

101
00:04:20,520 --> 00:04:23,600
它就是在所有这些线程里头去查找

102
00:04:23,640 --> 00:04:26,480
我未来需要的资源的总量

103
00:04:26,520 --> 00:04:31,920
是否小于我当前有的这些资源总量

104
00:04:31,960 --> 00:04:34,960
并且当前这个线程是没有执行完的

105
00:04:35,000 --> 00:04:37,000
如果能找到这种情况

106
00:04:37,040 --> 00:04:39,720
那实际上就说明我当前的可用资源

107
00:04:39,760 --> 00:04:42,360
是可以满足某一个线程的

108
00:04:42,400 --> 00:04:44,080
未来的所有需要的

109
00:04:44,120 --> 00:04:44,800
那这时候呢

110
00:04:44,840 --> 00:04:47,920
我能把它的资源给回收回来

111
00:04:47,960 --> 00:04:50,760
如果你找了一圈之后没有找到

112
00:04:50,800 --> 00:04:51,920
那这时候呢

113
00:04:51,960 --> 00:04:54,200
就相当于是不安全了

114
00:04:54,240 --> 00:04:56,840
如果找到那这时候呢

115
00:04:56,880 --> 00:04:59,960
我就会把资源放回到可用资源里

116
00:05:00,000 --> 00:05:02,280
就是放回到work里

117
00:05:02,320 --> 00:05:04,280
同时把它的状态改为true

118
00:05:04,320 --> 00:05:06,800
也就是说这个线程结束了

119
00:05:06,840 --> 00:05:09,160
然后我再回到这来继续找

120
00:05:09,200 --> 00:05:11,120
到最后所有的都满足

121
00:05:11,160 --> 00:05:12,960
或者说有一个不满足

122
00:05:13,000 --> 00:05:14,880
但是我找不着剩余的资源

123
00:05:14,920 --> 00:05:18,840
可以满足某一个线程未来的需要

124
00:05:18,880 --> 00:05:20,160
那这是最后一步

125
00:05:20,200 --> 00:05:21,680
是否所有的线程

126
00:05:21,720 --> 00:05:23,880
都已经变成完成状态

127
00:05:23,920 --> 00:05:26,080
如果不是 它就是不安全的

128
00:05:26,120 --> 00:05:28,480
如果是那这时候它就是安全的

129
00:05:28,520 --> 00:05:31,600
这是银行家算法里头最核心的部分

130
00:05:31,640 --> 00:05:34,640
基本的思路就是我当前的剩余资源

131
00:05:34,680 --> 00:05:39,280
可以满足某一个线程的未来需要

132
00:05:39,320 --> 00:05:41,680
并且这种迭代循环到最后

133
00:05:41,720 --> 00:05:44,640
能够满足所有的线程的需要

134
00:05:44,680 --> 00:05:47,680
也就相当于我找到了一个安全序列

135
00:05:47,720 --> 00:05:49,640
有了这个基本的判断之后

136
00:05:49,680 --> 00:05:52,360
我们的银行家算法说起来就简单了

137
00:05:52,400 --> 00:05:55,040
每一次请求的时候

138
00:05:55,080 --> 00:05:57,160
我来判断这个请求是否安全

139
00:05:57,200 --> 00:05:58,640
首先第一个判断

140
00:05:58,680 --> 00:06:00,680
这个请求的资源量

141
00:06:00,720 --> 00:06:02,960
和最大的需求量比较

142
00:06:03,000 --> 00:06:04,400
它是不是比它小

143
00:06:04,440 --> 00:06:06,960
需要的资源量和你当前申请的资源量

144
00:06:07,000 --> 00:06:08,600
如果说你现在就已经超了

145
00:06:08,640 --> 00:06:10,600
那肯定这就已经报错了

146
00:06:10,640 --> 00:06:14,040
那我就拒绝分配给你相应的资源

147
00:06:14,080 --> 00:06:16,600
如果满足我需求的量

148
00:06:16,640 --> 00:06:19,120
还没有到我声称的最大量

149
00:06:19,160 --> 00:06:19,960
那这时候呢

150
00:06:20,000 --> 00:06:21,400
就进入第二步判断

151
00:06:21,440 --> 00:06:25,360
看我现在可用的资源是不是够你用的

152
00:06:25,400 --> 00:06:27,920
如果不够用线程必须等待

153
00:06:27,960 --> 00:06:29,480
如果说够用

154
00:06:29,520 --> 00:06:32,560
再来判断我现在这个是不是安全

155
00:06:32,600 --> 00:06:33,760
怎么来判断呢

156
00:06:33,800 --> 00:06:38,240
假定你把当前的用户申请允许了

157
00:06:38,280 --> 00:06:39,720
把资源分配给它了

158
00:06:39,760 --> 00:06:42,200
然后看我是不是能找到一个安全序列

159
00:06:42,240 --> 00:06:44,760
假定你已经把用户的请求分配完毕了

160
00:06:44,800 --> 00:06:48,680
这三个矩阵或者是向量

161
00:06:48,720 --> 00:06:49,920
它的状态发生变化

162
00:06:49,960 --> 00:06:52,160
然后我们调用前边的

163
00:06:52,200 --> 00:06:54,280
安全状态判断算法

164
00:06:54,320 --> 00:06:55,360
来对它进行判断

165
00:06:55,400 --> 00:06:57,200
判断完的结果有两个

166
00:06:57,240 --> 00:06:58,640
一个是安全的

167
00:06:58,680 --> 00:06:59,880
一个是不安全的

168
00:06:59,920 --> 00:07:02,000
如果安全的 那我同意分配

169
00:07:02,040 --> 00:07:04,160
并且把资源分配给相应用户

170
00:07:04,200 --> 00:07:05,520
如果不安全那这时候

171
00:07:05,560 --> 00:07:06,920
我前边就已经拒绝

172
00:07:06,960 --> 00:07:09,760
或者说到这我也再拒绝

173
00:07:09,800 --> 00:07:12,360
这是银行家算法

174
00:07:12,400 --> 00:07:14,160
那这个算法到底怎么来用呢

175
00:07:14,200 --> 00:07:16,280
我们下边通过一个例子来说明

176
00:07:16,320 --> 00:07:17,320
最主要的部分就是

177
00:07:17,360 --> 00:07:19,640
判断这个状态是否安全

178
00:07:19,680 --> 00:07:21,240
假定给一个初始状态

179
00:07:21,280 --> 00:07:24,080
这是我系统里的总的资源数目

180
00:07:24,120 --> 00:07:25,880
R1、R2、R3

181
00:07:25,920 --> 00:07:28,440
分别是9、3、6

182
00:07:28,480 --> 00:07:30,000
它的资源总数

183
00:07:30,040 --> 00:07:32,120
这是四个线程

184
00:07:32,160 --> 00:07:35,440
它们所声称的资源需求总量

185
00:07:35,480 --> 00:07:38,800
每一个的总量都小于我这个

186
00:07:38,840 --> 00:07:39,800
比如最大是9

187
00:07:39,840 --> 00:07:41,360
R1没有大于9的

188
00:07:41,400 --> 00:07:42,840
如果说这时候就有一个

189
00:07:42,880 --> 00:07:45,000
那你直接告诉它这事是不行的

190
00:07:45,040 --> 00:07:46,640
这是我已经分配出去

191
00:07:46,680 --> 00:07:48,600
到当前这个状态的

192
00:07:48,640 --> 00:07:52,400
这两个矩阵相减就是未来它需要的

193
00:07:52,440 --> 00:07:56,280
这时候我也可以告诉你我当前剩余的

194
00:07:56,320 --> 00:07:58,360
那这个状态是否安全呢

195
00:07:58,400 --> 00:08:00,920
我们需要判断的就是未来需要的量

196
00:08:00,960 --> 00:08:04,360
和我当前所剩余的这些资源比较而言

197
00:08:04,400 --> 00:08:06,840
是不是我可以找到一个序列

198
00:08:06,880 --> 00:08:09,640
最后把所有的资源全部收回

199
00:08:09,680 --> 00:08:11,720
我们对照了一下

200
00:08:11,760 --> 00:08:13,680
第一次你可以找谁

201
00:08:13,720 --> 00:08:15,840
1、2、3、4

202
00:08:15,880 --> 00:08:18,320
最后一个资源只有这一个

203
00:08:18,360 --> 00:08:21,320
T2是我正好所有的都满足的

204
00:08:21,360 --> 00:08:22,760
因为它只要R3

205
00:08:22,800 --> 00:08:24,240
我这里R3有 OK

206
00:08:24,280 --> 00:08:24,960
这事行了

207
00:08:25,000 --> 00:08:29,160
假定我把T2的需求满足分配

208
00:08:29,200 --> 00:08:31,840
给它一个R3资源 这时候呢

209
00:08:31,880 --> 00:08:33,200
我就可以把这里

210
00:08:33,240 --> 00:08:35,920
它用到的资源就都给收回来了

211
00:08:35,960 --> 00:08:39,080
那么这时候我这就变成6、2、3

212
00:08:39,120 --> 00:08:42,280
我分配完之后的状态是这样的

213
00:08:42,320 --> 00:08:45,640
原来这两个的状态就都清零了

214
00:08:45,680 --> 00:08:47,560
我这的状态变成6、2、3

215
00:08:47,600 --> 00:08:49,560
然后这时候说我是安全的吗

216
00:08:49,600 --> 00:08:50,920
实际上我们看下去

217
00:08:50,960 --> 00:08:53,560
我这的剩余资源可以满足

218
00:08:53,600 --> 00:08:56,080
剩下的三个线程任何一个

219
00:08:56,120 --> 00:08:58,200
当前执行都是可以的

220
00:08:58,240 --> 00:08:58,600
那这样的话

221
00:08:58,640 --> 00:09:03,520
我又可以把它们的都给回收回来

222
00:09:03,560 --> 00:09:04,760
再来 这样的话

223
00:09:04,800 --> 00:09:05,880
我们就看到最后剩一个

224
00:09:05,920 --> 00:09:06,680
这肯定满足

225
00:09:06,720 --> 00:09:09,880
所以我们说这个状态是安全的

226
00:09:09,920 --> 00:09:12,760
那我们再换一个例子来看

227
00:09:12,800 --> 00:09:15,840
在这地方同样是当前资源总数

228
00:09:15,880 --> 00:09:19,080
各个线程需要的资源总量

229
00:09:19,120 --> 00:09:21,160
以及与我已经分配出去的状态

230
00:09:21,200 --> 00:09:25,160
和未来各个线程需要的资源量

231
00:09:25,200 --> 00:09:27,440
和我当前的状态

232
00:09:27,480 --> 00:09:32,160
用户再想分配一个变成这种状态

233
00:09:32,200 --> 00:09:36,400
T1请求R1和R3各一个资源

234
00:09:36,440 --> 00:09:37,800
变成现在这种状态了

235
00:09:37,840 --> 00:09:40,120
那这种状态是安全的吗

236
00:09:40,160 --> 00:09:42,360
我们说如果你敢这么分配

237
00:09:42,400 --> 00:09:43,760
分配完了之后

238
00:09:43,800 --> 00:09:47,520
剩余的资源就已经没有办法满足

239
00:09:47,560 --> 00:09:50,720
这四个线程当中的任意一个

240
00:09:50,760 --> 00:09:51,680
未来的需要了

241
00:09:51,720 --> 00:09:53,440
这个可以满足剩下的R2

242
00:09:53,480 --> 00:09:55,320
都是不满足的了

243
00:09:55,360 --> 00:09:56,200
两个就不行

244
00:09:56,240 --> 00:09:58,560
然后R3的话

245
00:09:58,600 --> 00:09:59,600
那这两个不行

246
00:09:59,640 --> 00:10:02,520
所以最后你就没有办法找到一个

247
00:10:02,560 --> 00:10:06,640
当前资源够某一个线程未来所有的需要

248
00:10:06,680 --> 00:10:09,240
所以这个状态是不安全的

249
00:10:09,280 --> 00:10:14,360
如果说T1请求R1和R3资源数个数为一的话

250
00:10:14,400 --> 00:10:15,400
那么这个请求呢

251
00:10:15,440 --> 00:10:17,160
你是不能同意的

252
00:10:17,200 --> 00:10:19,640
同意了你这个系统就是不安全的了

253
00:10:19,680 --> 00:10:21,160


254
00:10:21,200 --> 00:10:21,680


255
00:10:21,720 --> 00:10:21,760