0
00:00:00,640 --> 00:00:15,880


1
00:00:15,920 --> 00:00:16,760
各位同学好

2
00:00:16,800 --> 00:00:18,760
那么我们这次课呢

3
00:00:18,800 --> 00:00:20,720
是讲解lab6

4
00:00:20,760 --> 00:00:23,120
lab6是关于处理器调度

5
00:00:23,160 --> 00:00:25,600
那这一节呢 

6
00:00:25,640 --> 00:00:27,480
主要有一个总体介绍

7
00:00:27,520 --> 00:00:29,360
调度的过程的一个分析

8
00:00:29,400 --> 00:00:30,760
以及我们说

9
00:00:30,800 --> 00:00:32,160
为了支持不同的调度算法

10
00:00:32,200 --> 00:00:33,640
我们要设计的一个支撑框架

11
00:00:33,680 --> 00:00:35,520
就是调度算法的一个支撑框架

12
00:00:35,560 --> 00:00:37,600
然后呢 给大家介绍一下

13
00:00:37,640 --> 00:00:39,160
在实验中已经提供的

14
00:00:39,200 --> 00:00:41,000
Round Robin的调度算法

15
00:00:41,040 --> 00:00:42,920
希望同学能够实现什么呢

16
00:00:42,960 --> 00:00:44,440
是一个Stride调度算法

17
00:00:44,480 --> 00:00:46,640
这个算法呢 在原理课里面没有讲

18
00:00:46,680 --> 00:00:49,200
我们希望通过同学的分析 理解

19
00:00:49,240 --> 00:00:51,840
能够在lab6中完成

20
00:00:51,880 --> 00:00:54,880
首先我们来看一下总体介绍

21
00:00:54,920 --> 00:00:56,680
那总体介绍 主要介绍一下

22
00:00:56,720 --> 00:00:59,280
我们这个实验的目标 练习

23
00:00:59,320 --> 00:01:02,480
和一个大致的流程概述

24
00:01:02,520 --> 00:01:05,280
可以看到 在我们完成了lab5之后

25
00:01:05,320 --> 00:01:07,720
我们说 我们可以创建前面的

26
00:01:07,760 --> 00:01:10,040
内核线程和用户进程

27
00:01:10,080 --> 00:01:11,280
当我们的操作系统中

28
00:01:11,320 --> 00:01:13,120
存在多个进程的时候

29
00:01:13,160 --> 00:01:14,840
比如说有多个进程的时候

30
00:01:14,880 --> 00:01:15,920
那就需要知道

31
00:01:15,960 --> 00:01:18,560
有些进程它会占用cpu执行

32
00:01:18,600 --> 00:01:21,600
有些进程可能会等待cpu执行

33
00:01:21,640 --> 00:01:23,560
这里面有一个生命周期的管理

34
00:01:23,600 --> 00:01:24,880
那我们这里面重点研究的

35
00:01:24,920 --> 00:01:27,080
是什么时候 基于什么原则

36
00:01:27,120 --> 00:01:29,320
来选择哪一个进程去执行

37
00:01:29,360 --> 00:01:31,760
这是我们说调度要考虑的问题

38
00:01:31,800 --> 00:01:32,720
这是我们lab6中

39
00:01:32,760 --> 00:01:34,200
重点需要去理解

40
00:01:34,240 --> 00:01:37,720
和掌握的一个知识

41
00:01:37,760 --> 00:01:39,840
好 那我们的目标可以看看

42
00:01:39,880 --> 00:01:40,920
细分一下 第一个是

43
00:01:40,960 --> 00:01:44,520
理解操作系统的调度管理机制

44
00:01:44,560 --> 00:01:46,040
第二个是熟悉ucore

45
00:01:46,080 --> 00:01:48,280
这个调度器的设计框架

46
00:01:48,320 --> 00:01:50,880
第三个是理解Round Robin调度算法

47
00:01:50,920 --> 00:01:53,960
第四个 我们要去根据你对Stride

48
00:01:54,000 --> 00:01:56,320
调度算法的理解来完成它

49
00:01:56,360 --> 00:01:59,720
到底怎么去实现它这个调度算法

