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


1
00:00:06,880 --> 00:00:08,600
好 那我们看看

2
00:00:08,640 --> 00:00:10,200
接下来我们要完成的练习就是

3
00:00:10,240 --> 00:00:11,560
stride scheduling

4
00:00:11,600 --> 00:00:12,960
这是一个我们在原理课

5
00:00:13,000 --> 00:00:14,560
没有讲的一个算法

6
00:00:14,600 --> 00:00:15,240
这个算法呢

7
00:00:15,280 --> 00:00:17,080
来自于一篇比较有名的一个论文

8
00:00:17,120 --> 00:00:19,400
大家有兴趣的话可以看看这篇论文

9
00:00:19,440 --> 00:00:23,680
这边给出了一个相应的链接

10
00:00:23,720 --> 00:00:25,640
当然我们也通过简单的图示

11
00:00:25,680 --> 00:00:26,680
来给大家展示一下

12
00:00:26,720 --> 00:00:29,280
这个算法它大致的一个含义是什么

13
00:00:29,320 --> 00:00:31,080
假定我们现在有三个进程

14
00:00:31,120 --> 00:00:33,000
P1  P2  P3

15
00:00:33,040 --> 00:00:35,320
那么呢 每个进程有两个属性

16
00:00:35,360 --> 00:00:36,760
一个属性是什么呢 它的步长

17
00:00:36,800 --> 00:00:39,360
就是说它现在执行到了什么地方

18
00:00:39,400 --> 00:00:41,160
你可以把这个理解为一个跑道

19
00:00:41,200 --> 00:00:42,160
可以看出来

20
00:00:42,200 --> 00:00:43,880
这个stride有三个

21
00:00:43,920 --> 00:00:46,080
P1是100 P2是106

22
00:00:46,120 --> 00:00:47,800
P3是102

23
00:00:47,840 --> 00:00:51,200
也就意味着现在最落后的是谁 是P1

24
00:00:51,240 --> 00:00:53,800
那么跑的最快的是谁呢  P2

25
00:00:53,840 --> 00:00:56,440
因为它这个106最大的一个值

26
00:00:56,480 --> 00:00:57,640
这是一个参数

27
00:00:57,680 --> 00:00:59,800
就是当前的它的位置

28
00:00:59,840 --> 00:01:00,840
第二个呢

29
00:01:00,880 --> 00:01:05,560
pass 要代表它一次要前进的步数

30
00:01:05,600 --> 00:01:08,360
比如说P1它一次前进的步数是16

31
00:01:08,400 --> 00:01:11,360
P2一次前进的步数是7

32
00:01:11,400 --> 00:01:14,120
P3一次前进的步数是10

33
00:01:14,160 --> 00:01:15,800
那我们这个调度的

34
00:01:15,840 --> 00:01:18,280
算法的策略怎么来选择呢

35
00:01:18,320 --> 00:01:20,160
我们要选择当前

36
00:01:20,200 --> 00:01:24,960
步长最小的一个值的进程去执行它

37
00:01:25,000 --> 00:01:27,480
然后呢 它执行的长度是多少呢

38
00:01:27,520 --> 00:01:30,360
是这个当前的步长加上它这个pass

39
00:01:30,400 --> 00:01:31,680
所以说我们可以看到

40
00:01:31,720 --> 00:01:33,480
在这种情况下我们要选择哪个呢

41
00:01:33,520 --> 00:01:35,920
很明显 这个P1

42
00:01:35,960 --> 00:01:39,840
它这个当前的步长是最小的

43
00:01:39,880 --> 00:01:41,080
所以我们选择它

44
00:01:41,120 --> 00:01:45,920
然后呢 它会去走一段距离

45
00:01:45,960 --> 00:01:48,280
是stride加上pass

46
00:01:48,320 --> 00:01:50,120
我们叫做步进值

47
00:01:50,160 --> 00:01:50,880
一个是步长值

48
00:01:50,920 --> 00:01:51,840
一个是步进值 OK

49
00:01:51,880 --> 00:01:53,360
它到这个位置了

50
00:01:53,400 --> 00:01:55,160
好 我们接下来再看一看

51
00:01:55,200 --> 00:01:57,240
当前谁的步长是最小的呢

