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


1
00:00:07,400 --> 00:00:10,560
下面我们继续来讨论置换算法    

2
00:00:10,600 --> 00:00:12,200
  那首先我们讨论的

3
00:00:12,240 --> 00:00:15,840
是时间片轮转算法

4
00:00:15,880 --> 00:00:17,920
在时间片轮转算法里头呢

5
00:00:17,960 --> 00:00:20,680
我们首先要约定一个

6
00:00:20,720 --> 00:00:23,640
进程调度的基本时间单位

7
00:00:23,680 --> 00:00:25,280
就这里的时间片

8
00:00:25,320 --> 00:00:28,880
它是处理机资源分配的基本单位

9
00:00:28,920 --> 00:00:31,960
每个进程上来之后执行一个时间片

10
00:00:32,000 --> 00:00:34,080
那我们用下面这个图示

11
00:00:34,120 --> 00:00:36,200
来说明时间片轮转算法

12
00:00:36,240 --> 00:00:38,040
它的基本工作原理

13
00:00:38,080 --> 00:00:39,440
这头呢是CPU

14
00:00:39,480 --> 00:00:41,440
然后这是它的就绪队列

15
00:00:41,480 --> 00:00:44,000
中间会时间片结束的时候

16
00:00:44,040 --> 00:00:48,680
会有时钟中断导致后续的处理

17
00:00:48,720 --> 00:00:50,720
那具体处理是这样的

18
00:00:50,760 --> 00:00:52,560
时间片结束的时候

19
00:00:52,600 --> 00:00:56,800
那按照先来先服务算法

20
00:00:56,840 --> 00:00:59,520
切换到下一个就绪进程

21
00:00:59,560 --> 00:01:00,800
那这里的下一个就绪进程

22
00:01:00,840 --> 00:01:02,400
是排到这里的第一位

23
00:01:02,440 --> 00:01:04,120
好 结束的这个呢

24
00:01:04,160 --> 00:01:06,440
是排到它的队的最后

25
00:01:06,480 --> 00:01:07,720
好 这样一来的话

26
00:01:07,760 --> 00:01:09,960
就是如果有n个进程

27
00:01:10,000 --> 00:01:12,280
那每个进程呢占一个时间片

28
00:01:12,320 --> 00:01:15,600
那这就是每隔n-1个时间片

29
00:01:15,640 --> 00:01:19,440
进程占用一个时间片来执行

30
00:01:19,480 --> 00:01:22,400
那在这个周期性的轮转当中

31
00:01:22,440 --> 00:01:26,040
每一个进程呢分到了1/n的时间

32
00:01:26,080 --> 00:01:30,240
这是时间片轮转算法的基本思路

33
00:01:30,280 --> 00:01:32,560
下面我们通过一个例子

34
00:01:32,600 --> 00:01:35,280
来说明它的运行过程

35
00:01:35,320 --> 00:01:39,280
那这地方呢假定时间片的长度是20

36
00:01:39,320 --> 00:01:41,920
然后现在有四个进程

37
00:01:41,960 --> 00:01:46,320
它们分别的执行时间在这里

38
00:01:46,360 --> 00:01:49,400
下面我看一下 它的执行过程

39
00:01:49,440 --> 00:01:52,120
我们用下面这个图来表示

40
00:01:52,160 --> 00:01:57,560
首先每个进程执行20个时间单位

41
00:01:57,600 --> 00:02:00,320
那在这里头呢 P2呢只有8个

42
00:02:00,360 --> 00:02:01,560
那执行到这儿呢

43
00:02:01,600 --> 00:02:03,840
20到28 它就结束了

44
00:02:03,880 --> 00:02:05,760
好 第一圈执行下来之后呢

45
00:02:05,800 --> 00:02:08,000
进程二就结束了

46
00:02:08,040 --> 00:02:09,400
好 接着来第二圈

47
00:02:09,440 --> 00:02:14,400
那么这时候呢只有三个1 3 4

48
00:02:14,440 --> 00:02:16,720
第二圈结束的时候呢 我们看到 

49
00:02:16,760 --> 00:02:20,000
P4又已经全部执行完毕了

50
00:02:20,040 --> 00:02:23,440
那它也退出 整个进程结束

51
00:02:23,480 --> 00:02:26,040
现在还剩P1和P3

52
00:02:26,080 --> 00:02:29,000
好 再接着往下来

53
00:02:29,040 --> 00:02:31,240
到这个时候呢

54
00:02:31,280 --> 00:02:33,480
P1也执行完了P3执行 

55
00:02:33,520 --> 00:02:35,600
最后还剩一个P3

56
00:02:35,640 --> 00:02:38,280
好 这是它整个执行过程的

57
00:02:38,320 --> 00:02:40,480
CPU的占用情况

58
00:02:40,520 --> 00:02:44,760
那我们来看看它的等待时间特征

59
00:02:44,800 --> 00:02:46,640
这是四个进程

60
00:02:46,680 --> 00:02:49,400
在执行过程当中的等待时间

61
00:02:49,440 --> 00:02:51,200
我们以其中的一个为例

62
00:02:51,240 --> 00:02:54,680
比如说P1 它执行了几次呢