50
00:01:59,760 --> 00:02:01,280
这是我们的目标

51
00:02:01,320 --> 00:02:04,640
为此你需要去对ucore的

52
00:02:04,680 --> 00:02:07,320
lab6里面的源码进行一个分析

53
00:02:07,360 --> 00:02:09,160
包括调度器的框架

54
00:02:09,200 --> 00:02:10,640
Round Robin调度算法

55
00:02:10,680 --> 00:02:16,080
以及Stride调度算法

56
00:02:16,120 --> 00:02:17,720
那其实我们可以看看

57
00:02:17,760 --> 00:02:18,920
对于应用程序而言

58
00:02:18,960 --> 00:02:20,520
比如hello这个应用程序

59
00:02:20,560 --> 00:02:21,960
看起来它这里面

60
00:02:22,000 --> 00:02:24,160
和操作系统的调度没有任何关系

61
00:02:24,200 --> 00:02:25,200
但其实呢

62
00:02:25,240 --> 00:02:27,200
操作系统在管理这个进程的

63
00:02:27,240 --> 00:02:29,720
从创建到最后它消失

64
00:02:29,760 --> 00:02:31,320
这个过程呢 其实我们操作系统

65
00:02:31,360 --> 00:02:33,720
有多次的调度的机会

66
00:02:33,760 --> 00:02:35,720
去选择让这个进程执行

67
00:02:35,760 --> 00:02:37,400
或者是不让它执行

68
00:02:37,440 --> 00:02:38,800
这其实是在后面

69
00:02:38,840 --> 00:02:40,560
我们操作系统的底层

70
00:02:40,600 --> 00:02:43,040
来完成了整个调度的过程

71
00:02:43,080 --> 00:02:44,480
而所有的过程

72
00:02:44,520 --> 00:02:46,800
对我们应用程序的执行来说

73
00:02:46,840 --> 00:02:51,120
是透明的 看不见的

74
00:02:51,160 --> 00:02:53,400
好 那我们再把大致的流程

75
00:02:53,440 --> 00:02:54,520
给大家介绍一下

76
00:02:54,560 --> 00:02:56,360
首先我们回顾一下

77
00:02:56,400 --> 00:02:58,360
这个调度 其实并不是说

78
00:02:58,400 --> 00:02:59,960
在lab6才出现

79
00:03:00,000 --> 00:03:03,040
在早期的lab5

80
00:03:03,080 --> 00:03:04,680
其实已经出现了调度

81
00:03:04,720 --> 00:03:07,000
我们可以回顾一下 看看怎么回事

82
00:03:07,040 --> 00:03:08,640
lab5中它完成了

83
00:03:08,680 --> 00:03:10,960
对用户进程的管理

84
00:03:11,000 --> 00:03:12,840
那在这个管理过程中呢

85
00:03:12,880 --> 00:03:14,240
涉及到对整个进程

86
00:03:14,280 --> 00:03:16,560
生命周期的管理

87
00:03:16,600 --> 00:03:17,880
我们这边其实已经存在了

88
00:03:17,920 --> 00:03:20,160
对一般进程它也有个调度

89
00:03:20,200 --> 00:03:22,320
只是这个调度很简单 是FIFO

90
00:03:22,360 --> 00:03:24,960
我们说先进先出这么一个调度算法

91
00:03:25,000 --> 00:03:28,040
这里面呢 一个进程当创建完之后

92
00:03:28,080 --> 00:03:29,320
它处于就绪态

93
00:03:29,360 --> 00:03:32,600
然后一旦被我们的ucore选择

94
00:03:32,640 --> 00:03:34,640
去让它在CPU上执行的时候

95
00:03:34,680 --> 00:03:36,480
它就从头执行 直到结束

96
00:03:36,520 --> 00:03:38,120
中间不会被打断

97
00:03:38,160 --> 00:03:39,320
只有结束之后

98
00:03:39,360 --> 00:03:42,240
我们的ucore才会去查找

99
00:03:42,280 --> 00:03:44,640
下一个处于就绪态的进程

100
00:03:44,680 --> 00:03:47,280
让它去执行

101
00:03:47,320 --> 00:03:49,760
那么这个查找下一个进程

