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


1
00:00:06,480 --> 00:00:08,600
下面我们来介绍调度准则

2
00:00:08,680 --> 00:00:11,720
也就说在我们处理机调度里头

3
00:00:11,760 --> 00:00:13,880
我们调度的策略

4
00:00:13,920 --> 00:00:19,600
和调度算法好坏的一个比较指标

5
00:00:19,640 --> 00:00:21,480
那首先呢是调度策略

6
00:00:21,520 --> 00:00:23,760
调度策略呢是用来确定

7
00:00:23,800 --> 00:00:26,440
我如何从就绪队列当中

8
00:00:26,480 --> 00:00:28,720
选择下一个执行进程

9
00:00:28,760 --> 00:00:29,960
那这种选择呢

10
00:00:30,000 --> 00:00:31,080
到底选择哪一个

11
00:00:31,120 --> 00:00:32,080
实际上跟我们选择的

12
00:00:32,120 --> 00:00:34,120
调度目标是有关系的

13
00:00:34,160 --> 00:00:36,600
好 那这里我们具体说起来

14
00:00:36,640 --> 00:00:37,600
有些什么问题呢

15
00:00:37,640 --> 00:00:40,040
具体说起来就是挑选哪一个

16
00:00:40,080 --> 00:00:41,440
第二个 挑选的时候

17
00:00:41,480 --> 00:00:43,680
我用什么样的一个准则

18
00:00:43,720 --> 00:00:44,840
来进行挑选

19
00:00:44,880 --> 00:00:47,200
好 调度策略确定下来之后呢

20
00:00:47,240 --> 00:00:48,880
那调度策略的实现

21
00:00:48,920 --> 00:00:51,840
就是我们这里的调度算法

22
00:00:51,880 --> 00:00:53,400
然后我们在这里呢

23
00:00:53,440 --> 00:00:55,000
需要约定一个目标

24
00:00:55,040 --> 00:00:57,640
说我到底这两个调度算法

25
00:00:57,680 --> 00:01:00,200
或者是调度策略哪个比哪个好

26
00:01:00,240 --> 00:01:02,400
在前面我们讲过存储管理

27
00:01:02,440 --> 00:01:04,320
里头有置换算法

28
00:01:04,360 --> 00:01:06,960
那个置换算法的标准很清楚

29
00:01:07,000 --> 00:01:09,400
说到底哪个置换算法好呢

30
00:01:09,440 --> 00:01:12,040
最后 对一个序列来讲

31
00:01:12,080 --> 00:01:15,240
它的缺页次数最少 这就是好的

32
00:01:15,280 --> 00:01:16,840
如果说是在一类的

33
00:01:16,880 --> 00:01:18,040
测试用例里头

34
00:01:18,080 --> 00:01:20,680
它平均的缺页次数少 那就是好的

35
00:01:20,720 --> 00:01:22,840
但是对于调度策略来说呢

36
00:01:22,880 --> 00:01:25,160
这件事情就没有这么简单了

37
00:01:25,200 --> 00:01:28,400
那为了具体说明 我们的调度算法

38
00:01:28,440 --> 00:01:30,200
用什么来作为它的考核指标

39
00:01:30,240 --> 00:01:32,080
我们在这儿呢 有必要介绍一下

40
00:01:32,120 --> 00:01:34,480
处理机的使用模式

41
00:01:34,520 --> 00:01:37,040
也就是说我们通常情况下

42
00:01:37,080 --> 00:01:39,360
进程占用CPU来执行

43
00:01:39,400 --> 00:01:40,560
它通常处于

44
00:01:40,600 --> 00:01:42,680
这样两种模式之间来回切换

45
00:01:42,720 --> 00:01:44,880
一个是用CPU算

46
00:01:44,920 --> 00:01:46,160
这叫CPU计算

47
00:01:46,200 --> 00:01:48,520
另一个呢 我在CPU指挥下

