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


1
00:00:07,160 --> 00:00:11,600
下面我们来介绍调度算法

2
00:00:11,640 --> 00:00:13,120
那么在这里头呢

3
00:00:13,160 --> 00:00:15,760
我们的调度算法呢分成了六种

4
00:00:15,800 --> 00:00:17,840
大致可以分成这样几类

5
00:00:17,880 --> 00:00:21,000
第一类呢关于就绪队列怎么排

6
00:00:21,040 --> 00:00:22,200
然后第二类呢

7
00:00:22,240 --> 00:00:24,800
是关于每一次执行时间

8
00:00:24,840 --> 00:00:26,760
的长短的控制

9
00:00:26,800 --> 00:00:28,720
然后再有后面两种

10
00:00:28,760 --> 00:00:31,840
是关于多种算法

11
00:00:31,880 --> 00:00:34,240
如何把它综合到一起

12
00:00:34,280 --> 00:00:39,560
那首先是这几种算法的一个大致说明

13
00:00:39,600 --> 00:00:42,600
首先是先来先服务算法

14
00:00:42,640 --> 00:00:44,400
这个算法呢 它是按着

15
00:00:44,440 --> 00:00:48,280
到就绪队列里的先后顺序来排队的

16
00:00:48,320 --> 00:00:50,640
那我们在找就绪进程的时候

17
00:00:50,680 --> 00:00:52,880
也是按照这个先后顺序来的

18
00:00:52,920 --> 00:00:55,600
跟我们前面讲的FIFO是很相似的

19
00:00:55,640 --> 00:00:56,720
那在那个地方呢

20
00:00:56,760 --> 00:00:59,480
是用来做置换算法的

21
00:00:59,520 --> 00:01:01,840
第二个是说 第一种算法它

22
00:01:01,880 --> 00:01:05,880
按先来后到没有考虑到进程的特征

23
00:01:05,920 --> 00:01:07,440
那在这儿 第二类呢

24
00:01:07,480 --> 00:01:09,840
就是短进程优先

25
00:01:09,880 --> 00:01:11,320
这里头呢会有几种

26
00:01:11,360 --> 00:01:13,800
稍微有一些小区别的变种

27
00:01:13,840 --> 00:01:14,840
那它们是按照

28
00:01:14,880 --> 00:01:20,480
作业执行时间的长短来进行排队的。

29
00:01:20,520 --> 00:01:25,160
然后第三个 是高响应比优先算法

30
00:01:25,200 --> 00:01:26,480
在这个算法里头呢

31
00:01:26,520 --> 00:01:31,160
它考虑的是进程在就绪队列里的等待时间

32
00:01:31,200 --> 00:01:33,320
依据等待时间的长短呢

33
00:01:33,360 --> 00:01:36,680
来考虑它排的这个队的情况

34
00:01:36,720 --> 00:01:39,960
好 下面呢是时间片轮转算法

35
00:01:40,000 --> 00:01:42,960
那它是让各个进程

36
00:01:43,000 --> 00:01:45,600
轮流占用一个基本的时间片

37
00:01:45,640 --> 00:01:47,160
然后在这里头

38
00:01:47,200 --> 00:01:48,720
排到就绪队列里头呢

39
00:01:48,760 --> 00:01:50,120
仍然按照我们前面的

40
00:01:50,160 --> 00:01:52,560
先来先服务算法来进行排队

41
00:01:52,600 --> 00:01:54,200
在那基础上呢多了一个

42
00:01:54,240 --> 00:01:57,200
执行时间的最大长度限制

43
00:01:57,240 --> 00:02:00,480
你最长不能执行超过一个时间片

44
00:02:00,520 --> 00:02:02,880
在这之前 你可以由于等待

45
00:02:02,920 --> 00:02:06,960
或者结束而让出CPU使用权

46
00:02:07,000 --> 00:02:08,920
而多级反馈队列呢

