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


1
00:00:07,400 --> 00:00:10,920
下面我们来介绍第三类同步方法

2
00:00:10,960 --> 00:00:14,680
就是这里的更高级的抽象方法

3
00:00:14,720 --> 00:00:18,520
它实际上是基于硬件的同步原语

4
00:00:18,600 --> 00:00:21,480
来实现的同步方法

5
00:00:21,520 --> 00:00:24,160
我们在前面已经说过中断禁用

6
00:00:24,200 --> 00:00:27,600
可以实现进程之间的同步

7
00:00:27,640 --> 00:00:31,480
那还有一类呢是原子操作指令

8
00:00:31,520 --> 00:00:33,640
也就说把若干个我们在同步当中

9
00:00:33,680 --> 00:00:35,560
会用到的操作

10
00:00:35,600 --> 00:00:37,240
把它合成一个原子操作

11
00:00:37,280 --> 00:00:40,280
在硬件上保证它的原子性

12
00:00:40,320 --> 00:00:41,320
这样的话 操作系统

13
00:00:41,360 --> 00:00:43,480
就可以基于这个来实现

14
00:00:43,520 --> 00:00:46,840
更高级的编程抽象

15
00:00:46,880 --> 00:00:49,320
简化进程同步

16
00:00:49,360 --> 00:00:51,200
第一个呢是锁

17
00:00:51,240 --> 00:00:54,400
锁呢实际上是一个抽象的数据结构

18
00:00:54,440 --> 00:00:55,280
这个数据结构呢

19
00:00:55,320 --> 00:00:57,040
由一个二进制变量

20
00:00:57,080 --> 00:01:00,680
和两个操作原语组成

21
00:01:00,720 --> 00:01:03,680
二进制变量呢它表示两种状态

22
00:01:03,720 --> 00:01:06,520
一种是锁定一种是解锁

23
00:01:06,560 --> 00:01:08,880
而两个操作呢是这样的

24
00:01:08,920 --> 00:01:10,800
一个是锁的请求

25
00:01:10,840 --> 00:01:12,880
我要申请这个锁

26
00:01:12,920 --> 00:01:15,840
那这个操作呢 它是原子的

27
00:01:15,880 --> 00:01:17,560
在请求的过程当中

28
00:01:17,600 --> 00:01:20,480
一直到获取到这个锁之前

29
00:01:20,520 --> 00:01:23,160
它都一直处于等待状态

30
00:01:23,200 --> 00:01:24,520
那它返回的时候

31
00:01:24,560 --> 00:01:27,040
你就已经获得这个锁了

32
00:01:27,080 --> 00:01:29,160
第二个操作呢是释放

33
00:01:29,200 --> 00:01:32,880
释放锁呢 它是唤醒其它的

34
00:01:32,920 --> 00:01:35,680
等待这个锁的进程

35
00:01:35,720 --> 00:01:38,240
有了这两个操作之后

36
00:01:38,280 --> 00:01:42,200
我们用它来实现临界区的访问

37
00:01:42,240 --> 00:01:43,560
那就很方便了

38
00:01:43,600 --> 00:01:45,680
那这是临界区的访问

39
00:01:45,720 --> 00:01:48,480
进入区就是请求操作

40
00:01:48,520 --> 00:01:52,600
退出区呢就是释放操作

41
00:01:52,640 --> 00:01:55,360
那有了这个之后这件事情就行了

42
00:01:55,400 --> 00:01:56,720
那它内部呢我们是

43
00:01:56,760 --> 00:01:58,840
基于原子操作指令

44
00:01:58,880 --> 00:02:00,240
原子操作指令呢

45
00:02:00,280 --> 00:02:02,400
是CPU体系结构当中

46
00:02:02,440 --> 00:02:05,800
提供的一类特殊的指令

47
00:02:05,840 --> 00:02:08,520
这些指令呢把若干个操作