52
00:01:57,280 --> 00:01:59,320
P3现在是102

53
00:01:59,360 --> 00:02:00,800
所以说我们接下来呢

54
00:02:00,840 --> 00:02:04,440
我们的调度算法应该选择P3

55
00:02:04,480 --> 00:02:07,680
然后它执行的步长是什么呢

56
00:02:07,720 --> 00:02:10,520
10  102加上10等于112

57
00:02:10,560 --> 00:02:11,760
到这个位置

58
00:02:11,800 --> 00:02:13,960
好 再接下来是P2

59
00:02:14,000 --> 00:02:16,960


60
00:02:17,000 --> 00:02:20,600
它走的步长会到113这个位置

61
00:02:20,640 --> 00:02:23,160
好 这三个进程都走了一轮之后呢

62
00:02:23,200 --> 00:02:24,640
我们接下来再判断

63
00:02:24,680 --> 00:02:28,160
第二轮的时候谁最小呢 P3最小

64
00:02:28,200 --> 00:02:35,840
所以在这个时候应该选择P3去执行

65
00:02:35,880 --> 00:02:39,840
这时候它已经变成122了

66
00:02:39,880 --> 00:02:46,520
再接下来很明显P2执行

67
00:02:46,560 --> 00:02:48,920
然后周而复始来完成这个

68
00:02:48,960 --> 00:02:52,360
所有进程的一个选择 让谁去执行

69
00:02:52,400 --> 00:02:53,680
那可以看出来

70
00:02:53,720 --> 00:02:56,720
这里面谁的步进值越小

71
00:02:56,760 --> 00:02:59,800
那么它被调度的次数会越多

72
00:02:59,840 --> 00:03:01,240
大家想想为什么

73
00:03:01,280 --> 00:03:04,440
这给大家留一个思考

74
00:03:04,480 --> 00:03:06,640
那这个算法呢 它具有两个特点

75
00:03:06,680 --> 00:03:08,000
它可以基于

76
00:03:08,040 --> 00:03:09,720
进程的优先级来进行调度

77
00:03:09,760 --> 00:03:11,000
那么这个优先级会和

78
00:03:11,040 --> 00:03:14,120
我们的步进长度成一个反比

79
00:03:14,160 --> 00:03:15,600
我们后面会讲到

80
00:03:15,640 --> 00:03:16,480
第二个呢

81
00:03:16,520 --> 00:03:18,640
它整个这个调度的选择是确定的

82
00:03:18,680 --> 00:03:20,080
每一次选择不是

83
00:03:20,120 --> 00:03:21,360
一个随机出现的一个值

84
00:03:21,400 --> 00:03:22,520
而是一个确定的值

85
00:03:22,560 --> 00:03:24,800
所以这个算法具有这两个优势

86
00:03:24,840 --> 00:03:29,680
我们希望大家采取一定的数据结构

87
00:03:29,720 --> 00:03:32,280
和一定的操作过程

88
00:03:32,320 --> 00:03:35,240
来完成对这个算法的一个实现

89
00:03:35,280 --> 00:03:37,560
这里面首先就要选择合适数据结构

90
00:03:37,600 --> 00:03:39,280
为什么呢

91
00:03:39,320 --> 00:03:41,240
因为我们基于数据结构

92
00:03:41,280 --> 00:03:45,560
要完成相应的插入 查找 删除操作

93
00:03:45,600 --> 00:03:46,680
而这个和我们

94
00:03:46,720 --> 00:03:47,720
这个数据结构紧密联系

95
00:03:47,760 --> 00:03:50,120
到底是取的list还是一个特殊的队列

96
00:03:50,160 --> 00:03:51,800
比如优先队列等等

97
00:03:51,840 --> 00:03:54,040
这些都影响到你后续的

98
00:03:54,080 --> 00:03:55,960
这个算法的实现

99
00:03:56,000 --> 00:03:57,240
那我们完成的步骤

100
00:03:57,280 --> 00:03:59,040
第一步就是选择完数据结构之后呢

101
00:03:59,080 --> 00:04:01,560
你就要去实现里面的

102
00:04:01,600 --> 00:04:04,520
很重要的初始化函数init

103
00:04:04,560 --> 00:04:07,080
从而可以完成对这个相应的队列