47
00:02:08,960 --> 00:02:13,240
是把我们的就绪队列排成多个子队列

48
00:02:13,280 --> 00:02:14,520
不同的子队列里头呢

49
00:02:14,560 --> 00:02:16,520
我可以有不同的算法

50
00:02:16,560 --> 00:02:18,480
并且可以在多个队列之间

51
00:02:18,520 --> 00:02:21,120
调整一个进程所排的队列

52
00:02:21,160 --> 00:02:23,680
这样的话就形成了一种综合的算法

53
00:02:23,720 --> 00:02:27,240
而最后的公平共享调度算法呢

54
00:02:27,280 --> 00:02:30,360
它强调的是按照

55
00:02:30,400 --> 00:02:34,960
进程占用的资源的情况来进行调度

56
00:02:35,000 --> 00:02:36,600
保证我们每一个进程

57
00:02:36,640 --> 00:02:39,320
占用的资源呢是相对公平的

58
00:02:39,360 --> 00:02:42,640
好 下面我们具体来说每一种算法

59
00:02:42,680 --> 00:02:45,440
首先是先来先服务算法

60
00:02:45,480 --> 00:02:46,800
那这种算法呢

61
00:02:46,840 --> 00:02:49,720
它是按照进程进入就绪状态

62
00:02:49,760 --> 00:02:53,000
的先后顺序来排队

63
00:02:53,040 --> 00:02:55,040
那这是就绪队列里的排法

64
00:02:55,080 --> 00:02:56,600
取的时候怎么办呢

65
00:02:56,640 --> 00:02:59,600
我一个进程在进入 等待或者结束

66
00:02:59,640 --> 00:03:03,200
也就说进程主动让出CPU

67
00:03:03,240 --> 00:03:05,080
然后我从就绪队列当中

68
00:03:05,120 --> 00:03:08,800
选择下一个进程占用CPU

69
00:03:08,840 --> 00:03:11,600
那在这种算法里头呢

70
00:03:11,640 --> 00:03:13,400
它的特征是啥样子的

71
00:03:13,440 --> 00:03:14,200
那我们在这儿呢

72
00:03:14,240 --> 00:03:17,080
对它的周转时间做一个分析

73
00:03:17,120 --> 00:03:19,160
假定我有三个进程

74
00:03:19,200 --> 00:03:23,480
它们分别的执行时间是12 3 3

75
00:03:23,520 --> 00:03:25,640
然后假定它们到达的顺序

76
00:03:25,680 --> 00:03:26,760
是这样一个顺序

77
00:03:26,800 --> 00:03:30,280
好 那我们按照先来先服务算法的要求

78
00:03:30,320 --> 00:03:31,520
那就是第一个执行完

79
00:03:31,560 --> 00:03:33,600
执行第二个 再执行第三个

80
00:03:33,640 --> 00:03:35,680
第一个12 到了12

81
00:03:35,720 --> 00:03:37,520
然后第二个是3 到了15

82
00:03:37,560 --> 00:03:39,600
第三个是3 到了18

83
00:03:39,640 --> 00:03:42,400
好 这是我们来看它的周转时间

84
00:03:42,440 --> 00:03:44,960
周转时间假定它们到达的时间

85
00:03:45,000 --> 00:03:47,280
基本上是同一个时刻到达

86
00:03:47,320 --> 00:03:48,520
好 那这样它的周转时间

87
00:03:48,560 --> 00:03:51,240
就变成是12 15 18

88
00:03:51,280 --> 00:03:52,920
除以3得15

89
00:03:52,960 --> 00:03:54,920
好这时候我们直观上就感觉到

90
00:03:54,960 --> 00:03:57,680
由于第一个进程执行时间比较长

91
00:03:57,720 --> 00:03:59,480
后面两个等的时间比较长

92
00:03:59,520 --> 00:04:01,640
好 这样的话周转时间变得长了

93
00:04:01,680 --> 00:04:03,600
如果说我换一个顺序

