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


1
00:00:07,560 --> 00:00:11,600
下面我们来讨论死锁检测算法

2
00:00:11,640 --> 00:00:14,640
死锁检测和前边的银行家算法

3
00:00:14,680 --> 00:00:16,160
不一样的地方在于

4
00:00:16,200 --> 00:00:19,240
我不管分配的时候状态

5
00:00:19,280 --> 00:00:22,960
我只是在系统运行不下去

6
00:00:23,000 --> 00:00:24,160
我要去检测

7
00:00:24,200 --> 00:00:26,240
看看系统里的资源分配状态

8
00:00:26,280 --> 00:00:29,040
看是否已经出现死锁

9
00:00:29,080 --> 00:00:30,280
所以死锁检测呢

10
00:00:30,320 --> 00:00:34,760
是首先它允许系统进入死锁状态

11
00:00:34,800 --> 00:00:39,320
然后系统维护资源分配图

12
00:00:39,360 --> 00:00:41,560
当前哪些已经分配出去

13
00:00:41,600 --> 00:00:43,840
哪些正在请求

14
00:00:43,880 --> 00:00:45,600
具有这样一张图

15
00:00:45,640 --> 00:00:50,200
然后周期性的调用死锁检测算法

16
00:00:50,240 --> 00:00:52,960
来看这里是否存在死锁

17
00:00:53,000 --> 00:00:55,040
如果有 那我就会

18
00:00:55,080 --> 00:00:59,920
调用死锁恢复机制来进行恢复

19
00:00:59,960 --> 00:01:03,680
那我们首先关心的是如何来检测

20
00:01:03,720 --> 00:01:07,240
刚才我们在银行家算法里头

21
00:01:07,280 --> 00:01:10,200
这个分配是否安全

22
00:01:10,240 --> 00:01:12,560
那我是假装分配出去

23
00:01:12,600 --> 00:01:15,760
然后去看它是否安全

24
00:01:15,800 --> 00:01:18,640
而死锁检测呢实际上你已经分配完了

25
00:01:18,680 --> 00:01:21,520
只是去看它是否安全了

26
00:01:21,560 --> 00:01:22,400
那这时候说

27
00:01:22,440 --> 00:01:24,760
这个检测和前边的银行家算法里的

28
00:01:24,800 --> 00:01:27,120
安全检测有什么区别

29
00:01:27,160 --> 00:01:27,920
那实际上在这里呢

30
00:01:27,960 --> 00:01:29,120
最主要的一个区别就是

31
00:01:29,160 --> 00:01:32,840
它没有最大资源请求量的判断

32
00:01:32,880 --> 00:01:34,960
其它的它们俩是很相似的

33
00:01:35,000 --> 00:01:37,120
首先它有一个向量

34
00:01:37,160 --> 00:01:40,160
我现在系统里还有哪些可用资源

35
00:01:40,200 --> 00:01:42,160
这是个M 维的向量

36
00:01:42,200 --> 00:01:45,520
然后再有一个M乘N的矩阵

37
00:01:45,560 --> 00:01:47,640
是说我每一个进程

38
00:01:47,680 --> 00:01:51,560
已经分配了每一类资源各是多少

39
00:01:51,600 --> 00:01:54,000
这是它的基本数据结构

40
00:01:54,040 --> 00:01:56,600
然后说我们怎么检测呢

41
00:01:56,640 --> 00:02:03,720
我首先是对两个变量进行初始化

42
00:02:03,760 --> 00:02:05,480
一个是work

43
00:02:05,520 --> 00:02:08,360
指的是我现在系统里的空闲资源

44
00:02:08,400 --> 00:02:10,160
也就是它的可用资源

45
00:02:10,200 --> 00:02:13,000
然后是每一个线程的状态

46
00:02:13,040 --> 00:02:15,240
它是否还占用资源

47
00:02:15,280 --> 00:02:16,960
如果说它还占用资源

48
00:02:17,000 --> 00:02:18,600
那它就是false

49
00:02:18,640 --> 00:02:19,800
这就是我们要考虑的

50
00:02:19,840 --> 00:02:21,080
如果它已经不占用资源

51
00:02:21,120 --> 00:02:22,400
那么这个要么是结束的

52
00:02:22,440 --> 00:02:24,280
要么不是我们这里关心的

53
00:02:24,320 --> 00:02:28,720
资源所需要讨论的

54
00:02:28,760 --> 00:02:31,800
然后我们就需要来检查

55
00:02:31,840 --> 00:02:34,880
是否是我现在剩余的这些资源

56
00:02:34,920 --> 00:02:38,360
够某一个线程执行到结束

