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


1
00:00:06,960 --> 00:00:08,960
下面我们通过一个

2
00:00:09,000 --> 00:00:10,600
生活当中的例子

3
00:00:10,640 --> 00:00:13,840
来说明同步的问题

4
00:00:13,880 --> 00:00:18,040
和相应的解决办法

5
00:00:18,080 --> 00:00:21,040
在计算机里头和生活当中呢

6
00:00:21,080 --> 00:00:21,960
实际上有些问题

7
00:00:22,000 --> 00:00:23,840
我们是可以来进行类比的

8
00:00:23,880 --> 00:00:25,280
这种类比的办法呢

9
00:00:25,320 --> 00:00:27,680
可以我们利用生活当中的常识

10
00:00:27,720 --> 00:00:29,200
来帮助我们理解

11
00:00:29,240 --> 00:00:31,560
操作系统当中的同步问题

12
00:00:31,600 --> 00:00:33,320
当然你在做这件事情时候

13
00:00:33,360 --> 00:00:34,400
也需要想到

14
00:00:34,440 --> 00:00:37,680
计算机和人之间的一些区别

15
00:00:37,720 --> 00:00:41,400
比如说我们在进行协调的时候

16
00:00:41,440 --> 00:00:42,880
我们人的一些假设前提

17
00:00:42,920 --> 00:00:44,600
和计算机是不一样的

18
00:00:44,640 --> 00:00:45,400
所以这时候呢

19
00:00:45,440 --> 00:00:47,560
他们的处理也会不一样

20
00:00:47,600 --> 00:00:49,840
好 我们先看一个例子

21
00:00:49,880 --> 00:00:53,480
这是一个家庭采购的例子

22
00:00:53,520 --> 00:00:54,800
说一家里头

23
00:00:54,840 --> 00:00:56,040
我们冰箱里头

24
00:00:56,080 --> 00:00:58,120
放有各种各样的食品

25
00:00:58,160 --> 00:00:59,160
好 那这时候问

26
00:00:59,200 --> 00:01:01,920
如果说冰箱里东西吃完了

27
00:01:01,960 --> 00:01:02,960
那这时候怎么办

28
00:01:03,000 --> 00:01:04,760
那家里的成员会说

29
00:01:04,800 --> 00:01:08,680
我去看冰箱里有没有面包

30
00:01:08,720 --> 00:01:10,320
如果没有

31
00:01:10,360 --> 00:01:12,840
那我就离开家去商店去买

32
00:01:12,880 --> 00:01:14,240
那到达商店之后

33
00:01:14,280 --> 00:01:16,720
买完再回来把它放进冰箱里头

34
00:01:16,760 --> 00:01:17,840
这件事情就算行了

35
00:01:17,880 --> 00:01:20,040
我想我们很多家庭里呢

36
00:01:20,080 --> 00:01:21,760
都是这样安排的

37
00:01:21,800 --> 00:01:23,560
但是在实际生活当中

38
00:01:23,600 --> 00:01:26,080
我们也可能会出现这种情况

39
00:01:26,120 --> 00:01:27,560
第二个人进来之后

40
00:01:27,600 --> 00:01:29,120
由于时间错开一点

41
00:01:29,160 --> 00:01:32,680
头一个人在去商店的路上

42
00:01:32,720 --> 00:01:34,440
第二个人呢开始看冰箱

43
00:01:34,480 --> 00:01:36,040
这时候他们俩没打照面

44
00:01:36,080 --> 00:01:36,840
当然你说我们俩

45
00:01:36,880 --> 00:01:38,880
去同一个商店买的路上会碰到

46
00:01:38,920 --> 00:01:40,000
那这事没有了

47
00:01:40,040 --> 00:01:41,200
但是每家基本上

48
00:01:41,240 --> 00:01:42,240
都会碰到过这种情况

49
00:01:42,280 --> 00:01:43,680
我买重的时候

50
00:01:43,720 --> 00:01:45,520
好 那这样的话这种情况

51
00:01:45,560 --> 00:01:47,320
我们怎么解决

52
00:01:47,360 --> 00:01:48,960
那你说我在家里通常情况下

53
00:01:49,000 --> 00:01:51,160
很少量的几次重复

54
00:01:51,200 --> 00:01:52,600
我们是可以接受的

55
00:01:52,640 --> 00:01:54,000
但是对于计算机来说

56
00:01:54,040 --> 00:01:56,920
这件事情是不好办的

57
00:01:56,960 --> 00:01:58,040
我们怎么能够把

58
00:01:58,080 --> 00:02:00,000
这件事情的协调做得

59
00:02:00,040 --> 00:02:02,360
很成功和高效

60
00:02:02,400 --> 00:02:03,520
那这时候呢

61
00:02:03,560 --> 00:02:04,600
就有这样几个条件

62
00:02:04,640 --> 00:02:07,280
一呢是冰箱里头没有面包之后

63
00:02:07,320 --> 00:02:08,840
我必须有人去买

64
00:02:08,880 --> 00:02:11,320
就说有人看到冰箱里没有了

65
00:02:11,360 --> 00:02:13,000
那他就会去买

66
00:02:13,040 --> 00:02:14,240
第二个呢是说

67
00:02:14,280 --> 00:02:16,560
我最多只能一个人去买

68
00:02:16,600 --> 00:02:19,440
因为如果说多个人一块去买的话

69
00:02:19,480 --> 00:02:20,840
这时就会买重

70
00:02:20,880 --> 00:02:22,280
那怎么解决这个问题呢