94
00:04:03,640 --> 00:04:05,880
假定到达顺序是这样子的

95
00:04:05,920 --> 00:04:07,680
那两个短的在前头

96
00:04:07,720 --> 00:04:09,960
那么这时候它的周转时间是什么样

97
00:04:10,000 --> 00:04:13,040
那周转时间就变成了9

98
00:04:13,080 --> 00:04:15,120
从这两个比较的角度来看呢

99
00:04:15,160 --> 00:04:16,960
我们看到 这个算法

100
00:04:17,000 --> 00:04:18,720
它的周转跟你这个

101
00:04:18,760 --> 00:04:22,200
队列到达的时间有很大的关系

102
00:04:22,240 --> 00:04:23,440
如果说你运气不好

103
00:04:23,480 --> 00:04:26,680
排到一个长的执行时间的进程的后面

104
00:04:26,720 --> 00:04:30,080
那么你的等待时间呢那就很长

105
00:04:30,120 --> 00:04:33,880
好 这是呢我们这种算法它的特征

106
00:04:33,920 --> 00:04:36,680
它的好处是简单

107
00:04:36,720 --> 00:04:40,160
排队的依据很容易获得

108
00:04:40,200 --> 00:04:42,240
排队过程当中呢也不需要什么变化

109
00:04:42,280 --> 00:04:43,920
所以这种算法比较简单

110
00:04:43,960 --> 00:04:46,760
它的麻烦呢是 

111
00:04:46,800 --> 00:04:49,560
平均等待时间波动非常大

112
00:04:49,600 --> 00:04:51,040
也就说如果你一个进程

113
00:04:51,080 --> 00:04:53,760
短的进程排在一个长的进程后面

114
00:04:53,800 --> 00:04:55,720
那你的等待时间就长了

115
00:04:55,760 --> 00:04:57,640
所以这时候呢你排的位置

116
00:04:57,680 --> 00:05:00,680
对你这算法特征呢影响很大

117
00:05:00,720 --> 00:05:04,680
再有一个呢是它资源的利用效率比较低

118
00:05:04,720 --> 00:05:07,320
那你说我一个进程进入等待

119
00:05:07,360 --> 00:05:08,760
另一个马上不就运行了嘛

120
00:05:08,800 --> 00:05:11,400
这时候它怎么会CPU利用效率低呢

121
00:05:11,440 --> 00:05:12,800
那我们看一种情况

122
00:05:12,840 --> 00:05:15,760
说有一个CPU密集型的进程

123
00:05:15,800 --> 00:05:17,040
那这时候它一直算

124
00:05:17,080 --> 00:05:18,360
算的时候它就会

125
00:05:18,400 --> 00:05:19,800
实际上I/O设备的操作

126
00:05:19,840 --> 00:05:22,120
可以和CPU并行的

127
00:05:22,160 --> 00:05:25,400
但是由于你CPU密集型进程呢正在运行

128
00:05:25,440 --> 00:05:28,040
那这时候I/O设备呢就空闲了

129
00:05:28,080 --> 00:05:29,480
那后面如果说你还有

130
00:05:29,520 --> 00:05:31,920
很多要进行I/O的这样一些进程呢

131
00:05:31,960 --> 00:05:36,680
也不会因为你当前CPU占用

132
00:05:36,720 --> 00:05:39,120
然后I/O设备空闲

133
00:05:39,160 --> 00:05:41,520
而让你可以先来执行I/O

134
00:05:41,560 --> 00:05:42,280
好 那这样一来

135
00:05:42,320 --> 00:05:45,960
你的I/O设备它的利用效率就低了

136
00:05:46,000 --> 00:05:47,520
好 那我们这时候

137
00:05:47,560 --> 00:05:49,480
要想对这种算法做改进

138
00:05:49,520 --> 00:05:50,640
改进怎么办呢

139
00:05:50,680 --> 00:05:51,560
我们排队的时候

