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


1
00:00:07,080 --> 00:00:08,240
好 那我们来看一下

2
00:00:08,280 --> 00:00:10,280
信号量的设计与实现

3
00:00:10,320 --> 00:00:13,040
首先回顾一下信号量的原理

4
00:00:13,080 --> 00:00:14,520
那所谓信号量 它的定义

5
00:00:14,560 --> 00:00:16,280
就包含了一个信号值

6
00:00:16,320 --> 00:00:17,440
一个整型的信号值

7
00:00:17,480 --> 00:00:19,200
还有一个呢 是等待队列

8
00:00:19,240 --> 00:00:20,960
这是组成了我们信号量的

9
00:00:21,000 --> 00:00:23,600
一个数据结构

10
00:00:23,640 --> 00:00:25,400
那么它的这个操作呢包含两块

11
00:00:25,440 --> 00:00:27,280
一块是P操作 一块是V操作

12
00:00:27,320 --> 00:00:28,760
对于P操作而言呢

13
00:00:28,800 --> 00:00:31,200
它会判断一下这个信号值

14
00:00:31,240 --> 00:00:32,960
信号值在做了减减操作之后

15
00:00:33,000 --> 00:00:34,720
如果小于0的话

16
00:00:34,760 --> 00:00:36,400
我们会把当前这个线程

17
00:00:36,440 --> 00:00:37,760
会加入等待队列里面去

18
00:00:37,800 --> 00:00:39,040
因为这时候它表明 

19
00:00:39,080 --> 00:00:42,160
它满足不了信号量的需求

20
00:00:42,200 --> 00:00:45,640
同时呢 让这个线程进入等待状态

21
00:00:45,680 --> 00:00:47,040
这是P操作

22
00:00:47,080 --> 00:00:49,600
那么V操作呢正好是反的一个过程

23
00:00:49,640 --> 00:00:52,040
然后会把信号值做个加加

24
00:00:52,080 --> 00:00:53,680
然后进一步判断

25
00:00:53,720 --> 00:00:55,840
看这个信号值是小于等于0的吗

26
00:00:55,880 --> 00:00:56,960
如果是的话

27
00:00:57,000 --> 00:01:00,080
它就会认为我们现在有一个线程

28
00:01:00,120 --> 00:01:02,120
可以得到信号量资源

29
00:01:02,160 --> 00:01:03,480
可以去进一步执行

30
00:01:03,520 --> 00:01:05,640
为此呢它会把某一个线程

31
00:01:05,680 --> 00:01:08,000
从等待队列里面取出来

32
00:01:08,040 --> 00:01:10,040
然后呢 唤醒这个线程

33
00:01:10,080 --> 00:01:12,000
这就是P操作和V操作的一个

34
00:01:12,040 --> 00:01:15,440
大致一个原理的一个表述

35
00:01:15,480 --> 00:01:18,440
我们来看看怎么来具体实现它

36
00:01:18,480 --> 00:01:19,720
我们来怎么设计它呢

37
00:01:19,760 --> 00:01:21,240
其实可以一一对应

38
00:01:21,280 --> 00:01:22,360
我们可以看到原理

39
00:01:22,400 --> 00:01:23,800
和我们ucorelab

40
00:01:23,840 --> 00:01:25,880
它怎么来完成这个对应关系的

41
00:01:25,920 --> 00:01:27,920
对于这个数据结构可以看出来

42
00:01:27,960 --> 00:01:29,880
这个对应还是挺直观的

43
00:01:29,920 --> 00:01:33,120
这个信号值和这个value是对应的

44
00:01:33,160 --> 00:01:34,400
这里面的等待队列

45
00:01:34,440 --> 00:01:36,440
和我们刚才讲到等待队列

46
00:01:36,480 --> 00:01:37,720
也是一一对应的

47
00:01:37,760 --> 00:01:40,400
所以呢 从数据结构上来看

48
00:01:40,440 --> 00:01:43,920
这两个之间是一致的

49
00:01:43,960 --> 00:01:46,280
那我们看它的P操作和V操作实现

50
00:01:46,320 --> 00:01:47,880
有什么样的一些区别

