0
00:00:00,000 --> 00:00:06,800


1
00:00:06,840 --> 00:00:10,360
下面我们来讨论如何用前面的

2
00:00:10,400 --> 00:00:12,480
信号量和管程的方法

3
00:00:12,520 --> 00:00:17,480
来解决几个经典的同步问题

4
00:00:17,520 --> 00:00:19,120
这就是我们这里说到的

5
00:00:19,160 --> 00:00:23,440
哲学家就餐问题和读者写者问题

6
00:00:23,480 --> 00:00:27,440
首先我们来看哲学家就餐问题

7
00:00:27,480 --> 00:00:29,560
这个问题的描述是这样的

8
00:00:29,600 --> 00:00:33,760
有五位哲学家围坐在一个圆桌旁

9
00:00:33,800 --> 00:00:36,080
这是这五位哲学家

10
00:00:36,120 --> 00:00:40,040
他们编号分别为0到4

11
00:00:40,080 --> 00:00:44,680
然后桌子上呢放了5把刀叉

12
00:00:44,720 --> 00:00:47,560
每个哲学家之间呢有一个

13
00:00:47,600 --> 00:00:49,960
那这地方纯粹是为了我们在这里

14
00:00:50,000 --> 00:00:54,400
来讨论同步互斥而设置一种场景

15
00:00:54,440 --> 00:00:56,680
在这里头呢

16
00:00:56,720 --> 00:00:59,160
每个哲学家会进行思考

17
00:00:59,200 --> 00:01:02,080
或者就餐两种操作

18
00:01:02,120 --> 00:01:06,280
那思考呢不需要周围的资源

19
00:01:06,320 --> 00:01:11,040
而就餐呢 他需要拿到两个叉子

20
00:01:11,080 --> 00:01:12,320
他才可以开始就餐

21
00:01:12,360 --> 00:01:13,280
所以这时候呢

22
00:01:13,320 --> 00:01:16,800
两个哲学家之间

23
00:01:16,840 --> 00:01:19,760
会需要共享一把叉子

24
00:01:19,800 --> 00:01:21,560
那我们可以在这儿认为呢

25
00:01:21,600 --> 00:01:22,920
这个叉子是我在这里头

26
00:01:22,960 --> 00:01:26,440
两个哲学家之间的共享资源

27
00:01:26,480 --> 00:01:28,640
在思考的时候

28
00:01:28,680 --> 00:01:32,360
哲学家会把两把叉子都放回原处

29
00:01:32,400 --> 00:01:35,240
在他旁边的哲学家就可以用

30
00:01:35,280 --> 00:01:37,440
这个叉子来进行就餐了

31
00:01:37,480 --> 00:01:41,680
好 我的问题是我如何让

32
00:01:41,720 --> 00:01:44,320
这五个哲学家能够有序的进行

33
00:01:44,360 --> 00:01:46,040
他们想进行的操作

34
00:01:46,080 --> 00:01:48,200
也就说他思考的时候

35
00:01:48,240 --> 00:01:49,400
这时候随时可以进行

36
00:01:49,440 --> 00:01:50,240
不就餐的话

37
00:01:50,280 --> 00:01:52,200
他就可以在这里进行思考

38
00:01:52,240 --> 00:01:53,240
那关键问题是

39
00:01:53,280 --> 00:01:55,480
他想就餐的时候会怎么样

40
00:01:55,520 --> 00:01:59,120
如果说相邻的两个哲学家都想就餐

41
00:01:59,160 --> 00:02:00,120
那这时候呢

42
00:02:00,160 --> 00:02:02,400
他们就需要有一个人等待

43
00:02:02,440 --> 00:02:04,000
原因在于 这时候他们俩之间

44
00:02:04,040 --> 00:02:05,120
只有一个叉子

45
00:02:05,160 --> 00:02:07,960
这个叉子只能保证一个人用

46
00:02:08,000 --> 00:02:09,000
好 这时候我们说

47
00:02:09,040 --> 00:02:11,640
用什么办法我们能解决这些问题呢