48
00:02:08,560 --> 00:02:09,880
合成一个原子操作

49
00:02:09,920 --> 00:02:11,040
保证它们之间中间

50
00:02:11,080 --> 00:02:15,240
不会出现部分执行的状态

51
00:02:15,280 --> 00:02:19,280
一个呢测试与置位指令

52
00:02:19,320 --> 00:02:21,600
通常我们说的TS指令

53
00:02:21,640 --> 00:02:22,560
它的功能呢

54
00:02:22,600 --> 00:02:25,600
是从内存单元中读取数据

55
00:02:25,640 --> 00:02:30,240
测试并且置位该存储单元

56
00:02:30,280 --> 00:02:33,360
测试呢就是判断这个值是不是1

57
00:02:33,400 --> 00:02:35,920
然后并且往这个单元里呢写1

58
00:02:35,960 --> 00:02:37,960
也就说如果里头是1

59
00:02:38,000 --> 00:02:40,280
那你读出来写进去的还是1

60
00:02:40,320 --> 00:02:41,560
内容没变

61
00:02:41,600 --> 00:02:43,560
但是我们知道里头是1了

62
00:02:43,600 --> 00:02:44,920
好 如果里头是0

63
00:02:44,960 --> 00:02:46,640
那这时候呢我读出来的0

64
00:02:46,680 --> 00:02:47,880
写进去的1

65
00:02:47,920 --> 00:02:50,320
好 那这是我对它进行修改了

66
00:02:50,360 --> 00:02:53,120
这条指令的准确含义呢

67
00:02:53,160 --> 00:02:54,640
可以用这个伪码来表示

68
00:02:54,680 --> 00:02:57,480
实际上这是从里头读出一个量来

69
00:02:57,520 --> 00:03:00,560
然后把另外一个量写进去

70
00:03:00,600 --> 00:03:02,640
并且把读出的量呢返回回来

71
00:03:02,680 --> 00:03:04,440
这是它的功能

72
00:03:04,480 --> 00:03:08,880
这三个基本的操作合到一起

73
00:03:08,920 --> 00:03:10,400
它是一个原子操作

74
00:03:10,440 --> 00:03:11,600
它们不会被中断

75
00:03:11,640 --> 00:03:13,520
好 基于这一条 我们来实现

76
00:03:13,560 --> 00:03:17,280
我们前面的同步就会很方便

77
00:03:17,320 --> 00:03:20,320
另一条呢是交换指令

78
00:03:20,360 --> 00:03:23,600
它的功能呢是交换内存中两个值

79
00:03:23,640 --> 00:03:25,600
实际上它的指令含义呢

80
00:03:25,640 --> 00:03:26,520
我们可以用这样一段

81
00:03:26,560 --> 00:03:28,040
伪码来表示

82
00:03:28,080 --> 00:03:29,120
用一个temp

83
00:03:29,160 --> 00:03:30,240
把第一个值读出来

84
00:03:30,280 --> 00:03:31,720
然后把第二个值复制过去之后

85
00:03:31,760 --> 00:03:32,920
再把你读出来的值呢

86
00:03:32,960 --> 00:03:34,640
复制到第二个值

87
00:03:34,680 --> 00:03:36,080
好 用这种办法呢

88
00:03:36,120 --> 00:03:37,960
我们可以把两个值呢做交换

89
00:03:38,000 --> 00:03:39,120
这也是一个原子操作

90
00:03:39,160 --> 00:03:41,320
也就说读出来和写进去之间

91
00:03:41,360 --> 00:03:43,880
不会产生部分执行的状态

92
00:03:43,920 --> 00:03:45,880
那如果说我们

93
00:03:45,920 --> 00:03:49,360
以前面的分配进程ID为例

94
00:03:49,400 --> 00:03:51,040
如果我们这里读出来和

95
00:03:51,080 --> 00:03:53,240
写进去这两个是一个整体的话