104
00:04:07,120 --> 00:04:10,600
数组 堆 等的初始化

105
00:04:10,640 --> 00:04:11,560
紧接着呢

106
00:04:11,600 --> 00:04:12,600
会基于这种数据结构

107
00:04:12,640 --> 00:04:16,160
来实现入队和出队这么两个函数

108
00:04:16,200 --> 00:04:17,680
这里面再次提醒一下

109
00:04:17,720 --> 00:04:19,400
这个入队出队是一个抽象的概念

110
00:04:19,440 --> 00:04:20,520
它并不代表说

111
00:04:20,560 --> 00:04:21,320
你处理的数据结构

112
00:04:21,360 --> 00:04:22,760
一定要是一个queue

113
00:04:22,800 --> 00:04:26,600
一个队列

114
00:04:26,640 --> 00:04:27,840
第二个呢 我们要实现什么呢

115
00:04:27,880 --> 00:04:29,360
就是选择操作

116
00:04:29,400 --> 00:04:31,880
就是到底选择哪一个来

117
00:04:31,920 --> 00:04:34,840
作为接下来占用CPU执行的进程

118
00:04:34,880 --> 00:04:39,240
这是pick_next要完成的工作

119
00:04:39,280 --> 00:04:41,440
假定我们选择了之后呢

120
00:04:41,480 --> 00:04:42,760
接下来还要干的一个事情

121
00:04:42,800 --> 00:04:44,680
是proc_tick

122
00:04:44,720 --> 00:04:48,120
proc_tick是要改变当前的

123
00:04:48,160 --> 00:04:49,960
一个调度的一个参数

124
00:04:50,000 --> 00:04:51,520
是否需要调度了

125
00:04:51,560 --> 00:04:53,040
proc_tick在哪改呢

126
00:04:53,080 --> 00:04:54,000
我们前面也讲到

127
00:04:54,040 --> 00:04:55,320
是在中断的

128
00:04:55,360 --> 00:04:57,280
关于时钟中断处理例程里面

129
00:04:57,320 --> 00:05:00,640
会对这做一定的设置

130
00:05:00,680 --> 00:05:03,800
如果认为当前进程用完了时间片

131
00:05:03,840 --> 00:05:05,360
因为它每一个时钟中断

132
00:05:05,400 --> 00:05:08,000
代表一个时间片的一小部分

133
00:05:08,040 --> 00:05:09,280
当比如说一百个时钟中断

134
00:05:09,320 --> 00:05:11,040
代表一个时间片的话

135
00:05:11,080 --> 00:05:12,320
那么用完了时间片

136
00:05:12,360 --> 00:05:13,800
那么就需要重新调度

137
00:05:13,840 --> 00:05:16,400
这时候就要设置一个调度的一个

138
00:05:16,440 --> 00:05:17,160
我们前面讲的

139
00:05:17,200 --> 00:05:19,640
设置一个调度的变量

140
00:05:19,680 --> 00:05:21,040
叫做need_resched

141
00:05:21,080 --> 00:05:22,480
把它置为1之后呢

142
00:05:22,520 --> 00:05:24,120
在接下来的某一个调度点

143
00:05:24,160 --> 00:05:30,120
就会完成对schedule这个函数的调用

144
00:05:30,160 --> 00:05:32,960
好 这前面几个函数执行完之后

145
00:05:33,000 --> 00:05:34,160
我们还要完成一个

146
00:05:34,200 --> 00:05:36,000
入队和出队的一个实现

147
00:05:36,040 --> 00:05:39,160
把这个实现了那我们就认为

148
00:05:39,200 --> 00:05:41,440
我们就把这个关于这个调度算法

149
00:05:41,480 --> 00:05:43,560
最关键的几个函数实现完毕

150
00:05:43,600 --> 00:05:45,520
最后还需要干的一个事情就是

151
00:05:45,560 --> 00:05:48,760
把它的这个调度类设置对

152
00:05:48,800 --> 00:05:51,320
就是在sched_init这个函数里面呢

153
00:05:51,360 --> 00:05:54,240
来设置一个default_sched_class

154
00:05:54,280 --> 00:05:55,440
设置好之后就意味着

155
00:05:55,480 --> 00:05:57,720
我们的schedule函数能够找到