51
00:01:47,920 --> 00:01:49,360
这是原理部分

52
00:01:49,400 --> 00:01:50,560
这是实现部分

53
00:01:50,600 --> 00:01:51,960
我们首先关注一下

54
00:01:52,000 --> 00:01:52,760
我们的实现呢

55
00:01:52,800 --> 00:01:55,040
是按照一些小的节来组成的

56
00:01:55,080 --> 00:01:56,520
首先我们看P操作

57
00:01:56,560 --> 00:01:58,480
其实在P操作的开始

58
00:01:58,520 --> 00:02:00,440
和P操作结束的时候呢

59
00:02:00,480 --> 00:02:03,720
应该是对一个共享数据的一个保护

60
00:02:03,760 --> 00:02:07,000
所以说我们有一个Local_intr_save

61
00:02:07,040 --> 00:02:10,280
和local_intr_restore 这两个函数

62
00:02:10,320 --> 00:02:12,520
放在头和尾的位置

63
00:02:12,560 --> 00:02:14,080
使得中间的操作

64
00:02:14,120 --> 00:02:16,760
不会被打断或者被调度

65
00:02:16,800 --> 00:02:17,960
这很关键

66
00:02:18,000 --> 00:02:20,080
因为对于不同线程而言

67
00:02:20,120 --> 00:02:23,040
这个sem 它是一个共享的变量

68
00:02:23,080 --> 00:02:25,840
有可能多个线程 或者多个进程

69
00:02:25,880 --> 00:02:28,240
会同时访这个信号值

70
00:02:28,280 --> 00:02:29,920
所以我们需要通过这种方式

71
00:02:29,960 --> 00:02:32,880
使得当某一个进程或者线程

72
00:02:32,920 --> 00:02:34,600
对这个sem进行操作的时候

73
00:02:34,640 --> 00:02:36,320
或者进行访问的时候

74
00:02:36,360 --> 00:02:37,560
比如这里面还有个判断 	

75
00:02:37,600 --> 00:02:39,000
其它的线程和进程

76
00:02:39,040 --> 00:02:40,920
无法对它进行操作

77
00:02:40,960 --> 00:02:42,760
这是通过这个操作来保证的

78
00:02:42,800 --> 00:02:44,280
就是我们说的Local_intr_save

79
00:02:44,320 --> 00:02:45,960
和Local_intr_restor

80
00:02:46,000 --> 00:02:47,760
我们说 屏蔽中断机制

81
00:02:47,800 --> 00:02:49,280
这已经用到我们刚才讲到的

82
00:02:49,320 --> 00:02:53,280
一个底层机制 屏蔽中断

83
00:02:53,320 --> 00:02:54,640
好 对于这两步 

84
00:02:54,680 --> 00:02:57,640
我们说 想判断当前这个进程

85
00:02:57,680 --> 00:02:59,680
是否应该进入等待

86
00:02:59,720 --> 00:03:02,920
还是说继续去执行临界区代码呢

87
00:03:02,960 --> 00:03:04,840
用的一个这是sem- -

88
00:03:04,880 --> 00:03:06,000
和一个if判断

89
00:03:06,040 --> 00:03:07,640
我们这里面有点不太一样

90
00:03:07,680 --> 00:03:08,520
我们是直接判断

91
00:03:08,560 --> 00:03:10,880
这个sem->value是否大于0

92
00:03:10,920 --> 00:03:12,960
如果对于这里面大于0

93
00:03:13,000 --> 00:03:14,920
其实意味着这个if条件不满足

94
00:03:14,960 --> 00:03:17,160
也意味着它可以进入临界区去执行

95
00:03:17,200 --> 00:03:18,720
我们在这里面可以看出来也是一样

96
00:03:18,760 --> 00:03:20,240
如果semphore大于0

97
00:03:20,280 --> 00:03:24,200
它会直接恢复intr并restore

98
00:03:24,240 --> 00:03:26,160
这就是这一块的代码

99
00:03:26,200 --> 00:03:28,040
和这边代码对应关系

100
00:03:28,080 --> 00:03:29,480
这有点区别

101
00:03:29,520 --> 00:03:31,880