48
00:01:48,560 --> 00:01:49,840
我要进行I/O操作

49
00:01:49,880 --> 00:01:51,360
这时候要跟外设打交道

50
00:01:51,400 --> 00:01:52,640
在外设打交道时候呢

51
00:01:52,680 --> 00:01:54,640
CPU通常情况下处于等待状态

52
00:01:54,680 --> 00:01:55,520
通常情况下呢

53
00:01:55,560 --> 00:01:56,400
我们的应用程序

54
00:01:56,440 --> 00:02:01,240
在这两种状态之间做交替执行

55
00:02:01,280 --> 00:02:02,280
那这种过程呢 

56
00:02:02,320 --> 00:02:06,280
我们可以用这样一个图式来表现出来

57
00:02:06,320 --> 00:02:07,760
CPU计算 I/O操作

58
00:02:07,800 --> 00:02:09,200
CPU计算 I/O操作

59
00:02:09,240 --> 00:02:12,080
这几个序列是交替进行的

60
00:02:12,120 --> 00:02:13,440
那从这种交替里头

61
00:02:13,480 --> 00:02:15,440
我们能发现些什么规律呢

62
00:02:15,480 --> 00:02:19,280
这些规律对我们的调度算法有影响吗

63
00:02:19,320 --> 00:02:22,280
那我们对这里的这个执行的过程

64
00:02:22,320 --> 00:02:23,800
做这样一些统计

65
00:02:23,840 --> 00:02:25,000
统计出这样一个结果

66
00:02:25,040 --> 00:02:29,720
说我们关心它每一次CPU执行的时间

67
00:02:29,760 --> 00:02:31,400
这是这儿的横轴

68
00:02:31,440 --> 00:02:34,160
然后根据每一次时间长短呢

69
00:02:34,200 --> 00:02:37,120
对所有的CPU执行时间呢做一个统计

70
00:02:37,160 --> 00:02:41,240
纵向是某一个长度的执行时间

71
00:02:41,280 --> 00:02:42,920
它总的执行次数

72
00:02:42,960 --> 00:02:45,720
那这时候呢我们就得到这样一条曲线

73
00:02:45,760 --> 00:02:47,960
从这儿呢我们可以看到每一次执行呢

74
00:02:48,000 --> 00:02:50,160
通常情况下它的时间都很短

75
00:02:50,200 --> 00:02:51,440
比如说在这里看到的

76
00:02:51,480 --> 00:02:53,960
就是8毫秒以内

77
00:02:54,000 --> 00:02:55,800
好 那更长的时间呢

78
00:02:55,840 --> 00:02:58,160
如果说你给它分配更长的时间片

79
00:02:58,200 --> 00:03:01,120
那这时候呢 我们这件事情就没必要了

80
00:03:01,160 --> 00:03:02,720
所以这个呢可以用来说

81
00:03:02,760 --> 00:03:05,560
我们每一次执行的时间到底分配多长

82
00:03:05,600 --> 00:03:07,920
这是会有依据的

83
00:03:07,960 --> 00:03:09,000
好 那这时候说

84
00:03:09,040 --> 00:03:11,600
我们一个要决定下一个给谁

85
00:03:11,640 --> 00:03:12,640
那肯定是要给到

86
00:03:12,680 --> 00:03:14,240
下一个就绪的进程

87
00:03:14,280 --> 00:03:16,040
但是就绪进程如果有多个的话

88
00:03:16,080 --> 00:03:17,240
我们怎么来判断

89
00:03:17,280 --> 00:03:18,960
那这是第一个问题

90
00:03:19,000 --> 00:03:20,000
第二个是说

91
00:03:20,040 --> 00:03:21,640
如果在这里有时间片机制

92
00:03:21,680 --> 00:03:23,000
也就是我对时间有要求的话

93
00:03:23,040 --> 00:03:25,640
那进程如果说你的时间片分短了

94
00:03:25,680 --> 00:03:27,040
比如说在这里头