71
00:02:22,320 --> 00:02:25,840
那说 这是一种很极端的做法

72
00:02:25,880 --> 00:02:29,240
说我在冰箱上加一锁并且有一钥匙

73
00:02:29,280 --> 00:02:31,880
那买之前呢我把冰箱锁上

74
00:02:31,920 --> 00:02:33,360
然后我回来放进去之后

75
00:02:33,400 --> 00:02:34,680
我再把它打开

76
00:02:34,720 --> 00:02:35,520
好这样一来的话

77
00:02:35,560 --> 00:02:38,320
第二个人来看冰箱已经锁上了

78
00:02:38,360 --> 00:02:40,520
那这时候呢他就不会再去买

79
00:02:40,560 --> 00:02:41,440
那这时候说

80
00:02:41,480 --> 00:02:43,040
这种解决办法好像

81
00:02:43,080 --> 00:02:45,280
在我们生活当中不会这样做

82
00:02:45,320 --> 00:02:46,840
那比如说这里这种情况

83
00:02:46,880 --> 00:02:49,000
你把冰箱锁上仅仅是为了面包

84
00:02:49,040 --> 00:02:50,280
实际上冰箱里还有别的东西

85
00:02:50,320 --> 00:02:52,280
那别人想取别的食品的时候

86
00:02:52,320 --> 00:02:53,840
那它也取不出来了

87
00:02:53,880 --> 00:02:54,960
所以这种做法呢

88
00:02:55,000 --> 00:02:57,000
对于我们来说是不恰当的

89
00:02:57,040 --> 00:02:58,080
那我们需要在这里呢

90
00:02:58,120 --> 00:02:59,760
来讲解决办法

91
00:02:59,800 --> 00:03:01,280
我们怎么来做呢

92
00:03:01,320 --> 00:03:02,800
首先想到的一个办法呢

93
00:03:02,840 --> 00:03:04,960
是在冰箱上贴一便签

94
00:03:05,000 --> 00:03:06,800
然后用这个便签呢

95
00:03:06,840 --> 00:03:09,440
表示有人去买面包去了

96
00:03:09,480 --> 00:03:12,040
其他的人看到这个便签之后

97
00:03:12,080 --> 00:03:13,960
他就不会再去买了

98
00:03:14,000 --> 00:03:15,360
这一种做法

99
00:03:15,400 --> 00:03:17,680
我们把它比较具体地描述出来

100
00:03:17,720 --> 00:03:18,920
就是采购之前

101
00:03:18,960 --> 00:03:20,960
我留下一张便签

102
00:03:21,000 --> 00:03:24,120
完成采购之后我把便签去掉

103
00:03:24,160 --> 00:03:25,720
那别人看到便签的时候呢

104
00:03:25,760 --> 00:03:27,720
他就不去买了

105
00:03:27,760 --> 00:03:30,680
这是我们的自然语言描述

106
00:03:30,720 --> 00:03:34,320
然后我们把它变成伪代码的形式

107
00:03:34,360 --> 00:03:35,600
就是这样的

108
00:03:35,640 --> 00:03:37,920
先检查是否有面包

109
00:03:37,960 --> 00:03:42,080
然后检查是否有别人留下的便签

110
00:03:42,120 --> 00:03:44,960
然后如果没有的话我就留下便签

111
00:03:45,000 --> 00:03:46,600
然后去买面包

112
00:03:46,640 --> 00:03:48,520
然后把便签去掉

113
00:03:48,560 --> 00:03:50,080
整个过程结束

114
00:03:50,120 --> 00:03:51,400
那这时的问题是说

115
00:03:51,440 --> 00:03:54,120
如果用计算机来执行

116
00:03:54,160 --> 00:03:58,040
这段代码它有效吗

117
00:03:58,080 --> 00:04:02,040
那我们在这里呢说它会有麻烦

118
00:04:02,080 --> 00:04:05,520
仍然是偶尔会出现买多了情况

119
00:04:05,560 --> 00:04:07,960
那什么情况下会出现买多呢

120
00:04:08,000 --> 00:04:13,200
说 检查面包和检查便签之后

121
00:04:13,240 --> 00:04:15,040
在你贴便签之前

122
00:04:15,080 --> 00:04:16,960
如果有其他的人来

123
00:04:17,000 --> 00:04:18,840
检查面包和便签的话

124
00:04:18,880 --> 00:04:20,320
那这时候它也是没有的

125
00:04:20,360 --> 00:04:20,920
好 这时候呢

126
00:04:20,960 --> 00:04:22,680
就会出现两个人一块去买

127
00:04:22,720 --> 00:04:24,240
那你说在生活当中

128
00:04:24,280 --> 00:04:26,600
我检查便签有没有和

129
00:04:26,640 --> 00:04:28,240
往上贴便签这件事情

130
00:04:28,280 --> 00:04:29,480
两个是挨着的

131
00:04:29,520 --> 00:04:30,840
如果另外一个人来检查的话

132
00:04:30,880 --> 00:04:32,360
我们会看到

133
00:04:32,400 --> 00:04:34,080
但是把它放到

134
00:04:34,120 --> 00:04:35,520
计算机程序里来运行的时候呢

135
00:04:35,560 --> 00:04:37,880
你两个进程交替执行

136
00:04:37,920 --> 00:04:39,440
检查和后面的设置

137
00:04:39,480 --> 00:04:42,200
它俩是没办法做到这一点的

138
00:04:42,240 --> 00:04:42,840
所以在这儿呢

139
00:04:42,880 --> 00:04:43,600
这在生活当中