96
00:03:53,280 --> 00:03:56,920
那我ID加1就没问题了

97
00:03:56,960 --> 00:03:59,720
好 这是两个基本的原语

98
00:03:59,760 --> 00:04:02,600
基于这两个原子操作指令

99
00:04:02,640 --> 00:04:04,480
我们可以来实现锁

100
00:04:04,520 --> 00:04:05,760
那在这儿呢 我们先是

101
00:04:05,800 --> 00:04:09,720
用TS指令来实现自旋锁

102
00:04:09,760 --> 00:04:12,320
它的做法是这样的

103
00:04:12,360 --> 00:04:13,640
初始化

104
00:04:13,680 --> 00:04:16,320
你这个锁里这个初值为0

105
00:04:16,360 --> 00:04:20,560
然后我来构造它的请求操作原语

106
00:04:20,600 --> 00:04:21,800
实际上这里头呢

107
00:04:21,840 --> 00:04:24,200
就是用TS指令去把

108
00:04:24,240 --> 00:04:26,800
你这里的value这个值读出来

109
00:04:26,840 --> 00:04:28,480
并且往里写1

110
00:04:28,520 --> 00:04:30,480
那如果里头是1

111
00:04:30,520 --> 00:04:33,760
那这个操作呢就相当于是个检查

112
00:04:33,800 --> 00:04:34,960
如果里头是0

113
00:04:35,000 --> 00:04:36,280
那么就把里设置为1

114
00:04:36,320 --> 00:04:37,760
并且这个循环结束

115
00:04:37,800 --> 00:04:41,200
好 它就进到下面这个页区去了

116
00:04:41,240 --> 00:04:42,760
好 释放的时候呢

117
00:04:42,800 --> 00:04:45,320
就是把这个值改成0

118
00:04:45,360 --> 00:04:48,280
那我们看这个写入的过程呢

119
00:04:48,320 --> 00:04:49,280
我们把它展开之后

120
00:04:49,320 --> 00:04:50,640
变成这样两种

121
00:04:50,680 --> 00:04:52,360
一种呢原来里头是0

122
00:04:52,400 --> 00:04:53,400
那么这时候呢

123
00:04:53,440 --> 00:04:54,800
实际上相当于这个锁

124
00:04:54,840 --> 00:04:56,600
处于解锁的状态

125
00:04:56,640 --> 00:04:58,400
好 这时候我把里写成1

126
00:04:58,440 --> 00:05:00,080
也就相当于我占用这个锁

127
00:05:00,120 --> 00:05:03,560
并且使得其它的进程就处于

128
00:05:03,600 --> 00:05:06,120
后续来的就处于等待状态了

129
00:05:06,160 --> 00:05:11,280
而如果锁处于锁定的状态

130
00:05:11,320 --> 00:05:13,240
也就处于忙的状态

131
00:05:13,280 --> 00:05:15,160
那么这时候呢你读出来的是1

132
00:05:15,200 --> 00:05:16,000
写进去的是1

133
00:05:16,040 --> 00:05:16,960
好 那它的状态

134
00:05:17,000 --> 00:05:18,440
没有发生任何的改变

135
00:05:18,480 --> 00:05:21,520
好 那这是用TS指令

136
00:05:21,560 --> 00:05:23,280
实现的自旋锁

137
00:05:23,320 --> 00:05:26,280
那我们看看它有什么样的特点

138
00:05:26,320 --> 00:05:28,440
那在这里头呢是

139
00:05:28,480 --> 00:05:31,520
这个自旋锁里头的TS指令的执行

140
00:05:31,560 --> 00:05:33,440
它是要耗用CPU时间的

141
00:05:33,480 --> 00:05:35,920
所以它在等待状态的时候呢

142
00:05:35,960 --> 00:05:37,880
它是消耗CPU的

143
00:05:37,920 --> 00:05:40,040
好 那我们看基于这个