95
00:03:27,080 --> 00:03:28,120
我分的时间很短

96
00:03:28,160 --> 00:03:29,200
那大多数操作

97
00:03:29,240 --> 00:03:30,640
都没有执行到一个阶段的时候

98
00:03:30,680 --> 00:03:31,560
你把它暂停下来

99
00:03:31,600 --> 00:03:32,680
好 这样你恢复回来的时候

100
00:03:32,720 --> 00:03:34,320
有些事情没法做了

101
00:03:34,360 --> 00:03:37,880
好 这时候呢我可能被迫放弃CPU

102
00:03:37,920 --> 00:03:40,600
这时候对进程的执行是不利的

103
00:03:40,640 --> 00:03:41,760
所以我们在这儿要选一个

104
00:03:41,800 --> 00:03:43,760
合适的时间尺度

105
00:03:43,800 --> 00:03:47,200
来作为我们这里时间片的基本单位 

106
00:03:47,240 --> 00:03:48,920
好 有了这个介绍之后

107
00:03:48,960 --> 00:03:51,000
我们再来看

108
00:03:51,040 --> 00:03:55,360
我们关心的调度算法的目标

109
00:03:55,400 --> 00:03:58,520
我会用什么样的一些指标来度量

110
00:03:58,560 --> 00:04:00,440
我这个调度算法好与坏

111
00:04:00,480 --> 00:04:03,520
首先第一个是CPU的使用率

112
00:04:03,560 --> 00:04:08,840
也就说你不同的调度算法在进程执行等待I/O的时候

113
00:04:08,880 --> 00:04:13,120
我是不是能够及时的找到另一个进程来占用CPU来执行

114
00:04:13,160 --> 00:04:14,640
如果能那这样的话

115
00:04:14,680 --> 00:04:17,640
我总的CPU的繁忙的时间

116
00:04:17,680 --> 00:04:19,200
的比例就会提高

117
00:04:19,240 --> 00:04:20,880
那最理想这是到100%

118
00:04:20,920 --> 00:04:23,440
好 这是系统关心的一个目标

119
00:04:23,480 --> 00:04:25,560
还有一个呢是吞吐力

120
00:04:25,600 --> 00:04:28,920
在单位时间内我完成的进程数目

121
00:04:28,960 --> 00:04:31,000
这是从系统利用效率的角度

122
00:04:31,040 --> 00:04:32,800
来讲我关心的两个指标

123
00:04:32,840 --> 00:04:34,160
而从用户的角度来讲呢

124
00:04:34,200 --> 00:04:36,960
我们可能关心的是另外一些指标

125
00:04:37,000 --> 00:04:38,960
比如说周转时间

126
00:04:39,000 --> 00:04:42,200
从我提交作业到最后算出结果

127
00:04:42,240 --> 00:04:43,920
这中间有多长时间

128
00:04:43,960 --> 00:04:45,680
这是周转时间用户关心的

129
00:04:45,720 --> 00:04:47,040
换个角度来说呢

130
00:04:47,080 --> 00:04:49,440
他可能会关心我的等待时间

131
00:04:49,480 --> 00:04:50,840
这里的等待时间是指

132
00:04:50,880 --> 00:04:54,000
我进程在就绪队列的时间

133
00:04:54,040 --> 00:04:56,400
因为处于我们进程状态里的

134
00:04:56,440 --> 00:04:58,000
那个等待状态的时间

135
00:04:58,040 --> 00:04:59,120
那是必须等的

136
00:04:59,160 --> 00:05:00,360
因为你等I/O操作没结束

137
00:05:00,400 --> 00:05:01,600
想干别的干不了

138
00:05:01,640 --> 00:05:02,720
那我们能缩短的

139
00:05:02,760 --> 00:05:05,440
是在处于就绪状态的这个时间

140
00:05:05,480 --> 00:05:06,920
如果说我一个进程