140
00:05:51,600 --> 00:05:54,680
刚才说没有考虑到进程的特征

141
00:05:54,720 --> 00:05:58,680
那我们现在呢短进程优先算法

142
00:05:58,720 --> 00:06:00,720
它考虑到进程的特征

143
00:06:00,760 --> 00:06:02,360
考虑到进程什么特征呢

144
00:06:02,400 --> 00:06:05,120
考虑到进程的执行时间

145
00:06:05,160 --> 00:06:06,600
我在选择的时候呢

146
00:06:06,640 --> 00:06:09,640
选择执行时间最短的进程

147
00:06:09,680 --> 00:06:12,320
占用CPU进入运行状态

148
00:06:12,360 --> 00:06:14,920
那这时候说我选择最短的

149
00:06:14,960 --> 00:06:17,680
那这时候就按照预期的执行时间

150
00:06:17,720 --> 00:06:19,080
因为执行时间

151
00:06:19,120 --> 00:06:23,320
我是到执行的时候才会准确的知道

152
00:06:23,360 --> 00:06:25,440
事先我没有办法知道得很准确

153
00:06:25,480 --> 00:06:28,000
我只能是预期

154
00:06:28,040 --> 00:06:29,840
那这个预期就会有一个麻烦

155
00:06:29,880 --> 00:06:31,680
说我在这里头

156
00:06:31,720 --> 00:06:35,160
这是我们的进程状态图

157
00:06:35,200 --> 00:06:36,640
那我们在这里排的什么

158
00:06:36,680 --> 00:06:37,560
实际上排的就是

159
00:06:37,600 --> 00:06:41,600
把这个就绪队列按照这个来排了

160
00:06:41,640 --> 00:06:42,520
好 那在这里头呢

161
00:06:42,560 --> 00:06:45,520
这个预期的时间呢

162
00:06:45,560 --> 00:06:47,360
排完之后如果说我这里头

163
00:06:47,400 --> 00:06:49,080
还有一个新的进程到达

164
00:06:49,120 --> 00:06:50,120
并且它预计时间

165
00:06:50,160 --> 00:06:52,680
比当前正在执行的还短怎么办

166
00:06:52,720 --> 00:06:54,920
好 那这地方呢就有一个变种

167
00:06:54,960 --> 00:06:57,720
叫短剩余时间优先

168
00:06:57,760 --> 00:06:59,040
好 那也就是说相当于

169
00:06:59,080 --> 00:07:01,040
我一个进程正在执行

170
00:07:01,080 --> 00:07:02,800
它预期的执行时间很长

171
00:07:02,840 --> 00:07:04,560
我又来了一个新的进程

172
00:07:04,600 --> 00:07:05,680
它预期的执行时间

173
00:07:05,720 --> 00:07:08,600
比当前正在已经执行了一半的这个进程

174
00:07:08,640 --> 00:07:10,280
剩下那个时间还要短

175
00:07:10,320 --> 00:07:11,760
那这时候我允许它抢先

176
00:07:11,800 --> 00:07:14,480
那就是短剩余时间优先

177
00:07:14,520 --> 00:07:17,320
好 那这种算法有些什么样的特征呢

178
00:07:17,360 --> 00:07:18,160
那我们看 

179
00:07:18,200 --> 00:07:21,480
它具有一个最优平均周转时间的特征

180
00:07:21,520 --> 00:07:23,880
也就说你别的算法

181
00:07:23,920 --> 00:07:26,800
你的平均周转时间都只能比它长

182
00:07:26,840 --> 00:07:28,200
不会比它短

183
00:07:28,240 --> 00:07:30,920
那我们看 它如何得到这个特点的

184
00:07:30,960 --> 00:07:33,920
在这儿呢我们假定有一个序列

185
00:07:33,960 --> 00:07:36,840
是进程的执行时间的序列

186
00:07:36,880 --> 00:07:38,520
好 那如果说我按照