57
00:02:38,400 --> 00:02:40,960
那所谓的执行到结束它有一个请求

58
00:02:41,000 --> 00:02:43,240
这个请求和当前的

59
00:02:43,280 --> 00:02:45,240
可用资源之间是个啥关系

60
00:02:45,280 --> 00:02:47,040
如果是能找到

61
00:02:47,080 --> 00:02:50,840
我满足某一个线程的当前请求

62
00:02:50,880 --> 00:02:53,760
那这时候说 就算是找着了

63
00:02:53,800 --> 00:02:56,880
如果说找了一圈之后没有办法满足

64
00:02:56,920 --> 00:03:01,040
那这时候系统就有可能进入死锁状态了

65
00:03:01,080 --> 00:03:04,560
找到之后我就把它以分配的

66
00:03:04,600 --> 00:03:07,800
相当于我当前这个请求的资源

67
00:03:07,840 --> 00:03:10,800
用剩余的资源是可以满足的分配给它

68
00:03:10,840 --> 00:03:14,400
它完成运行它已经分配资源

69
00:03:14,440 --> 00:03:18,320
又可以回收回来到这个work里头

70
00:03:18,360 --> 00:03:22,360
那这样的话我这个线程就变成完成状态

71
00:03:22,400 --> 00:03:24,320
然后我再回来找

72
00:03:24,360 --> 00:03:27,440
如果说我经过若干轮

73
00:03:27,480 --> 00:03:30,560
我把所有的线程的状态

74
00:03:30,600 --> 00:03:32,840
都变成是完成状态的话

75
00:03:32,880 --> 00:03:35,040
那么这时候呢

76
00:03:35,080 --> 00:03:37,760
我的系统就算是安全的

77
00:03:37,800 --> 00:03:41,560
如果说这里头有一个它是false

78
00:03:41,600 --> 00:03:43,560
还处在等待状态的话

79
00:03:43,600 --> 00:03:46,240
那么这时候它就是产生了死锁

80
00:03:46,280 --> 00:03:47,600
我们看到在这里呢

81
00:03:47,640 --> 00:03:50,160
银行家算法和死锁检测算法

82
00:03:50,200 --> 00:03:51,440
它俩非常相似

83
00:03:51,480 --> 00:03:55,040
但是有一些小的区别

84
00:03:55,080 --> 00:03:57,960
然后它的计算量呢

85
00:03:58,000 --> 00:04:03,520
我在这是对每一个线程要循环一圈

86
00:04:03,560 --> 00:04:07,320
然后我要检查最多会到N的平方轮

87
00:04:07,360 --> 00:04:11,080
然后我每一个资源会进行一次操作

88
00:04:11,120 --> 00:04:14,560
那这时候呢 会是M乘N的平方

89
00:04:14,600 --> 00:04:15,360
所以在这里头

90
00:04:15,400 --> 00:04:16,800
如果说你的进程数目

91
00:04:16,840 --> 00:04:18,160
和资源量很大的话

92
00:04:18,200 --> 00:04:21,560
那这个死锁检测的开销是很大的

93
00:04:21,600 --> 00:04:24,000
还有一个就是我多长时间检测一次

94
00:04:24,040 --> 00:04:25,400
把这些开销算到里头去

95
00:04:25,440 --> 00:04:28,240
实际上开销是很大的

96
00:04:28,280 --> 00:04:30,480
那我们在前边说操作系统内部呢

97
00:04:30,520 --> 00:04:32,480
通常情况下不管死锁的事

98
00:04:32,520 --> 00:04:35,240
也就是由于这个原因

99
00:04:35,280 --> 00:04:37,120
下边我们通过一个实际的例子

100
00:04:37,160 --> 00:04:39,240
来看死锁检测

101
00:04:39,280 --> 00:04:40,520
在这个例子当中呢

102
00:04:40,560 --> 00:04:43,280
我有五个线程 三种资源

103
00:04:43,320 --> 00:04:45,760
它的资源总数的情况在这

104
00:04:45,800 --> 00:04:48,160
分别是7、2、6

105
00:04:48,200 --> 00:04:51,760
然后这个是它当前已经分配出去的状态

106
00:04:51,800 --> 00:04:54,120
和当前各个进程请求的状态

107
00:04:54,160 --> 00:04:56,080
在这我们实际上就可以看到一种情况

108
00:04:56,120 --> 00:04:58,840
我这里有两个请求是0

109
00:04:58,880 --> 00:05:00,880
实际上我们通常情况下

110
00:05:00,920 --> 00:05:03,120
只是在没有可用资源的时候

