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


1
00:00:07,120 --> 00:00:11,160
下面我们来介绍软件同步方法

2
00:00:11,200 --> 00:00:13,440
基于软件的同步方法呢

3
00:00:13,480 --> 00:00:16,320
它是在两个进程之间

4
00:00:16,440 --> 00:00:18,440
通过共享变量的访问

5
00:00:18,480 --> 00:00:21,200
来实现线程之间的同步

6
00:00:21,240 --> 00:00:22,320
那这一类方法呢

7
00:00:22,360 --> 00:00:26,320
我们给它的大致模式先给它描述

8
00:00:26,360 --> 00:00:30,040
假定有两个线程 T0和T1

9
00:00:30,080 --> 00:00:32,480
然后每一个线程呢

10
00:00:32,520 --> 00:00:35,160
它的实现代码都是这样一种格局

11
00:00:35,200 --> 00:00:38,280
进入区 临界区 退出区

12
00:00:38,320 --> 00:00:40,760
然后我们在这里控制的地方呢

13
00:00:40,800 --> 00:00:43,480
是在进入区和退出区里头

14
00:00:43,520 --> 00:00:46,080
通过一些共享变量的修改

15
00:00:46,120 --> 00:00:49,120
来同步它们之间的行为

16
00:00:49,160 --> 00:00:51,360
那我们在这里的所有的方法呢

17
00:00:51,400 --> 00:00:53,400
都是要讨论在进入区里头

18
00:00:53,440 --> 00:00:55,160
我要对哪些共享的变量

19
00:00:55,200 --> 00:01:00,680
进行什么样的设置和判断

20
00:01:00,720 --> 00:01:04,000
那这些方法呢跟我们前面讨论到的

21
00:01:04,040 --> 00:01:06,520
生活当中同步问题呢是一致的

22
00:01:06,560 --> 00:01:09,960
我们跟那儿呢做一个类比性的讨论

23
00:01:10,000 --> 00:01:11,720
首先第一个尝试 说

24
00:01:11,760 --> 00:01:12,640
我在这里呢

25
00:01:12,680 --> 00:01:15,600
在两个线程之间共享一个变量

26
00:01:15,640 --> 00:01:20,120
这个变量呢表示允许谁进入临界区

27
00:01:20,160 --> 00:01:21,800
那这里是允许进入

28
00:01:21,840 --> 00:01:25,560
临界区的线程的ID

29
00:01:25,600 --> 00:01:27,040
好 那这时候我们说

30
00:01:27,080 --> 00:01:31,680
线程Ti实现代码呢是这样的

31
00:01:31,720 --> 00:01:36,120
它先判断当前这个turn的值

32
00:01:36,160 --> 00:01:37,680
到底是不是i

33
00:01:37,720 --> 00:01:40,440
如果不是 也就相当于我本身是i

34
00:01:40,480 --> 00:01:44,320
允许另外一个线程进入临界区

35
00:01:44,360 --> 00:01:47,160
i不允许进入临界区

36
00:01:47,200 --> 00:01:49,000
那这时候呢它就一直等待

37
00:01:49,040 --> 00:01:53,360
等待另一个线程把它改成i

38
00:01:53,400 --> 00:01:56,440
好 如果 这样的话就是

39
00:01:56,480 --> 00:01:59,760
在它自己等待它变成是它之后

40
00:01:59,800 --> 00:02:01,800
它能进去 进去之后呢

41
00:02:01,840 --> 00:02:03,640
执行临界区的代码

42
00:02:03,680 --> 00:02:05,600
执行完毕之后退出的时候呢

43
00:02:05,640 --> 00:02:10,000
在退出区呢 它把turn改成j

44
00:02:10,040 --> 00:02:12,600
也就说另一个线程ID

45
00:02:12,640 --> 00:02:14,840
那我们看这种情况

46
00:02:14,880 --> 00:02:16,800
能满足我们的要求吗

47
00:02:16,840 --> 00:02:20,240
如果说turn的值是i

48
00:02:20,280 --> 00:02:24,160
那么这时候呢线程Ti