140
00:04:43,640 --> 00:04:45,720
这种做法就是有效的

141
00:04:45,760 --> 00:04:46,880
而在计算机里呢

142
00:04:46,920 --> 00:04:49,800
这种做法就是会有麻烦的

143
00:04:49,840 --> 00:04:52,720
好 我们下面具体来看一下这个麻烦

144
00:04:52,760 --> 00:04:55,680
首先是两个进程A和B

145
00:04:55,720 --> 00:04:58,320
第一个呢做检查

146
00:04:58,360 --> 00:04:59,920
检查是否有面包

147
00:04:59,960 --> 00:05:02,560
检查是否有人贴便签

148
00:05:02,600 --> 00:05:05,200
然后这时候呢做了进程切换

149
00:05:05,240 --> 00:05:07,600
切换到另一个进程B

150
00:05:07,640 --> 00:05:09,640
它检查有没有面包

151
00:05:09,680 --> 00:05:11,040
检查有没有便签

152
00:05:11,080 --> 00:05:12,960
这两个进程的检查结果

153
00:05:13,000 --> 00:05:15,440
都是没有面包没有便签

154
00:05:15,480 --> 00:05:17,320
好 那这时候它们会做什么

155
00:05:17,360 --> 00:05:19,120
那都会去采购

156
00:05:19,160 --> 00:05:21,360
好 这时候又切回到A

157
00:05:21,400 --> 00:05:24,600
它就留下一个便签然后去买面包

158
00:05:24,640 --> 00:05:28,000
好 然后这边呢

159
00:05:28,040 --> 00:05:30,400
也留下一个便签也去买面包

160
00:05:30,440 --> 00:05:33,640
这时候我们看到有啥麻烦了

161
00:05:33,680 --> 00:05:37,760
这两个都会买重复的面包

162
00:05:37,800 --> 00:05:39,960
那你说在这里头你这么切换

163
00:05:40,000 --> 00:05:42,840
这两者之间这个间距

164
00:05:42,880 --> 00:05:45,640
是我们在生活当中碰不到的

165
00:05:45,680 --> 00:05:47,200
或者说很少碰到的

166
00:05:47,240 --> 00:05:49,680
好 那在这儿呢他就会出现

167
00:05:49,720 --> 00:05:53,200
所以这个地方有问题

168
00:05:53,240 --> 00:05:56,040
因为它会有间歇性的麻烦

169
00:05:56,080 --> 00:05:57,280
而这种错误呢

170
00:05:57,320 --> 00:05:58,760
它并不是在所有情况下

171
00:05:58,800 --> 00:05:59,960
每次运行都会有

172
00:06:00,000 --> 00:06:01,800
它会很难调试

173
00:06:01,840 --> 00:06:03,200
并且这时候你需要知道

174
00:06:03,240 --> 00:06:04,000
我在什么地方

175
00:06:04,040 --> 00:06:06,560
可能会出现调度

176
00:06:06,600 --> 00:06:09,280
所以这种方案呢是我们不理想的

177
00:06:09,320 --> 00:06:10,360
那这时候我们怎么办呢

178
00:06:10,400 --> 00:06:12,000
第二种做法说

179
00:06:12,040 --> 00:06:14,120
我把便签挪到前面去贴

180
00:06:14,160 --> 00:06:16,480
我先贴上便签然后再来检查

181
00:06:16,520 --> 00:06:18,320
这时候是不是就没问题了

182
00:06:18,360 --> 00:06:22,480
好 那我们把这件事情也转换成代码

183
00:06:22,520 --> 00:06:24,480
贴便签一前一后

184
00:06:24,520 --> 00:06:26,120
中间做检查

185
00:06:26,160 --> 00:06:28,080
没有之后去买面包

186
00:06:28,120 --> 00:06:29,760
这种做法行得通吗

187
00:06:29,800 --> 00:06:35,360
好 我们也来看具体的一种可能性

188
00:06:35,400 --> 00:06:39,040
贴便签 切换 再贴便签

189
00:06:39,080 --> 00:06:40,840
这时候大家就已经会

190
00:06:40,880 --> 00:06:42,520
察觉到一个问题

191
00:06:42,560 --> 00:06:44,520
两个都贴便签之后

192
00:06:44,560 --> 00:06:48,120
那么不管你怎么切换

193
00:06:48,160 --> 00:06:51,240
它都会检查有没有面包

194
00:06:51,280 --> 00:06:52,960
没有 或者是有

195
00:06:53,000 --> 00:06:54,400
好有没有便签

196
00:06:54,440 --> 00:06:56,160
他会检查有便签

197
00:06:56,200 --> 00:06:58,840
好 那他就不会去买面包了

198
00:06:58,880 --> 00:07:00,720
好 这边呢也是一样的

199
00:07:00,760 --> 00:07:01,960
检查有便签

200
00:07:02,000 --> 00:07:03,320
他也不会去买面包了

201
00:07:03,360 --> 00:07:06,840
好 那等到你最后一个回来

202
00:07:06,880 --> 00:07:10,840
这时候会出现什么情况

203
00:07:10,880 --> 00:07:13,600
我们这两个买面包的动作

204
00:07:13,640 --> 00:07:15,320
没有任何一个进程执行

205
00:07:15,360 --> 00:07:16,480
他们都出来了

206
00:07:16,520 --> 00:07:18,200
这时候我冰箱里也没有面包

207
00:07:18,240 --> 00:07:19,520
好 这时候我们就找到了

208
00:07:19,560 --> 00:07:21,720
一种情况它会失败