102
00:03:31,920 --> 00:03:33,360
如果小于0的话

103
00:03:33,400 --> 00:03:34,960
我们就会把当前这个线程呢

104
00:03:35,000 --> 00:03:36,360
放到等待队列里面去

105
00:03:36,400 --> 00:03:39,080
同时让当前线程处于等待状态

106
00:03:39,120 --> 00:03:40,520
就这两步完成的事情

107
00:03:40,560 --> 00:03:42,680
那如果我们是在ucore里面实现

108
00:03:42,720 --> 00:03:43,560
怎么来做呢

109
00:03:43,600 --> 00:03:46,080
我们首先会申请一个等待项

110
00:03:46,120 --> 00:03:47,720
一个wait的等待项

111
00:03:47,760 --> 00:03:49,360
并且把这个等待项呢

112
00:03:49,400 --> 00:03:50,920
挂到等待队列里面去

113
00:03:50,960 --> 00:03:52,320
而这个等待队列呢

114
00:03:52,360 --> 00:03:56,120
是在我们这个semaphore里面一个成员变量

115
00:03:56,160 --> 00:03:58,360
我们semaphore成员变量是等待队列

116
00:03:58,400 --> 00:04:03,000
关联起来 使得我们这个进程

117
00:04:03,040 --> 00:04:06,000
或者线程呢 它能够处于一种

118
00:04:06,040 --> 00:04:07,280
就是等待状态

119
00:04:07,320 --> 00:04:08,760
它能够把那个状态记录下来

120
00:04:08,800 --> 00:04:12,360
同时呢还会去做一个schedule

121
00:04:12,400 --> 00:04:15,200
由于在这里面就是wait_current_set

122
00:04:15,240 --> 00:04:17,280
它已经把这个线程

123
00:04:17,320 --> 00:04:19,400
或者进程设置为等待状态

124
00:04:19,440 --> 00:04:21,520
所以说当执行schedule的时候呢

125
00:04:21,560 --> 00:04:23,240
也意味着会有一个新的进程

126
00:04:23,280 --> 00:04:24,720
会被选出来去执行

127
00:04:24,760 --> 00:04:26,880
而当前的线程 或者进程

128
00:04:26,920 --> 00:04:33,280
它会被处于一种等待状态

129
00:04:33,320 --> 00:04:35,000
那如果说我们当前这个

130
00:04:35,040 --> 00:04:37,960
等待的线程被唤醒了

131
00:04:38,000 --> 00:04:39,160
接下来会做什么事情呢

132
00:04:39,200 --> 00:04:40,680
对原理来说可以看着

133
00:04:40,720 --> 00:04:42,480
这里没有任何执行 直接就跳出了

134
00:04:42,520 --> 00:04:44,600
但实际上在具体实现的时候

135
00:04:44,640 --> 00:04:45,800
需要考虑这个问题

136
00:04:45,840 --> 00:04:48,200
什么呢 第一个 等待线程

137
00:04:48,240 --> 00:04:51,240
它所对应等待项是否被删除掉

138
00:04:51,280 --> 00:04:52,520
如果没有被删除掉

139
00:04:52,560 --> 00:04:55,600
我们会调wait_current_del来完成

140
00:04:55,640 --> 00:04:57,920
把这个等待项从等待队列里面

141
00:04:57,960 --> 00:04:59,320
删除这么一个操作

142
00:04:59,360 --> 00:05:00,440
这是一个问题

143
00:05:00,480 --> 00:05:01,920
第二个问题是说 

144
00:05:01,960 --> 00:05:05,560
有可能当前的线程唤醒了这个原因

145
00:05:05,600 --> 00:05:07,120
就是wakeup_flag

146
00:05:07,160 --> 00:05:10,120
这个原因呢是和当时等待那个原因

147
00:05:10,160 --> 00:05:12,400
是不一致的 就是wait_state

148
00:05:12,440 --> 00:05:13,600
这两者不一致

149
00:05:13,640 --> 00:05:15,000
如果这两者不一致意味着什么

150
00:05:15,040 --> 00:05:16,800
意味着出现一种比较奇怪的现象

151
00:05:16,840 --> 00:05:19,320
我们会要把这个状态给返回回去