156
00:05:57,760 --> 00:06:00,760
你所设计的这个特定的一个调度类

157
00:06:00,800 --> 00:06:03,360
针对你的这个Stride调度算法的调度类

158
00:06:03,400 --> 00:06:05,680
来完成具体的调度过程

159
00:06:05,720 --> 00:06:08,600
当你完成了上述的函数和相应的一个

160
00:06:08,640 --> 00:06:10,320
关于这个算法的

161
00:06:10,360 --> 00:06:12,320
调度类的一个设置之后呢

162
00:06:12,360 --> 00:06:14,440
我们可以通过执行如下这个命令

163
00:06:14,480 --> 00:06:16,080
make run-priority

164
00:06:16,120 --> 00:06:18,840
来检查你是否正确的实现了这个

165
00:06:18,880 --> 00:06:22,960
stride调度算法

166
00:06:23,000 --> 00:06:24,320
那我们接下来呢

167
00:06:24,360 --> 00:06:26,640
给大家做一些提示

168
00:06:26,680 --> 00:06:27,880
使大家可以比较方便的

169
00:06:27,920 --> 00:06:29,440
来完成这个实验

170
00:06:29,480 --> 00:06:30,560
首先第一点就在于

171
00:06:30,600 --> 00:06:32,840
你怎么选择一个合适的数据结构

172
00:06:32,880 --> 00:06:33,960
那么这个数据结构呢

173
00:06:34,000 --> 00:06:35,760
会有助于你完成针对

174
00:06:35,800 --> 00:06:37,360
stride这个调度算法的

175
00:06:37,400 --> 00:06:42,320
插入 删除和选择这么几个操作

176
00:06:42,360 --> 00:06:44,600
这里面可以用前面讲的list

177
00:06:44,640 --> 00:06:46,160
双向链表来完成

178
00:06:46,200 --> 00:06:47,840
也可以用一些更新的一些数据结构

179
00:06:47,880 --> 00:06:49,120
priority queue

180
00:06:49,160 --> 00:06:50,800
这代表是优先队列

181
00:06:50,840 --> 00:06:52,480
那么优先队列呢

182
00:06:52,520 --> 00:06:54,800
又可以用进一步的具体的叫做

183
00:06:54,840 --> 00:06:56,360
斜堆（skew heap）这么一个数据结构

184
00:06:56,400 --> 00:06:57,600
来完成相应的操作

185
00:06:57,640 --> 00:06:58,880
就是哪三个操作呢

186
00:06:58,920 --> 00:07:02,200
插入 删除 查找

187
00:07:02,240 --> 00:07:03,920
如果采取双向链表

188
00:07:03,960 --> 00:07:05,200
那么它的这个时间开销

189
00:07:05,240 --> 00:07:08,000
是和我们进程个数呈一个线性关系

190
00:07:08,040 --> 00:07:10,080
就O(n)这么一个关系

191
00:07:10,120 --> 00:07:11,840
那它的执行开销比较大

192
00:07:11,880 --> 00:07:13,520
如果我们采取一种新的数据结构

193
00:07:13,560 --> 00:07:16,400
比如说基于斜堆的优先队列的话

194
00:07:16,440 --> 00:07:18,640
那么它的这个执行开销

195
00:07:18,680 --> 00:07:21,600
就是查找 删除 插入

196
00:07:21,640 --> 00:07:23,640
会比基于双向链表这个开销呢

197
00:07:23,680 --> 00:07:25,280
要优化很多

198
00:07:25,320 --> 00:07:26,160
所以说我们这里可以

199
00:07:26,200 --> 00:07:29,000
采取基于斜堆的优先队列

200
00:07:29,040 --> 00:07:31,880
来完成这么一个数据结构一个组织

201
00:07:31,920 --> 00:07:33,960
那这里面很重要就在于一个比较

202
00:07:34,000 --> 00:07:35,240
因为它是一个堆结构

203
00:07:35,280 --> 00:07:36,320
这个比较函数呢

204
00:07:36,360 --> 00:07:37,800
大家可以看它怎么实现的

205
00:07:37,840 --> 00:07:40,960


206
00:07:41,000 --> 00:07:43,280
有了这个斜堆这么一个结构之后呢