209
00:07:21,760 --> 00:07:25,160
那这时候呢会出现什么情况

210
00:07:25,200 --> 00:07:26,440
谁也不会去买面包

211
00:07:26,480 --> 00:07:28,200
那这样就没面包了

212
00:07:28,240 --> 00:07:29,560
好 说你把这个便签

213
00:07:29,600 --> 00:07:31,400
挪到前边来也不行

214
00:07:31,440 --> 00:07:33,240
刚才我们说放到后面不行了

215
00:07:33,280 --> 00:07:34,200
挪到前面也不行

216
00:07:34,240 --> 00:07:34,920
那这时候是啥呢

217
00:07:34,960 --> 00:07:36,800
说你检查便签的时候

218
00:07:36,840 --> 00:07:39,480
没有区分到底是谁留下的便签

219
00:07:39,520 --> 00:07:40,600
甚至于这种情况

220
00:07:40,640 --> 00:07:42,640
只有你自己在执行的时候

221
00:07:42,680 --> 00:07:45,200
他也没法买回面包来

222
00:07:45,240 --> 00:07:47,120
好 那说 我们在这里怎么办呢

223
00:07:47,160 --> 00:07:52,120
我们把便签做得更准确一些

224
00:07:52,160 --> 00:07:54,040
A留的便签和B留的便签

225
00:07:54,080 --> 00:07:55,160
我是不一样的

226
00:07:55,200 --> 00:07:56,120
好 那这时候呢

227
00:07:56,160 --> 00:07:58,560
就转到我们的第三种方案

228
00:07:58,600 --> 00:08:00,280
第三种方案呢

229
00:08:00,320 --> 00:08:02,720
是在便签上加上标记

230
00:08:02,760 --> 00:08:06,360
以区别这个便签到底是谁留下的

231
00:08:06,400 --> 00:08:08,720
这样的话我只检查对方的便签

232
00:08:08,760 --> 00:08:09,680
那这时候呢

233
00:08:09,720 --> 00:08:12,760
我们给出相应的代码

234
00:08:12,800 --> 00:08:14,080
那我们仍然是在

235
00:08:14,120 --> 00:08:18,840
检查之前留便签 两边

236
00:08:18,880 --> 00:08:20,880
留便签呢便签上有标记

237
00:08:20,920 --> 00:08:23,400
那从这里我们写伪码上来说呢

238
00:08:23,440 --> 00:08:24,960
这两边的代码已经不一样了

239
00:08:25,000 --> 00:08:28,000
但实际上如果说你加上相应的数组

240
00:08:28,040 --> 00:08:29,680
并且用数组下标

241
00:08:29,720 --> 00:08:31,400
作为你这个进程标识的话

242
00:08:31,440 --> 00:08:32,320
那这个地方的代码呢

243
00:08:32,360 --> 00:08:34,400
仍然可以写成是一样的

244
00:08:34,440 --> 00:08:35,680
好 在这种情况下

245
00:08:35,720 --> 00:08:38,120
留下便签检查是否有对方的便签

246
00:08:38,160 --> 00:08:40,000
如果没有检查是否有面包

247
00:08:40,040 --> 00:08:42,080
如果没有面包那我去买面包

248
00:08:42,120 --> 00:08:43,280
两边都是这样

249
00:08:43,320 --> 00:08:44,360
好 那这时候说

250
00:08:44,400 --> 00:08:47,360
这个做法能行得通吗

251
00:08:47,400 --> 00:08:50,320
好 我们看一个实际的情况

252
00:08:50,360 --> 00:08:51,680
在这里呢大家

253
00:08:51,720 --> 00:08:53,480
第一个进程先留下便签

254
00:08:53,520 --> 00:08:55,200
然后第二个进程留下便签

255
00:08:55,240 --> 00:08:57,200
我们看这种极端的情况

256
00:08:57,240 --> 00:08:58,960
它会是什么样的结果

257
00:08:59,000 --> 00:09:00,720
切回去这边再来

258
00:09:00,760 --> 00:09:01,920
执行这个代码的时候

259
00:09:01,960 --> 00:09:04,640
因为他已经有了对方的便签

260
00:09:04,680 --> 00:09:07,200
那这时候他不会去检查是否有面包

261
00:09:07,240 --> 00:09:08,720
然后直接出来了

262
00:09:08,760 --> 00:09:10,120
好 那这时候说

263
00:09:10,160 --> 00:09:11,760
到这边的时候呢

264
00:09:11,800 --> 00:09:13,760
他检查是否有对方的便签

265
00:09:13,800 --> 00:09:17,480
那有 那他也不会检查是否有面包

266
00:09:17,520 --> 00:09:18,520
好 那这样一来的话

267
00:09:18,560 --> 00:09:21,200
实际上两边都没有去检查

268
00:09:21,240 --> 00:09:23,880
是否有面包就直接出来了

269
00:09:23,920 --> 00:09:27,000
好 那这时候说会出现啥情况

270
00:09:27,040 --> 00:09:29,680
实际上大家都留下便签

271
00:09:29,720 --> 00:09:30,600
并且我这便签上

272
00:09:30,640 --> 00:09:32,440
也能区分出是谁留的

273
00:09:32,480 --> 00:09:34,360
但是这时候呢

274
00:09:34,400 --> 00:09:37,400
由于我留便签的时候是说你要去买

275
00:09:37,440 --> 00:09:40,800
双方都认为对方去买

276
00:09:40,840 --> 00:09:42,000
好 这时候麻烦就出来了

277
00:09:42,040 --> 00:09:43,560
这时候谁也没买