141
00:05:06,960 --> 00:05:09,400
从等待状态到了就绪

142
00:05:09,440 --> 00:05:11,520
马上就能占用CPU来执行的话

143
00:05:11,560 --> 00:05:15,000
那我的这个周转时间肯定就会短

144
00:05:15,040 --> 00:05:18,240
好 然后对于交互性应用来说

145
00:05:18,280 --> 00:05:20,360
我还关心它的响应时间

146
00:05:20,400 --> 00:05:23,960
从我提交请求到系统给出响应

147
00:05:24,000 --> 00:05:25,400
这中间需要多长时间

148
00:05:25,440 --> 00:05:27,360
比如说我敲键盘 玩游戏

149
00:05:27,400 --> 00:05:29,840
那这时候它不能及时响应我的操作

150
00:05:29,880 --> 00:05:33,040
这是影响用户体验的

151
00:05:33,080 --> 00:05:34,480
好 那在这里头我们说

152
00:05:34,520 --> 00:05:36,400
到底这些指标搁到一起

153
00:05:36,440 --> 00:05:38,080
好像他们都是矛盾的

154
00:05:38,120 --> 00:05:39,640
我们怎么来做 好

155
00:05:39,680 --> 00:05:40,920
这里头呢就有一个

156
00:05:40,960 --> 00:05:43,440
我到底关心哪项指标是我的重点

157
00:05:43,480 --> 00:05:44,960
通常情况下用户只是说

158
00:05:45,000 --> 00:05:46,480
我希望更快的服务

159
00:05:46,520 --> 00:05:47,920
到底怎么算快

160
00:05:47,960 --> 00:05:49,520
那在这儿呢

161
00:05:49,560 --> 00:05:52,160
我们给出这样一些描述

162
00:05:52,200 --> 00:05:53,320
那在不同的情况下

163
00:05:53,360 --> 00:05:55,440
我们对快的描述是不一样的

164
00:05:55,480 --> 00:05:58,440
比如说我在传文件的时候 

165
00:05:58,480 --> 00:06:01,240
带宽高 那这时候是快

166
00:06:01,280 --> 00:06:03,160
对应到我们调度算法里头呢

167
00:06:03,200 --> 00:06:04,560
我在单位时间里

168
00:06:04,600 --> 00:06:07,480
能执行更多的进程 这叫快

169
00:06:07,520 --> 00:06:09,040
而在另一些情况下

170
00:06:09,080 --> 00:06:10,560
如果说我是在玩游戏的时候

171
00:06:10,600 --> 00:06:12,440
那我希望它的响应速度好

172
00:06:12,480 --> 00:06:13,520
那就延时低

173
00:06:13,560 --> 00:06:14,720
对于调度算法呢 

174
00:06:14,760 --> 00:06:16,760
它就是有低的响应延迟

175
00:06:16,800 --> 00:06:19,720
也就是说响应时间很短 很快

176
00:06:19,760 --> 00:06:21,080
那在这里头呢

177
00:06:21,120 --> 00:06:24,640
这两个因素实际上是相互独立的

178
00:06:24,680 --> 00:06:27,040
延时低并不一定意味着高带宽

179
00:06:27,080 --> 00:06:29,640
高带宽并不一定意味着低延时

180
00:06:29,680 --> 00:06:31,760
它们俩是相互独立的 

181
00:06:31,800 --> 00:06:33,520
好 我们在这儿呢用一个类比

182
00:06:33,560 --> 00:06:36,280
来说明它们之间的关系

183
00:06:36,320 --> 00:06:39,440
低延时是指说我想喝水

184
00:06:39,480 --> 00:06:40,280
那这时候呢

185
00:06:40,320 --> 00:06:42,560
那杯水我能很快的有水

186
00:06:42,600 --> 00:06:43,560
我就能喝上了

187
00:06:43,600 --> 00:06:45,200
所以这时候呢是从

