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


1
00:00:06,680 --> 00:00:07,880
那我们接下来看一下

2
00:00:07,920 --> 00:00:09,840
这个调度算法支撑框架

3
00:00:09,880 --> 00:00:11,480
那么有了调度算法支撑框架之后

4
00:00:11,520 --> 00:00:13,040
我们可以更有效的去完成

5
00:00:13,080 --> 00:00:14,920
对不同调度算法的一个

6
00:00:14,960 --> 00:00:18,240
具体的一个执行

7
00:00:18,280 --> 00:00:19,600
那我们前面已经讲了

8
00:00:19,640 --> 00:00:20,360
调度执行的

9
00:00:20,400 --> 00:00:21,560
一个大致的过程

10
00:00:21,600 --> 00:00:22,360
在这里面呢

11
00:00:22,400 --> 00:00:23,800
有一个很核心的函数

12
00:00:23,840 --> 00:00:26,680
叫什么呢 schedule

13
00:00:26,720 --> 00:00:27,720
那么这个函数呢会在

14
00:00:27,760 --> 00:00:30,000
不同的我们说调度点的时候呢

15
00:00:30,040 --> 00:00:31,280
会被调用

16
00:00:31,320 --> 00:00:33,080
它进一步去完成对

17
00:00:33,120 --> 00:00:35,040
调度算法的一个调用过程

18
00:00:35,080 --> 00:00:36,200
那么这个具体的调度点呢

19
00:00:36,240 --> 00:00:39,640
我们在后续有一个讲解

20
00:00:39,680 --> 00:00:41,360
那我们看一下这些调度点

21
00:00:41,400 --> 00:00:43,520
到底是做了什么事情

22
00:00:43,560 --> 00:00:45,920
好 第一个呢是do_exit

23
00:00:45,960 --> 00:00:48,760
就是代表一个进程要退出执行了

24
00:00:48,800 --> 00:00:50,280
就是它生命周期要结束了

25
00:00:50,320 --> 00:00:52,160
这时候呢 我们需要换一个

26
00:00:52,200 --> 00:00:53,600
新的一个进程去执行

27
00:00:53,640 --> 00:00:55,120
这里面会调schedule

28
00:00:55,160 --> 00:00:56,480
第二个是do_wait

29
00:00:56,520 --> 00:00:59,840
主要是用于父进程等待子进程结束

30
00:00:59,880 --> 00:01:02,560
来回收子进程的资源

31
00:01:02,600 --> 00:01:03,280
这个时候呢

32
00:01:03,320 --> 00:01:05,840
它本身处于等待和睡眠状态

33
00:01:05,880 --> 00:01:08,000
一旦被唤醒它就要去调用

34
00:01:08,040 --> 00:01:10,760
回收的一些工作来完成

35
00:01:10,800 --> 00:01:15,680
对子进程所占用资源的回收

36
00:01:15,720 --> 00:01:17,280
第三个是init_main

37
00:01:17,320 --> 00:01:19,960
其实它也是调do_wait

38
00:01:20,000 --> 00:01:22,560
来完成对其它一些子进程的一个

39
00:01:22,600 --> 00:01:23,720
占用资源的回收

40
00:01:23,760 --> 00:01:25,600
为什么这里面单独拎出来说呢

41
00:01:25,640 --> 00:01:29,040
因为它是所有用户进程的祖先

42
00:01:29,080 --> 00:01:31,600
当其它的就是没有父进程的

43
00:01:31,640 --> 00:01:33,720
那些子进程执行完毕之后呢

44
00:01:33,760 --> 00:01:35,320
就需要通过这个最终那个祖先

45
00:01:35,360 --> 00:01:37,000
init_main来完成对这些

46
00:01:37,040 --> 00:01:38,040
我们称之为

47
00:01:38,080 --> 00:01:43,520
孤儿子进程的资源的回收

48
00:01:43,560 --> 00:01:45,640
那么这第四个是cpu_idle

49
00:01:45,680 --> 00:01:47,040
cpu_idle代表什么呢

50
00:01:47,080 --> 00:01:48,680
就是idle kernel thread