278
00:09:43,600 --> 00:09:45,680
好 那这时候怎么办呢

279
00:09:45,720 --> 00:09:49,000
那我们说我们再来做一个调整

280
00:09:49,040 --> 00:09:51,280
我在这里头呢

281
00:09:51,320 --> 00:09:56,040
这边A和B我们代码做了一些修改

282
00:09:56,080 --> 00:09:57,320
然后说你在这里头呢

283
00:09:57,360 --> 00:09:59,360
其中一个进程

284
00:09:59,400 --> 00:10:01,560
在检查到对方有便签之后

285
00:10:01,600 --> 00:10:04,280
那我就重复的检查

286
00:10:04,320 --> 00:10:06,480
一直到对方没有便签了

287
00:10:06,520 --> 00:10:08,080
而另一个进程呢

288
00:10:08,120 --> 00:10:10,920
仍然跟前面的做法是一样的

289
00:10:10,960 --> 00:10:12,560
跟我们前面方案3

290
00:10:12,600 --> 00:10:14,640
好 那这个办法能行吗

291
00:10:14,680 --> 00:10:17,200
那我们来解释一下看看

292
00:10:17,240 --> 00:10:21,320
他到底在什么情况下是行得通的

293
00:10:21,360 --> 00:10:23,840
比如说我们仍然是刚才那种情况

294
00:10:23,880 --> 00:10:26,560
前一个进程留下便签

295
00:10:26,600 --> 00:10:27,960
第二个进程留下便签

296
00:10:28,000 --> 00:10:30,240
然后两边进行检查

297
00:10:30,280 --> 00:10:31,720
那在前面程序里呢

298
00:10:31,760 --> 00:10:33,920
后边这个检查有对方的便签

299
00:10:33,960 --> 00:10:35,520
它就直接走掉了

300
00:10:35,560 --> 00:10:37,440
那这个时候呢由于两边不一样

301
00:10:37,480 --> 00:10:39,960
我头一个在检查的时候

302
00:10:40,000 --> 00:10:41,880
他检查对方留有便签

303
00:10:41,920 --> 00:10:43,360
这时候我不是走掉

304
00:10:43,400 --> 00:10:45,040
而是在这儿一直等待

305
00:10:45,080 --> 00:10:47,480
一直等到B把便签撤掉

306
00:10:47,520 --> 00:10:49,360
那我会在这儿

307
00:10:49,400 --> 00:10:51,640
好 等到B把便签撤掉的时候呢

308
00:10:51,680 --> 00:10:53,720
我们刚才说如果说这个B

309
00:10:53,760 --> 00:10:56,400
留下便签的时候在它的前面

310
00:10:56,440 --> 00:10:59,440
那这时候呢他会看到A留有便签

311
00:10:59,480 --> 00:11:01,080
所以他直接走掉了

312
00:11:01,120 --> 00:11:03,320
那这时候呢他检查一下

313
00:11:03,360 --> 00:11:05,440
然后看有A的便签

314
00:11:05,480 --> 00:11:07,200
那他就直接走掉了

315
00:11:07,240 --> 00:11:08,720
好 他没有去买面包

316
00:11:08,760 --> 00:11:10,840
而这时候呢A呢

317
00:11:10,880 --> 00:11:14,480
由于一直等到B离开 好

318
00:11:14,520 --> 00:11:17,080
检查完了之后说那这时候离开了

319
00:11:17,120 --> 00:11:17,920
B没有去买

320
00:11:17,960 --> 00:11:20,120
那这时候他再去看是否有面包

321
00:11:20,160 --> 00:11:21,600
没面包他去买

322
00:11:21,640 --> 00:11:23,000
那这样的话在这种情况下

323
00:11:23,040 --> 00:11:25,240
他是能够回来的

324
00:11:25,280 --> 00:11:26,120
好 那这时候我们看到

325
00:11:26,160 --> 00:11:27,280
这两个进程呢

326
00:11:27,320 --> 00:11:29,160
它的代码是不一样了

327
00:11:29,200 --> 00:11:31,520
这时候我也没办法换方式

328
00:11:31,560 --> 00:11:33,040
让它俩写成完全一样

329
00:11:33,080 --> 00:11:34,000
那这时候问

330
00:11:34,040 --> 00:11:35,760
我们刚才那种情况

331
00:11:35,800 --> 00:11:37,360
它能够避免掉了

332
00:11:37,400 --> 00:11:39,640
它还会再有别的问题吗

333
00:11:39,680 --> 00:11:41,480
好 实际上在这里头呢

334
00:11:41,520 --> 00:11:43,880
我们需要把它所有可能

335
00:11:43,920 --> 00:11:46,640
这种切换的组合都想一遍

336
00:11:46,680 --> 00:11:48,360
想清楚每一种情况

337
00:11:48,400 --> 00:11:50,480
它都能通过的话

338
00:11:50,520 --> 00:11:52,120
枚举完 那这件事情呢

339
00:11:52,160 --> 00:11:53,480
它就能通过了

340
00:11:53,520 --> 00:11:54,800
那这时候实际上我们在做

341
00:11:54,840 --> 00:11:56,360
同步互斥问题的时候

342
00:11:56,400 --> 00:11:59,320
很多时候是需要很仔细去想

343
00:11:59,360 --> 00:12:01,680
像这种分的情况

344
00:12:01,720 --> 00:12:02,480
你比如说在这里头

345
00:12:02,520 --> 00:12:04,320
我们会关键想哪条呢

346
00:12:04,360 --> 00:12:06,720
一个是什么时间留便签