187
00:07:38,560 --> 00:07:41,400
由短到长的这个顺序来排

188
00:07:41,440 --> 00:07:42,560
它的执行顺序

189
00:07:42,600 --> 00:07:43,760
那么这时候呢

190
00:07:43,800 --> 00:07:46,240
它得到的周转时间是什么

191
00:07:46,280 --> 00:07:49,920
这个地方ri实际上是

192
00:07:49,960 --> 00:07:54,640
从0到执行完毕这个时间的长度

193
00:07:54,680 --> 00:07:56,320
好 我们说这个时间呢 

194
00:07:56,360 --> 00:07:57,920
是它的最短时间

195
00:07:57,960 --> 00:07:59,120
那我调整一下顺序

196
00:07:59,160 --> 00:08:00,760
是不是只会比它长吗

197
00:08:00,800 --> 00:08:02,120
那实际上这是可以证明的

198
00:08:02,160 --> 00:08:04,080
那我们看一下

199
00:08:04,120 --> 00:08:06,120
假定 我调整

200
00:08:06,160 --> 00:08:07,680
这时候不管你做什么样的调整

201
00:08:07,720 --> 00:08:11,240
都可以转换成一系列的基本调整

202
00:08:11,280 --> 00:08:13,520
我只要保证每一次调整

203
00:08:13,560 --> 00:08:15,520
它的时间你只会变长 不会变短

204
00:08:15,560 --> 00:08:17,960
那么你总的时间就不会比我这个还短

205
00:08:18,000 --> 00:08:20,080
那每一个最基本的调整是什么呢

206
00:08:20,120 --> 00:08:21,880
实际上我是把两个对掉

207
00:08:21,920 --> 00:08:26,520
那在这儿呢我把3 4 5倒了一下

208
00:08:26,560 --> 00:08:28,560
那在这里头呢

209
00:08:28,600 --> 00:08:30,920
2 前面两个还是跟原来一样

210
00:08:30,960 --> 00:08:33,360
现在不是执行3了 而是执行4

211
00:08:33,400 --> 00:08:35,800
那4呢 我倒了一遍之后

212
00:08:35,840 --> 00:08:37,720
这时候它的完成时间是什么

213
00:08:37,760 --> 00:08:40,120
是从这个点减去它的长度

214
00:08:40,160 --> 00:08:41,560
我给了这个表示

215
00:08:41,600 --> 00:08:44,520
然后5呢实际上是从这个地方

216
00:08:44,560 --> 00:08:48,760
5减去3 也就相当于它串到后面来

217
00:08:48,800 --> 00:08:50,200
把它俩往前串了

218
00:08:50,240 --> 00:08:52,080
然后这个P3执行结束呢

219
00:08:52,120 --> 00:08:53,760
本来就是一个r5

220
00:08:53,800 --> 00:08:55,360
为了后边我说起来方便

221
00:08:55,400 --> 00:08:58,400
我把它表示成r3在这个时间

222
00:08:58,440 --> 00:09:00,880
加上这两个的长度

223
00:09:00,920 --> 00:09:03,920
这里C3 C4 C5

224
00:09:03,960 --> 00:09:07,480
都是进程Pi的执行时间。

225
00:09:07,520 --> 00:09:08,840
好 有了这个之后

226
00:09:08,880 --> 00:09:12,440
我们继续来算它的平均周转时间

227
00:09:12,480 --> 00:09:14,520
这是把它全加在一起

228
00:09:14,560 --> 00:09:17,560
然后我做一个等式变换

229
00:09:17,600 --> 00:09:20,840
好 这时候呢把最后变的这一段加到这儿

230
00:09:20,880 --> 00:09:22,960
那我们看到

231
00:09:23,000 --> 00:09:24,280
由于我们这一个

232
00:09:24,320 --> 00:09:26,240
是按照由小到大排的