49
00:02:24,200 --> 00:02:28,320
进入一个判断是可以的

50
00:02:28,360 --> 00:02:30,240
OK 它就进去了

51
00:02:30,280 --> 00:02:32,880
好 如果不是那就它一直等着

52
00:02:32,920 --> 00:02:34,920
那这时候说如果这个地方

53
00:02:34,960 --> 00:02:37,720
是j来访问那它就进不去

54
00:02:37,760 --> 00:02:40,000
那这时候我们看到

55
00:02:40,040 --> 00:02:41,600
i和j之间访问临界区的

56
00:02:41,640 --> 00:02:43,320
关系是啥样的

57
00:02:43,360 --> 00:02:45,600
开始的时候假定它等于i

58
00:02:45,640 --> 00:02:47,720
那么这时候呢i能进去

59
00:02:47,760 --> 00:02:50,280
j能进去吗 j进不去

60
00:02:50,320 --> 00:02:53,040
好 i进去之后它改成j

61
00:02:53,080 --> 00:02:54,840
好 这时候如果i再来进的话

62
00:02:54,880 --> 00:02:57,360
它进不去了 j也能进去

63
00:02:57,400 --> 00:02:59,240
这时候我们就会发现一种现象

64
00:02:59,280 --> 00:03:00,920
它们俩是交替进入临界区

65
00:03:00,960 --> 00:03:02,960
这是很好的一种做法

66
00:03:03,000 --> 00:03:05,520
但如果说某一个线程

67
00:03:05,560 --> 00:03:08,040
想连续两次进入临界区

68
00:03:08,080 --> 00:03:10,480
那这时候它就会有麻烦

69
00:03:10,520 --> 00:03:12,440
所以这种做法呢

70
00:03:12,480 --> 00:03:15,800
它能够满足我们说的忙则等待

71
00:03:15,840 --> 00:03:17,760
也就说我在这里头

72
00:03:17,800 --> 00:03:19,480
任何一个线程进到里头去的时候

73
00:03:19,520 --> 00:03:21,880
不会有第二个同时在里头

74
00:03:21,920 --> 00:03:24,400
但是它不满足空闲则入

75
00:03:24,440 --> 00:03:26,720
也就相当于如果说这里是空闲的

76
00:03:26,760 --> 00:03:28,960
但是这时候编号不是你

77
00:03:29,000 --> 00:03:30,520
那你进不去了

78
00:03:30,560 --> 00:03:32,880
好 那我们对这种做法呢

79
00:03:32,920 --> 00:03:36,120
进行进一步的修改

80
00:03:36,160 --> 00:03:37,720
那这是第二种做法

81
00:03:37,760 --> 00:03:38,960
我们在前面呢

82
00:03:39,000 --> 00:03:41,640
设置一个变量turn不够用

83
00:03:41,680 --> 00:03:44,440
那我们这儿呢现在设置两个变量

84
00:03:44,480 --> 00:03:46,160
也就相当于一个数组

85
00:03:46,200 --> 00:03:51,800
描述每个线程它是否是在临界区

86
00:03:51,840 --> 00:03:53,320
这种做法和刚才那个地方

87
00:03:53,360 --> 00:03:54,240
有什么不一样呢

88
00:03:54,280 --> 00:03:56,280
这就相当于我是用两个来表示

89
00:03:56,320 --> 00:03:59,440
我尝试着解决两个线程

90
00:03:59,480 --> 00:04:01,640
需要交替进入的问题

91
00:04:01,680 --> 00:04:03,040
好 那这时候呢

92
00:04:03,080 --> 00:04:07,200
线程Ti的实现代码我们这样来做

93
00:04:07,240 --> 00:04:12,160
先判断另外一个线程它的flag是1

94
00:04:12,200 --> 00:04:13,280
如果它不是

95
00:04:13,320 --> 00:04:15,040
也就相当于它没在临界区里头

96
00:04:15,080 --> 00:04:19,240
那我就把自己的标识改成1

97
00:04:19,280 --> 00:04:20,480
那这时候我在临界区

98
00:04:20,520 --> 00:04:21,680
然后进入临界区