51
00:01:48,720 --> 00:01:50,040
它是一个特殊的进程

52
00:01:50,080 --> 00:01:52,040
它主要在什么情况下被激活执行呢

53
00:01:52,080 --> 00:01:54,400
就是当前就绪队列里面

54
00:01:54,440 --> 00:01:56,080
没有就绪进程的时候

55
00:01:56,120 --> 00:01:59,480
这时候idle_thread就会执行

56
00:01:59,520 --> 00:02:01,400
它会不停的轮询

57
00:02:01,440 --> 00:02:03,360
然后去调用schedule来查找

58
00:02:03,400 --> 00:02:06,880
是否有处于就绪态的进程存在

59
00:02:06,920 --> 00:02:07,560
一旦有的时候

60
00:02:07,600 --> 00:02:10,840
它就会完成一个进程切换

61
00:02:10,880 --> 00:02:12,400
第五个是lock

62
00:02:12,440 --> 00:02:13,600
第五lock这一块呢主要是

63
00:02:13,640 --> 00:02:15,080
跟我们的lab7相关

64
00:02:15,120 --> 00:02:16,640
就是同步互斥相关

65
00:02:16,680 --> 00:02:17,840
这里面我们稍微讲一下

66
00:02:17,880 --> 00:02:20,920
它也是说想得到一个lock资源得不到之后

67
00:02:20,960 --> 00:02:24,040
它会调schedule来把自己挂起

68
00:02:24,080 --> 00:02:25,040
处于睡眠状态

69
00:02:25,080 --> 00:02:26,080
得不到这个资源了

70
00:02:26,120 --> 00:02:27,600
然后一旦资源得到满足

71
00:02:27,640 --> 00:02:28,720
它会被唤醒

72
00:02:28,760 --> 00:02:30,640
然后从而可以进一步进入就绪队列

73
00:02:30,680 --> 00:02:35,280
参与选择 执行

74
00:02:35,320 --> 00:02:37,200
第六个比较特殊 trap

75
00:02:37,240 --> 00:02:38,880
那trap实际上是说

76
00:02:38,920 --> 00:02:40,400
比如我们说产生了一个时钟中断

77
00:02:40,440 --> 00:02:41,840
时钟中断会打断

78
00:02:41,880 --> 00:02:44,000
当前正在运行的进程

79
00:02:44,040 --> 00:02:45,320
然后干什么事情呢

80
00:02:45,360 --> 00:02:48,320
它会去做当前一些跟调度相关的

81
00:02:48,360 --> 00:02:49,880
一些资源的一些调整

82
00:02:49,920 --> 00:02:51,760
比如说这个时间片

83
00:02:51,800 --> 00:02:53,440
这个时间片的这个资源

84
00:02:53,480 --> 00:02:54,920
我们时间片用完了

85
00:02:54,960 --> 00:02:56,480
那么你这个进程就要被换出

86
00:02:56,520 --> 00:02:58,880
那么时间片的改变是在哪完成的呢

87
00:02:58,920 --> 00:03:01,160
是在这个trap与时钟中断

88
00:03:01,200 --> 00:03:03,000
相关的处理里面

89
00:03:03,040 --> 00:03:04,760
对时间片做一个调整

90
00:03:04,800 --> 00:03:08,360
从而可以影响到后续的调度选择

91
00:03:08,400 --> 00:03:10,480
并进一步产生调度

92
00:03:10,520 --> 00:03:11,440
好 这一块呢

93
00:03:11,480 --> 00:03:12,800
是跟我们的调度算法

94
00:03:12,840 --> 00:03:15,160
是有紧密联系的

95
00:03:15,200 --> 00:03:16,880
那么我们这个调度算法

96
00:03:16,920 --> 00:03:18,440
它为了能够正常的运行

97
00:03:18,480 --> 00:03:20,440
它需要知道进程的那些事件

98
00:03:20,480 --> 00:03:23,200
那如何知道的呢

99
00:03:23,240 --> 00:03:25,680
有专门一个proc_tick这么一个函数

100
00:03:25,720 --> 00:03:27,680
这个从字面意思上可以看出来