233
00:09:26,280 --> 00:09:31,520
所以这里的C3一定是小于C4 C5

234
00:09:31,560 --> 00:09:36,040
所以这个数 肯定是一个非负的数

235
00:09:36,080 --> 00:09:38,040
也就说 是0或者是一个正数

236
00:09:38,080 --> 00:09:39,080
那么这样一来的话

237
00:09:39,120 --> 00:09:41,320
你这个下面这个周转时间

238
00:09:41,360 --> 00:09:43,520
一定是比上面这个大的

239
00:09:43,560 --> 00:09:45,040
好 那从这个角度来讲呢

240
00:09:45,080 --> 00:09:46,880
我们看到短作业优先呢

241
00:09:46,920 --> 00:09:49,880
它可以有最优的平均周转时间

242
00:09:49,920 --> 00:09:51,640
这是它的好的特征

243
00:09:51,680 --> 00:09:54,520
但是它也会有麻烦

244
00:09:54,560 --> 00:09:55,680
它的麻烦是什么呢

245
00:09:55,720 --> 00:09:57,680
如果我一台机器里头

246
00:09:57,720 --> 00:09:59,320
就绪进程不断地产生

247
00:09:59,360 --> 00:10:01,000
不断地产生正在执行

248
00:10:01,040 --> 00:10:03,640
因为你是按照由短到长来排的

249
00:10:03,680 --> 00:10:05,880
那如果说我短的很多

250
00:10:05,920 --> 00:10:09,800
那这么长的就会一直得不到CPU的资源

251
00:10:09,840 --> 00:10:12,320
好 那这时候呢就会导致饥饿

252
00:10:12,360 --> 00:10:14,720
也就是说我有一个进程处于就绪状态

253
00:10:14,760 --> 00:10:16,880
由于它声称它的运行时间比较长

254
00:10:16,920 --> 00:10:19,520
好 所有的短的作业呢 进程呢

255
00:10:19,560 --> 00:10:21,680
都在它前面加塞了

256
00:10:21,720 --> 00:10:24,560
好 那这时候它就得不到CPU资源了

257
00:10:24,600 --> 00:10:26,000
好 那同时呢

258
00:10:26,040 --> 00:10:27,880
这时候还有一个问题

259
00:10:27,920 --> 00:10:31,560
它需要预知你的执行时间

260
00:10:31,600 --> 00:10:34,880
那我如何来估计CPU的进程

261
00:10:34,920 --> 00:10:37,280
的下一个执行时间长短呢

262
00:10:37,320 --> 00:10:40,440
那这和我们前面做

263
00:10:40,480 --> 00:10:42,720
内存的置换算法的时候

264
00:10:42,760 --> 00:10:44,280
的状态是一样的

265
00:10:44,320 --> 00:10:46,160
我们希望知道未来的情况

266
00:10:46,200 --> 00:10:48,760
但是要知道未来是很麻烦的

267
00:10:48,800 --> 00:10:51,120
好 那这时候我们用过去来预测

268
00:10:51,160 --> 00:10:52,160
那实际上在这里头

269
00:10:52,200 --> 00:10:54,280
我们的预测有这样几种办法

270
00:10:54,320 --> 00:10:57,040
第一个 我到底要执行多长时间

271
00:10:57,080 --> 00:10:59,640
我去问用户 用户你自己来说

272
00:10:59,680 --> 00:11:01,720
这时候就可能有两种情况

273
00:11:01,760 --> 00:11:03,760
一种是说用户 

274
00:11:03,800 --> 00:11:05,600
因为我想很快能运行

275
00:11:05,640 --> 00:11:08,200
我告诉你我只需要执行一秒钟

276
00:11:08,240 --> 00:11:09,960
实际上我执行了一分钟

277
00:11:10,000 --> 00:11:11,000
那这时候怎么办呢

278
00:11:11,040 --> 00:11:12,760
那说对于操作系统来讲

279
00:11:12,800 --> 00:11:14,440
你声称你执行多长时间