63
00:02:54,720 --> 00:02:58,120
第一次 第二次 第三次

64
00:02:58,160 --> 00:03:00,200
分三个时间片它就执行完了

65
00:03:00,240 --> 00:03:02,360
那么中间等待的时间是什么呢

66
00:03:02,400 --> 00:03:05,000
起头它是第一个所以没有等待时间

67
00:03:05,040 --> 00:03:09,680
然后第二的话就是20到68

68
00:03:09,720 --> 00:03:15,160
然后第三次是从88到112

69
00:03:15,200 --> 00:03:17,760
那这地方就是68-20

70
00:03:17,800 --> 00:03:20,480
112-88 好 那这个地方呢

71
00:03:20,520 --> 00:03:22,480
这是它的等待时间

72
00:03:22,520 --> 00:03:23,680
那我们算一下

73
00:03:23,720 --> 00:03:27,840
它的平均等待时间 是66.25

74
00:03:27,880 --> 00:03:28,960
那我们看到 

75
00:03:29,000 --> 00:03:31,120
这是一个时间片轮转算法

76
00:03:31,160 --> 00:03:32,760
它的运行过程

77
00:03:32,800 --> 00:03:34,880
那我们看到中间等待的时间呢

78
00:03:34,920 --> 00:03:37,360
相对来说比较长的

79
00:03:37,400 --> 00:03:38,480
好 那这时候说

80
00:03:38,520 --> 00:03:41,880
我们时间片到底设置为多长合适呢

81
00:03:41,920 --> 00:03:43,640
那我们说在这里头呢

82
00:03:43,680 --> 00:03:47,080
时间片轮转算法由于它靠时钟中断

83
00:03:47,120 --> 00:03:50,120
强行把正在执行的进程结束掉了

84
00:03:50,160 --> 00:03:51,240
所以它在这儿呢

85
00:03:51,280 --> 00:03:54,600
有额外的上下文切换的开销

86
00:03:54,640 --> 00:03:56,760
不像我们前面的一些算法

87
00:03:56,800 --> 00:03:59,520
它只在进程到等待状态的时候

88
00:03:59,560 --> 00:04:02,680
它才会有进程切换

89
00:04:02,720 --> 00:04:03,960
那我们说在这里头

90
00:04:04,000 --> 00:04:06,120
我们把时间片设多大合适呢

91
00:04:06,160 --> 00:04:08,560
那先看两个极端的情况

92
00:04:08,600 --> 00:04:10,480
时间片很大

93
00:04:10,520 --> 00:04:12,680
大到可以任何一个进程

94
00:04:12,720 --> 00:04:14,600
都在一个时间片内能完成

95
00:04:14,640 --> 00:04:17,280
那这时候它的算法变成什么样了

96
00:04:17,320 --> 00:04:19,920
变成一个先来先服务了

97
00:04:19,960 --> 00:04:21,280
也就是说来了之后

98
00:04:21,320 --> 00:04:23,640
按照来的顺序去就绪队列里排

99
00:04:23,680 --> 00:04:25,560
一次执行肯定结束

100
00:04:25,600 --> 00:04:28,120
那这就变成了先来先服务

101
00:04:28,160 --> 00:04:30,160
而这时候呢它的等待时间呢

102
00:04:30,200 --> 00:04:32,240
就跟我们先来先服务是一样的。

103
00:04:32,280 --> 00:04:35,880
好 那这是很长 不太合适

104
00:04:35,920 --> 00:04:38,080
而对于时间片短

105
00:04:38,120 --> 00:04:40,080
那你比如说我们在这里极端的情况

106
00:04:40,120 --> 00:04:43,800
我大量一半以上的时间是在做切换

107
00:04:43,840 --> 00:04:45,760
执行的时间只是按其中的一半

108
00:04:45,800 --> 00:04:46,880
那么这时候呢

109
00:04:46,920 --> 00:04:47,840
这个上下文切换

110
00:04:47,880 --> 00:04:49,240
它是有很大的开销的

111
00:04:49,280 --> 00:04:50,800
好 这些开销呢

112
00:04:50,840 --> 00:04:53,240
会影响到系统的吞吐量

113
00:04:53,280 --> 00:04:53,920
所以我们这儿呢

114
00:04:53,960 --> 00:04:57,200
时间片大了对进程的响应时间不好

115
00:04:57,240 --> 00:04:59,320
小了对系统的开销不好

116
00:04:59,360 --> 00:05:02,280
那这时候我们要选择一个合适的尺度

117
00:05:02,320 --> 00:05:04,080
目前呢对这个问题呢

118
00:05:04,120 --> 00:05:06,920
只有一些经验值在这里来设

119
00:05:06,960 --> 00:05:08,880
你比如说在这里头我们现在系统

120
00:05:08,920 --> 00:05:10,000
通常情况下呢

121
00:05:10,040 --> 00:05:12,440
它是10毫秒左右一个时间片

122
00:05:12,480 --> 00:05:13,560
这个时间片呢

123
00:05:13,600 --> 00:05:17,200
上下文切换的开销呢是在百分之一左右