101
00:03:27,720 --> 00:03:29,000
tick怎么叫tick呢

102
00:03:29,040 --> 00:03:31,000
实际上就是时钟的一个节拍

103
00:03:31,040 --> 00:03:32,760
那很明显可以理解到

104
00:03:32,800 --> 00:03:36,160
我们在去做中断处理的时候

105
00:03:36,200 --> 00:03:37,720
它会响应一个时钟中断

106
00:03:37,760 --> 00:03:38,840
而在那个时刻

107
00:03:38,880 --> 00:03:41,040
我们能够让调度算法

108
00:03:41,080 --> 00:03:42,520
感知到时钟中断的产生

109
00:03:42,560 --> 00:03:45,120
从而可以去调整它们那些参数

110
00:03:45,160 --> 00:03:47,600
比如说时间片的大小

111
00:03:47,640 --> 00:03:51,720
这是很重要的一个感知的一个功能

112
00:03:51,760 --> 00:03:52,640
第二个呢

113
00:03:52,680 --> 00:03:56,200
我们需要能够让一个进程

114
00:03:56,240 --> 00:03:59,000
从就绪队列里面进去和出来

115
00:03:59,040 --> 00:04:01,360
那这个进队和出队的一个过程

116
00:04:01,400 --> 00:04:04,240
这个和我们的调度算法的实现

117
00:04:04,280 --> 00:04:05,880
是有紧密关系的

118
00:04:05,920 --> 00:04:08,400
它不仅仅说是一个简单的队列

119
00:04:08,440 --> 00:04:10,200
你可以把它理解为一个

120
00:04:10,240 --> 00:04:11,120
抽象数据结构

121
00:04:11,160 --> 00:04:12,080
它可以用其它的

122
00:04:12,120 --> 00:04:17,360
堆 表 链表 数组来实现

123
00:04:17,400 --> 00:04:20,480
这是说的这个就绪队列这一块

124
00:04:20,520 --> 00:04:21,560
你可以有不同的数据结构

125
00:04:21,600 --> 00:04:23,520
但是你要保证两个操作

126
00:04:23,560 --> 00:04:25,040
第一个操作它能够进队列里面

127
00:04:25,080 --> 00:04:30,000
第二个是要从队列里面取出来

128
00:04:30,040 --> 00:04:31,400
第三个就是要pick up

129
00:04:31,440 --> 00:04:35,480
选取一个进程去执行

130
00:04:35,520 --> 00:04:36,640
那么这个选取的过程呢

131
00:04:36,680 --> 00:04:38,040
是和具体的算法相关

132
00:04:38,080 --> 00:04:40,480
所以说我们要实现不同的调度算法

133
00:04:40,520 --> 00:04:41,840
那么你这个pick up的实现

134
00:04:41,880 --> 00:04:44,560
有很大的不同

135
00:04:44,600 --> 00:04:45,280
最后一个呢

136
00:04:45,320 --> 00:04:46,800
一旦你选取完之后呢

137
00:04:46,840 --> 00:04:48,800
那你就需要去说和当前

138
00:04:48,840 --> 00:04:51,040
正在占用CPU的进程呢做一个交换

139
00:04:51,080 --> 00:04:52,800
选择新进程

140
00:04:52,840 --> 00:04:54,160
和这个老的进程来做交换

141
00:04:54,200 --> 00:04:55,200
这个是什么呢

142
00:04:55,240 --> 00:04:56,480
process switch就是我们说的

143
00:04:56,520 --> 00:04:58,040
进程切换要完成功能

144
00:04:58,080 --> 00:04:59,440
但是进程切换呢

145
00:04:59,480 --> 00:05:02,440
本身是和我们的算法是没关系的

146
00:05:02,480 --> 00:05:04,360
只是说当你的算法选择了

147
00:05:04,400 --> 00:05:06,560
一个新的进程之后要完成一个切换

148
00:05:06,600 --> 00:05:09,960
OK 那这些过程

149
00:05:10,000 --> 00:05:13,160
我们可以把它抽样成一些函数

150
00:05:13,200 --> 00:05:15,840
初始化 进队 出队 选择

