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


1
00:00:16,280 --> 00:00:17,800
各位同学 大家好

2
00:00:17,840 --> 00:00:22,840
今天我们来介绍死锁和进程通讯

3
00:00:22,880 --> 00:00:25,160
死锁呢 是进程之间

4
00:00:25,200 --> 00:00:28,120
由于共享资源所导致的一种

5
00:00:28,160 --> 00:00:29,720
无限期等待的情况

6
00:00:29,760 --> 00:00:30,640
那在这里头呢

7
00:00:30,680 --> 00:00:33,280
我们会讨论死锁的基本概念

8
00:00:33,320 --> 00:00:36,000
处理死锁的方法都有哪些

9
00:00:36,040 --> 00:00:38,720
我们会具体介绍银行家算法

10
00:00:38,760 --> 00:00:40,440
和死锁检测算法

11
00:00:40,480 --> 00:00:42,920
这两个具体的算法

12
00:00:42,960 --> 00:00:44,000
另外一个部分呢

13
00:00:44,040 --> 00:00:45,160
是进程间通讯

14
00:00:45,200 --> 00:00:46,640
也就是说两个进程之间

15
00:00:46,680 --> 00:00:49,240
它们有一些什么样的通讯手段

16
00:00:49,280 --> 00:00:50,080
那在这里呢

17
00:00:50,120 --> 00:00:53,480
我们会介绍四种 信号和管道

18
00:00:53,520 --> 00:00:56,640
消息队列和共享内存

19
00:00:56,680 --> 00:00:59,560
那首先呢 我们来介绍死锁

20
00:00:59,600 --> 00:01:03,720
死锁是由于竞争资源或通讯关系

21
00:01:03,760 --> 00:01:06,160
两个或更多个线程

22
00:01:06,200 --> 00:01:08,720
在执行的过程当中出现的一种

23
00:01:08,760 --> 00:01:12,080
永远相互等待其他进程

24
00:01:12,120 --> 00:01:15,480
才能引发的事件的状态

25
00:01:15,520 --> 00:01:17,960
那这时候呢 我们先通过一个

26
00:01:18,000 --> 00:01:19,760
具体的例子来看一下

27
00:01:19,800 --> 00:01:22,200
这就是单向通行桥梁

28
00:01:22,240 --> 00:01:23,960
那在这里头呢 这个桥梁呢

29
00:01:24,000 --> 00:01:27,520
我们可以认为它是一种共享的资源

30
00:01:27,560 --> 00:01:30,080
桥梁上只能单向通行

31
00:01:30,120 --> 00:01:32,600
那这时候呢 不同方向的车

32
00:01:32,640 --> 00:01:36,080
会共享这个单向通行的桥梁

33
00:01:36,120 --> 00:01:38,000
那桥梁的每一部分呢

34
00:01:38,040 --> 00:01:40,480
是一个资源

35
00:01:40,520 --> 00:01:43,120
如果这个桥梁整个是一个资源

36
00:01:43,160 --> 00:01:45,360
它也不会出现问题

37
00:01:45,400 --> 00:01:46,880
那要占用就整个占用

38
00:01:46,920 --> 00:01:48,000
实际上我们在这里

39
00:01:48,040 --> 00:01:50,800
是由于部分占用所导致的问题

40
00:01:50,840 --> 00:01:54,080
在这里呢 桥梁在使用的时候

41
00:01:54,120 --> 00:01:55,400
可能出现死锁

42
00:01:55,440 --> 00:01:56,440
比如说在这里头

43
00:01:56,480 --> 00:01:58,440
对向行驶的两个车辆

44
00:01:58,480 --> 00:02:00,560
在桥梁上正相遇了

45
00:02:00,600 --> 00:02:03,520
好 那这时候谁也没有办法继续前行

46
00:02:03,560 --> 00:02:04,560
都等待对方 

47
00:02:04,600 --> 00:02:07,240
而这种等待呢 是没有结果的

48
00:02:07,280 --> 00:02:09,440
这种情况下呢 在我们通常做法呢