207
00:07:43,320 --> 00:07:44,680
我们就可以完成

208
00:07:44,720 --> 00:07:46,800
关于这个数据结构的初始化

209
00:07:46,840 --> 00:07:49,520
插入 移除这么一个操作

210
00:07:49,560 --> 00:07:50,640
那么通过比较呢

211
00:07:50,680 --> 00:07:53,280
能够很快找着当前

212
00:07:53,320 --> 00:07:56,720
最值得去执行的那个进程在哪

213
00:07:56,760 --> 00:08:01,920
它正好是这个堆顶很容易找着

214
00:08:01,960 --> 00:08:03,320
那么进一步我们会去修改

215
00:08:03,360 --> 00:08:06,080
关于进程控制块的这么一个结构

216
00:08:06,120 --> 00:08:07,720
增加一些相关的信息

217
00:08:07,760 --> 00:08:09,600
比如说它有一个针对

218
00:08:09,640 --> 00:08:12,240
斜堆的这么一个运行队列

219
00:08:12,280 --> 00:08:14,000
那么我们会把我们这个

220
00:08:14,040 --> 00:08:16,440
就绪进程呢挂到这个队列里面去

221
00:08:16,480 --> 00:08:18,760
第二个呢这里面有一个stride

222
00:08:18,800 --> 00:08:22,120
代表当前进程它这个步长值是多少

223
00:08:22,160 --> 00:08:23,600
还有是一个优先级

224
00:08:23,640 --> 00:08:24,880
这个优先级什么意思呢

225
00:08:24,920 --> 00:08:26,640
就是说你优先级越高

226
00:08:26,680 --> 00:08:30,040
证明你越有优先执行的权限

227
00:08:30,080 --> 00:08:32,480
它和我们刚才说那个步进值pass

228
00:08:32,520 --> 00:08:33,800
正好起一个反比

229
00:08:33,840 --> 00:08:35,600
优先级越高它的pass值越低

230
00:08:35,640 --> 00:08:37,160
而pass值越低呢

231
00:08:37,200 --> 00:08:38,040
也意味着它有

232
00:08:38,080 --> 00:08:42,720
更多的机会被调度去执行

233
00:08:42,760 --> 00:08:45,000
另外还需要整个队列一个结构

234
00:08:45,040 --> 00:08:46,360
我们还是一个run_queue

235
00:08:46,400 --> 00:08:47,320
但是这里面专门有一个

236
00:08:47,360 --> 00:08:49,280
特殊的 叫lab6的run_queue

237
00:08:49,320 --> 00:08:52,960
来完成对这个结构管理和记录

238
00:08:53,000 --> 00:08:55,600
当然这个结构跟前面不太一样

239
00:08:55,640 --> 00:08:56,600
在哪呢

240
00:08:56,640 --> 00:08:57,800
我们前面一般是用list

241
00:08:57,840 --> 00:08:59,480
list entry是一个双向链表

242
00:08:59,520 --> 00:09:01,800
这里面是skew_heap

243
00:09:01,840 --> 00:09:08,920
基于斜堆这么一个数据结构

244
00:09:08,960 --> 00:09:11,560
好 这里面还给大家一些提示就是

245
00:09:11,600 --> 00:09:14,200
这个pass和priority

246
00:09:14,240 --> 00:09:17,600
到底什么样一个关系

247
00:09:17,640 --> 00:09:19,440
我们这里面来设置就是pass

248
00:09:19,480 --> 00:09:23,040
等于一个BIG_VALUE / lab6_priority

249
00:09:23,080 --> 00:09:24,040
这个lab6的priority

250
00:09:24,080 --> 00:09:27,160
代表某一个进程它的优先级

251
00:09:27,200 --> 00:09:29,000
这个值可以设置成不一样的

252
00:09:29,040 --> 00:09:29,760
可以设置很大

253
00:09:29,800 --> 00:09:31,040
也可以设置很小

254
00:09:31,080 --> 00:09:32,320
那么BIG_VALUE就可以

255
00:09:32,360 --> 00:09:33,440
设置一个相当大的值

256
00:09:33,480 --> 00:09:36,080
就说有这些priority都不会大于这个BIG_VALUE

257
00:09:36,120 --> 00:09:38,320
使得这个BIG_VALUE除以这个priority