124
00:05:17,240 --> 00:05:20,280
好 这是关于时间片的问题

125
00:05:20,320 --> 00:05:21,840
那我们说在这里头

126
00:05:21,880 --> 00:05:23,560
我们想看一下它的这个等待时间

127
00:05:23,600 --> 00:05:25,000
到底是什么样的情况

128
00:05:25,040 --> 00:05:29,040
我们还是以刚才的那个例子来说

129
00:05:29,080 --> 00:05:30,720
那我们把它对照

130
00:05:30,760 --> 00:05:33,120
先来先服务和时间片轮转算法

131
00:05:33,160 --> 00:05:36,760
这两个算法它的等待时间

132
00:05:36,800 --> 00:05:37,800
那我们先假定呢

133
00:05:37,840 --> 00:05:40,840
上下文切换的时间呢为零 忽略不计

134
00:05:40,880 --> 00:05:41,880
好 那这时候我看

135
00:05:41,920 --> 00:05:45,760
每一个做法它的平均等待时间

136
00:05:45,800 --> 00:05:47,720
这地方最后的这两个呢

137
00:05:47,760 --> 00:05:50,680
先来先服务算法到达情况影响很大

138
00:05:50,720 --> 00:05:52,800
所以我们在这儿取两个极端的情况

139
00:05:52,840 --> 00:05:55,000
一个是最差 一个是最好

140
00:05:55,040 --> 00:05:56,040
实际上最好的呢

141
00:05:56,080 --> 00:05:58,520
就相当于是短进程优先

142
00:05:58,560 --> 00:06:02,360
好 最差的呢相当于长进程优先

143
00:06:02,400 --> 00:06:05,840
那中间呢这几个是我取不同的时间片

144
00:06:05,880 --> 00:06:07,960
我们看一下算出来的结果

145
00:06:08,000 --> 00:06:10,280
那这是它的平均等待时间

146
00:06:10,320 --> 00:06:12,920
我们看到最好和最差的情况

147
00:06:12,960 --> 00:06:14,360
都是先来先服务的

148
00:06:14,400 --> 00:06:16,080
所以你到达的序列

149
00:06:16,120 --> 00:06:19,640
对它的实际情况抖动很大

150
00:06:19,680 --> 00:06:22,400
好 而对于时间片轮转呢

151
00:06:22,440 --> 00:06:23,040
那么这时候呢

152
00:06:23,080 --> 00:06:25,800
它基本上是在它们的中间

153
00:06:25,840 --> 00:06:29,520
这是这两种算法的比较

154
00:06:29,560 --> 00:06:31,240
好 那接下来说

155
00:06:31,280 --> 00:06:32,920
每一个进程占用CPU

156
00:06:32,960 --> 00:06:35,080
执行多长时间这件事情定下来了

157
00:06:35,120 --> 00:06:37,880
然后我们排队的事情也定下来了

158
00:06:37,920 --> 00:06:39,680
但这时候 它仍然没有办法

159
00:06:39,720 --> 00:06:43,400
用一个算法满足我们应用的所有需求

160
00:06:43,440 --> 00:06:45,040
好 那这时候 我们就想到

161
00:06:45,080 --> 00:06:47,560
是不是可以把这算法组合到一起

162
00:06:47,600 --> 00:06:50,160
实际上我们刚才的时间片轮转算法

163
00:06:50,200 --> 00:06:52,400
已经是把先来先服务

164
00:06:52,440 --> 00:06:55,720
和时间片划分的这种做法

165
00:06:55,760 --> 00:06:57,280
两个结合到一起

166
00:06:57,320 --> 00:06:58,280
好 那在这儿呢 

167
00:06:58,320 --> 00:07:02,400
第一个做法呢就是多级队列调度算法

168
00:07:02,440 --> 00:07:07,480
它把就绪队列分成若干个子队列

169
00:07:07,520 --> 00:07:09,520
每个子队列是相互独立的

170
00:07:09,560 --> 00:07:10,920
比如说我们在这里头

171
00:07:10,960 --> 00:07:13,960
前台 那是交互的应用

172
00:07:14,000 --> 00:07:16,360
那这时候我要求时间片短

173
00:07:16,400 --> 00:07:19,960
那后台呢 是计算时间比较长的

174
00:07:20,000 --> 00:07:24,040
那这时候呢我可能用先来先服务算法

175
00:07:24,080 --> 00:07:26,200
好 这两个交替到一起

176
00:07:26,240 --> 00:07:29,520
我用一个时间片算法

177
00:07:29,560 --> 00:07:32,320
好 然后说我各个队列之间

178
00:07:32,360 --> 00:07:33,720
可以有自己的调度算法

179
00:07:33,760 --> 00:07:35,240
这我们前台 用时间片轮转

180
00:07:35,280 --> 00:07:39,280
后台 用先来先服务

181
00:07:39,320 --> 00:07:42,040
然后队列之间怎么办

182
00:07:42,080 --> 00:07:45,880
那队列之间 既可以说我固定优先级

183
00:07:45,920 --> 00:07:48,400
前台想想是该优先

184
00:07:48,440 --> 00:07:52,080
好 后台呢有空的时候我再来处理