49
00:02:09,480 --> 00:02:12,200
是一个方向的车辆倒退

50
00:02:12,240 --> 00:02:14,400
好 那这样另一个方向呢能通行

51
00:02:14,440 --> 00:02:16,040
这实际上就是我们在这里头

52
00:02:16,080 --> 00:02:19,080
给到的一种死锁的解决办法

53
00:02:19,120 --> 00:02:20,480
就是资源的抢占

54
00:02:20,520 --> 00:02:21,720
与此同时呢 

55
00:02:21,760 --> 00:02:23,400
即使不出现这种情况

56
00:02:23,440 --> 00:02:25,640
也会出现饥饿的情况

57
00:02:25,680 --> 00:02:27,760
一个方向的车持续的运行

58
00:02:27,800 --> 00:02:29,080
而另一个方向的车呢

59
00:02:29,120 --> 00:02:32,160
就没有办法通过这个桥梁了

60
00:02:32,200 --> 00:02:34,840
这是实际生活当中的一个例子

61
00:02:34,880 --> 00:02:36,600
我们在操作系统里头

62
00:02:36,640 --> 00:02:38,320
对于资源共享的情况

63
00:02:38,360 --> 00:02:41,880
也会有一个跟它很类似的情况

64
00:02:41,920 --> 00:02:46,160
那在具体讨论如何解决的办法之前

65
00:02:46,200 --> 00:02:49,800
我们需要比较深入的来分析一下

66
00:02:49,840 --> 00:02:52,840
死锁它出现的相关背景情况

67
00:02:52,880 --> 00:02:55,120
你比如说我们资源的使用过程

68
00:02:55,160 --> 00:02:57,760
出现死锁的条件等等

69
00:02:57,800 --> 00:02:59,520
首先呢 我们来看

70
00:02:59,560 --> 00:03:02,680
进程访问资源它的流程

71
00:03:02,720 --> 00:03:03,720
在系统里头呢

72
00:03:03,760 --> 00:03:07,080
我们存在各种类型的资源

73
00:03:07,120 --> 00:03:09,080
比如说像我们这里说到的

74
00:03:09,120 --> 00:03:12,440
CPU的执行时间 内存 I/O设备

75
00:03:12,480 --> 00:03:13,800
每一类资源呢

76
00:03:13,840 --> 00:03:15,240
可能会有多个实例

77
00:03:15,280 --> 00:03:17,640
你比如说像你的CPU

78
00:03:17,680 --> 00:03:20,000
可能有多个CPU

79
00:03:20,040 --> 00:03:20,840
对于这些资源呢

80
00:03:20,880 --> 00:03:21,680
我们在访问的时候

81
00:03:21,720 --> 00:03:23,840
通常是什么样的流程呢

82
00:03:23,880 --> 00:03:26,800
那进程访问资源的流程是这样的

83
00:03:26,840 --> 00:03:29,840
说这个资源为系统所占用

84
00:03:29,880 --> 00:03:30,800
进程在使用的时候

85
00:03:30,840 --> 00:03:32,960
首先我需要申请

86
00:03:33,000 --> 00:03:35,360
申请系统当中空闲的资源

87
00:03:35,400 --> 00:03:37,400
然后申请到了之后呢

88
00:03:37,440 --> 00:03:38,560
这个资源的状态

89
00:03:38,600 --> 00:03:41,240
就由空闲变成被进程占用了

90
00:03:41,280 --> 00:03:43,480
然后进程占用资源使用

91
00:03:43,520 --> 00:03:45,240
这有一个持续的时间段

92
00:03:45,280 --> 00:03:48,680
等它用完了之后 它会释放资源

93
00:03:48,720 --> 00:03:49,960
释放资源之后呢

94
00:03:50,000 --> 00:03:51,080
这时候资源的状态呢

95
00:03:51,120 --> 00:03:53,400
就由占用变成了空闲

96
00:03:53,440 --> 00:03:57,360
这是一个资源的使用的流程