347
00:12:06,760 --> 00:12:09,040
你比如说一边留便签

348
00:12:09,080 --> 00:12:11,520
另一边没有参与这件事情

349
00:12:11,560 --> 00:12:15,080
那这时候说我检查是否留下便签

350
00:12:15,120 --> 00:12:17,120
是否检查对放有没有便签

351
00:12:17,160 --> 00:12:18,200
对方不存在

352
00:12:18,240 --> 00:12:19,360
好 那这时候呢

353
00:12:19,400 --> 00:12:21,000
他就直接检查有没有面包

354
00:12:21,040 --> 00:12:22,080
他自己就会去买

355
00:12:22,120 --> 00:12:23,520
所以你只有一个进程

356
00:12:23,560 --> 00:12:25,080
A运行的时候没有问题

357
00:12:25,120 --> 00:12:26,600
能正常买回面包来

358
00:12:26,640 --> 00:12:29,200
好 只有一个B呢也能行

359
00:12:29,240 --> 00:12:32,040
好 那实际上我们重点需要关心的是

360
00:12:32,080 --> 00:12:33,920
这两个他们之间检查的时候

361
00:12:33,960 --> 00:12:35,840
留便签的时候有交互

362
00:12:35,880 --> 00:12:40,000
一种是说B在A之前

363
00:12:40,040 --> 00:12:42,040
那B在A之前的话

364
00:12:42,080 --> 00:12:44,360
那他在这儿留便签的时候呢

365
00:12:44,400 --> 00:12:47,040
这个B有可能留下便签之后

366
00:12:47,080 --> 00:12:49,360
他检查没有A的便签

367
00:12:49,400 --> 00:12:50,720
好 或者说刚好检查有

368
00:12:50,760 --> 00:12:54,400
好 刚好检查B没有便签的时候

369
00:12:54,440 --> 00:12:55,840
A没有留下便签的时候

370
00:12:55,880 --> 00:12:58,040
那这时候呢他会去买面包

371
00:12:58,080 --> 00:12:58,920
买面包的话

372
00:12:58,960 --> 00:13:00,400
A再来检查在中间

373
00:13:00,440 --> 00:13:01,920
在这个之后某个时间

374
00:13:01,960 --> 00:13:03,240
他会检查B如果这时候

375
00:13:03,280 --> 00:13:06,120
正在买的过程当中他会等到这儿

376
00:13:06,160 --> 00:13:07,520
等完结束之后呢

377
00:13:07,560 --> 00:13:09,080
后面再来检查的时候

378
00:13:09,120 --> 00:13:10,600
那这边已经有面包了

379
00:13:10,640 --> 00:13:11,480
他不会去买

380
00:13:11,520 --> 00:13:13,720
所以这种情况也是行的

381
00:13:13,760 --> 00:13:17,840
好 那这时候说我这个B在A之后

382
00:13:17,880 --> 00:13:21,640
并且是在你检查完之后

383
00:13:21,680 --> 00:13:24,200
你比如我检查这个B没有留下便签

384
00:13:24,240 --> 00:13:25,800
我就怎么去看有没有面包

385
00:13:25,840 --> 00:13:29,320
如果这时候B在这儿留下自己便签

386
00:13:29,360 --> 00:13:30,680
情况会是什么样

387
00:13:30,720 --> 00:13:32,120
大家可以仔细去想想

388
00:13:32,160 --> 00:13:33,240
那我们说通过

389
00:13:33,280 --> 00:13:35,080
各种各样的情况组合到一起

390
00:13:35,120 --> 00:13:37,760
那这件事情是没有问题的

391
00:13:37,800 --> 00:13:39,000
那这时候问

392
00:13:39,040 --> 00:13:40,960
这个做法怎么样

393
00:13:41,000 --> 00:13:42,760
好像枚举的情况很多

394
00:13:42,800 --> 00:13:44,680
我们想起来很不容易

395
00:13:44,720 --> 00:13:45,880
所以这件事情呢

396
00:13:45,920 --> 00:13:48,080
它是有效的 但是很复杂

397
00:13:48,120 --> 00:13:51,800
你很难去验证它的有效性

398
00:13:51,840 --> 00:13:53,960
这时候说 我们这样做之后

399
00:13:54,000 --> 00:13:56,320
它的麻烦是两头代码不一样

400
00:13:56,360 --> 00:13:58,240
略微有一点不一样的时候

401
00:13:58,280 --> 00:14:00,160
它结果就会差很远

402
00:14:00,200 --> 00:14:01,800
好 那如果说我有更多的进程

403
00:14:01,840 --> 00:14:02,960
这事怎么干

404
00:14:03,000 --> 00:14:05,400
哦 一想这个问题好像更复杂

405
00:14:05,440 --> 00:14:07,480
还有一个问题是

406
00:14:07,520 --> 00:14:12,440
A他必须在中间要反复的去查

407
00:14:12,480 --> 00:14:14,320
这时候呢他不能干别的

408
00:14:14,360 --> 00:14:16,880
就好比说我们要去打电话找一个人

409
00:14:16,920 --> 00:14:18,640
我打完电话之后不在

410
00:14:18,680 --> 00:14:20,200
那我再去一次

411
00:14:20,240 --> 00:14:22,920
在我们这里呢称之为叫忙等待

412
00:14:22,960 --> 00:14:25,360
那这种呢他是要占用CPU的

413
00:14:25,400 --> 00:14:27,240
好 这也是他的问题

414
00:14:27,280 --> 00:14:28,080
那这时候说

415
00:14:28,120 --> 00:14:29,720
我们是不是有更有效的办法