144
00:05:40,080 --> 00:05:41,640
我是不是可以把等待的时候

145
00:05:41,680 --> 00:05:44,080
占用CPU的这件事情呢有所缓解

146
00:05:44,120 --> 00:05:45,280
那我们就把这个

147
00:05:45,320 --> 00:05:48,480
变成一个无忙等待的锁

148
00:05:48,520 --> 00:05:50,760
那怎么做呢

149
00:05:50,800 --> 00:05:53,920
首先我在你那个锁的数据结构里呢

150
00:05:53,960 --> 00:05:56,480
加上一个等待队列

151
00:05:56,520 --> 00:05:57,520
这个等待队列呢

152
00:05:57,560 --> 00:05:59,120
就是我等待这个锁的

153
00:05:59,160 --> 00:06:01,240
相应的进程所排的队列

154
00:06:01,280 --> 00:06:04,520
然后我把这个锁的请求操作

155
00:06:04,560 --> 00:06:07,680
在里又增加一段内容

156
00:06:07,720 --> 00:06:10,240
先while 进行判断

157
00:06:10,280 --> 00:06:13,080
如果说在这里头呢

158
00:06:13,120 --> 00:06:16,080
查询一次之后 里头是1

159
00:06:16,120 --> 00:06:18,400
那么我就把我当前线程呢

160
00:06:18,440 --> 00:06:21,240
放到等待队列里头

161
00:06:21,280 --> 00:06:25,240
同时呢 执行调度程序

162
00:06:25,280 --> 00:06:28,400
那这时候其它进行可以继续执行

163
00:06:28,440 --> 00:06:31,080
好 一旦是切换回来

164
00:06:31,120 --> 00:06:32,760
轮着我再运行的时候

165
00:06:32,800 --> 00:06:35,960
就是有释放锁操作

166
00:06:36,000 --> 00:06:39,000
把我这个线程从等待状态

167
00:06:39,040 --> 00:06:40,480
变成就绪状态了

168
00:06:40,520 --> 00:06:42,920
好 回来的时候呢我再继续去查

169
00:06:42,960 --> 00:06:44,160
好 如果这时候

170
00:06:44,200 --> 00:06:47,000
它的状态是解锁的状态

171
00:06:47,040 --> 00:06:49,280
那请求就完成了

172
00:06:49,320 --> 00:06:52,040
好 这时候我就可以进入到临界区

173
00:06:52,080 --> 00:06:55,200
好 转过身来在释放的时候

174
00:06:55,240 --> 00:06:59,480
比我们刚才的忙等待多了点什么

175
00:06:59,520 --> 00:07:02,560
填0 表示释放锁

176
00:07:02,600 --> 00:07:03,920
这跟原来是一样的

177
00:07:03,960 --> 00:07:05,640
那加了一句就是

178
00:07:05,680 --> 00:07:07,000
我把这个线程呢

179
00:07:07,040 --> 00:07:08,360
从等待队列里头

180
00:07:08,400 --> 00:07:10,400
放到就绪队列里头去

181
00:07:10,440 --> 00:07:12,400
这是这一步做的

182
00:07:12,440 --> 00:07:13,520
好 有了这个的话

183
00:07:13,560 --> 00:07:15,760
那你在等待的过程当中呢

184
00:07:15,800 --> 00:07:21,520
我就处于放弃CPU使用权的状态

185
00:07:21,560 --> 00:07:24,000
这样的话我CPU就可以干别的了

186
00:07:24,040 --> 00:07:26,240
好 我们看到在这个过程当中呢

187
00:07:26,280 --> 00:07:28,760
我们就实现了让权等待

188
00:07:28,800 --> 00:07:33,120
这是基于TS指令的实现

189
00:07:33,160 --> 00:07:35,480
那我们说基于交换指令

190
00:07:35,520 --> 00:07:38,400
也是一样可以来做成这件事情的

191
00:07:38,440 --> 00:07:39,800
那基本上就是把这个

