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


1
00:00:07,920 --> 00:00:12,920
下面我们来讨论实时和多处理机调度

2
00:00:12,960 --> 00:00:17,480
实时调度呢是对时间有要求的调度算法

3
00:00:17,520 --> 00:00:19,120
而多处理机调度呢

4
00:00:19,160 --> 00:00:24,200
是指在有多个处理机的系统里

5
00:00:24,240 --> 00:00:25,600
它的调度算法

6
00:00:25,640 --> 00:00:27,400
那在这里 我们只能对它

7
00:00:27,440 --> 00:00:30,000
做一个简要的讨论

8
00:00:30,040 --> 00:00:32,480
实时操作系统是指

9
00:00:32,520 --> 00:00:34,760
它的正确性依赖于时间

10
00:00:34,800 --> 00:00:37,360
和功能两方面的操作系统

11
00:00:37,400 --> 00:00:39,160
也就说你操作系统实践

12
00:00:39,200 --> 00:00:40,360
它不仅仅是要求功能

13
00:00:40,400 --> 00:00:42,880
而且要求在指定的时间内

14
00:00:42,920 --> 00:00:46,040
完成相应的功能

15
00:00:46,080 --> 00:00:47,320
好 实时系统呢

16
00:00:47,360 --> 00:00:49,480
它的性能指标要求呢

17
00:00:49,520 --> 00:00:51,560
就是时间约束的及时性

18
00:00:51,600 --> 00:00:52,240
也就相当于 

19
00:00:52,280 --> 00:00:54,400
我必须在约定的时间内

20
00:00:54,440 --> 00:00:56,280
完成约定的工作

21
00:00:56,320 --> 00:00:59,040
速度和平均性能相对来说就不重要了

22
00:00:59,080 --> 00:01:00,000
那在这里头呢

23
00:01:00,040 --> 00:01:01,760
它最显著的特征是什么呢

24
00:01:01,800 --> 00:01:03,520
它最显著特征是在于

25
00:01:03,560 --> 00:01:06,280
要求时间约束的可预测性

26
00:01:06,320 --> 00:01:08,720
也就说我必须知道在什么情况下

27
00:01:08,760 --> 00:01:11,680
我的这些时间约束是能够达到的

28
00:01:11,720 --> 00:01:13,800
那在说调度算法之前呢

29
00:01:13,840 --> 00:01:17,400
我们首先来定义一下实时任务

30
00:01:17,440 --> 00:01:19,640
任务是指我要做的一件事情

31
00:01:19,680 --> 00:01:22,040
比如说计算 读写文件

32
00:01:22,080 --> 00:01:25,080
或者说信息传递

33
00:01:25,120 --> 00:01:27,040
那对于时间的要求呢

34
00:01:27,080 --> 00:01:28,240
就是它的属性

35
00:01:28,280 --> 00:01:32,280
它有时间的参数 在什么时间完成

36
00:01:32,320 --> 00:01:34,040
然后它要占用哪些资源

37
00:01:34,080 --> 00:01:36,120
这是任务的相关属性

38
00:01:36,160 --> 00:01:36,920
那这个属性

39
00:01:36,960 --> 00:01:40,160
我们可以用这样一个图示来表示

40
00:01:40,200 --> 00:01:44,200
首先在一个时刻发出任务请求

41
00:01:44,240 --> 00:01:45,720
好 这时候呢我要来

42
00:01:45,760 --> 00:01:48,000
由操作系统来做这件事情

43
00:01:48,040 --> 00:01:49,920
然后呢 还有一个呢就是

44
00:01:49,960 --> 00:01:51,800
操作系统的执行时间

45
00:01:51,840 --> 00:01:53,480
我要来处理这个任务的时候

46
00:01:53,520 --> 00:01:54,920
它需要多长时间

47
00:01:54,960 --> 00:01:57,320
然后再有一个就是截止时间

48
00:01:57,360 --> 00:01:59,280
截止时间呢 有准确的时刻

49
00:01:59,320 --> 00:02:02,640
和从请求到截止中间这个长度

50
00:02:02,680 --> 00:02:04,520
那分别是相对截止时间

51
00:02:04,560 --> 00:02:07,040
和绝对截止时间

52
00:02:07,080 --> 00:02:11,160
好 这是一个实时任务它的要求

53
00:02:11,200 --> 00:02:13,640
然后通常情况下我们在实时系统里呢