97
00:03:57,400 --> 00:03:58,640
那在这个流程当中呢

98
00:03:58,680 --> 00:03:59,480
我们可以看到 

99
00:03:59,520 --> 00:04:02,320
资源和进程之间的相互关系了

100
00:04:02,360 --> 00:04:04,440
然后为了更进一步的讨论

101
00:04:04,480 --> 00:04:07,120
我如何来解决死锁的问题

102
00:04:07,160 --> 00:04:09,760
那我们有必要对资源的特征

103
00:04:09,800 --> 00:04:11,520
进行一个分析

104
00:04:11,560 --> 00:04:12,120
在这里头呢

105
00:04:12,160 --> 00:04:14,760
我们就把资源分成了两类

106
00:04:14,800 --> 00:04:16,760
一类叫可重用资源

107
00:04:16,800 --> 00:04:18,920
对于这些可重用资源呢

108
00:04:18,960 --> 00:04:21,600
它的这些资源是不可以删除的

109
00:04:21,640 --> 00:04:22,680
任何一个时刻呢

110
00:04:22,720 --> 00:04:24,840
只能有一个进程使用

111
00:04:24,880 --> 00:04:27,080
一个进程使用释放之后

112
00:04:27,120 --> 00:04:29,320
另外的进程就可以重用了

113
00:04:29,360 --> 00:04:31,320
比如说像CPU

114
00:04:31,360 --> 00:04:33,480
你占用一个时间段 再使用

115
00:04:33,520 --> 00:04:34,840
好 过一会儿之后

116
00:04:34,880 --> 00:04:36,440
你用完了 你释放

117
00:04:36,480 --> 00:04:40,800
另外一个线程就可以来使用CPU的资源

118
00:04:40,840 --> 00:04:42,040
大家交替使用

119
00:04:42,080 --> 00:04:43,760
这就是我们前面所说到的

120
00:04:43,800 --> 00:04:46,120
调度所要解决的问题了

121
00:04:46,160 --> 00:04:47,520
那对于这种资源呢

122
00:04:47,560 --> 00:04:50,360
它有些什么样的实例呢

123
00:04:50,400 --> 00:04:52,840
那我们这里头处理器  I/O通道

124
00:04:52,880 --> 00:04:55,880
存储  I/O设备 那这些都是

125
00:04:55,920 --> 00:04:57,160
这是硬件资源

126
00:04:57,200 --> 00:04:58,400
也有一些软件资源

127
00:04:58,440 --> 00:05:01,400
你比如说文件 数据库等等这些

128
00:05:01,440 --> 00:05:02,880
都是我们这里的资源

129
00:05:02,920 --> 00:05:06,040
这些资源呢 是不可以被删除的

130
00:05:06,080 --> 00:05:07,000
那至少是在这里头

131
00:05:07,040 --> 00:05:08,720
文件我们是可以删除的

132
00:05:08,760 --> 00:05:09,760
但实际上这是对应于

133
00:05:09,800 --> 00:05:12,480
进程在访问这些资源的过程

134
00:05:12,520 --> 00:05:16,440
当中的一种情况

135
00:05:16,480 --> 00:05:18,240
还有就是在这里

136
00:05:18,280 --> 00:05:19,920
它可能会出现死锁

137
00:05:19,960 --> 00:05:22,120
那出现死锁的原因是说

138
00:05:22,160 --> 00:05:24,760
一个进程我会占用一部分资源

139
00:05:24,800 --> 00:05:27,960
并且请求另外一部分资源

140
00:05:28,000 --> 00:05:29,480
如果说你是一个整体的话

141
00:05:29,520 --> 00:05:30,840
这种情况也没有了

142
00:05:30,880 --> 00:05:32,720
这是可重用资源

143
00:05:32,760 --> 00:05:35,280
还有一类叫消费资源

144
00:05:35,320 --> 00:05:36,640
这一类消费资源

145
00:05:36,680 --> 00:05:40,000
它有一个创建和销毁的过程