48
00:02:11,680 --> 00:02:13,240
说我在这里首先想到的

49
00:02:13,280 --> 00:02:15,240
是用信号量的办法

50
00:02:15,280 --> 00:02:17,800
那信号量的办法我如何来解决呢

51
00:02:17,840 --> 00:02:18,960
那我们在这里做法呢

52
00:02:19,000 --> 00:02:22,720
第一个方案是说我每把叉子

53
00:02:22,760 --> 00:02:26,080
算是一个资源对应着一个信号量

54
00:02:26,120 --> 00:02:28,400
那它的初值是1

55
00:02:28,440 --> 00:02:31,840
好 然后说先有一个程序的框架

56
00:02:31,880 --> 00:02:32,840
五个哲学家

57
00:02:32,880 --> 00:02:35,720
每个哲学家的ID呢这里的i

58
00:02:35,760 --> 00:02:38,920
它可能是0到4

59
00:02:38,960 --> 00:02:44,440
它可以进行两种操作 思考和就餐

60
00:02:44,480 --> 00:02:46,080
我们在这里需要考虑

61
00:02:46,120 --> 00:02:48,360
主要部分是他就餐这一部分

62
00:02:48,400 --> 00:02:50,040
就餐的时候他需要拿到

63
00:02:50,080 --> 00:02:53,760
左边的刀叉和右边的刀叉

64
00:02:53,800 --> 00:02:56,600
那这时候我们说两个P操作

65
00:02:56,640 --> 00:03:00,200
来获得他左边和右边的叉子

66
00:03:00,240 --> 00:03:04,040
如果他能获得到他就会就餐

67
00:03:04,080 --> 00:03:05,680
等他吃完之后

68
00:03:05,720 --> 00:03:09,600
他释放两边的刀叉

69
00:03:09,640 --> 00:03:12,400
整个又回来 他可以又进行思考

70
00:03:12,440 --> 00:03:13,920
那这时候的问题是

71
00:03:13,960 --> 00:03:16,440
这个算法行吗

72
00:03:16,480 --> 00:03:19,120
那在多数情况下它是没问题的

73
00:03:19,160 --> 00:03:20,240
你比如说在这里头

74
00:03:20,280 --> 00:03:22,200
我先申请左边的刀叉

75
00:03:22,240 --> 00:03:23,320
那如果申请不到

76
00:03:23,360 --> 00:03:25,480
那我再去申请右边的刀叉

77
00:03:25,520 --> 00:03:27,520
如果两边申请到我就就餐

78
00:03:27,560 --> 00:03:29,640
如果申请到一个

79
00:03:29,680 --> 00:03:32,400
旁边这个人呢已经先拿取

80
00:03:32,440 --> 00:03:34,120
我的右边的刀叉

81
00:03:34,160 --> 00:03:35,360
对于他来说是左边

82
00:03:35,400 --> 00:03:37,240
好 那也时候呢

83
00:03:37,280 --> 00:03:39,600
我就会等着他就餐完毕之后

84
00:03:39,640 --> 00:03:41,960
他放下刀叉然后进行思考的时候

85
00:03:42,000 --> 00:03:43,920
我再拿起右边刀叉

86
00:03:43,960 --> 00:03:46,920
这时候我也可以开始就餐了

87
00:03:46,960 --> 00:03:48,880
但是在一种极端的情况下

88
00:03:48,920 --> 00:03:50,400
大家可以想象

89
00:03:50,440 --> 00:03:52,200
如果五个哲学家

90
00:03:52,240 --> 00:03:53,800
他们都在同一时间

91
00:03:53,840 --> 00:03:55,040
进行相同的动作

92
00:03:55,080 --> 00:03:57,200
这时候会出现什么情况

93
00:03:57,240 --> 00:03:59,600
大家一起拿左边的刀叉

94
00:03:59,640 --> 00:04:02,360
先假定在前面所有的刀叉

95
00:04:02,400 --> 00:04:03,920
都是放在那儿的