54
00:02:13,680 --> 00:02:16,480
它是处理周期性这种类似的任务

55
00:02:16,520 --> 00:02:18,800
这叫周期实时任务

56
00:02:18,840 --> 00:02:20,680
那对于周期实时任务呢

57
00:02:20,720 --> 00:02:22,160
我们可以这样来描述

58
00:02:22,200 --> 00:02:25,720
除了我在这里头有一个请求时间

59
00:02:25,760 --> 00:02:28,000
截止时间和它的长度之外

60
00:02:28,040 --> 00:02:31,880
那还有一个就是它的规律性的重复

61
00:02:31,920 --> 00:02:34,000
那么有了这个规律性的重复之后呢

62
00:02:34,040 --> 00:02:36,680
这件事情我们就会定义这样几个参数

63
00:02:36,720 --> 00:02:39,200
一个是周期 它的这个间隔

64
00:02:39,240 --> 00:02:41,600
第一次请求到第二次请求

65
00:02:41,640 --> 00:02:44,120
然后它的执行时间

66
00:02:44,160 --> 00:02:47,440
在这里呢要求是你最大的执行时间

67
00:02:47,480 --> 00:02:49,920
因为中间有可能会快

68
00:02:49,960 --> 00:02:51,000
如果你要想保证实时的话

69
00:02:51,040 --> 00:02:53,600
你必须保证最坏的情况它能算出来

70
00:02:53,640 --> 00:02:56,520
然后再有一个呢就是使用率

71
00:02:56,560 --> 00:02:57,480
我这一块使用

72
00:02:57,520 --> 00:03:00,480
占我整个CPU时间长度来讲

73
00:03:00,520 --> 00:03:01,880
它能占多大比例

74
00:03:01,920 --> 00:03:03,360
那最好是100%，

75
00:03:03,400 --> 00:03:06,800
但实际上100% 很难保证它的实时性

76
00:03:06,840 --> 00:03:08,640
那我多少能保证的

77
00:03:08,680 --> 00:03:12,760
这是其中一个重要指标

78
00:03:12,800 --> 00:03:14,440
好 然后在这种情况下

79
00:03:14,480 --> 00:03:16,680
我们对满足实时要求呢

80
00:03:16,720 --> 00:03:20,000
又把它按照要求的强烈程度不同

81
00:03:20,040 --> 00:03:22,960
分成硬实时和软实时

82
00:03:23,000 --> 00:03:24,640
硬实时是指 

83
00:03:24,680 --> 00:03:26,920
错过这个时间截止实现

84
00:03:26,960 --> 00:03:28,840
那么这时候呢它就会有灾难性

85
00:03:28,880 --> 00:03:30,400
或者非常严重的后果

86
00:03:30,440 --> 00:03:32,960
所以这时候 对系统的要求是

87
00:03:33,000 --> 00:03:35,600
必须验证 在最坏的情况下

88
00:03:35,640 --> 00:03:38,480
能够满足这个实现的要求

89
00:03:38,520 --> 00:03:40,040
而软实时呢 

90
00:03:40,080 --> 00:03:42,360
是指我系统通常情况下

91
00:03:42,400 --> 00:03:44,280
能够满足任务的实现

92
00:03:44,320 --> 00:03:45,240
如果不满足的话

93
00:03:45,280 --> 00:03:48,040
系统可以降级提供服务

94
00:03:48,080 --> 00:03:49,800
那这时候呢 要求系统

95
00:03:49,840 --> 00:03:54,160
尽量保证满足系统任务的实现

96
00:03:54,200 --> 00:03:56,880
但不是必须

97
00:03:56,920 --> 00:04:00,560
好 那么我们在实时的系统上

98
00:04:00,600 --> 00:04:04,000
要求系统周期性完成一系列的

99
00:04:04,040 --> 00:04:05,440
周期性的任务

100
00:04:05,480 --> 00:04:06,720
好 在这种情况下

101
00:04:06,760 --> 00:04:08,680
我们来定义可调度性

102
00:04:08,720 --> 00:04:10,240
也就相当于我的调度算法

103
00:04:10,280 --> 00:04:11,160
在什么情况下

104
00:04:11,200 --> 00:04:13,080
它是能够满足实现的要求

105
00:04:13,120 --> 00:04:16,160
可调度表示一个实时系统

106
00:04:16,200 --> 00:04:20,120
它能够满足任务的实现要求