151
00:05:15,880 --> 00:05:17,280
还有一个tick

152
00:05:17,320 --> 00:05:19,240
这么一个所谓的调度类

153
00:05:19,280 --> 00:05:20,240
就这么形成了

154
00:05:20,280 --> 00:05:21,720
我们就通过这种调度类呢

155
00:05:21,760 --> 00:05:23,360
来提供一个统一的接口

156
00:05:23,400 --> 00:05:26,520
形成一个所谓的调度算法的一个框架

157
00:05:26,560 --> 00:05:29,720
你只要完成不同的实现

158
00:05:29,760 --> 00:05:32,280
就可以对应着你的调度算法

159
00:05:32,320 --> 00:05:34,320
从而可以使得我们的ucore操作系统呢

160
00:05:34,360 --> 00:05:36,600
能够采取不同的调度策略

161
00:05:36,640 --> 00:05:41,240
来进行整个进程的一个管理和调度

162
00:05:41,280 --> 00:05:41,960
那么我们看一下

163
00:05:42,000 --> 00:05:43,880
就是刚才你实现的那些调度算法

164
00:05:43,920 --> 00:05:45,760
所涉及到的一些核心的一些函数

165
00:05:45,800 --> 00:05:48,960
是怎么被ucore来调度的呢

166
00:05:49,000 --> 00:05:50,880
这里面需要注意一个重要的函数

167
00:05:50,920 --> 00:05:51,960
叫schedule

168
00:05:52,000 --> 00:05:54,120
它是可以理解为一个总控函数

169
00:05:54,160 --> 00:05:56,040
由这个总控函数完成了

170
00:05:56,080 --> 00:05:57,480
对那个调度算法中

171
00:05:57,520 --> 00:06:00,720
各个核心函数的一个调用过程

172
00:06:00,760 --> 00:06:03,200
那么第一个函数呢 是进入队列

173
00:06:03,240 --> 00:06:04,960
就是enqueue这么一个函数

174
00:06:05,000 --> 00:06:05,640
那么这个函数呢

175
00:06:05,680 --> 00:06:07,160
实际上会调我们调度算法里面的

176
00:06:07,200 --> 00:06:09,080
那个进入队列的函数

177
00:06:09,120 --> 00:06:10,360
就是enqueue那个函数

178
00:06:10,400 --> 00:06:11,960
什么情况下会调用呢

179
00:06:12,000 --> 00:06:13,320
可以看到

180
00:06:13,360 --> 00:06:15,160
如果当前的这个进程current

181
00:06:15,200 --> 00:06:16,840
代表当前的进程

182
00:06:16,880 --> 00:06:19,080
它的状态处于就绪态

183
00:06:19,120 --> 00:06:20,440
runnable是就绪态

184
00:06:20,480 --> 00:06:21,200
在这种情况下

185
00:06:21,240 --> 00:06:22,520
它首先要把当前的进程

186
00:06:22,560 --> 00:06:25,360
放到就绪队列里面去

187
00:06:25,400 --> 00:06:27,800
这是为了做进一步的选择

188
00:06:27,840 --> 00:06:29,800
做这个考虑的

189
00:06:29,840 --> 00:06:31,080
接下来呢

190
00:06:31,120 --> 00:06:32,240
那么这个pick_next呢

191
00:06:32,280 --> 00:06:34,160
它会进一步去调用

192
00:06:34,200 --> 00:06:35,560
我们说的那个调度算法里面的

193
00:06:35,600 --> 00:06:37,680
对应的函数pick_next

194
00:06:37,720 --> 00:06:39,440
它会根据你这个算法的实现

195
00:06:39,480 --> 00:06:42,240
来选择一个新的一个进程

196
00:06:42,280 --> 00:06:45,880
好 一旦选择出一个新的进程之后

197
00:06:45,920 --> 00:06:48,120
我们认为这个进程应该占用CPU执行

198
00:06:48,160 --> 00:06:49,640
所以说它会把这个进程

199
00:06:49,680 --> 00:06:52,360
从就绪队列里面取出来

200
00:06:52,400 --> 00:06:53,480
执行一个dequeue