102
00:03:49,800 --> 00:03:51,880
是由谁完成的呢

103
00:03:51,920 --> 00:03:53,000
是我们的idle

104
00:03:53,040 --> 00:03:54,360
idle实际上是一个内核线程

105
00:03:54,400 --> 00:03:56,040
我们在里面其实大家再注意一下

106
00:03:56,080 --> 00:03:58,680
我们在讲lab4 lab5的时候

107
00:03:58,720 --> 00:04:00,400
虽然说它是一个是内核线程

108
00:04:00,440 --> 00:04:01,320
一个是用户进程

109
00:04:01,360 --> 00:04:03,480
但是它们的调度 它们的管理

110
00:04:03,520 --> 00:04:05,000
这一块其实是大同小异

111
00:04:05,040 --> 00:04:06,920
基本上是一样的 有一些区别

112
00:04:06,960 --> 00:04:09,880
大家再回顾一下 有哪些区别

113
00:04:09,920 --> 00:04:11,800
那么这个idle这个内核线程呢

114
00:04:11,840 --> 00:04:14,080
它会不断的遍历这个进程池

115
00:04:14,120 --> 00:04:15,440
直到找到第一个

116
00:04:15,480 --> 00:04:17,040
runnable状态的进程

117
00:04:17,080 --> 00:04:19,040
所谓runnable 就是就绪状态

118
00:04:19,080 --> 00:04:20,440
然后找到这个之后呢

119
00:04:20,480 --> 00:04:22,720
就会完成一个进程切换

120
00:04:22,760 --> 00:04:24,800
把自身给挂起

121
00:04:24,840 --> 00:04:28,040
然后去执行找到的进程 去执行它

122
00:04:28,080 --> 00:04:30,640
那么这就是一个最简单的

123
00:04:30,680 --> 00:04:38,360
基于FIFO这种调度策略的调度算法

124
00:04:38,400 --> 00:04:40,520
我们前面讲到了lab4和lab5

125
00:04:40,560 --> 00:04:43,280
其实都和进程管理相关

126
00:04:43,320 --> 00:04:45,600
大家来回顾一下lab4和lab5

127
00:04:45,640 --> 00:04:47,520
它们完成的内核的

128
00:04:47,560 --> 00:04:49,240
线程和用户的进程

129
00:04:49,280 --> 00:04:50,640
它们在管理上面

130
00:04:50,680 --> 00:04:55,000
到底有哪些事情要做

131
00:04:55,040 --> 00:04:56,800
那这种方式我们来给一个评价

132
00:04:56,840 --> 00:04:58,720
这种方式怎么样呢

133
00:04:58,760 --> 00:05:00,040
其实这种方式呢

134
00:05:00,080 --> 00:05:01,200
它体现不出

135
00:05:01,240 --> 00:05:03,800
进程和进程之间的一些特点

136
00:05:03,840 --> 00:05:05,840
比如说我们说进程有优先级

137
00:05:05,880 --> 00:05:07,400
这个进程运行时间太长了

138
00:05:07,440 --> 00:05:09,880
其实它应该在更短的时间就应该结束

139
00:05:09,920 --> 00:05:12,320
让给其他的进程去占用CPU

140
00:05:12,360 --> 00:05:14,280
去完成它各自的工作

141
00:05:14,320 --> 00:05:15,640
如果是基于FIFO这种方式

142
00:05:15,680 --> 00:05:18,080
虽然我们的调度实现很简单

143
00:05:18,120 --> 00:05:19,920
但是呢 它的效率不高

144
00:05:19,960 --> 00:05:21,920
这个在原理课上已经讲过

145
00:05:21,960 --> 00:05:22,920
不同的调度算法

146
00:05:22,960 --> 00:05:25,520
它们有不同的评价指标

147
00:05:25,560 --> 00:05:26,440
我们基于这个评价指标

148
00:05:26,480 --> 00:05:31,120
来衡量这个算法它的好坏

149
00:05:31,160 --> 00:05:32,520
那么我们就是为此

150
00:05:32,560 --> 00:05:35,160
重新设计了lab6这个调度框架

151
00:05:35,200 --> 00:05:37,480
这个lab6里面它主要完成两块