96
00:04:03,960 --> 00:04:05,840
好 大家一起拿左边刀叉

97
00:04:05,880 --> 00:04:07,960
然后这时候都拿到左边之后

98
00:04:08,000 --> 00:04:08,960
这时候五个哲学家

99
00:04:09,000 --> 00:04:11,040
每个人拿到一个刀叉

100
00:04:11,080 --> 00:04:12,680
都是左边的对于他们来说

101
00:04:12,720 --> 00:04:14,920
好 这时候他开始拿去拿右边这个

102
00:04:14,960 --> 00:04:16,960
那这时候会出现啥情况

103
00:04:17,000 --> 00:04:19,160
每个哲学家右边都没有了

104
00:04:19,200 --> 00:04:20,520
好 那按照刚才我们约定说

105
00:04:20,560 --> 00:04:24,920
这时候等着下一个用完了我再来用

106
00:04:24,960 --> 00:04:26,200
但实际上这时候呢

107
00:04:26,240 --> 00:04:29,040
每一个人都拿到了左边的刀叉

108
00:04:29,080 --> 00:04:30,640
没有拿到右边了

109
00:04:30,680 --> 00:04:33,360
而这时候所有人呢都开始等待

110
00:04:33,400 --> 00:04:34,720
那这时候会等出结果来吗

111
00:04:34,760 --> 00:04:36,960
没有任何一个人可以开始就餐

112
00:04:37,000 --> 00:04:38,040
那这样一来的话

113
00:04:38,080 --> 00:04:40,840
所有的人都是无限期等待下去

114
00:04:40,880 --> 00:04:42,760
好 那所以这时候出现什么问题

115
00:04:42,800 --> 00:04:44,880
这个算法是不正确的

116
00:04:44,920 --> 00:04:46,600
有可能进入死锁

117
00:04:46,640 --> 00:04:48,280
也就是五个人同时

118
00:04:48,320 --> 00:04:49,720
拿左边刀叉的时候

119
00:04:49,760 --> 00:04:52,640
那它就会进入死锁状态

120
00:04:52,680 --> 00:04:56,040
好 那这个不行我怎么改呢

121
00:04:56,080 --> 00:04:58,960
那这就是我们想到的第二种做法

122
00:04:59,000 --> 00:05:00,600
极端的做法

123
00:05:00,640 --> 00:05:02,000
因为实际上在我们系统里头

124
00:05:02,040 --> 00:05:04,920
我们希望把资源得到充分的利用

125
00:05:04,960 --> 00:05:07,000
一旦我没有办法做充分利用的时候

126
00:05:07,040 --> 00:05:09,280
我就把所有资源打成一个整包

127
00:05:09,320 --> 00:05:10,880
然后说只有一个进程

128
00:05:10,920 --> 00:05:13,880
可以占用这一整包的资源

129
00:05:13,920 --> 00:05:16,600
不管它是不是都需要

130
00:05:16,640 --> 00:05:17,480
那在这种情况下

131
00:05:17,520 --> 00:05:20,640
我这个系统也能正常的运行下去

132
00:05:20,680 --> 00:05:22,440
只是效率低一些就是了

133
00:05:22,480 --> 00:05:24,120
好 那我们想到是这种做法

134
00:05:24,160 --> 00:05:26,160
我设置一个互斥变量

135
00:05:26,200 --> 00:05:27,640
我任何一个时刻

136
00:05:27,680 --> 00:05:30,640
只有一个哲学家可以就餐

137
00:05:30,680 --> 00:05:33,440
那这事呢也变得可以能解决出来

138
00:05:33,480 --> 00:05:35,240
那在这儿也是这样的

139
00:05:35,280 --> 00:05:36,480
这是思考就餐

140
00:05:36,520 --> 00:05:38,400
我需要保护就餐这一段

141
00:05:38,440 --> 00:05:40,320
我用这个 mutex

142
00:05:40,360 --> 00:05:42,680
来作为这个互斥信号量

143
00:05:42,720 --> 00:05:44,000
好 在这个地方呢