107
00:04:20,160 --> 00:04:21,400
那可调度系统呢

108
00:04:21,440 --> 00:04:23,320
我们可以用这样一个图来表述

109
00:04:23,360 --> 00:04:28,280
说我有三个周期性的任务

110
00:04:28,320 --> 00:04:30,600
它们出现的频率

111
00:04:30,640 --> 00:04:34,000
和执行时间是各不相同的

112
00:04:34,040 --> 00:04:35,560
那现在的问题是

113
00:04:35,600 --> 00:04:37,200
在这个系统里头

114
00:04:37,240 --> 00:04:39,240
执行这样三类周期性的任务

115
00:04:39,280 --> 00:04:40,960
它可调度吗

116
00:04:41,000 --> 00:04:43,280
它可以满足这个实现的要求吗

117
00:04:43,320 --> 00:04:46,000
好 那如何来判断这个呢

118
00:04:46,040 --> 00:04:48,760
我就需要确定一个任务的执行持续

119
00:04:48,800 --> 00:04:53,360
如果说你能给出一个任务的执行持续

120
00:04:53,400 --> 00:04:56,720
满足所有的任务对实现的要求

121
00:04:56,760 --> 00:04:57,840
那么这时候呢

122
00:04:57,880 --> 00:04:59,720
这个系统就是可调度的

123
00:04:59,760 --> 00:05:01,400
那这样一来我在这里头

124
00:05:01,440 --> 00:05:02,360
给了这个任务之后

125
00:05:02,400 --> 00:05:03,440
我如何能知道

126
00:05:03,480 --> 00:05:06,760
它能不能满足这个可调度性的要求呢

127
00:05:06,800 --> 00:05:09,320
那这时候就是我们这里说的调度算法

128
00:05:09,360 --> 00:05:11,280
那在这儿呢我们有两类

129
00:05:11,320 --> 00:05:13,200
一类是静态 一类是动态

130
00:05:13,240 --> 00:05:18,480
静态是指 我事先把执行顺序排出来

131
00:05:18,520 --> 00:05:20,800
然后你就照这个调度就行了

132
00:05:20,840 --> 00:05:22,760
我可以从理论上保证

133
00:05:22,800 --> 00:05:25,200
我一定能够满足你的要求

134
00:05:25,240 --> 00:05:27,640
另一种呢动态

135
00:05:27,680 --> 00:05:30,480
动态呢我没有办法事先给出你来

136
00:05:30,520 --> 00:05:32,640
那这时候执行的过程当中我来给

137
00:05:32,680 --> 00:05:34,680
那这时候呢 执行的过程当中

138
00:05:34,720 --> 00:05:35,760
我也需要保证

139
00:05:35,800 --> 00:05:38,240
我最后能不能达到它的要求

140
00:05:38,280 --> 00:05:40,160
好 那对这两个算法呢

141
00:05:40,200 --> 00:05:42,400
我们做一个简要的介绍

142
00:05:42,440 --> 00:05:46,640
一个呢是静态的调度算法

143
00:05:46,680 --> 00:05:49,880
那叫做速率单调调度算法

144
00:05:49,920 --> 00:05:51,120
它的做法是什么呢

145
00:05:51,160 --> 00:05:53,600
它根据你这个任务的周期

146
00:05:53,640 --> 00:05:55,360
来安排它的优先级

147
00:05:55,400 --> 00:05:58,080
频率越高 周期越短的 

148
00:05:58,120 --> 00:05:59,520
优先级越高

149
00:05:59,560 --> 00:06:00,920
然后调度的时候呢是

150
00:06:00,960 --> 00:06:03,480
周期越短的先执行

151
00:06:03,520 --> 00:06:05,680
周期越长的后执行

152
00:06:05,720 --> 00:06:08,560
那你说这个调度算法好像很简单

153
00:06:08,600 --> 00:06:10,760
实际上它麻烦的地方在哪呢

154
00:06:10,800 --> 00:06:12,040
麻烦的地方在于

155
00:06:12,080 --> 00:06:14,320
我这个系统里到底

156
00:06:14,360 --> 00:06:17,800
执行多少任务的时候 它是可调度的

157
00:06:17,840 --> 00:06:20,200
好 那实际上呢我们在这里呢

158
00:06:20,240 --> 00:06:22,800
你有相关的文献可以证明