152
00:05:37,520 --> 00:05:39,640
一块是关于调度的初始化过程

153
00:05:39,680 --> 00:05:41,800
一块是具体的调度过程

154
00:05:41,840 --> 00:05:43,440
那么在初始化过程中

155
00:05:43,480 --> 00:05:46,160
首先我们需要去实现一个调度算法

156
00:05:46,200 --> 00:05:48,080
那基于一个调度类来实现的

157
00:05:48,120 --> 00:05:49,000
我们这里面用了C语言

158
00:05:49,040 --> 00:05:51,800
来实现一个函数指针的一个列表

159
00:05:51,840 --> 00:05:52,800
这个函数指针的列表呢

160
00:05:52,840 --> 00:05:53,880
接口是统一的

161
00:05:53,920 --> 00:05:55,720
但是具体的调度的

162
00:05:55,760 --> 00:05:58,760
这个算法的实现是不一样的

163
00:05:58,800 --> 00:06:00,160
那我们说在ucore的设计里面

164
00:06:00,200 --> 00:06:01,680
设计了一种机制

165
00:06:01,720 --> 00:06:03,280
可以用C语言来实现

166
00:06:03,320 --> 00:06:05,520
一种类的表示方式

167
00:06:05,560 --> 00:06:07,640
通过这种方式呢

168
00:06:07,680 --> 00:06:09,920
我们具体完成一个调度算法的实现

169
00:06:09,960 --> 00:06:12,280
然后绑定到ucore里

170
00:06:12,320 --> 00:06:13,960
缺省的调度类里面去

171
00:06:14,000 --> 00:06:16,000
从而可以使得我们的ucore

172
00:06:16,040 --> 00:06:18,160
可以去调用你的这个调度算法

173
00:06:18,200 --> 00:06:19,280
在哪调用呢 

174
00:06:19,320 --> 00:06:20,240
为此我们需要

175
00:06:20,280 --> 00:06:22,040
进一步去设置相应的调度点

176
00:06:22,080 --> 00:06:23,800
所谓调度点 或者叫抢占点

177
00:06:23,840 --> 00:06:26,280
就是说当产生一些特殊的事件之后

178
00:06:26,320 --> 00:06:27,600
我们需要去触发

179
00:06:27,640 --> 00:06:28,600
我们的ucore操作系统

180
00:06:28,640 --> 00:06:30,200
去完成一个调度

181
00:06:30,240 --> 00:06:31,880
把这个设置好之后

182
00:06:31,920 --> 00:06:34,880
就完成了整个调度的初始化过程

183
00:06:34,920 --> 00:06:36,480
那接下来我们看一下

184
00:06:36,520 --> 00:06:39,280
当产生了一些事件之后

185
00:06:39,320 --> 00:06:41,040
我们就会在ucore里面

186
00:06:41,080 --> 00:06:43,360
得到这些事件的一些信息

187
00:06:43,400 --> 00:06:44,760
然后就到特定的调度点

188
00:06:44,800 --> 00:06:47,680
去开始做两个事情

189
00:06:47,720 --> 00:06:50,080
一个事情是要调整一些调度的参数

190
00:06:50,120 --> 00:06:51,520
因为我们的调度算法

191
00:06:51,560 --> 00:06:55,000
是基于这些参数来具体的去选择

192
00:06:55,040 --> 00:06:58,320
最后应该选择哪一个进程去执行

193
00:06:58,360 --> 00:07:00,760
还有就是要调用相应的调度算法

194
00:07:00,800 --> 00:07:02,960
这是他们要干的两个事情

195
00:07:03,000 --> 00:07:05,560
当调用调度算法的时候呢

196
00:07:05,600 --> 00:07:07,240
调度算法会做两个事情

197
00:07:07,280 --> 00:07:09,040
第一个是要选择新的进程

198
00:07:09,080 --> 00:07:11,640
第二个完成进程切换

199
00:07:11,680 --> 00:07:13,200
这里面呢 分两种情况

200
00:07:13,240 --> 00:07:14,960
首先是如果有新的一个

201
00:07:15,000 --> 00:07:16,680
优先级更高的进程