146
00:05:40,040 --> 00:05:42,600
比如说这里头我们看到的一些实例

147
00:05:42,640 --> 00:05:46,400
中断 中断又出现和处理例程

148
00:05:46,440 --> 00:05:50,200
信号 消息 这些都是有一个进程产生

149
00:05:50,240 --> 00:05:53,440
另一个进程使用 这样一个过程

150
00:05:53,480 --> 00:05:56,520
那在这里头呢 它可能出现死锁

151
00:05:56,560 --> 00:05:58,360
比如说我们在这里时常见到的

152
00:05:58,400 --> 00:06:01,520
通讯双方相互等待对方的消息

153
00:06:01,560 --> 00:06:03,040
这是时常出现的一种情况

154
00:06:03,080 --> 00:06:04,400
那这时候相互等下去

155
00:06:04,440 --> 00:06:07,040
就出现无限期的等待了

156
00:06:07,080 --> 00:06:08,640
好 我们在这里头呢

157
00:06:08,680 --> 00:06:10,920
对资源有了一个描述

158
00:06:10,960 --> 00:06:14,960
对进程访问资源的过程有了一个描述

159
00:06:15,000 --> 00:06:16,920
好 那这时候我们如何来描述

160
00:06:16,960 --> 00:06:18,640
进程和资源之间的关系呢

161
00:06:18,680 --> 00:06:20,760
这是我们这里的资源分配图

162
00:06:20,800 --> 00:06:24,120
它描述资源和进程之间的

163
00:06:24,160 --> 00:06:26,600
分配和占用关系

164
00:06:26,640 --> 00:06:28,080
这是一个有向图

165
00:06:28,120 --> 00:06:30,520
那这个有向图里都有些什么内容呢

166
00:06:30,560 --> 00:06:33,760
首先第一个它有两类顶点

167
00:06:33,800 --> 00:06:36,200
一类是我们系统当中的进程

168
00:06:36,240 --> 00:06:39,280
每一进程用一个圆圈来表示

169
00:06:39,320 --> 00:06:42,080
然后另一类顶点呢 是资源

170
00:06:42,120 --> 00:06:44,760
每一类资源对应着一个顶点

171
00:06:44,800 --> 00:06:48,440
资源里头的实例的数目

172
00:06:48,480 --> 00:06:51,120
在这里用小圆点来表示

173
00:06:51,160 --> 00:06:52,920
好 那这是我们顶点的情况

174
00:06:52,960 --> 00:06:56,280
然后这些顶点之间的关系有两种

175
00:06:56,320 --> 00:06:57,560
资源请求边

176
00:06:57,600 --> 00:07:01,080
一个进程指向一类资源

177
00:07:01,120 --> 00:07:03,320
表示这个进程要请求

178
00:07:03,360 --> 00:07:06,400
这类资源当中的一个实例

179
00:07:06,440 --> 00:07:07,680
还有一类呢

180
00:07:07,720 --> 00:07:09,120
是资源分配边

181
00:07:09,160 --> 00:07:11,960
这表示一个资源实例 

182
00:07:12,000 --> 00:07:15,560
已经分配给了某一个进程 在这

183
00:07:15,600 --> 00:07:18,400
用这个资源分配图我们就可以表示出

184
00:07:18,440 --> 00:07:24,320
进程和资源之间的申请和占用关系

185
00:07:24,360 --> 00:07:26,880
这是一个实际的例子

186
00:07:26,920 --> 00:07:28,640
我们从这张图里可以看到

187
00:07:28,680 --> 00:07:32,000
有四种资源 有三个进程

188
00:07:32,040 --> 00:07:34,320
它们之间有请求关系

189
00:07:34,360 --> 00:07:37,520
也有占用关系

190
00:07:37,560 --> 00:07:38,640
在这个图里头呢

191
00:07:38,680 --> 00:07:41,120
我们想知道 会不会出现死锁呢

192
00:07:41,160 --> 00:07:44,360
我们看下去之后 比如说这里头