280
00:11:14,480 --> 00:11:16,040
那你就排到相应队列里头

281
00:11:16,080 --> 00:11:17,880
好 那就把你声称时间到了之后

282
00:11:17,920 --> 00:11:18,760
你还没执行完

283
00:11:18,800 --> 00:11:21,400
系统可以把你强行终止掉

284
00:11:21,440 --> 00:11:22,840
那还有一种情况

285
00:11:22,880 --> 00:11:25,320
用户干脆我不知道我会执行多长时间

286
00:11:25,360 --> 00:11:27,080
因为它在某些情况下

287
00:11:27,120 --> 00:11:28,240
它不知道数据处理

288
00:11:28,280 --> 00:11:32,040
到底要什么样的复杂程度

289
00:11:32,080 --> 00:11:33,400
好 这种情况怎么办

290
00:11:33,440 --> 00:11:36,880
这时候我们还是有另一种做法

291
00:11:36,920 --> 00:11:39,760
就是用过去预测未来

292
00:11:39,800 --> 00:11:43,320
那这就是执行时间的预估

293
00:11:43,360 --> 00:11:44,480
那怎么来预估呢

294
00:11:44,520 --> 00:11:47,720
就是利用历史信息来预测

295
00:11:47,760 --> 00:11:49,520
预估未来的执行时间

296
00:11:49,560 --> 00:11:52,920
那具体的做法呢是这样的

297
00:11:52,960 --> 00:11:54,200
这是一个小事例

298
00:11:54,240 --> 00:11:56,880
说 我在这个程序里呢做一组循环

299
00:11:56,920 --> 00:12:00,680
读数据 数据处理 那这就相当于I/O

300
00:12:00,720 --> 00:12:04,200
然后进行CPU 执行

301
00:12:04,240 --> 00:12:05,640
那在这个过程当中

302
00:12:05,680 --> 00:12:07,520
我们给出这样一个公式

303
00:12:07,560 --> 00:12:10,880
说我下一次执行时间的预测

304
00:12:10,920 --> 00:12:12,160
在这里头呢

305
00:12:12,200 --> 00:12:15,200
就是这一次的执行时间

306
00:12:15,240 --> 00:12:17,000
你N次的执行时间

307
00:12:17,040 --> 00:12:19,000
前面加上一个衰减系数

308
00:12:19,040 --> 00:12:21,360
然后加上你上一次的预估值

309
00:12:21,400 --> 00:12:22,960
把它俩加在一起

310
00:12:23,000 --> 00:12:25,120
就是你下一次的预估值

311
00:12:25,160 --> 00:12:26,560
就实际上把当前时间

312
00:12:26,600 --> 00:12:29,320
和你上一次预估值做一个校正

313
00:12:29,360 --> 00:12:31,800
好 那这时候我得到一个新的预估值

314
00:12:31,840 --> 00:12:35,680
那这一种呢相当于如果我把它展开之后

315
00:12:35,720 --> 00:12:37,400
实际上就是把前面的

316
00:12:37,440 --> 00:12:40,120
每一次的执行时间做衰减

317
00:12:40,160 --> 00:12:41,920
当前最近的这一次呢

318
00:12:41,960 --> 00:12:44,160
它的影响权重是最大的

319
00:12:44,200 --> 00:12:46,760
后面呢以前的个次依次衰减

320
00:12:46,800 --> 00:12:49,760
到一定时间长度之后就可以忽略不计了

321
00:12:49,800 --> 00:12:51,400
这是在这里预测的做法

322
00:12:51,440 --> 00:12:53,280
那这种预测的做法呢

323
00:12:53,320 --> 00:12:54,760
带来的结果是说

324
00:12:54,800 --> 00:12:58,640
这是我实际的执行的过程当中

325
00:12:58,680 --> 00:13:01,200
的每一次占用CPU的时候