185
00:07:52,120 --> 00:07:53,440
好 这时候就可能有什么

186
00:07:53,480 --> 00:07:55,120
我们前面讨论到的

187
00:07:55,160 --> 00:07:56,080
你按照这个来的话

188
00:07:56,120 --> 00:07:57,440
它就会导致饥饿

189
00:07:57,480 --> 00:08:02,120
就是后台的这些长进程它的优先级低

190
00:08:02,160 --> 00:08:03,520
而且运算时间很长

191
00:08:03,560 --> 00:08:07,640
前台的交互进程的短进程

192
00:08:07,680 --> 00:08:08,640
数量很大的话

193
00:08:08,680 --> 00:08:10,640
那么它就会出现饥饿

194
00:08:10,680 --> 00:08:14,080
好 那说我换种办法

195
00:08:14,120 --> 00:08:16,400
用时间片轮转 那在这里呢

196
00:08:16,440 --> 00:08:19,480
每个队列分得一定的时间配额

197
00:08:19,520 --> 00:08:22,120
保证它总的时间占一定比例

198
00:08:22,160 --> 00:08:23,160
好 那你比如说这里头

199
00:08:23,200 --> 00:08:25,800
前台占80% 后台占20%

200
00:08:25,840 --> 00:08:27,440
前台有作业的时候呢

201
00:08:27,480 --> 00:08:30,240
它可以很好的得到及时的响应

202
00:08:30,280 --> 00:08:34,160
后台呢也不至于完全处于饥饿的状态

203
00:08:34,200 --> 00:08:35,960
在刚才的多极队列里头呢

204
00:08:36,000 --> 00:08:38,320
各个队列之间呢是没有交互的

205
00:08:38,360 --> 00:08:39,960
那进一步往前改进呢

206
00:08:40,000 --> 00:08:42,080
就是多级反馈队列

207
00:08:42,120 --> 00:08:43,440
那么多级反馈队列呢

208
00:08:43,480 --> 00:08:46,080
是队列之间可以相互移动

209
00:08:46,120 --> 00:08:47,000
也就说我一个进程

210
00:08:47,040 --> 00:08:49,320
在执行一段时间可以在队列A

211
00:08:49,360 --> 00:08:51,120
执行一段时间之后

212
00:08:51,160 --> 00:08:53,720
可以把它放到队列B里头

213
00:08:53,760 --> 00:08:56,320
那这种做法呢 它会变得更灵活

214
00:08:56,360 --> 00:08:58,280
比如说我们在这里头一种做法

215
00:08:58,320 --> 00:08:59,480
时间片的大小

216
00:08:59,520 --> 00:09:02,280
我可以在不同队列之间做调整

217
00:09:02,320 --> 00:09:04,400
那优先级越高的

218
00:09:04,440 --> 00:09:05,840
那它时间片越小

219
00:09:05,880 --> 00:09:09,080
优先级越低的呢它时间片越大

220
00:09:09,120 --> 00:09:10,400
好 然后在这里头

221
00:09:10,440 --> 00:09:12,600
如果说你执行的时间越长

222
00:09:12,640 --> 00:09:14,840
我把你的优先级调的更低

223
00:09:14,880 --> 00:09:17,400
那这地方我们用这样一个图示来表示

224
00:09:17,440 --> 00:09:19,840
我这个地方分了N个优先级

225
00:09:19,880 --> 00:09:22,520
由高到低 

226
00:09:22,560 --> 00:09:24,960
然后时间片q呢

227
00:09:25,000 --> 00:09:27,200
t0是基本的时间单位

228
00:09:27,240 --> 00:09:30,880
优先级越低 那它就会倍增

229
00:09:30,920 --> 00:09:33,440
好 那这时候每一个进程

230
00:09:33,480 --> 00:09:36,520
上来之后在优先级最高的一级

231
00:09:36,560 --> 00:09:38,680
好 如果说它一个时间片用完

232
00:09:38,720 --> 00:09:41,200
它还没有执行完 那它就降级

233
00:09:41,240 --> 00:09:42,400
好 这样一来的话

234
00:09:42,440 --> 00:09:44,880
我们这个算法就得到这样一个特征

235
00:09:44,920 --> 00:09:47,480
CPU密集型的进程

236
00:09:47,520 --> 00:09:51,040
那它的优先级会逐步降低

237
00:09:51,080 --> 00:09:53,440
并且时间片会分的很大

238
00:09:53,480 --> 00:09:54,360
好 这样的话

239
00:09:54,400 --> 00:09:57,400
它切换的这个开销呢相对来说变小

240
00:09:57,440 --> 00:10:00,480
而对于I/O密集型的进程

241
00:10:00,520 --> 00:10:03,320
那这时候呢它会停留在高优先级上

242
00:10:03,360 --> 00:10:05,120
因为每一次它算的时间都很短

243
00:10:05,160 --> 00:10:07,600
它的时间片没用完

244
00:10:07,640 --> 00:10:08,840
好 这样一来的话

245
00:10:08,880 --> 00:10:09,960
我们有可能在这里

246
00:10:10,000 --> 00:10:14,920
形成一个很好的多级反馈队列的算法