144
00:05:44,040 --> 00:05:47,480
P操作和V操作 任何一个哲学家

145
00:05:47,520 --> 00:05:51,160
他只要是申请到这个互斥信号量

146
00:05:51,200 --> 00:05:53,400
也就是我们这里说二进制信号量

147
00:05:53,440 --> 00:05:55,800
好 那这时候呢它就可以进行就餐

148
00:05:55,840 --> 00:05:57,600
因为它的初值是1

149
00:05:57,640 --> 00:05:59,040
所以任何一个时刻

150
00:05:59,080 --> 00:06:02,960
只有一个哲学家能够

151
00:06:03,000 --> 00:06:05,160
获取到这个信号量

152
00:06:05,200 --> 00:06:09,000
然后他再去依次

153
00:06:09,040 --> 00:06:12,480
拿起左边和右边的刀叉

154
00:06:12,520 --> 00:06:14,680
那这时候它会碰到障碍吗

155
00:06:14,720 --> 00:06:18,000
不会 因为这五个信号量

156
00:06:18,040 --> 00:06:19,760
你只有在申请到了

157
00:06:19,800 --> 00:06:21,240
二进制信号量之后

158
00:06:21,280 --> 00:06:23,240
你才有可能来申请到

159
00:06:23,280 --> 00:06:25,040
刀叉的信号量

160
00:06:25,080 --> 00:06:26,640
而任何一个时刻呢

161
00:06:26,680 --> 00:06:29,200
我只有一个进程

162
00:06:29,240 --> 00:06:31,840
申请到二进制信号量

163
00:06:31,880 --> 00:06:33,080
好 那这时候呢

164
00:06:33,120 --> 00:06:35,200
后面这两个申请不会碰到问题

165
00:06:35,240 --> 00:06:36,760
好 他会就餐

166
00:06:36,800 --> 00:06:39,480
吃完之后他放下刀叉

167
00:06:39,520 --> 00:06:41,840
然后释放互斥信号量

168
00:06:41,880 --> 00:06:44,640
他继续上面的思考

169
00:06:44,680 --> 00:06:46,040
那从这种做法里头呢

170
00:06:46,080 --> 00:06:49,400
我们看到 这是能够保证

171
00:06:49,440 --> 00:06:51,040
大家顺序吃饭的

172
00:06:51,080 --> 00:06:53,000
但是我这时候的情况

173
00:06:53,040 --> 00:06:54,360
是我有五把刀叉

174
00:06:54,400 --> 00:06:55,120
按道理来说

175
00:06:55,160 --> 00:06:57,040
我可以给两个人一起吃

176
00:06:57,080 --> 00:07:01,440
因为总会剩一把刀叉在那儿放着

177
00:07:01,480 --> 00:07:02,680
而我们现在这里头呢

178
00:07:02,720 --> 00:07:04,280
我只要他一个人吃

179
00:07:04,320 --> 00:07:08,000
好 那这样话它的效率就降低了

180
00:07:08,040 --> 00:07:10,760
但是它是正确的

181
00:07:10,800 --> 00:07:15,760
这种做法呢我们认为它可以接受

182
00:07:15,800 --> 00:07:17,800
但是性能不好

183
00:07:17,840 --> 00:07:20,800
我们有没有更好的办法

184
00:07:20,840 --> 00:07:23,000
好 那这时候我们说

185
00:07:23,040 --> 00:07:25,240
再给出第三种解决方案

186
00:07:25,280 --> 00:07:27,200
我仍然是用五把刀叉

187
00:07:27,240 --> 00:07:30,320
但是我不会设一个全局的锁

188
00:07:30,360 --> 00:07:32,720
把整个就餐这事

189
00:07:32,760 --> 00:07:35,240
变成一个临界区的操作

190
00:07:35,280 --> 00:07:36,600
那我怎么办呢

191
00:07:36,640 --> 00:07:38,320
针对我们刚才说到的

192
00:07:38,360 --> 00:07:41,800
五个哲学家一起拿起左边的刀叉