99
00:04:21,720 --> 00:04:22,400
出来的时候

100
00:04:22,440 --> 00:04:25,000
我把自己这个标识呢改成0

101
00:04:25,040 --> 00:04:26,240
那这种做法呢

102
00:04:26,280 --> 00:04:28,000
和我们前面的第一种尝试

103
00:04:28,040 --> 00:04:30,360
想想看有什么区别

104
00:04:30,400 --> 00:04:33,720
线程Ti想进入临界区

105
00:04:33,760 --> 00:04:35,080
它做判断

106
00:04:35,120 --> 00:04:38,080
假设另一个没有在临界区

107
00:04:38,120 --> 00:04:40,880
那它判断是通过的

108
00:04:40,920 --> 00:04:42,520
OK 好 它这时候呢

109
00:04:42,560 --> 00:04:45,400
把自己的标识改了然后进去

110
00:04:45,440 --> 00:04:47,480
如果它再来一遍可以吗

111
00:04:47,520 --> 00:04:50,320
它再来一遍同样的做法仍然没问题

112
00:04:50,360 --> 00:04:53,680
一个线程连续进入是可以的

113
00:04:53,720 --> 00:04:56,160
好 如果说它交替进入呢

114
00:04:56,200 --> 00:04:57,800
那也没问题

115
00:04:57,840 --> 00:05:00,160
好像改善了我们前面

116
00:05:00,200 --> 00:05:03,240
第一种尝试里头的麻烦

117
00:05:03,280 --> 00:05:05,440
但是它有什么问题吗

118
00:05:05,480 --> 00:05:07,040
还记得我们在前面讲

119
00:05:07,080 --> 00:05:09,120
采购当中那个同步

120
00:05:09,160 --> 00:05:13,760
说两个先判断 后设置

121
00:05:13,800 --> 00:05:16,800
两个同时判断之后会出现什么

122
00:05:16,840 --> 00:05:18,480
同时设置

123
00:05:18,520 --> 00:05:20,000
那同时设置之后呢

124
00:05:20,040 --> 00:05:22,640
两个线程就同时进入到

125
00:05:22,680 --> 00:05:23,760
临界区里头去了

126
00:05:23,800 --> 00:05:26,400
那这时候这是它的毛病

127
00:05:26,440 --> 00:05:29,160
它就不能满足忙则等待

128
00:05:29,200 --> 00:05:31,320
好 那这种做法不行了

129
00:05:31,360 --> 00:05:34,160
之后怎么办呢

130
00:05:34,200 --> 00:05:39,160
我们把前面含义做一下改动

131
00:05:39,200 --> 00:05:40,800
也就说前面我们就像

132
00:05:40,840 --> 00:05:43,240
我们在采购那个同步里头

133
00:05:43,280 --> 00:05:46,480
我们是先贴标签还是后贴标签

134
00:05:46,520 --> 00:05:47,400
刚才那种做法呢

135
00:05:47,440 --> 00:05:50,080
相当于是后贴标签

136
00:05:50,120 --> 00:05:52,480
那这时候呢我把这个flag含义改了

137
00:05:52,520 --> 00:05:54,200
不表示我在临界区

138
00:05:54,240 --> 00:05:57,040
而表示我想进入临界区

139
00:05:57,080 --> 00:06:00,440
那这时候呢相当于我是先贴标签

140
00:06:00,480 --> 00:06:02,400
这是它的实现代码

141
00:06:02,440 --> 00:06:04,000
先贴标签后做判断

142
00:06:04,040 --> 00:06:07,560
这时候我们说 前面的采购同步里头

143
00:06:07,600 --> 00:06:10,440
先贴标签后做判断会出现什么问题

144
00:06:10,480 --> 00:06:13,920
两个都有可能判断完了之后

145
00:06:13,960 --> 00:06:15,320
都觉得自己进不去

146
00:06:15,360 --> 00:06:17,400
OK 那就都进不去了

147
00:06:17,440 --> 00:06:19,560
那这是它的问题

148
00:06:19,600 --> 00:06:22,520
它能够满足不能同时进