247
00:10:14,960 --> 00:10:16,480
好 在这个算法之上呢

248
00:10:16,520 --> 00:10:20,000
我们又有一类公平共享调度算法

249
00:10:20,040 --> 00:10:24,000
那它强调的是资源访问的公平

250
00:10:24,040 --> 00:10:26,520
把用户和进程分组

251
00:10:26,560 --> 00:10:28,720
一些用户呢比另一些用户重要

252
00:10:28,760 --> 00:10:31,960
那这样的话 它分的时间会更大

253
00:10:32,000 --> 00:10:34,920
然后不重要的这些用户呢

254
00:10:34,960 --> 00:10:36,240
不能让它垄断资源

255
00:10:36,280 --> 00:10:39,040
也就的说按用户的优先级来做这件事情

256
00:10:39,080 --> 00:10:40,120
那实际上我们在这儿

257
00:10:40,160 --> 00:10:42,520
用这个图示来描述

258
00:10:42,560 --> 00:10:44,720
系统资源我在调度器控制下

259
00:10:44,760 --> 00:10:46,000
分成若干组

260
00:10:46,040 --> 00:10:47,160
每一组占用的时间

261
00:10:47,200 --> 00:10:48,480
在执行的过程当中

262
00:10:48,520 --> 00:10:50,120
我是进行相应统计的

263
00:10:50,160 --> 00:10:51,920
好 这样一来的话我们就可以

264
00:10:51,960 --> 00:10:54,920
没有使用完的资源那就按比例分

265
00:10:54,960 --> 00:10:56,160
好 那在这里头呢

266
00:10:56,200 --> 00:10:57,880
如果说我的资源没用到

267
00:10:57,920 --> 00:10:59,400
我所约定的份额

268
00:10:59,440 --> 00:11:03,200
那这时候我优先获得相应的使用权

269
00:11:03,240 --> 00:11:04,840
这些时候呢的问题是说

270
00:11:04,880 --> 00:11:06,360
这个算法到底怎么来实现

271
00:11:06,400 --> 00:11:08,200
它的开销是什么样子

272
00:11:08,240 --> 00:11:11,000
我在这儿就不做仔细介绍了

273
00:11:11,040 --> 00:11:15,120
有兴趣同学可以下去进一步去看

274
00:11:15,160 --> 00:11:18,760
好 到这儿呢我们就说清楚了

275
00:11:18,800 --> 00:11:23,000
六种经典的 或者叫传统的调度算法

276
00:11:23,040 --> 00:11:26,040
每一种算法呢它各有特点

277
00:11:26,080 --> 00:11:27,800
对于先来先服务呢

278
00:11:27,840 --> 00:11:30,560
这个算法是很简单 但它不公平

279
00:11:30,600 --> 00:11:33,520
平均等待时间变动很大

280
00:11:33,560 --> 00:11:37,800
然后改进的一种办法是进程优先

281
00:11:37,840 --> 00:11:39,040
那这时候它不公平

282
00:11:39,080 --> 00:11:42,440
但是有一个特征是平均周转时间最小

283
00:11:42,480 --> 00:11:44,560
然后它有的毛病是

284
00:11:44,600 --> 00:11:47,440
需要预测未来的执行时间

285
00:11:47,480 --> 00:11:49,880
然后可能导致饥饿

286
00:11:49,920 --> 00:11:53,720
好 而高响应比优先呢

287
00:11:53,760 --> 00:11:57,280
实际上它考虑的是我的等待时间

288
00:11:57,320 --> 00:11:58,440
然后在这里呢

289
00:11:58,480 --> 00:12:01,840
它是基于短进程优先来改进的

290
00:12:01,880 --> 00:12:05,840
只是换了一下它排队的指标

291
00:12:05,880 --> 00:12:10,280
然后时间片轮转算法 它是公平的

292
00:12:10,320 --> 00:12:13,320
然后平均等待时间呢性能会比较差

293
00:12:13,360 --> 00:12:15,040
但它的交互性会很好

294
00:12:15,080 --> 00:12:17,920
然后多级反馈队列呢提供一套机制

295
00:12:17,960 --> 00:12:20,840
使得我多种算法可以集成到一起

296
00:12:20,880 --> 00:12:21,680
实际上我们现在

297
00:12:21,720 --> 00:12:23,840
在实际系统里用到的算法呢

298
00:12:23,880 --> 00:12:26,280
基本上是这种综合的算法

299
00:12:26,320 --> 00:12:27,360
只是综合的方式呢

300
00:12:27,400 --> 00:12:28,920
各个系统不一样

301
00:12:28,960 --> 00:12:31,360
而公平共享算法呢

302
00:12:31,400 --> 00:12:32,440
它强调的是

303
00:12:32,480 --> 00:12:36,320
公平是它第一个要衡量的指标

304
00:12:36,360 --> 00:12:38,600
好 那么刚才我们讨论清楚了

305
00:12:38,640 --> 00:12:42,840
这个传统的调度算法当中

306
00:12:42,880 --> 00:12:45,280
各自的特点和基本的做法

307
00:12:45,320 --> 00:12:47,800
那么我们对于实际系统里头