188
00:06:45,240 --> 00:06:46,640
我提出这个请求

189
00:06:46,680 --> 00:06:49,360
到有水这个时间段

190
00:06:49,400 --> 00:06:52,120
而如果说我是想把一个游泳池灌满

191
00:06:52,160 --> 00:06:53,120
那这时候呢

192
00:06:53,160 --> 00:06:55,000
开始有水的时间我并不关心

193
00:06:55,040 --> 00:06:57,720
我关心的是最后灌满水的时间

194
00:06:57,760 --> 00:06:59,280
这时候实际上需要的是

195
00:06:59,320 --> 00:07:02,120
你这个水管子流量必须大

196
00:07:02,160 --> 00:07:06,160
好 这是吞吐量和响应延时这两个指标

197
00:07:06,200 --> 00:07:09,280
它们之间的对快的这个描述

198
00:07:09,320 --> 00:07:11,160
好 依据这些描述

199
00:07:11,200 --> 00:07:12,040
我们就可以把

200
00:07:12,080 --> 00:07:14,680
处理机调度策略的目标

201
00:07:14,720 --> 00:07:15,960
分成这样几个方面

202
00:07:16,000 --> 00:07:18,920
一个呢是响应时间目标

203
00:07:18,960 --> 00:07:21,560
我们希望快的响应

204
00:07:21,600 --> 00:07:23,600
也就说减少响应时间

205
00:07:23,640 --> 00:07:25,840
及时处理用户的输入请求

206
00:07:25,880 --> 00:07:29,640
尽快地把输出反馈给用户

207
00:07:29,680 --> 00:07:34,360
那同时呢 我们希望这种响应的时间

208
00:07:34,400 --> 00:07:36,600
它的抖动必须很小

209
00:07:36,640 --> 00:07:38,160
原因在于 如果说

210
00:07:38,200 --> 00:07:40,680
你在某一些情况下响应时间很短

211
00:07:40,720 --> 00:07:43,800
在另外一些情况下响应时间很长

212
00:07:43,840 --> 00:07:45,200
那实际上这时候用户体验

213
00:07:45,240 --> 00:07:46,600
它是很不稳定的

214
00:07:46,640 --> 00:07:49,520
所以在这儿 可预测的响应时间

215
00:07:49,560 --> 00:07:53,600
比高差异的低响应时间更重要

216
00:07:53,640 --> 00:07:56,880
好 这是从这个角度来讲呢

217
00:07:56,920 --> 00:07:59,480
我们改善了它的响应时间

218
00:07:59,520 --> 00:08:00,000
那这时候呢

219
00:08:00,040 --> 00:08:02,320
用户的交互体验就会好

220
00:08:02,360 --> 00:08:04,520
如果说你操作了

221
00:08:04,560 --> 00:08:06,640
机器没有及时给出响应

222
00:08:06,680 --> 00:08:08,600
那这时候呢用户很可能就会说

223
00:08:08,640 --> 00:08:09,640
我就把机器

224
00:08:09,680 --> 00:08:11,760
认为它有故障了就会把它重启

225
00:08:11,800 --> 00:08:13,600
好 所以在这个地方呢

226
00:08:13,640 --> 00:08:16,280
响应时间是操作系统的一个

227
00:08:16,320 --> 00:08:19,720
重要的调度算法要达到目标

228
00:08:19,760 --> 00:08:22,760
这就是它这里的计算延时

229
00:08:22,800 --> 00:08:25,360
另一个目标呢是吞吐量目标

230
00:08:25,400 --> 00:08:29,720
也就说我们希望增加系统的吞吐量

231
00:08:29,760 --> 00:08:31,120
那增加系统吞吐量呢

232
00:08:31,160 --> 00:08:34,880
可以从两个角度来提出解决的方案

233
00:08:34,920 --> 00:08:37,320
一个呢是减少开销

234
00:08:37,360 --> 00:08:40,000
比如说我们上下文切换的时候