202
00:07:16,720 --> 00:07:18,320
那么我们要选择这个进程 选出来

203
00:07:18,360 --> 00:07:19,600
那基于里面的算法

204
00:07:19,640 --> 00:07:22,720
我们可以有不同的选择策略

205
00:07:22,760 --> 00:07:24,560
假定你选出了一个新的进程之后

206
00:07:24,600 --> 00:07:26,360
我们就要进行进程切换

207
00:07:26,400 --> 00:07:29,120
这是一种情况

208
00:07:29,160 --> 00:07:30,720
有新的进程去运行

209
00:07:30,760 --> 00:07:31,760
另一种情况呢

210
00:07:31,800 --> 00:07:34,840
有可能说你这个调度的过程当中

211
00:07:34,880 --> 00:07:36,400
发觉没有就绪进程了

212
00:07:36,440 --> 00:07:37,640
在这种情况下

213
00:07:37,680 --> 00:07:40,520
我们就会切到idle线程去运行

214
00:07:40,560 --> 00:07:41,920
这时候idle线程干什么事呢

215
00:07:41,960 --> 00:07:43,080
它只干一件事情

216
00:07:43,120 --> 00:07:44,760
就是不停的去查询

217
00:07:44,800 --> 00:07:46,960
是否有就绪的进程

218
00:07:47,000 --> 00:07:48,680
如果有 它就做切换

219
00:07:48,720 --> 00:07:50,640
如果没有 它就在不停的查询

220
00:07:50,680 --> 00:07:51,960
做一个循环

221
00:07:52,000 --> 00:07:53,360
这就是说idle线程

222
00:07:53,400 --> 00:07:55,160
在这里面起到新的作用

223
00:07:55,200 --> 00:07:57,120
接下来我们介绍一下调度过程

224
00:07:57,160 --> 00:07:58,480
那么这个调度过程呢

225
00:07:58,520 --> 00:08:00,400
比前面讲的那个总体介绍的过程

226
00:08:00,440 --> 00:08:02,440
稍微要具体一点

227
00:08:02,480 --> 00:08:04,360
那么使得我们可以更清楚的认识到

228
00:08:04,400 --> 00:08:06,320
我们原理课堂讲的那些调度算法

229
00:08:06,360 --> 00:08:08,440
怎么能够在ucore操作系统里面

230
00:08:08,480 --> 00:08:10,760
能够具体的得以执行

231
00:08:10,800 --> 00:08:12,120
首先我们看一下

232
00:08:12,160 --> 00:08:15,920
就是怎么能够产生调度

233
00:08:15,960 --> 00:08:18,720
这里面就涉及到触发的一个过程

234
00:08:18,760 --> 00:08:21,120
第一点我们前面讲到有一些触发点

235
00:08:21,160 --> 00:08:22,760
由于有一些事件的产生

236
00:08:22,800 --> 00:08:24,800
使得这些触发点能够被调用

237
00:08:24,840 --> 00:08:25,600
那么触发点呢

238
00:08:25,640 --> 00:08:27,200
就是最终能激活

239
00:08:27,240 --> 00:08:30,120
调度算法的一个执行

240
00:08:30,160 --> 00:08:31,560
这是第一步

241
00:08:31,600 --> 00:08:34,120
那么一旦调度算法得以执行之后呢

242
00:08:34,160 --> 00:08:36,320
那么它干的第一个事是什么事呢

243
00:08:36,360 --> 00:08:38,400
第一个事就是要把当前的这个进程

244
00:08:38,440 --> 00:08:40,240
放入到就绪队列里面去

245
00:08:40,280 --> 00:08:41,200
这是第一步

246
00:08:41,240 --> 00:08:43,360
第二步呢 从就绪队列里

247
00:08:43,400 --> 00:08:45,400
选取一个 它认为最合适的

248
00:08:45,440 --> 00:08:47,640
一个进程去占用CPU执行

249
00:08:47,680 --> 00:08:50,800
pick up一个process

250
00:08:50,840 --> 00:08:52,680
第三步呢

251
00:08:52,720 --> 00:08:54,720
就是把这个选择的进程呢

252
00:08:54,760 --> 00:08:56,640
从就绪队列里面取出来