308
00:12:47,840 --> 00:12:49,320
我们还是以ucore为例

309
00:12:49,360 --> 00:12:51,920
介绍一下它的调度算法

310
00:12:51,960 --> 00:12:54,360
是怎么在系统里工作的

311
00:12:54,400 --> 00:12:58,000
首先呢我们看一下它的调度队列

312
00:12:58,040 --> 00:12:59,920
那在调度队列这个数据结构里头

313
00:12:59,960 --> 00:13:02,600
我们看到它有相应的指针结构

314
00:13:02,640 --> 00:13:05,280
来描述我就绪队列的排法

315
00:13:05,320 --> 00:13:07,160
然后每一个进程的相关的

316
00:13:07,200 --> 00:13:09,760
时间片的信息 在这里有描述

317
00:13:09,800 --> 00:13:10,840
好 这样一来的话

318
00:13:10,880 --> 00:13:15,040
就可以通过它把所有的进程串到一起

319
00:13:15,080 --> 00:13:16,640
放到各自的队列当中

320
00:13:16,680 --> 00:13:23,160
从而形成调度算法所需要的调度信息

321
00:13:23,200 --> 00:13:25,200
然后再一个就是说

322
00:13:25,240 --> 00:13:29,720
我们这里调度和进程状态之间的关联

323
00:13:29,760 --> 00:13:32,560
我们前面讲了三进程状态模型

324
00:13:32,600 --> 00:13:34,840
和我们调度之间的关系

325
00:13:34,880 --> 00:13:37,960
而我们的ucore呢更简单

326
00:13:38,000 --> 00:13:41,200
只有两种基本的状态

327
00:13:41,240 --> 00:13:44,120
创建和退出 这两个状态呢

328
00:13:44,160 --> 00:13:46,640
相对来说执行的时间很少

329
00:13:46,680 --> 00:13:51,200
那主要的是可执行和等待状态

330
00:13:51,240 --> 00:13:52,640
那在这里头呢 

331
00:13:52,680 --> 00:13:56,040
我们相应的状态转变

332
00:13:56,080 --> 00:13:57,960
分别在这几个相应的函数

333
00:13:58,000 --> 00:13:59,120
你比如说创建结束之后

334
00:13:59,160 --> 00:14:00,560
放在就绪队列里

335
00:14:00,600 --> 00:14:01,680
我们前面已经说过

336
00:14:01,720 --> 00:14:03,480
在proc_init里头

337
00:14:03,520 --> 00:14:05,240
好 那在这里头呢

338
00:14:05,280 --> 00:14:06,520
会有这样几个函数

339
00:14:06,560 --> 00:14:11,640
会导致运行状态的进程变到等待状态

340
00:14:11,680 --> 00:14:13,800
好 等待事件出现的时候

341
00:14:13,840 --> 00:14:16,200
它会回到运行状态

342
00:14:16,240 --> 00:14:19,720
然后exit 它会出来

343
00:14:19,760 --> 00:14:21,160
那在这些状态里头呢

344
00:14:21,200 --> 00:14:24,840
会和我们的进程切换联络到一起

345
00:14:24,880 --> 00:14:27,520
我们看一下它的切换的过程

346
00:14:27,560 --> 00:14:31,240
这是我们进程执行过程当中的

347
00:14:31,280 --> 00:14:33,840
内核和用户态之间的交互

348
00:14:33,880 --> 00:14:36,000
我们如果说只有一个进程的话

349
00:14:36,040 --> 00:14:37,800
在用户态执行

350
00:14:37,840 --> 00:14:40,920
那可能会出现中断或者系统调用

351
00:14:40,960 --> 00:14:42,840
这时候切换到内核

352
00:14:42,880 --> 00:14:44,880
这两个的切换呢对于我们来说

353
00:14:44,920 --> 00:14:47,760
在我们这个层面上来讲是一致的

354
00:14:47,800 --> 00:14:49,720
好 切换过去之后

355
00:14:49,760 --> 00:14:52,040
它保护中断的现场

356
00:14:52,080 --> 00:14:53,560
然后处理中断

357
00:14:53,600 --> 00:14:55,320
正常情况下处理完之后

358
00:14:55,360 --> 00:14:57,520
它回到用户态继续执行了 对吗

359
00:14:57,560 --> 00:14:59,360
好 现在我们在这儿呢

360
00:14:59,400 --> 00:15:01,080
在中间加了一个调度

361
00:15:01,120 --> 00:15:02,680
也就说我处理完了之后

362
00:15:02,720 --> 00:15:05,680
并不是直接恢复最后的现场

363
00:15:05,720 --> 00:15:08,480
而是在这里呢加了一个调度

364
00:15:08,520 --> 00:15:11,600
调度之后呢我就可以到另外的进程

365
00:15:11,640 --> 00:15:14,560
好 另外的进程呢最后会回到这儿来

366
00:15:14,600 --> 00:15:18,240
那这时候我们看一下整个的过程

367
00:15:18,280 --> 00:15:20,680
首先 是在执行的过程当中

368
00:15:20,720 --> 00:15:22,440
出现系统调用