193
00:07:41,840 --> 00:07:43,920
之后所面临的死锁的情况

194
00:07:43,960 --> 00:07:45,400
我让他们每个人

195
00:07:45,440 --> 00:07:47,560
拿刀叉的时候有差异

196
00:07:47,600 --> 00:07:49,240
不至于是所有的人

197
00:07:49,280 --> 00:07:51,320
全部都一起拿起左边的

198
00:07:51,360 --> 00:07:52,440
那这样一来的话就

199
00:07:52,480 --> 00:07:55,080
不会出现构成环路的情况

200
00:07:55,120 --> 00:07:56,400
那总会有先有后

201
00:07:56,440 --> 00:07:58,800
好 最后保证大家都能拿到

202
00:07:58,840 --> 00:08:00,280
那在通常情况下呢

203
00:08:00,320 --> 00:08:02,480
我可以两个人一起就餐

204
00:08:02,520 --> 00:08:03,800
那在这儿怎么做呢

205
00:08:03,840 --> 00:08:08,080
好 我在这儿设一个分支结构

206
00:08:08,120 --> 00:08:10,200
如果说根据每个人的编号不同

207
00:08:10,240 --> 00:08:13,440
我采取不同的动作

208
00:08:13,480 --> 00:08:14,600
偶数编号的

209
00:08:14,640 --> 00:08:17,360
我先拿左边后拿右边

210
00:08:17,400 --> 00:08:20,400
奇数的先拿右边后拿左边

211
00:08:20,440 --> 00:08:21,520
那这样一来的话

212
00:08:21,560 --> 00:08:23,400
就不会出现五个都拿到

213
00:08:23,440 --> 00:08:26,520
一部分资源构成环路这种情况

214
00:08:26,560 --> 00:08:28,760
好 那等他就餐完了之后

215
00:08:28,800 --> 00:08:30,280
我把刀叉放回去

216
00:08:30,320 --> 00:08:32,520
那这时候我有必要再在这个地方

217
00:08:32,560 --> 00:08:34,880
再把它分成两种情况吗

218
00:08:34,920 --> 00:08:36,840
实际上这个操作它是不会堵塞的

219
00:08:36,880 --> 00:08:39,240
所以你不用把它分成两种情况

220
00:08:39,280 --> 00:08:40,360
好 那么这时候说

221
00:08:40,400 --> 00:08:41,560
在这种情况下我可以

222
00:08:41,600 --> 00:08:44,840
两个哲学家同时就餐吗

223
00:08:44,880 --> 00:08:48,920
你比如说0号和2号

224
00:08:48,960 --> 00:08:50,680
假定这时候没有其他人的话

225
00:08:50,720 --> 00:08:53,000
那他们俩是可以的

226
00:08:53,040 --> 00:08:54,520
因为中间隔了一个哲学家

227
00:08:54,560 --> 00:08:55,800
好 那这时候他们俩

228
00:08:55,840 --> 00:08:58,040
都可以拿到相应的叉子

229
00:08:58,080 --> 00:08:59,800
他不断是正确的

230
00:08:59,840 --> 00:09:00,880
不会出现死锁

231
00:09:00,920 --> 00:09:03,360
并且允许 有可能的话

232
00:09:03,400 --> 00:09:05,600
两个人同时就餐

233
00:09:05,640 --> 00:09:06,920
这是我们在这里呢

234
00:09:06,960 --> 00:09:08,640
用信号量能给出的

235
00:09:08,680 --> 00:09:10,840
一种比较理想的办法

236
00:09:10,880 --> 00:09:11,600
那这时候问

237
00:09:11,640 --> 00:09:13,440
这种做法是不是最优的呢

238
00:09:13,480 --> 00:09:14,160
我是不是可以

239
00:09:14,200 --> 00:09:16,320
还想得出更好的办法呢

240
00:09:16,360 --> 00:09:17,640
这个呢留给大家

241
00:09:17,680 --> 00:09:19,040
下去之后进行思考

242
00:09:19,080 --> 00:09:19,120