111
00:05:03,160 --> 00:05:06,000
我才会来做这种检查

112
00:05:06,040 --> 00:05:09,320
这两个没有请求的这个线程

113
00:05:09,360 --> 00:05:11,200
它肯定是可以执行结束的

114
00:05:11,240 --> 00:05:13,000
我们让它执行结束

115
00:05:13,040 --> 00:05:14,720


116
00:05:14,760 --> 00:05:18,840
这时候看到我的可用资源是变成3 1 3

117
00:05:18,880 --> 00:05:19,840
这时我看

118
00:05:19,880 --> 00:05:22,520
我这个资源是否可以满足剩余的

119
00:05:22,560 --> 00:05:26,240
还需要资源的这些线程的资源需求量

120
00:05:26,280 --> 00:05:28,640
我们从这可以看到 它都满足

121
00:05:28,680 --> 00:05:30,280
所以这时候这个状态呢

122
00:05:30,320 --> 00:05:32,400
它是能够正常结束

123
00:05:32,440 --> 00:05:35,080
里头是没有死锁的

124
00:05:35,120 --> 00:05:38,920


125
00:05:38,960 --> 00:05:41,720
这是我们找到了一个安全序列

126
00:05:41,760 --> 00:05:43,480
所以在这示例里头呢

127
00:05:43,520 --> 00:05:47,080
看这个检查还是比较容易的

128
00:05:47,120 --> 00:05:48,800
我们换一个角度

129
00:05:48,840 --> 00:05:50,120
我实际上在这里呢

130
00:05:50,160 --> 00:05:53,240
就把这两个的量给换了一下

131
00:05:53,280 --> 00:05:55,760
这时候第一个仍然是可以结束

132
00:05:55,800 --> 00:05:58,440
然后第三个原来是可以结束

133
00:05:58,480 --> 00:06:00,720
现在变成是还要申请

134
00:06:00,760 --> 00:06:01,920
但这时我们就看到

135
00:06:01,960 --> 00:06:03,320
实际上这时候你没有办法

136
00:06:03,360 --> 00:06:06,160
找到一个可以结束的状态

137
00:06:06,200 --> 00:06:09,520
因为第一个可以回收是B这个资源

138
00:06:09,560 --> 00:06:12,600
而B这个资源呢 只有它需要

139
00:06:12,640 --> 00:06:14,960
剩下的都A和C

140
00:06:15,000 --> 00:06:16,960
A和C都没有了 那这样的话

141
00:06:17,000 --> 00:06:20,320
我们就都没有办法顺利的完成

142
00:06:20,360 --> 00:06:21,120
所以这时候呢

143
00:06:21,160 --> 00:06:23,280
系统里就出现死锁了

144
00:06:23,320 --> 00:06:25,520
那出现死锁之后我们就会想到

145
00:06:25,560 --> 00:06:28,480
这死锁怎么来处理

146
00:06:28,520 --> 00:06:29,280
那在这之前呢

147
00:06:29,320 --> 00:06:31,240
我们还会再有一个问题

148
00:06:31,280 --> 00:06:34,040
说死锁检测算法我怎么来用

149
00:06:34,080 --> 00:06:35,600
刚才我们说是没有资源了

150
00:06:35,640 --> 00:06:37,960
我会来做这死锁检测

151
00:06:38,000 --> 00:06:41,040
然后我多长时间检测一次

152
00:06:41,080 --> 00:06:41,720
那这时候呢

153
00:06:41,760 --> 00:06:44,920
你不能等它系统里已经是完全搞不动了

154
00:06:44,960 --> 00:06:46,840
你才会来做这种检测

155
00:06:46,880 --> 00:06:47,760
那这时候呢

156
00:06:47,800 --> 00:06:50,960
你往回滚的量也是会很大的

157
00:06:51,000 --> 00:06:54,000
这是你在选择时间和周期的时候

158
00:06:54,040 --> 00:06:55,960
需要考虑的问题

159
00:06:56,000 --> 00:06:58,400
然后再有一个呢

160
00:06:58,440 --> 00:07:00,280
就是如果说里头出现了

161
00:07:00,320 --> 00:07:03,320
多个造成死锁的循环

162
00:07:03,360 --> 00:07:05,000
那这时候你很难分辨出

163
00:07:05,040 --> 00:07:07,440
哪一个是里头的关键

164
00:07:07,480 --> 00:07:09,600
因为我们找出关键的原因是

165
00:07:09,640 --> 00:07:12,960
为了减少我终止的进程的数目

166
00:07:13,000 --> 00:07:14,080
如果你找不着的话