369
00:15:22,480 --> 00:15:24,840
或者说中断 或者说异常

370
00:15:24,880 --> 00:15:27,400
这时候呢它切到内核

371
00:15:27,440 --> 00:15:28,760
那切过来的时候呢

372
00:15:28,800 --> 00:15:31,360
它会保存中断的现场

373
00:15:31,400 --> 00:15:33,960
保存完之后 那我进行中断处理

374
00:15:34,000 --> 00:15:35,760
因为这是要求时间的

375
00:15:35,800 --> 00:15:38,200
那 处理完之后呢

376
00:15:38,240 --> 00:15:41,160
正常情况下我就恢复用户态的现场

377
00:15:41,200 --> 00:15:42,960
然后就回去了

378
00:15:43,000 --> 00:15:44,680
但是现在调度之后

379
00:15:44,720 --> 00:15:47,360
调度的结果 如果说你是

380
00:15:47,400 --> 00:15:48,880
仍然是执行这个进程

381
00:15:48,920 --> 00:15:50,640
那跟原来一样

382
00:15:50,680 --> 00:15:53,160
好 如果说你是执行其它进程

383
00:15:53,200 --> 00:15:55,240
那么就切到另一个进程了

384
00:15:55,280 --> 00:15:56,560
而假定另一个进程

385
00:15:56,600 --> 00:15:58,640
实际上刚才也是执行到这个地方

386
00:15:58,680 --> 00:16:00,000
然后做的切换

387
00:16:00,040 --> 00:16:01,560
那到这儿来的时候呢

388
00:16:01,600 --> 00:16:05,920
它就会回到恢复中断现场

389
00:16:05,960 --> 00:16:08,840
那到这儿呢 确实是恢复中断现场

390
00:16:08,880 --> 00:16:10,760
恢复完之后它怎么办

391
00:16:10,800 --> 00:16:14,560
它就回到用户态去了

392
00:16:14,600 --> 00:16:15,440
就到这儿

393
00:16:15,480 --> 00:16:17,000
好 到用户态继续执行

394
00:16:17,040 --> 00:16:21,480
那在这里执行的过程当中呢

395
00:16:21,520 --> 00:16:23,640
它还会再出现中断

396
00:16:23,680 --> 00:16:25,840
比如说我时间片用完

397
00:16:25,880 --> 00:16:27,800
这时候再出现中断

398
00:16:27,840 --> 00:16:28,640
中断怎么办

399
00:16:28,680 --> 00:16:31,320
跟刚才这地方是一样的

400
00:16:31,360 --> 00:16:32,720
它进到内核态

401
00:16:32,760 --> 00:16:35,520
好 这时候呢保存中断现场

402
00:16:35,560 --> 00:16:39,800
进行中断处理 然后进行调度

403
00:16:39,840 --> 00:16:40,760
调度完了之后

404
00:16:40,800 --> 00:16:43,960
如果说切回上一回执行的那个进程

405
00:16:44,000 --> 00:16:45,200
怎么办

406
00:16:45,240 --> 00:16:49,360
切回去 好 这时候对于这个进程来说

407
00:16:49,400 --> 00:16:52,440
你可以理解为它处理完中断现场

408
00:16:52,480 --> 00:16:57,680
然后恢复用户态的现场

409
00:16:57,720 --> 00:17:00,640
然后回到用户态继续执行

410
00:17:00,680 --> 00:17:05,520
那整个这个切换的过程就完成了

411
00:17:05,560 --> 00:17:07,720
好 然后调度实际在哪

412
00:17:07,760 --> 00:17:10,200
就是由内核态返回到用户态

413
00:17:10,240 --> 00:17:12,160
之前那个时刻

414
00:17:12,200 --> 00:17:13,600
那我做这个调度，

415
00:17:13,640 --> 00:17:14,920
调度完之后到别的了

416
00:17:14,960 --> 00:17:16,440
回来的时候我再恢复

417
00:17:16,480 --> 00:17:17,560
然后回到用户态

418
00:17:17,600 --> 00:17:20,200
这样的话 既不影响到中断的及时处理

419
00:17:20,240 --> 00:17:22,600
也可以让各个进程之间

420
00:17:22,640 --> 00:17:24,520
能够交替运行

421
00:17:24,560 --> 00:17:25,680
好 那这个过程呢

422
00:17:25,720 --> 00:17:27,000
希望大家下去之后

423
00:17:27,040 --> 00:17:29,320
通过实际的ucore代码阅读

424
00:17:29,360 --> 00:17:36,200
来理解这个过程的执行情况

425
00:17:36,240 --> 00:17:38,040
好 那如果说我们在这里

426
00:17:38,080 --> 00:17:42,160
要加自己的调度算法 我怎么加呢

427
00:17:42,200 --> 00:17:44,360
在ucore里呢定义了一个调度类

428
00:17:44,400 --> 00:17:45,280
在这里头呢 

429
00:17:45,320 --> 00:17:48,800
约定了调度算法对外提供的接口

430
00:17:48,840 --> 00:17:49,960
比如说我们在这里头

431
00:17:50,000 --> 00:17:51,360
调度算法会什么