258
00:09:38,360 --> 00:09:41,200
会得到一个pass就是步进值

259
00:09:41,240 --> 00:09:44,360
那步进值越小它前进的越慢

260
00:09:44,400 --> 00:09:45,800
那我们调度时候呢

261
00:09:45,840 --> 00:09:48,280
就会更多的选择这种进程去执行

262
00:09:48,320 --> 00:09:50,280
这也是为什么这个pass和priority

263
00:09:50,320 --> 00:09:52,800
正好是起反比的作用

264
00:09:52,840 --> 00:09:55,640
第二个需要大家注意的是什么呢

265
00:09:55,680 --> 00:09:56,840
这个步长

266
00:09:56,880 --> 00:09:58,520
这个stride这个值呢

267
00:09:58,560 --> 00:10:01,200
随着它不停地累加 其实会溢出

268
00:10:01,240 --> 00:10:02,480
你怎么保证这个溢出

269
00:10:02,520 --> 00:10:05,400
不会影响到对这个值判断

270
00:10:05,440 --> 00:10:07,000
比如到底选择哪一个

271
00:10:07,040 --> 00:10:09,560
最小那个stride去执行

272
00:10:09,600 --> 00:10:12,200
这个我们是需要有一些特殊的考虑

273
00:10:12,240 --> 00:10:13,880


274
00:10:13,920 --> 00:10:16,520
大家要想到这里面有一些约束条件

275
00:10:16,560 --> 00:10:19,520
比如说STRIDE_MAX减去STRIDE_MIN

276
00:10:19,560 --> 00:10:24,640
要小于PASS_MAX 这是一个约束条件

277
00:10:24,680 --> 00:10:26,960
第二个呢我们还做一个特定设置

278
00:10:27,000 --> 00:10:29,000
STRIDE和PASS是无符号整数

279
00:10:29,040 --> 00:10:31,080
大家可以关注一下我们数据结构

280
00:10:31,120 --> 00:10:35,560
可以看到都是unit32_t 32位无符号整型

281
00:10:35,600 --> 00:10:37,120
那么有了这个之后呢

282
00:10:37,160 --> 00:10:39,320
我们再做比较的时候

283
00:10:39,360 --> 00:10:41,200
是用的有符号值来比较

284
00:10:41,240 --> 00:10:43,200
那么这一种设计技巧呢

285
00:10:43,240 --> 00:10:47,600
使得我们可以避免出现溢出之后

286
00:10:47,640 --> 00:10:49,920
无法去做正确的判断

287
00:10:49,960 --> 00:10:50,680
到底这个stride

288
00:10:50,720 --> 00:10:52,920
谁大谁小这么一种情况

289
00:10:52,960 --> 00:10:54,280
在这里面大家有必要去

290
00:10:54,320 --> 00:10:56,400
深入理解一下这个stride

291
00:10:56,440 --> 00:10:58,360
的比较是怎么来完成的

292
00:10:58,400 --> 00:10:59,960
在它不停累加情况下

293
00:11:00,000 --> 00:11:01,280
依然能正确的判断出

294
00:11:01,320 --> 00:11:03,400
到底是谁的这个stride值最小

295
00:11:03,440 --> 00:11:06,360


296
00:11:06,400 --> 00:11:09,080
好 那前面给大家做了简单介绍

297
00:11:09,120 --> 00:11:11,480
希望大家 能够基于这些介绍

298
00:11:11,520 --> 00:11:15,080
能够理解关于这个调度算法的

299
00:11:15,120 --> 00:11:16,600
一个支撑框架怎么来的

300
00:11:16,640 --> 00:11:18,640
第二 基于这个支撑框架知道

301
00:11:18,680 --> 00:11:20,400
我们ucore操作系统

302
00:11:20,440 --> 00:11:22,000
在什么时候可以完成

303
00:11:22,040 --> 00:11:25,360
对调度算法一个函数的执行 这是一个

304
00:11:25,400 --> 00:11:27,240
第三个希望大家能够

305
00:11:27,280 --> 00:11:29,320
参考Round Robin这个调度算法

306
00:11:29,360 --> 00:11:31,520
来完成对这个stride调度算法的实现

307
00:11:31,560 --> 00:11:31,600