149
00:06:22,560 --> 00:06:26,480
但是不能满足如果空闲我可以进去

150
00:06:26,520 --> 00:06:28,360
这就是空闲则入

151
00:06:28,400 --> 00:06:30,480
好 这种做法呢也不行

152
00:06:30,520 --> 00:06:32,560
也就相当于我把标签贴在前头

153
00:06:32,600 --> 00:06:33,720
贴在后头都不行

154
00:06:33,760 --> 00:06:34,640
好 那这时候呢

155
00:06:34,680 --> 00:06:36,880
我把这两个合在一起

156
00:06:36,920 --> 00:06:40,360
这就是我们这里的Peterson算法

157
00:06:40,400 --> 00:06:41,800
这是两个进程之间

158
00:06:41,840 --> 00:06:45,160
能够完成同步的算法

159
00:06:45,200 --> 00:06:47,520
它怎么做的呢

160
00:06:47,560 --> 00:06:51,080
turn表示当前谁进入临界区

161
00:06:51,120 --> 00:06:55,960
而flag表示我请求进入临界区

162
00:06:56,000 --> 00:06:57,200
好 这时候我们说

163
00:06:57,240 --> 00:07:00,360
进入区的代码是先设置标志

164
00:07:00,400 --> 00:07:02,440
相当于这时候设置的标志有两个

165
00:07:02,480 --> 00:07:04,400
一个是我想进入

166
00:07:04,440 --> 00:07:06,520
第二个是turn的值

167
00:07:06,560 --> 00:07:09,080
然后我在后面做一个判断

168
00:07:09,120 --> 00:07:10,440
那这时候想想看

169
00:07:10,480 --> 00:07:13,000
这和我们前面先设置标志

170
00:07:13,040 --> 00:07:14,800
后做判断有什么区别

171
00:07:14,840 --> 00:07:16,720
那这地方它俩同时

172
00:07:16,760 --> 00:07:19,040
设置了一个变量 turn

173
00:07:19,080 --> 00:07:20,840
这是问题的关键

174
00:07:20,880 --> 00:07:23,520
我把这一步设置完了之后呢

175
00:07:23,560 --> 00:07:25,080
我后面的判断

176
00:07:25,120 --> 00:07:28,040
就能够区别出来它们俩

177
00:07:28,080 --> 00:07:30,200
好 我们具体看一下

178
00:07:30,240 --> 00:07:35,280
如果说另一个线程j

179
00:07:35,320 --> 00:07:37,360
它没有申请进入

180
00:07:37,400 --> 00:07:39,800
那我这儿直接能进去没问题

181
00:07:39,840 --> 00:07:41,320
因为这两个条件里头

182
00:07:41,360 --> 00:07:43,680
有一个不成立它就进来了

183
00:07:43,720 --> 00:07:46,280
好 假定说另一个也申请了

184
00:07:46,320 --> 00:07:47,680
它也变成true

185
00:07:47,720 --> 00:07:49,240
好 那这时候会什么呢

186
00:07:49,280 --> 00:07:53,120
会有这样一个turn在这儿等着

187
00:07:53,160 --> 00:07:55,720
因为这个变量是

188
00:07:55,760 --> 00:07:58,120
往存储单元里写数据

189
00:07:58,160 --> 00:08:00,440
两个线程同时往里写

190
00:08:00,480 --> 00:08:01,720
或者并发往里写

191
00:08:01,760 --> 00:08:03,240
那总是有一前一后

192
00:08:03,280 --> 00:08:05,000
好 不管是哪一个

193
00:08:05,040 --> 00:08:06,480
因为在总线上仲裁之后

194
00:08:06,520 --> 00:08:08,200
我是有一前一后的

195
00:08:08,240 --> 00:08:08,840
在这里呢

196
00:08:08,880 --> 00:08:10,400
假定我在这儿

197
00:08:10,440 --> 00:08:11,480
我写的是j

198
00:08:11,520 --> 00:08:12,720
如果我是最后一个写的

199
00:08:12,760 --> 00:08:14,120
会什么样的情况

200
00:08:14,160 --> 00:08:16,040
另一个flag是true