432
00:17:51,400 --> 00:17:53,560
我有一个进程变成就绪状态

433
00:17:53,600 --> 00:17:55,960
我如何把它加到就绪队列里头

434
00:17:56,000 --> 00:17:58,960
我要选择下一个进程占用CPU来运行

435
00:17:59,000 --> 00:18:00,240
我选择哪个进程

436
00:18:00,280 --> 00:18:02,440
那这时候呢 对应着两个函数

437
00:18:02,480 --> 00:18:04,640
一个是入队 一个是出队

438
00:18:04,680 --> 00:18:06,080
有了这两个函数之后

439
00:18:06,120 --> 00:18:08,080
我就知道不同的调度算法

440
00:18:08,120 --> 00:18:11,080
就可以按照自己的调度方法

441
00:18:11,120 --> 00:18:13,520
由等待状态变成就绪状态的进程

442
00:18:13,560 --> 00:18:15,440
放到就绪队列里头

443
00:18:15,480 --> 00:18:17,160
也可以从里头选择出

444
00:18:17,200 --> 00:18:19,040
下一个要执行的进程

445
00:18:19,080 --> 00:18:21,520
来从这个就绪队列里头取出来

446
00:18:21,560 --> 00:18:24,240
好 那除此之外还有几个函数

447
00:18:24,280 --> 00:18:26,400
一个是pick_next 

448
00:18:26,440 --> 00:18:29,200
就是我选择下一个进程

449
00:18:29,240 --> 00:18:32,920
然后还有一个呢 就是proc_tick

450
00:18:32,960 --> 00:18:34,040
tick实际上相当于

451
00:18:34,080 --> 00:18:36,120
我们在这里呢会支持时钟中断

452
00:18:36,160 --> 00:18:37,320
时钟中断的时候

453
00:18:37,360 --> 00:18:38,840
在不同的调度算法呢

454
00:18:38,880 --> 00:18:42,320
你的计数 或者说对优先级的修改

455
00:18:42,360 --> 00:18:44,480
是不一致的 好 那在这儿有这个

456
00:18:44,520 --> 00:18:46,360
再加上一个初始化 OK

457
00:18:46,400 --> 00:18:48,600
我整个调度算法的内容呢

458
00:18:48,640 --> 00:18:51,640
都可以从这儿和我的系统接起来了

459
00:18:51,680 --> 00:18:52,720
好 那这样一来的话

460
00:18:52,760 --> 00:18:54,000
我的系统其它部分 

461
00:18:54,040 --> 00:18:56,240
不需要了解你的调度算法的细则

462
00:18:56,280 --> 00:18:58,160
我只要这个接口能接上

463
00:18:58,200 --> 00:18:59,360
那你的调度算法

464
00:18:59,400 --> 00:19:02,080
就可以在我这个系统里面工作了

465
00:19:02,120 --> 00:19:04,840
好 每个人呢只需要实现这几个函数

466
00:19:04,880 --> 00:19:07,480
你就可以把你自己的调度算法呢实现出来了

467
00:19:07,520 --> 00:19:09,680
并且和系统对接起来

468
00:19:09,720 --> 00:19:10,560
好 那实际上

469
00:19:10,600 --> 00:19:12,760
我们系统里怎么用这些东西呢

470
00:19:12,800 --> 00:19:16,120
那这就是我们ucore调度框架

471
00:19:16,160 --> 00:19:17,960
那我们说在用户态

472
00:19:18,000 --> 00:19:20,800
前面讲进程控制的时候

473
00:19:20,840 --> 00:19:22,960
已经说过了这样一些函数

474
00:19:23,000 --> 00:19:26,200
这些函数都和进程控制相关

475
00:19:26,240 --> 00:19:28,240
然后这地方是调度

476
00:19:28,280 --> 00:19:31,280
其中一部分是直接到这儿来

477
00:19:31,320 --> 00:19:33,680
重要的都是从schedule过来

478
00:19:33,720 --> 00:19:34,840
好 这个地方接的

479
00:19:34,880 --> 00:19:36,240
就是我们刚才说的

480
00:19:36,280 --> 00:19:40,160
调度类接口里的那些接口函数

481
00:19:40,200 --> 00:19:41,680
好 你的实现的函数呢

482
00:19:41,720 --> 00:19:45,440
通过填这个数据结构的函数指针

483
00:19:45,480 --> 00:19:47,880
那把你的调度算法接到这里头来

484
00:19:47,920 --> 00:19:51,280
那上面的系统调用和用户态

485
00:19:51,320 --> 00:19:52,960
通过这一边连到这儿来

486
00:19:53,000 --> 00:19:55,120
那这样的话系统应用

487
00:19:55,160 --> 00:19:59,120
就依据你的调度算法再进行调度

488
00:19:59,160 --> 00:20:01,120
这是ucore的调度框架

489
00:20:01,160 --> 00:20:02,400
那在实验当中呢

490
00:20:02,440 --> 00:20:03,880
要求大家去实现一种

491
00:20:03,920 --> 00:20:07,240
简单的调度算法 叫stride

492
00:20:07,280 --> 00:20:07,880


493
00:20:07,920 --> 00:20:07,960