416
00:14:29,760 --> 00:14:31,560
好 那我们在这儿呢

417
00:14:31,600 --> 00:14:33,040
我们给出一种假定

418
00:14:33,080 --> 00:14:36,360
假定我能用原子操作实现一个锁

419
00:14:36,400 --> 00:14:37,920
那我们这事就好做了

420
00:14:37,960 --> 00:14:40,200
什么原子操作实现的锁呢

421
00:14:40,240 --> 00:14:41,840
这个锁呢有这样一个功能

422
00:14:41,880 --> 00:14:43,520
首先我申请的时候

423
00:14:43,560 --> 00:14:46,080
在锁被释放之前

424
00:14:46,120 --> 00:14:48,320
我一直处于等待状态

425
00:14:48,360 --> 00:14:50,400
一直到他获得锁

426
00:14:50,440 --> 00:14:53,080
如果有两个进程

427
00:14:53,120 --> 00:14:55,000
同时在等待这个锁

428
00:14:55,040 --> 00:14:58,600
那么这时候呢他只会有一个获得

429
00:14:58,640 --> 00:15:00,640
另一个呢还继续等待

430
00:15:00,680 --> 00:15:02,720
如果说我们能做到这一点

431
00:15:02,760 --> 00:15:04,000
那这时候呢

432
00:15:04,040 --> 00:15:06,760
并且把它实现成一个原子操作

433
00:15:06,800 --> 00:15:09,680
在这中间呢不会被暂停

434
00:15:09,720 --> 00:15:12,600
释放呢就是解锁

435
00:15:12,640 --> 00:15:16,600
并且唤醒处于等待状态当中的进程

436
00:15:16,640 --> 00:15:18,200
有了这两条实现之后

437
00:15:18,240 --> 00:15:20,040
我们给出一个代码

438
00:15:20,080 --> 00:15:26,920
这时候呢是基于原子锁的解决方案

439
00:15:26,960 --> 00:15:28,400
刚开始申请

440
00:15:28,440 --> 00:15:30,600
然后在这里判断是否有面包

441
00:15:30,640 --> 00:15:32,600
去买面包

442
00:15:32,640 --> 00:15:34,720
然后到最后的时候呢

443
00:15:34,760 --> 00:15:36,960
释放这个锁 解锁

444
00:15:37,000 --> 00:15:40,400
好 那这时候呢被我们标准化成

445
00:15:40,440 --> 00:15:43,000
这部分代码叫临界区

446
00:15:43,040 --> 00:15:45,040
前面这一段呢叫进入临界区

447
00:15:45,080 --> 00:15:46,920
后面叫退出临界区

448
00:15:46,960 --> 00:15:48,920
相应的这两段代码保护下

449
00:15:48,960 --> 00:15:50,760
中间在这个临界区里头执行呢

450
00:15:50,800 --> 00:15:52,760
就只有一个进程

451
00:15:52,800 --> 00:15:53,880
好 基于这样的办法呢

452
00:15:53,920 --> 00:15:56,520
我们这件事情呢就能做的很好

453
00:15:56,560 --> 00:15:58,440
好 我们看到在这个例子当中

454
00:15:58,480 --> 00:15:59,880
两个进程为了

455
00:15:59,920 --> 00:16:02,440
协调他们之间的操作

456
00:16:02,480 --> 00:16:04,360
那中间的关系是很复杂的

457
00:16:04,400 --> 00:16:06,480
那如果说我们系统里有更多的资源

458
00:16:06,520 --> 00:16:08,120
这件事情会变成啥样呢

459
00:16:08,160 --> 00:16:09,920
好 我们在这儿呢做一个归纳

460
00:16:09,960 --> 00:16:11,520
进程之间的交互关系

461
00:16:11,560 --> 00:16:14,000
他们对对方的感知能到什么程度

462
00:16:14,040 --> 00:16:15,800
我们在这儿呢分了三种情况

463
00:16:15,840 --> 00:16:18,520
一种呢是完全不感知

464
00:16:18,560 --> 00:16:20,240
一种呢是两者通过

465
00:16:20,280 --> 00:16:23,560
一个第三方来协调

466
00:16:23,600 --> 00:16:26,320
你比如说都要占用共享的资源

467
00:16:26,360 --> 00:16:28,680
然后再有一种情况是

468
00:16:28,720 --> 00:16:30,560
两者需要直接进行通讯

469
00:16:30,600 --> 00:16:32,560
那这三种情况对应着

470
00:16:32,600 --> 00:16:36,080
他们之间交互关系呢是这样的

471
00:16:36,120 --> 00:16:37,080
没有关系的时候

472
00:16:37,120 --> 00:16:38,000
他是相互独立的

473
00:16:38,040 --> 00:16:39,240
相互不影响

474
00:16:39,280 --> 00:16:42,480
如果说我有共享的第三方

475
00:16:42,520 --> 00:16:44,000
这里我们需要通过

476
00:16:44,040 --> 00:16:47,240
共享这个资源来进行协调

477
00:16:47,280 --> 00:16:49,200
如果说两者有直接通讯

478
00:16:49,240 --> 00:16:49,840
那么这时候需要

479
00:16:49,880 --> 00:16:52,080
通过通讯来进行协调

480
00:16:52,120 --> 00:16:53,480
好 那在这种情况下

481
00:16:53,520 --> 00:16:55,360
他们之间的相互影响呢

482
00:16:55,400 --> 00:16:57,360
第一个情况独立的

483
00:16:57,400 --> 00:16:58,720
对这方没有影响