201
00:08:16,080 --> 00:08:18,440
然后我的标志呢

202
00:08:18,480 --> 00:08:20,800
turn的标志是按我最后写的

203
00:08:20,840 --> 00:08:22,200
那我判断相当于

204
00:08:22,240 --> 00:08:24,720
如果两个同时想进入的话

205
00:08:24,760 --> 00:08:27,840
后设置turn这个标志的

206
00:08:27,880 --> 00:08:29,680
那这个条件就成立

207
00:08:29,720 --> 00:08:31,880
而先写的后面这个条件不成立

208
00:08:31,920 --> 00:08:32,840
好 那这样的话

209
00:08:32,880 --> 00:08:36,960
就是先写turn这个标志的能进去

210
00:08:37,000 --> 00:08:38,880
而后写的就会在这儿等着

211
00:08:38,920 --> 00:08:43,320
那等到在退出区里头我把flag改了

212
00:08:43,360 --> 00:08:44,600
好 那么这个条件呢

213
00:08:44,640 --> 00:08:46,000
前面这个就不成立了

214
00:08:46,040 --> 00:08:50,280
好 那这是后写标志turn

215
00:08:50,320 --> 00:08:52,480
也就能进去了

216
00:08:52,520 --> 00:08:54,560
好 那这一个呢

217
00:08:54,600 --> 00:08:56,720
我们说跟我们前面讲

218
00:08:56,760 --> 00:08:58,280
采购同步一样的

219
00:08:58,320 --> 00:09:00,600
把它们所有的情况

220
00:09:00,640 --> 00:09:02,280
罗列出来进行分析

221
00:09:02,320 --> 00:09:05,000
写标志 判断它们

222
00:09:05,040 --> 00:09:09,080
所有可能的顺序一一进行分析

223
00:09:09,120 --> 00:09:10,760
我们说Peterson算法呢

224
00:09:10,800 --> 00:09:12,760
是可以完成

225
00:09:12,800 --> 00:09:14,760
我们的两个进程之间同步

226
00:09:14,800 --> 00:09:19,360
好 那在这种情况下我们说

227
00:09:19,400 --> 00:09:21,600
要是更多的进程怎么办

228
00:09:21,640 --> 00:09:23,760
我们先把这个两个进程的做法呢

229
00:09:23,800 --> 00:09:25,960
换一种形式来写

230
00:09:26,000 --> 00:09:28,560
这就是Dekkers算法

231
00:09:28,600 --> 00:09:30,200
它的做法是什么呢

232
00:09:30,240 --> 00:09:32,960
跟标志 跟我们前面的几乎一样的

233
00:09:33,000 --> 00:09:34,720
但是这个进入区的判断呢

234
00:09:34,760 --> 00:09:36,760
相对来说复杂一些

235
00:09:36,800 --> 00:09:39,360
那实际上也是先写

236
00:09:39,400 --> 00:09:41,600
然后后面去判断

237
00:09:41,640 --> 00:09:43,200
判断完了之后

238
00:09:43,240 --> 00:09:45,200
那看如果另一个也想进入

239
00:09:45,240 --> 00:09:46,880
实际上它就把自己改为false

240
00:09:46,920 --> 00:09:50,200
然后开始等待 前面这个

241
00:09:50,240 --> 00:09:51,360
这种做法呢

242
00:09:51,400 --> 00:09:53,840
退出去的做法跟那儿是一样的

243
00:09:53,880 --> 00:09:55,000
这种做法呢

244
00:09:55,040 --> 00:09:59,040
它可以很方便的扩展到多个线程

245
00:09:59,080 --> 00:10:01,560
而扩展到多个线程的做法呢

246
00:10:01,600 --> 00:10:04,720
就是我们这个图呢给出的图示

247
00:10:04,760 --> 00:10:06,400
我在这里有一个turn这个变量

248
00:10:06,440 --> 00:10:07,680
这是共享的

249
00:10:07,720 --> 00:10:10,760
然后是每一个线程 若干个

250
00:10:10,800 --> 00:10:12,360
我把它排成一个环