152
00:05:19,360 --> 00:05:22,000
让我们高层程序进一步判断

153
00:05:22,040 --> 00:05:23,680
是否是合理现象

154
00:05:23,720 --> 00:05:26,320
如果不合理 我们就说出现一些异常现象

155
00:05:26,360 --> 00:05:28,640
我们会做一些补偿的措施

156
00:05:28,680 --> 00:05:30,760
如果说我们这个wakeup_flag

157
00:05:30,800 --> 00:05:34,360
就唤醒这个状态和等待这个状态是一致的

158
00:05:34,400 --> 00:05:36,840
那我们就是一个正常的返回return 0

159
00:05:36,880 --> 00:05:40,560
这是说在一个线程被唤醒之后

160
00:05:40,600 --> 00:05:45,600
它要做的一系列操作

161
00:05:45,640 --> 00:05:47,360
那前面说的是P操作的过程

162
00:05:47,400 --> 00:05:50,000
那我们再看看V操作是怎么一回事

163
00:05:50,040 --> 00:05:51,280
首先也是同样

164
00:05:51,320 --> 00:05:53,440
由于它们对共享的变量sem

165
00:05:53,480 --> 00:05:55,880
做一个操作 和一个判断

166
00:05:55,920 --> 00:05:59,080
所以我们会把它用Local_intr_save

167
00:05:59,120 --> 00:06:01,320
和Local_intr_restore给它包起来

168
00:06:01,360 --> 00:06:03,080
从而保证互斥性

169
00:06:03,120 --> 00:06:05,760
这是第一步

170
00:06:05,800 --> 00:06:08,240
好 我们接下来看一下这个V操作

171
00:06:08,280 --> 00:06:10,520
这个V操作首先要判断一种情况是什么呢

172
00:06:10,560 --> 00:06:14,880
当前是否有线程处于等待状态

173
00:06:14,920 --> 00:06:16,960
当做一个sem++之后呢

174
00:06:17,000 --> 00:06:17,960
它会做一个判断

175
00:06:18,000 --> 00:06:19,280
是否sem>0

176
00:06:19,320 --> 00:06:21,240
如果大于0 意味着当前

177
00:06:21,280 --> 00:06:22,960
没有处于等待状态的线程

178
00:06:23,000 --> 00:06:24,520
所以它不需要唤醒

179
00:06:24,560 --> 00:06:26,560
这是原理上一个设计

180
00:06:26,600 --> 00:06:28,440
那么具体实现上呢有点不同

181
00:06:28,480 --> 00:06:30,080
我们是说首先判断一下

182
00:06:30,120 --> 00:06:31,680
这个等待队列是否为空

183
00:06:31,720 --> 00:06:33,040
这很好理解

184
00:06:33,080 --> 00:06:35,120
如果我们取出来这个等待队列

185
00:06:35,160 --> 00:06:36,520
上面这个元素是空

186
00:06:36,560 --> 00:06:39,520
意味着没有处于等待状态的线程

187
00:06:39,560 --> 00:06:41,960
这时候我会直接返回

188
00:06:42,000 --> 00:06:44,520
做一个加加操作之后就返回了

189
00:06:44,560 --> 00:06:49,720
这和我们红色部分是对应的

190
00:06:49,760 --> 00:06:51,120
另外一种情况是说

191
00:06:51,160 --> 00:06:54,600
如果现在有线程处于等待状态

192
00:06:54,640 --> 00:06:56,600
那我们需要把这个线程

193
00:06:56,640 --> 00:07:00,480
从等待状态变到就绪态 并唤醒它

194
00:07:00,520 --> 00:07:02,400
那是这两段完成的事情

195
00:07:02,440 --> 00:07:04,600
这是原理上讲的这个设计

196
00:07:04,640 --> 00:07:06,600
那对于我们具体实现呢

197
00:07:06,640 --> 00:07:07,720
其实用一个函数

198
00:07:07,760 --> 00:07:09,040
wakeup_wait

199
00:07:09,080 --> 00:07:10,720
就可以完成这两部分事情

200
00:07:10,760 --> 00:07:13,040
第一部分是从等待队列里面