192
00:07:39,840 --> 00:07:42,760
TS指令的功能换成交换指令

193
00:07:42,800 --> 00:07:46,000


194
00:07:46,040 --> 00:07:49,200
好 基于原子操作指令

195
00:07:49,240 --> 00:07:51,600
所构造的这种锁

196
00:07:51,640 --> 00:07:53,280
它有什么样的特征呢

197
00:07:53,320 --> 00:07:55,760
它是适应于单处理机

198
00:07:55,800 --> 00:07:58,640
也适应于共享内存的多处理机

199
00:07:58,680 --> 00:08:00,680
我们前面讲的中断禁用

200
00:08:00,720 --> 00:08:02,480
只能用于单处理机

201
00:08:02,520 --> 00:08:03,920
如果我有多个处理机的话

202
00:08:03,960 --> 00:08:05,120
你在一个处理机上

203
00:08:05,160 --> 00:08:08,560
禁止中断的响应 那不管用

204
00:08:08,600 --> 00:08:11,760
另一个处理机上如果说有中断响应

205
00:08:11,800 --> 00:08:14,920
或者说有其它的进程执行

206
00:08:14,960 --> 00:08:16,160
那它仍然可以修改

207
00:08:16,200 --> 00:08:18,600
你共享的那些变量

208
00:08:18,640 --> 00:08:19,880
好 再有一个呢

209
00:08:19,920 --> 00:08:23,400
它能适应任意数目的进程同步

210
00:08:23,440 --> 00:08:24,960
那在这里头它不像我们前面

211
00:08:25,000 --> 00:08:28,120
你两个进程同步是一种状态

212
00:08:28,160 --> 00:08:29,600
三个更多的时候

213
00:08:29,640 --> 00:08:31,160
这种状态就会更复杂

214
00:08:31,200 --> 00:08:32,720
那么在这儿呢都是一样

215
00:08:32,760 --> 00:08:35,160
相对来说它是简单

216
00:08:35,200 --> 00:08:38,320
并且容易验证它的正确性

217
00:08:38,360 --> 00:08:41,640
好 它支持多临界区

218
00:08:41,680 --> 00:08:43,080
如果你有若干个临界区

219
00:08:43,120 --> 00:08:44,080
每一个临界区对应着

220
00:08:44,120 --> 00:08:46,120
一个锁那就可以了

221
00:08:46,160 --> 00:08:47,880
当然它也有问题

222
00:08:47,920 --> 00:08:51,640
如果说你是忙等待锁

223
00:08:51,680 --> 00:08:56,720
那这时候呢它会占用CPU的时间

224
00:08:56,760 --> 00:08:59,280
另外呢它可能导致饥饿

225
00:08:59,320 --> 00:09:00,640
也就相当于我在这里呢

226
00:09:00,680 --> 00:09:01,760
并没有做到

227
00:09:01,800 --> 00:09:06,600
按先来后到的顺序来使用资源

228
00:09:06,640 --> 00:09:09,400
因为我在锁的请求操作当中呢

229
00:09:09,440 --> 00:09:12,280
我放到就绪队列里头来之后

230
00:09:12,320 --> 00:09:13,840
我会再去检查

231
00:09:13,880 --> 00:09:14,960
就像我们前面说的

232
00:09:15,000 --> 00:09:16,440
你在检查那个时刻

233
00:09:16,480 --> 00:09:19,800
如果说资源处于空闲状态

234
00:09:19,840 --> 00:09:21,000
那就申请到了

235
00:09:21,040 --> 00:09:22,520
那你回来的时候呢

236
00:09:22,560 --> 00:09:25,040
实际上各个线程它把就绪队列

237
00:09:25,080 --> 00:09:27,640
排定的顺序并不见得是

238
00:09:27,680 --> 00:09:31,120
我们申请锁的这个顺序