193
00:07:44,400 --> 00:07:47,600
进程P3占用资源R3

194
00:07:47,640 --> 00:07:49,040
它用完了之后它释放

195
00:07:49,080 --> 00:07:49,800
那这时候呢

196
00:07:49,840 --> 00:07:51,360
P2就可以得到运行

197
00:07:51,400 --> 00:07:53,320
运行结束之后 那所有这些

198
00:07:53,360 --> 00:07:56,360
请求的编就都会得以分配

199
00:07:56,400 --> 00:07:57,880
所有进程都能执行完

200
00:07:57,920 --> 00:07:59,440
那这种情况呢 

201
00:07:59,480 --> 00:08:01,480
它是不会出现死锁了

202
00:08:01,520 --> 00:08:02,720
再看下一个图

203
00:08:02,760 --> 00:08:06,000
这和刚才的图就多了一条边

204
00:08:06,040 --> 00:08:07,440
这时候呢 我们就看到

205
00:08:07,480 --> 00:08:10,680
在这里 出现了一个循环等待

206
00:08:10,720 --> 00:08:13,240
P2请求R3

207
00:08:13,280 --> 00:08:15,120
R3已经分配给了P3

208
00:08:15,160 --> 00:08:17,000
P3又请求R2

209
00:08:17,040 --> 00:08:18,880
R2已经分配给了P2

210
00:08:18,920 --> 00:08:20,360
这时候就有一个循环等待

211
00:08:20,400 --> 00:08:21,800
并且这个循环等待呢

212
00:08:21,840 --> 00:08:24,200
它没有结束的时候

213
00:08:24,240 --> 00:08:25,080
好 那这时候呢

214
00:08:25,120 --> 00:08:27,320
我们知道它会出现死锁

215
00:08:27,360 --> 00:08:29,440
对于这种简单的情况呢

216
00:08:29,480 --> 00:08:32,720
我们直接从这图上就可以很清楚的看出来

217
00:08:32,760 --> 00:08:34,720
但实际上我们遇到的麻烦是

218
00:08:34,760 --> 00:08:38,320
在系统当中有几百个进程

219
00:08:38,360 --> 00:08:41,800
有几十种 或者更多的资源

220
00:08:41,840 --> 00:08:43,480
这时候你再来做判断

221
00:08:43,520 --> 00:08:47,560
那就会有时间开销和比较困难

222
00:08:47,600 --> 00:08:50,000
这是一个资源分配图

223
00:08:50,040 --> 00:08:53,480
那里头也有一个循环

224
00:08:53,520 --> 00:08:55,600
但它会出现死锁吗

225
00:08:55,640 --> 00:08:56,480
细分析下去之后

226
00:08:56,520 --> 00:08:57,800
跟我们刚才情况一样的

227
00:08:57,840 --> 00:08:59,360
它不会出现死锁

228
00:08:59,400 --> 00:09:00,920
但是它要循环

229
00:09:00,960 --> 00:09:01,960
好 那这时候我们说

230
00:09:02,000 --> 00:09:06,640
不能仅仅依靠循环来判断是否出现死锁

231
00:09:06,680 --> 00:09:08,760
具体说起来我们会怎么来做呢

232
00:09:08,800 --> 00:09:09,920
那这就是我们这里的

233
00:09:09,960 --> 00:09:12,680
出现死锁的必要条件

234
00:09:12,720 --> 00:09:16,000
必须满足我们这里说到的四个条件

235
00:09:16,040 --> 00:09:19,000
同时满足才会出现死锁

236
00:09:19,040 --> 00:09:21,600
第一个条件呢 是互斥

237
00:09:21,640 --> 00:09:23,680
我们必须有某种资源

238
00:09:23,720 --> 00:09:27,720
任何一个时刻 只有一个进程使用

239
00:09:27,760 --> 00:09:29,840
如果说你的资源是可以共享

240
00:09:29,880 --> 00:09:30,880
不需要互斥的