235
00:08:40,040 --> 00:08:42,160
它的速度是不是能更快

236
00:08:42,200 --> 00:08:46,480
第二个是提高系统的利用效率

237
00:08:46,520 --> 00:08:47,960
你比如说CPU的利用率

238
00:08:48,000 --> 00:08:49,320
I/O设备的利用率

239
00:08:49,360 --> 00:08:51,880
如果让这两者都达到100%

240
00:08:51,920 --> 00:08:55,600
那你的效率是最高的

241
00:08:55,640 --> 00:08:57,520
同时减少等待时间

242
00:08:57,560 --> 00:08:58,680
这个减少等待时间

243
00:08:58,720 --> 00:09:01,240
用户和系统的目标呢是一致的

244
00:09:01,280 --> 00:09:04,560
减少等待时间可以提高它的响应性能

245
00:09:04,600 --> 00:09:07,680
也可以提高它的吞吐量的性能

246
00:09:07,720 --> 00:09:09,960
好 那也就说我们在这里呢 

247
00:09:10,000 --> 00:09:12,560
要在有用户交互的情况下

248
00:09:12,600 --> 00:09:15,120
应该保证系统的吞吐力

249
00:09:15,160 --> 00:09:17,080
否则的话 那我们这个系统呢

250
00:09:17,120 --> 00:09:19,640
它就没办法正常使用了

251
00:09:19,680 --> 00:09:21,160
好 这时候说

252
00:09:21,200 --> 00:09:24,200
吞吐量呢是系统的计算带宽

253
00:09:24,240 --> 00:09:25,880
也就相当于我在单位时间里头

254
00:09:25,920 --> 00:09:28,680
能够尽可能执行更多的进程

255
00:09:28,720 --> 00:09:32,000
这是我们想要达到的目标

256
00:09:32,040 --> 00:09:34,120
还有一个目标呢是公平性

257
00:09:34,160 --> 00:09:37,200
也就说我们的系统它是不是公平的

258
00:09:37,240 --> 00:09:38,400
什么是公平呢

259
00:09:38,440 --> 00:09:41,720
我保证每一个进程占用相同的CPU时间

260
00:09:41,760 --> 00:09:42,840
这是一种描述

261
00:09:42,880 --> 00:09:45,400
这样就公平了吗 那不一定

262
00:09:45,440 --> 00:09:48,480
如果说一个用户执行了更多的进程

263
00:09:48,520 --> 00:09:50,520
那这时候每个进程的时间相同

264
00:09:50,560 --> 00:09:52,920
各个用户之间它是不同的

265
00:09:52,960 --> 00:09:54,080
好 那这时候说

266
00:09:54,120 --> 00:09:55,080
我们换一种提法

267
00:09:55,120 --> 00:09:57,960
让每一个进程的等待时间相同

268
00:09:58,000 --> 00:10:01,000
所以在不同的时间 不同场合

269
00:10:01,040 --> 00:10:05,480
它对公平性的度量是不一样的

270
00:10:05,520 --> 00:10:07,960
好 所以在这里头我们说公平性

271
00:10:08,000 --> 00:10:10,280
实际上你为了增加它的公平性

272
00:10:10,320 --> 00:10:11,360
我在很多时候

273
00:10:11,400 --> 00:10:13,640
会增加它的平均响应时间

274
00:10:13,680 --> 00:10:15,120
也就是我会有一定的开销

275
00:10:15,160 --> 00:10:17,880
来保证它是公平的

276
00:10:17,920 --> 00:10:22,400
好 这是我们关于调度算法的度量指标

277
00:10:22,440 --> 00:10:24,400
和一个调度算法怎么算好

278
00:10:24,440 --> 00:10:26,120
给出来的相应的描述

279
00:10:26,200 --> 00:10:26,840


280
00:10:26,880 --> 00:10:26,920


281
00:10:26,960 --> 00:10:27,000