253
00:08:56,680 --> 00:08:58,040
因为我们需要把它去做

254
00:08:58,080 --> 00:09:00,600
完成一个接下来的切换

255
00:09:00,640 --> 00:09:04,280
使得当前的进程和我们选出来这个

256
00:09:04,320 --> 00:09:06,640
新的进程能够完成一个switch

257
00:09:06,680 --> 00:09:07,840
一旦完成switch之后呢

258
00:09:07,880 --> 00:09:11,480
我们就可以让这个进程去执行了

259
00:09:11,520 --> 00:09:12,320
所以说这就是

260
00:09:12,360 --> 00:09:16,120
让进程执行的这么一个图示

261
00:09:16,160 --> 00:09:18,600
在这里面我们可以看到

262
00:09:18,640 --> 00:09:21,680
所有处于就绪态的进程

263
00:09:21,720 --> 00:09:23,480
也就是说Runnable的进程

264
00:09:23,520 --> 00:09:25,360
它会在一个队列里面

265
00:09:25,400 --> 00:09:28,200
我们会有专门的数据结构叫run_queue

266
00:09:28,240 --> 00:09:30,880
来管理这个处于就绪态的进程

267
00:09:30,920 --> 00:09:32,720
也就意味着我们这个算法呢

268
00:09:32,760 --> 00:09:34,560
它会从就绪队列里面

269
00:09:34,600 --> 00:09:37,640
选取一个它认为合适的进程去执行

270
00:09:37,680 --> 00:09:39,520
当然还存在另外一种情况

271
00:09:39,560 --> 00:09:40,440
什么情况呢

272
00:09:40,480 --> 00:09:43,720
这个进程呢 它会睡眠或者等待

273
00:09:43,760 --> 00:09:45,920
因为当某一个进程

274
00:09:45,960 --> 00:09:48,120
它需要的资源得不到满足之后

275
00:09:48,160 --> 00:09:50,360
它就会去等待和睡眠

276
00:09:50,400 --> 00:09:52,520
这里面就存在一个所谓的等待队列

277
00:09:52,560 --> 00:09:53,640
或者睡眠队列

278
00:09:53,680 --> 00:09:56,400
来放置这些特殊的进程

279
00:09:56,440 --> 00:09:57,440
那么这两类呢

280
00:09:57,480 --> 00:09:58,840
就形成了我们整个这个

281
00:09:58,880 --> 00:10:01,400
进程的管理的一个过程

282
00:10:01,440 --> 00:10:04,040
那么我们这个lab6呢

283
00:10:04,080 --> 00:10:05,560
它的调度算法这一块

284
00:10:05,600 --> 00:10:08,040
主要设计的是处于就绪态的进程

285
00:10:08,080 --> 00:10:10,400
和正在运行的当前进程

286
00:10:10,440 --> 00:10:13,120
它们之间的一个相互切换的过程

287
00:10:13,160 --> 00:10:15,200
我们的调度算法主要涉及这两块

288
00:10:15,240 --> 00:10:17,000
但是呢 进程

289
00:10:17,040 --> 00:10:17,960
它有其它状态

290
00:10:18,000 --> 00:10:19,560
比如说刚才说得不到资源

291
00:10:19,600 --> 00:10:22,200
它会处于等待或者睡眠的一个状态

292
00:10:22,240 --> 00:10:24,000
以及当进程执行完毕之后

293
00:10:24,040 --> 00:10:27,400
它会退出整个生命周期

294
00:10:27,440 --> 00:10:28,160
那么这两个态呢

295
00:10:28,200 --> 00:10:30,120
其实也和调度是有关系的

296
00:10:30,160 --> 00:10:33,000
但是不太涉及到调度算法

297
00:10:33,040 --> 00:10:34,320
所以说我们重点关注的是

298
00:10:34,360 --> 00:10:36,280
怎么能够从就绪队列里面

299
00:10:36,320 --> 00:10:39,960
选取一个新的进程去占用CPU执行

300
00:10:40,000 --> 00:10:41,080
后续呢 在这一块

301
00:10:41,120 --> 00:10:42,600
会做进一步的展开讲解

302
00:10:42,640 --> 00:10:42,680