239
00:09:31,160 --> 00:09:34,400
同时它还可能出现死锁

240
00:09:34,440 --> 00:09:37,080
那这描述一种死锁的情况是

241
00:09:37,120 --> 00:09:39,400
有一个低优先级的进程

242
00:09:39,440 --> 00:09:41,960
它占用了临界区资源

243
00:09:42,000 --> 00:09:43,800
好 另一个请求

244
00:09:43,840 --> 00:09:46,400
访问临界区的高优先级进程

245
00:09:46,440 --> 00:09:48,880
由于它优先级高

246
00:09:48,920 --> 00:09:49,720
那么这时候呢

247
00:09:49,760 --> 00:09:52,440
它就可以占用CPU来执行

248
00:09:52,480 --> 00:09:54,360
而占用CPU来执行呢

249
00:09:54,400 --> 00:09:56,960
实际上它执行的那个代码是请求

250
00:09:57,000 --> 00:09:59,200
如果那个地方你用的是忙等待

251
00:09:59,240 --> 00:10:00,800
那么这时候呢它就一直等待

252
00:10:00,840 --> 00:10:03,560
这样的话两边就相互等了

253
00:10:03,600 --> 00:10:05,600
低优先级等CPU

254
00:10:05,640 --> 00:10:09,360
高优先级等临界区资源

255
00:10:09,400 --> 00:10:11,120
好 那这两个互不相让

256
00:10:11,160 --> 00:10:14,200
那我们就构成死锁了

257
00:10:14,240 --> 00:10:17,480
好 这是基于硬件同步操作指令

258
00:10:17,520 --> 00:10:20,440
来实现的同步办法

259
00:10:20,480 --> 00:10:24,160
好 它可以有很好的性能

260
00:10:24,200 --> 00:10:25,840
有很好的特征

261
00:10:25,880 --> 00:10:28,320
但它需要硬件的支持

262
00:10:28,360 --> 00:10:29,520
好 到这个地方呢

263
00:10:29,560 --> 00:10:30,720
我们就介绍完了

264
00:10:30,760 --> 00:10:33,600
这三种同步的方法

265
00:10:33,640 --> 00:10:35,240
那禁用中断呢

266
00:10:35,280 --> 00:10:37,760
它比较简单 然后

267
00:10:37,800 --> 00:10:41,080
它仅适用于单处理机

268
00:10:41,120 --> 00:10:42,240
并且它会对

269
00:10:42,280 --> 00:10:45,160
系统中断的响应时间呢会有影响

270
00:10:45,200 --> 00:10:46,080
那通常情况下

271
00:10:46,120 --> 00:10:47,440
我们只是在不得已的时候

272
00:10:47,480 --> 00:10:48,840
才会去用它

273
00:10:48,880 --> 00:10:50,480
也就说我没有其它办法的时候

274
00:10:50,520 --> 00:10:52,240
我才会去用它

275
00:10:52,280 --> 00:10:54,000
第二种呢是软件办法

276
00:10:54,040 --> 00:10:55,840
它依赖的条件会比较弱

277
00:10:55,880 --> 00:10:58,080
但是它的实现非常复杂

278
00:10:58,120 --> 00:10:59,480
那在我们现在这里头呢

279
00:10:59,520 --> 00:11:00,720
用的最多的呢

280
00:11:00,760 --> 00:11:02,440
是基于原子操作指令

281
00:11:02,480 --> 00:11:04,640
实现的同步的方法

282
00:11:04,680 --> 00:11:06,320
那它不仅适用于单处理机

283
00:11:06,360 --> 00:11:07,960
也适用于多处理机

284
00:11:08,000 --> 00:11:09,960
具有容易验证的特征

285
00:11:10,040 --> 00:11:13,360
好 这是我们介绍的三种同步方法

286
00:11:13,400 --> 00:11:15,440
好 今天的课就上到这里 下课

287
00:11:15,480 --> 00:11:15,520