484
00:16:58,760 --> 00:17:00,680
第二个呢是说他的结果

485
00:17:00,720 --> 00:17:03,120
依赖于共享资源的状态

486
00:17:03,160 --> 00:17:05,560
有可能一个进程占用了资源

487
00:17:05,600 --> 00:17:06,640
另一个进程要想

488
00:17:06,680 --> 00:17:07,760
使用这个资源的时候

489
00:17:07,800 --> 00:17:10,200
他就没办法使用了

490
00:17:10,240 --> 00:17:12,760
要么等到这个资源可以用

491
00:17:12,800 --> 00:17:15,840
要么这件事情他以失败告终

492
00:17:15,880 --> 00:17:18,240
而第三个呢双方通讯的时候

493
00:17:18,280 --> 00:17:19,200
这个结果就依赖于

494
00:17:19,240 --> 00:17:21,560
双方的通讯的结果

495
00:17:21,600 --> 00:17:23,360
好 那这时候呢通讯结果的不同呢

496
00:17:23,400 --> 00:17:25,000
他结果也是不一样

497
00:17:25,040 --> 00:17:26,640
好 在这个过程当中

498
00:17:26,680 --> 00:17:28,280
我们的进程之间呢

499
00:17:28,320 --> 00:17:30,360
会出现这样三种关系

500
00:17:30,400 --> 00:17:33,120
互斥 死锁和饥饿

501
00:17:33,160 --> 00:17:34,880
分别是指什么意思呢

502
00:17:34,920 --> 00:17:40,000
互斥是指一个进程占用了资源

503
00:17:40,040 --> 00:17:42,800
其它的进程就不能使用这个资源了

504
00:17:42,840 --> 00:17:47,200
那必须等待使用资源的进程释放

505
00:17:47,240 --> 00:17:49,320
那在这个过程当中呢

506
00:17:49,360 --> 00:17:52,600
资源的使用是互斥的

507
00:17:52,640 --> 00:17:54,480
第二个死锁

508
00:17:54,520 --> 00:17:56,720
死锁呢是多个进程

509
00:17:56,760 --> 00:17:59,040
各自都占有了一部分资源

510
00:17:59,080 --> 00:18:01,520
那这时候呢形成循环等待

511
00:18:01,560 --> 00:18:02,920
那各自占用一部分资源

512
00:18:02,960 --> 00:18:05,440
这种情况是允许存在的

513
00:18:05,480 --> 00:18:08,080
好 那等到某一个能够得到

514
00:18:08,120 --> 00:18:10,120
他所需要的所有资源

515
00:18:10,160 --> 00:18:12,200
好 那他执行结束之后释放资源

516
00:18:12,240 --> 00:18:14,360
好 这样的话这个

517
00:18:14,400 --> 00:18:16,360
部分等待其他的就能有资源

518
00:18:16,400 --> 00:18:17,560
到最后大家都用完了

519
00:18:17,600 --> 00:18:18,920
那这件事情出来

520
00:18:18,960 --> 00:18:21,440
如果构成一个循环等待

521
00:18:21,480 --> 00:18:23,640
就好比说我们在一个十字路口

522
00:18:23,680 --> 00:18:25,840
四辆车叉成一个井字

523
00:18:25,880 --> 00:18:28,120
好 那这时候呢所有的他就等的

524
00:18:28,160 --> 00:18:29,640
就谁也不让的话

525
00:18:29,680 --> 00:18:31,680
那这件事情就堵死了

526
00:18:31,720 --> 00:18:32,360
这种情况呢

527
00:18:32,400 --> 00:18:34,480
是我们这里说到的死锁

528
00:18:34,520 --> 00:18:37,040
还有一种情况呢是饥饿

529
00:18:37,080 --> 00:18:42,200
饥饿是指一些进程轮流占用资源

530
00:18:42,240 --> 00:18:44,960
而导致一个进程呢一直得不到资源

531
00:18:45,000 --> 00:18:47,440
比如说像我们前面说到的调度

532
00:18:47,480 --> 00:18:49,680
有一个进程占用CPU来执行

533
00:18:49,720 --> 00:18:51,160
但是它的优先级低

534
00:18:51,200 --> 00:18:52,840
而比它优先级高的进程呢

535
00:18:52,880 --> 00:18:54,760
又一直在运行

536
00:18:54,800 --> 00:18:55,240
那这样的话

537
00:18:55,280 --> 00:18:57,720
它就属于饥饿的状态

538
00:18:57,760 --> 00:19:00,800
好 那我们说在实际的操作系统里头

539
00:19:00,840 --> 00:19:02,720
由于我们有资源共享

540
00:19:02,760 --> 00:19:03,920
我们就会出现

541
00:19:03,960 --> 00:19:07,400
互斥 死锁和饥饿这些情况

542
00:19:07,440 --> 00:19:10,440
但是如果说我们想避免这种情况

543
00:19:10,480 --> 00:19:12,680
那我们资源利用效率呢又不够高

544
00:19:12,720 --> 00:19:14,320
好 所以我们在操作系统里头

545
00:19:14,360 --> 00:19:17,520
就要提供一组同步互斥的机制

546
00:19:17,560 --> 00:19:21,920
来在保证资源的使用率的前提下

547
00:19:21,960 --> 00:19:26,760
避免这些同步所带来的问题

548
00:19:26,800 --> 00:19:28,040
下面呢我们会具体来

549
00:19:28,080 --> 00:19:30,600
介绍它的各种各样的解决办法

550
00:19:30,640 --> 00:19:30,680