159
00:06:22,840 --> 00:06:25,880
你在一定的使用率的情况下

160
00:06:25,920 --> 00:06:27,520
速率单调调度算法

161
00:06:27,560 --> 00:06:32,000
是可以满足可调度性要求的

162
00:06:32,040 --> 00:06:33,120
好 相关的证明呢

163
00:06:33,160 --> 00:06:35,600
大家可以下去之后看相关的文献

164
00:06:35,640 --> 00:06:39,360
第二种呢是动态调度算法

165
00:06:39,400 --> 00:06:42,360
那这里是最早截止时间优先

166
00:06:42,400 --> 00:06:44,600
那它的思路呢也很简单

167
00:06:44,640 --> 00:06:47,520
告诉你说 我截止时间越早的

168
00:06:47,560 --> 00:06:48,840
我优先级越高

169
00:06:48,880 --> 00:06:52,120
那后面已经请求的这几个任务

170
00:06:52,160 --> 00:06:53,920
到底哪一个的截止时间最早

171
00:06:53,960 --> 00:06:55,800
那我先执行最早的

172
00:06:55,840 --> 00:06:57,280
好 然后呢执行

173
00:06:57,320 --> 00:06:58,840
截止时间最早的任务

174
00:06:58,880 --> 00:07:00,240
那这个算法就清楚了

175
00:07:00,280 --> 00:07:02,120
好 那这时候也有同样的问题

176
00:07:02,160 --> 00:07:05,800
我在什么样的情况下

177
00:07:05,840 --> 00:07:07,960
我有多少个周期性任务的时候

178
00:07:08,000 --> 00:07:10,960
动态调度算法是可调度的

179
00:07:11,000 --> 00:07:14,040
那这些问题呢我都只能是在这里提出

180
00:07:14,080 --> 00:07:14,960
详细的内容

181
00:07:15,000 --> 00:07:16,800
希望有兴趣的同学

182
00:07:16,840 --> 00:07:21,680
下去之后阅读相关的文献

183
00:07:21,720 --> 00:07:23,520
多处理机调度是指

184
00:07:23,560 --> 00:07:27,640
在有多个处理器的系统当中

185
00:07:27,680 --> 00:07:28,920
它的调度算法

186
00:07:28,960 --> 00:07:30,760
那多处理器调度呢

187
00:07:30,800 --> 00:07:32,760
它的特征有这样几条

188
00:07:32,800 --> 00:07:34,080
首先第一个 它是针对

189
00:07:34,120 --> 00:07:37,400
多个处理机组成的系统

190
00:07:37,440 --> 00:07:39,000
然后在这上头呢

191
00:07:39,040 --> 00:07:42,480
一条系统总线上连了多个物理的CPU

192
00:07:42,520 --> 00:07:46,200
每个CPU里 可能有多个逻辑的核

193
00:07:46,240 --> 00:07:47,280
然后在这里头

194
00:07:47,320 --> 00:07:49,800
我们来做它的调度算法

195
00:07:49,840 --> 00:07:51,200
那这个调度算法 

196
00:07:51,240 --> 00:07:53,120
可以在各个处理器之间呢

197
00:07:53,160 --> 00:07:55,280
实现负载共享

198
00:07:55,320 --> 00:07:56,680
好 那么我们现在

199
00:07:56,720 --> 00:07:58,320
用的最多的一类系统呢

200
00:07:58,360 --> 00:08:00,840
是对称多处理机系统

201
00:08:00,880 --> 00:08:03,320
在对称多处理机系统上的调度算法呢

202
00:08:03,360 --> 00:08:05,440
通常有这样一些特点

203
00:08:05,480 --> 00:08:06,960
一个是说每个处理机

204
00:08:07,000 --> 00:08:08,880
有自己的调度程序

205
00:08:08,920 --> 00:08:10,240
各自进行调度

206
00:08:10,280 --> 00:08:11,640
然后它们之间

207
00:08:11,680 --> 00:08:14,920
访问共享的资源的时候需要同步

208
00:08:14,960 --> 00:08:17,200
实际上对于多处理机调度来说

209
00:08:17,240 --> 00:08:21,960
同步是其中很大的一个问题

210
00:08:22,000 --> 00:08:23,280
多处理机调度算法

211
00:08:23,320 --> 00:08:26,400
其中很重要一个问题就是进程分配

212
00:08:26,440 --> 00:08:28,280
我们把一个进程