201
00:07:13,080 --> 00:07:15,320
把对应线程给找出来

202
00:07:15,360 --> 00:07:16,960
同时把它的状态

203
00:07:17,000 --> 00:07:19,160
从等待状态变到就绪状态

204
00:07:19,200 --> 00:07:21,600


205
00:07:21,640 --> 00:07:23,000
好 我们看一下

206
00:07:23,040 --> 00:07:25,320
怎么来调用信号量的P操作

207
00:07:25,360 --> 00:07:28,040
在ucorelab里面有一系列函数

208
00:07:28,080 --> 00:07:29,280
高层的函数 

209
00:07:29,320 --> 00:07:31,280
它会通过这个down操作

210
00:07:31,320 --> 00:07:34,320
来完成对这个信号量的P操作的访问

211
00:07:34,360 --> 00:07:35,800
这个down是一个函数

212
00:07:35,840 --> 00:07:37,680
它会进一步调一个_down

213
00:07:37,720 --> 00:07:39,680
来完成进一步一些工作

214
00:07:39,720 --> 00:07:40,440
完成什么呢

215
00:07:40,480 --> 00:07:43,120
首先对全局变量一个互斥的保护

216
00:07:43,160 --> 00:07:44,400
通过屏蔽中断

217
00:07:44,440 --> 00:07:45,840
这两个屏蔽中断来完成

218
00:07:45,880 --> 00:07:47,920
第二个呢是把当前的状态

219
00:07:47,960 --> 00:07:50,240
从运行态变到等待状态

220
00:07:50,280 --> 00:07:52,880
然后呢挂到这个等待队列里面去

221
00:07:52,920 --> 00:07:54,120
完成schedule

222
00:07:54,160 --> 00:07:56,080
这样就使得当前进程

223
00:07:56,120 --> 00:07:57,440
就不再占用CPU了

224
00:07:57,480 --> 00:07:58,760
有新的进程会被选出来

225
00:07:58,800 --> 00:08:00,480
占到CPU去执行

226
00:08:00,520 --> 00:08:02,200
一旦后续的工作中呢

227
00:08:02,240 --> 00:08:03,800
如果说通过V操作

228
00:08:03,840 --> 00:08:07,200
把这个当前等待线程给唤醒之后

229
00:08:07,240 --> 00:08:09,360
我们还会做进一步的

230
00:08:09,400 --> 00:08:13,080
把这个等待项给它删除的一些操作

231
00:08:13,120 --> 00:08:14,320
从而可以继续去

232
00:08:14,360 --> 00:08:16,560
从等待状态变到就绪态

233
00:08:16,600 --> 00:08:17,880
进入到就绪队列里面去

234
00:08:17,920 --> 00:08:20,560
进一步去完成相应的执行工作

235
00:08:20,600 --> 00:08:22,960
这是说调用信号量P操作

236
00:08:23,000 --> 00:08:26,440
的一个大致执行过程

237
00:08:26,480 --> 00:08:28,760
第二个 是关于调用信号量V操作的

238
00:08:28,800 --> 00:08:30,040
一个执行过程

239
00:08:30,080 --> 00:08:32,680
也是一样 有类似一系列高层函数

240
00:08:32,720 --> 00:08:34,080
会调这个UP函数

241
00:08:34,120 --> 00:08:36,480
这个UP函数呢就对应V操作

242
00:08:36,520 --> 00:08:38,760
UP会进一步调一个_up

243
00:08:38,800 --> 00:08:40,560
然后它完成同样类似事情

244
00:08:40,600 --> 00:08:42,560
首先要对全局变量做一个保护

245
00:08:42,600 --> 00:08:44,880
通过屏蔽中断来支撑

246
00:08:44,920 --> 00:08:47,200
然后呢去查找等待队列里面

247
00:08:47,240 --> 00:08:49,680
是否有等待的线程

248
00:08:49,720 --> 00:08:51,040
如果有 会把它唤醒

249
00:08:51,080 --> 00:08:52,680
如果没有 就直接跳出

250
00:08:52,720 --> 00:08:54,760
让信号量做个加加就OK了  

251
00:08:54,800 --> 00:08:54,840