201
00:06:53,520 --> 00:06:54,640
那么dequeue呢

202
00:06:54,680 --> 00:06:55,960
也和我们的调度算法里面

203
00:06:56,000 --> 00:06:58,160
对应的dequeue的函数是对应的

204
00:06:58,200 --> 00:07:00,000
选择出来之后

205
00:07:00,040 --> 00:07:01,640
有可能有两种情况

206
00:07:01,680 --> 00:07:03,360
一种情况是说你选不出来

207
00:07:03,400 --> 00:07:04,360
它可能为空

208
00:07:04,400 --> 00:07:05,480
选不出来为空

209
00:07:05,520 --> 00:07:06,680
在这种情况下

210
00:07:06,720 --> 00:07:09,520
我们会进一步去调用这个idleproc

211
00:07:09,560 --> 00:07:11,880
这是一个特殊的内核线程

212
00:07:11,920 --> 00:07:12,920
它干什么事情呢

213
00:07:12,960 --> 00:07:13,760
它只干一件事情

214
00:07:13,800 --> 00:07:16,800
就是不停的循环去调用schedule

215
00:07:16,840 --> 00:07:18,960
查询当前的就绪队列

216
00:07:19,000 --> 00:07:20,760
是否有处于就绪态的进程

217
00:07:20,800 --> 00:07:22,200
可以去执行

218
00:07:22,240 --> 00:07:23,120
这是一种情况

219
00:07:23,160 --> 00:07:24,520
第二种情况你选出来了

220
00:07:24,560 --> 00:07:27,280
选出来就是一个新的

221
00:07:27,320 --> 00:07:29,240
一个next这么一个进程

222
00:07:29,280 --> 00:07:30,120
选择出来之后呢

223
00:07:30,160 --> 00:07:32,600
它会和current这个进程做一个交换

224
00:07:32,640 --> 00:07:36,280
通过调proc_run进一步调switch_to

225
00:07:36,320 --> 00:07:39,120
来完成进程的切换

226
00:07:39,160 --> 00:07:44,600
这就是说这个总控的一个调度函数

227
00:07:44,640 --> 00:07:46,320
那我们再回顾一下

228
00:07:46,360 --> 00:07:48,560
我们说这个schedule函数它很重要

229
00:07:48,600 --> 00:07:50,000
它是一个核心

230
00:07:50,040 --> 00:07:52,360
首先它会在不同的调度点会被调用

231
00:07:52,400 --> 00:07:53,400
调用这个schedule

232
00:07:53,440 --> 00:07:55,200
同时呢 它会调一系列的

233
00:07:55,240 --> 00:07:57,000
进一步的函数

234
00:07:57,040 --> 00:07:59,000
来完成对不同调度算法的

235
00:07:59,040 --> 00:08:00,840
核心函数的调用

236
00:08:00,880 --> 00:08:02,000
从而可以实现

237
00:08:02,040 --> 00:08:04,400
调度算法所要达到的功能

238
00:08:04,440 --> 00:08:05,160
在这个基础上

239
00:08:05,200 --> 00:08:07,000
我们可以实现不同的调度算法

240
00:08:07,040 --> 00:08:08,720
包括我们说的FIFO

241
00:08:08,760 --> 00:08:10,200
那FIFO先进先出

242
00:08:10,240 --> 00:08:11,560
就是和我们原理课讲的

243
00:08:11,600 --> 00:08:12,840
FCFS是一个意思

244
00:08:12,880 --> 00:08:14,360
先来先服务

245
00:08:14,400 --> 00:08:15,400
都是一个意思

246
00:08:15,440 --> 00:08:17,120
这是一种最简单的调度算法

247
00:08:17,160 --> 00:08:18,520
也可以实现我们后续讲到的

248
00:08:18,560 --> 00:08:19,920
Round Robin这个调度算法

249
00:08:19,960 --> 00:08:21,920
以及需要大家做实验去完成的

250
00:08:21,960 --> 00:08:24,120
stride这个调度算法

251
00:08:24,160 --> 00:08:27,080
这就是说这个大致的一个调度框架

252
00:08:27,120 --> 00:08:27,160