213
00:08:28,320 --> 00:08:31,600
到底放到哪个处理机上运行

214
00:08:31,640 --> 00:08:33,720
那在这里呢分配的办法有两类

215
00:08:33,760 --> 00:08:36,760
一类叫做静态进程分配

216
00:08:36,800 --> 00:08:38,040
那么这时候呢 

217
00:08:38,080 --> 00:08:39,920
进程是从一开始执行

218
00:08:39,960 --> 00:08:43,160
就把它分配到一个固定的CPU上运行

219
00:08:43,200 --> 00:08:44,360
一直到它结束

220
00:08:44,400 --> 00:08:46,480
在这儿中间呢它不会切换

221
00:08:46,520 --> 00:08:47,960
好 对于这种情况呢

222
00:08:48,000 --> 00:08:50,160
每个处理机呢有自己的队列

223
00:08:50,200 --> 00:08:53,960
也就相当于我在起头的时候有一个分配

224
00:08:54,000 --> 00:08:56,400
然后就变成是一个单处理机的

225
00:08:56,440 --> 00:08:58,040
系统上的调度算法了

226
00:08:58,080 --> 00:09:00,960
好 这时候呢相对来说它的开销比较小

227
00:09:01,000 --> 00:09:03,520
因为每一个进程在调度的时候呢

228
00:09:03,560 --> 00:09:05,480
只需要管自己一个CPU

229
00:09:05,520 --> 00:09:06,920
而且进程分配给它之后

230
00:09:06,960 --> 00:09:08,080
它也不会再变了

231
00:09:08,120 --> 00:09:10,760
好 那这时候呢可能出现的问题是

232
00:09:10,800 --> 00:09:14,960
各个处理机它的繁忙程度会不均衡

233
00:09:15,000 --> 00:09:17,000
有可能你分配到某个处理机上

234
00:09:17,040 --> 00:09:19,000
里头的任务负载比较重

235
00:09:19,040 --> 00:09:20,880
那它就会很繁忙

236
00:09:20,920 --> 00:09:22,520
而在另外一个处理机上

237
00:09:22,560 --> 00:09:24,080
它的负载比较轻

238
00:09:24,120 --> 00:09:26,560
那这时候呢它就可能很空闲

239
00:09:26,600 --> 00:09:28,800
好 那你说这种做法不是很好

240
00:09:28,840 --> 00:09:32,920
那还有一类呢就是动态分配

241
00:09:32,960 --> 00:09:34,480
那么进程并不一定

242
00:09:34,520 --> 00:09:36,040
在某一个处理机上

243
00:09:36,080 --> 00:09:38,400
从头到尾一直在上面执行

244
00:09:38,440 --> 00:09:42,000
那它可以在中间的时候呢进行切换

245
00:09:42,040 --> 00:09:45,360
到任意的空闲处理机上运行

246
00:09:45,400 --> 00:09:46,400
这种做法呢

247
00:09:46,440 --> 00:09:51,080
它要求各个处理机共享一个就绪队列

248
00:09:51,120 --> 00:09:51,800
那这样的话

249
00:09:51,840 --> 00:09:54,280
以便于我能从一个切到另一个

250
00:09:54,320 --> 00:09:56,600
这就变成各个处理器共享的资源了

251
00:09:56,640 --> 00:09:57,680
在这种情况下

252
00:09:57,720 --> 00:10:00,320
你对它的访问就是需要进行同步了

253
00:10:00,360 --> 00:10:01,480
好 那样一来的话

254
00:10:01,520 --> 00:10:03,400
调度的开销就比较大

255
00:10:03,440 --> 00:10:05,400
因为我每一次选择的时候

256
00:10:05,440 --> 00:10:08,280
我都要去指定它到底在哪个处理机上

257
00:10:08,320 --> 00:10:09,920
这时候呢它的好处是

258
00:10:09,960 --> 00:10:12,400
我可以实现负载的均衡

259
00:10:12,440 --> 00:10:14,280
所以在我们实际系统当中呢

260
00:10:14,320 --> 00:10:17,320
这两种做法呢都是有采用的

261
00:10:17,360 --> 00:10:20,800
好 这是我们对多处理机调度的

262
00:10:20,840 --> 00:10:22,840
一个简要的介绍

263
00:10:22,880 --> 00:10:22,960


264
00:10:23,000 --> 00:10:23,040