167
00:07:14,120 --> 00:07:16,080
那这时候你就会终止很多进程

168
00:07:16,120 --> 00:07:19,280
这时候呢 它的开销也会是很大的

169
00:07:19,320 --> 00:07:22,600
假定说我能找着是否有死锁

170
00:07:22,640 --> 00:07:25,360
然后这时候我要进行进程的中终止

171
00:07:25,400 --> 00:07:30,000
我需要把产生死锁的进程终止掉

172
00:07:30,040 --> 00:07:32,440
我一次只终止一个

173
00:07:32,480 --> 00:07:34,200
因为你一块终止很多个的话

174
00:07:34,240 --> 00:07:36,400
有可能也是没必要的 我终止一个

175
00:07:36,440 --> 00:07:40,440
然后看它是否还会再有死锁

176
00:07:40,480 --> 00:07:42,760
那这时候说我到底终止哪一个呢

177
00:07:42,800 --> 00:07:43,520
这是我们在这里

178
00:07:43,560 --> 00:07:47,000
关于终止进程的顺序的考虑

179
00:07:47,040 --> 00:07:48,840
首先第一个我们按优先级

180
00:07:48,880 --> 00:07:50,960
那优先级最低的

181
00:07:51,000 --> 00:07:52,240
然后再一个就是

182
00:07:52,280 --> 00:07:54,520
我看它已经执行了多长时间

183
00:07:54,560 --> 00:07:56,880
和未来它可能需要执行多长时间

184
00:07:56,920 --> 00:07:57,960
有可能未来执行多长时间

185
00:07:58,000 --> 00:07:59,400
你干脆就不知道

186
00:07:59,440 --> 00:08:00,960
已经运行了多长时间

187
00:08:01,000 --> 00:08:04,320
运行时间越长的我们越希望留下它

188
00:08:04,360 --> 00:08:06,320
原因在于它已经占用系统资源

189
00:08:06,360 --> 00:08:08,000
算了很长时间了

190
00:08:08,040 --> 00:08:09,320
还有一种考虑是

191
00:08:09,360 --> 00:08:11,000
它已经占用的资源的情况

192
00:08:11,040 --> 00:08:13,200
实际上我们时间也是一种资源

193
00:08:13,240 --> 00:08:16,800
它已经占用的资源和未来需要的资源

194
00:08:16,840 --> 00:08:17,840
这都是我们在这里

195
00:08:17,880 --> 00:08:21,080
选择终止进程的时候所需要考虑的

196
00:08:21,120 --> 00:08:25,400
还有两种可能的考虑是我在终止的时候

197
00:08:25,440 --> 00:08:28,200
我会终止多少个进程

198
00:08:28,240 --> 00:08:29,920
这个数目越小越好

199
00:08:29,960 --> 00:08:34,120
然后会说我终止了进程是什么样的

200
00:08:34,160 --> 00:08:37,080
是前台的交互进程和后台的批处理

201
00:08:37,120 --> 00:08:38,720
我们通常情况下是愿意

202
00:08:38,760 --> 00:08:43,000
让用户交互的进程能够继续执行下去

203
00:08:43,040 --> 00:08:46,320
这是终止进程的选择

204
00:08:46,360 --> 00:08:48,360
然后我选择了要终止之后

205
00:08:48,400 --> 00:08:49,840
那我怎么来终止呢

206
00:08:49,880 --> 00:08:52,200
由抢夺资源

207
00:08:52,240 --> 00:08:54,320
抢占进程所占用的资源

208
00:08:54,360 --> 00:08:56,920
这是我选择成本最小的

209
00:08:56,960 --> 00:08:59,000
然后我可以回退

210
00:08:59,040 --> 00:09:00,440
回退到以前的某个状态

211
00:09:00,480 --> 00:09:03,360
然后继续启动进程的执行

212
00:09:03,400 --> 00:09:05,800


213
00:09:05,840 --> 00:09:09,440
在这里头呢 可能会出现饥饿

214
00:09:09,480 --> 00:09:12,000
我一个进程终止之后 我再继续执行

215
00:09:12,040 --> 00:09:15,840
可能还会是同样的进程被终止

216
00:09:15,880 --> 00:09:17,160
这时候呢

217
00:09:17,200 --> 00:09:21,600
就会出现我们这里说的饥饿情况

218
00:09:21,640 --> 00:09:25,080
这是我们关于死锁检测的讨论

219
00:09:25,120 --> 00:09:26,880


220
00:09:26,920 --> 00:09:27,080


221
00:09:27,120 --> 00:09:27,160