326
00:13:01,240 --> 00:13:04,080
进入等待状态之前它的执行时间

327
00:13:04,120 --> 00:13:07,320
好 然后在这上头呢我作为一个预测

328
00:13:07,360 --> 00:13:10,360
依据我刚才的公式 就是这一条线

329
00:13:10,400 --> 00:13:11,520
那么这一条线

330
00:13:11,560 --> 00:13:13,640
和我们前面这条黄的线

331
00:13:13,680 --> 00:13:16,960
它们俩之间可以有一个比较好的拟合

332
00:13:17,000 --> 00:13:18,960
那这就是我这里用过去

333
00:13:19,000 --> 00:13:22,040
预测未来的预测的结果

334
00:13:22,080 --> 00:13:26,720
好 那这是短作业优先算法

335
00:13:26,760 --> 00:13:30,960
然后第三个算法呢是最高响应比优先

336
00:13:31,000 --> 00:13:32,080
那在前面呢

337
00:13:32,120 --> 00:13:35,720
我只是考虑到进程执行时间的因素

338
00:13:35,760 --> 00:13:37,080
那有可能刚才说

339
00:13:37,120 --> 00:13:39,000
短进程优先

340
00:13:39,040 --> 00:13:45,360
会因为长进程等的时间而出现饥饿

341
00:13:45,400 --> 00:13:48,080
那现在呢我为了避免这种情况出现

342
00:13:48,120 --> 00:13:50,080
高响应比优先 我是在这里

343
00:13:50,120 --> 00:13:53,480
按照响应比R的值来排序

344
00:13:53,520 --> 00:13:55,000
这个R怎么计算呢

345
00:13:55,040 --> 00:13:56,880
W是你的等待时间

346
00:13:56,920 --> 00:14:00,680
S是你预估的执行时间

347
00:14:00,720 --> 00:14:03,280
那在这里头呢我这个等的时间越长

348
00:14:03,320 --> 00:14:06,600
我R因为它在分子 R会越来越大

349
00:14:06,640 --> 00:14:07,680
等的时间越长

350
00:14:07,720 --> 00:14:08,800
它的优先级越高

351
00:14:08,840 --> 00:14:10,560
那这样的话在一定程度上

352
00:14:10,600 --> 00:14:12,000
就可以避免我们刚才说的

353
00:14:12,040 --> 00:14:13,400
短进程优先里头的

354
00:14:13,440 --> 00:14:17,440
长进程等待时间长的这种情况

355
00:14:17,480 --> 00:14:19,000
而导致出现饥饿

356
00:14:19,040 --> 00:14:21,120
好  那么在这种算法里头呢

357
00:14:21,160 --> 00:14:25,480
那它是基于短进程优先算法之上的改进

358
00:14:25,520 --> 00:14:28,320
那在这里头呢它不允许强占

359
00:14:28,360 --> 00:14:30,880
好 那这时候呢它关注的是

360
00:14:30,920 --> 00:14:33,120
进程的等待时间 好

361
00:14:33,160 --> 00:14:36,600
这时候呢它可以避免无限期的等待

362
00:14:36,640 --> 00:14:37,960
因为你等的时间越长

363
00:14:38,000 --> 00:14:38,840
你的优先级越高

364
00:14:38,880 --> 00:14:40,600
最终你会变成最高优先级

365
00:14:40,640 --> 00:14:43,400
所以你能得到CPU的使用权

366
00:14:43,440 --> 00:14:46,600
好 到这个地方呢我们就说清楚了

367
00:14:46,640 --> 00:14:50,880
前面三种关于就绪队列排序的算法

368
00:14:50,920 --> 00:14:53,320
它根据先后到达顺序 

369
00:14:53,360 --> 00:14:55,080
执行时间 等待时间

370
00:14:55,120 --> 00:14:57,760
这样几个指标来排序

371
00:14:57,840 --> 00:14:59,240
 

372
00:14:59,280 --> 00:14:59,320