251
00:10:12,400 --> 00:10:15,680
每一个里头有一个flag的标志

252
00:10:15,720 --> 00:10:17,600
好 那我在进入的时候呢

253
00:10:17,640 --> 00:10:20,320
我先填这个flag标志说我想进入

254
00:10:20,360 --> 00:10:22,440
然后去看turn标志

255
00:10:22,480 --> 00:10:23,760
如果有多个想写

256
00:10:23,800 --> 00:10:26,880
那这个时候呢它总是会有最后一个

257
00:10:26,920 --> 00:10:29,120
好 那么在这种情况下

258
00:10:29,160 --> 00:10:36,240
这是当前正在访问临界区的那一个线程

259
00:10:36,280 --> 00:10:37,200
好 我要做什么呢

260
00:10:37,240 --> 00:10:40,520
进入区我就从这儿往后一直到i

261
00:10:40,560 --> 00:10:41,200
这是个环

262
00:10:41,240 --> 00:10:42,800
也可能会在另外一个位置

263
00:10:42,840 --> 00:10:44,920
就从它起头 到i这个地方

264
00:10:44,960 --> 00:10:48,120
这一段里是不是有其它线程

265
00:10:48,160 --> 00:10:50,320
也跟我一样的 同时想进入

266
00:10:50,360 --> 00:10:53,600
如果有 让他们先访问

267
00:10:53,640 --> 00:10:54,640
访问完了之后

268
00:10:54,680 --> 00:10:56,600
这个turn会一直往后蹿

269
00:10:56,640 --> 00:10:58,120
蹿到我这儿

270
00:10:58,160 --> 00:10:59,680
那这时候我进去

271
00:10:59,720 --> 00:11:01,800
那这就是我们这里说的

272
00:11:01,840 --> 00:11:03,480
进入区的做法

273
00:11:03,520 --> 00:11:05,920
而退出区等我用完了之后

274
00:11:05,960 --> 00:11:07,520
后面有可能

275
00:11:07,560 --> 00:11:09,000
也有其他在等着的

276
00:11:09,040 --> 00:11:11,240
我顺序的把标志

277
00:11:11,280 --> 00:11:14,040
给到下一个想进入的

278
00:11:14,080 --> 00:11:15,800
如果都没有转一圈之后

279
00:11:15,840 --> 00:11:17,640
我把自己留这儿就行了

280
00:11:17,680 --> 00:11:24,280
好 这是N个进程的软件同步方法

281
00:11:24,320 --> 00:11:25,520
好 那我们看到

282
00:11:25,560 --> 00:11:27,120
这几种方法搁到一起之后

283
00:11:27,160 --> 00:11:27,920
我们发现这个

284
00:11:27,960 --> 00:11:32,080
基于软件的同步方法它很复杂

285
00:11:32,120 --> 00:11:36,680
两个进程之间需要多个共享数据项

286
00:11:36,720 --> 00:11:38,720
我才能够完成这个同步

287
00:11:38,760 --> 00:11:41,640
同时这是一个盲等待

288
00:11:41,680 --> 00:11:44,760
也就说我在进入区里头

289
00:11:44,800 --> 00:11:47,040
我必须频繁地来

290
00:11:47,080 --> 00:11:50,760
查询共享变量的状态

291
00:11:50,800 --> 00:11:53,240
那这是呢软件同步方法

292
00:11:53,280 --> 00:11:55,560
所面临的问题

293
00:11:55,600 --> 00:11:58,160
好 经过这几个算法的介绍呢

294
00:11:58,200 --> 00:12:00,320
我们知道通过软件方法

295
00:12:00,360 --> 00:12:04,120
是可以实现多个进程之间的同步的

296
00:12:04,240 --> 00:12:07,120
但是这个方法比较复杂

297
00:12:07,200 --> 00:12:10,080
里头有错之后也不好查找

298
00:12:10,200 --> 00:12:12,720
如果说你是多个线程

299
00:12:12,760 --> 00:12:13,880
多个临界区

300
00:12:13,920 --> 00:12:15,720
那么这时候这个问题会变得更复杂

301
00:12:15,760 --> 00:12:15,800