241
00:09:30,920 --> 00:09:33,600
那不会出现这种情况

242
00:09:33,640 --> 00:09:37,120
第二个是持有并等待

243
00:09:37,160 --> 00:09:38,480
也就是说我一个进程

244
00:09:38,520 --> 00:09:40,720
如果说它本身不占有任何资源

245
00:09:40,760 --> 00:09:42,200
那就不会有别人等它

246
00:09:42,240 --> 00:09:44,240
它不会请求别的资源的话

247
00:09:44,280 --> 00:09:45,640
那它也就不会等别人

248
00:09:45,680 --> 00:09:46,480
好 那这样的话就是

249
00:09:46,520 --> 00:09:49,400
必须你持有至少一种资源

250
00:09:49,440 --> 00:09:53,480
并且正在等待获取其他进程占有的资源

251
00:09:53,520 --> 00:09:56,120
这时候才构成我们这里的第二个条件

252
00:09:56,160 --> 00:09:58,680
持有并等待

253
00:09:58,720 --> 00:10:02,280
然后第三个条件呢 是说非抢占

254
00:10:02,320 --> 00:10:03,240
那这类指的是 

255
00:10:03,280 --> 00:10:06,840
资源只有在进程使用后自愿放弃

256
00:10:06,880 --> 00:10:08,280
我不可以强行剥夺

257
00:10:08,320 --> 00:10:09,600
比如说就像我们刚才说的

258
00:10:09,640 --> 00:10:11,800
单向通行的桥梁

259
00:10:11,840 --> 00:10:14,440
两个都走到中间相互等待了

260
00:10:14,480 --> 00:10:17,080
那这时候司机通常情况下

261
00:10:17,120 --> 00:10:19,800
都希望对方主动放弃

262
00:10:19,840 --> 00:10:20,840
那实际上在这里头呢

263
00:10:20,880 --> 00:10:23,400
通常情况下 这个是不容易满足的

264
00:10:23,440 --> 00:10:25,840
好 这是第三个条件

265
00:10:25,880 --> 00:10:29,040
第四个条件呢 是循环等待

266
00:10:29,080 --> 00:10:33,400
我在这些资源的请求和占有关系中

267
00:10:33,440 --> 00:10:36,080
我必须存在一个循环等待

268
00:10:36,120 --> 00:10:39,320
也就是说存在一个等待进程的集合

269
00:10:39,360 --> 00:10:40,240


270
00:10:40,280 --> 00:10:43,040
0等1 1等2

271
00:10:43,080 --> 00:10:44,760
N减1等N

272
00:10:44,800 --> 00:10:46,640
一直到N等0

273
00:10:46,680 --> 00:10:48,120
这样构成一个循环

274
00:10:48,160 --> 00:10:49,360
如果没有这个循环的话

275
00:10:49,400 --> 00:10:51,200
也不会出现死锁

276
00:10:51,240 --> 00:10:53,960
有了这几个关于死锁的讨论

277
00:10:54,000 --> 00:10:55,440
那我们在这张图里呢

278
00:10:55,480 --> 00:10:57,480
去判断它是否有死锁

279
00:10:57,520 --> 00:10:59,440
那就看刚才说的那四个条件

280
00:10:59,480 --> 00:11:00,800
是否都成立

281
00:11:00,840 --> 00:11:03,000
那这时候我们刚才那两个例子

282
00:11:03,040 --> 00:11:04,560
一个是有死锁的

283
00:11:04,600 --> 00:11:07,240
一个是没有死锁的

284
00:11:07,280 --> 00:11:08,760
好 有了这些讨论之后

285
00:11:08,800 --> 00:11:11,480
我们下边就可以来具体地讨论

286
00:11:11,520 --> 00:11:13,360
我们对付死锁到底都有一些

287
00:11:13,400 --> 00:11:14,600
什么样的处理方法

288
00:11:14,640 --> 00:11:16,720


289
00:11:16,760 --> 00:11:17,200


290
00:11:17,240 --> 00:11:17,280