下面我们来讨论实时和多处理机调度
实时调度呢是对时间有要求的调度算法
而多处理机调度呢
是指在有多个处理机的系统里
它的调度算法
那在这里 我们只能对它
做一个简要的讨论
实时操作系统是指
它的正确性依赖于时间
和功能两方面的操作系统
也就说你操作系统实践
它不仅仅是要求功能
而且要求在指定的时间内
完成相应的功能
好 实时系统呢
它的性能指标要求呢
就是时间约束的及时性
也就相当于
我必须在约定的时间内
完成约定的工作
速度和平均性能相对来说就不重要了
那在这里头呢
它最显著的特征是什么呢
它最显著特征是在于
要求时间约束的可预测性
也就说我必须知道在什么情况下
我的这些时间约束是能够达到的
那在说调度算法之前呢
我们首先来定义一下实时任务
任务是指我要做的一件事情
比如说计算 读写文件
或者说信息传递
那对于时间的要求呢
就是它的属性
它有时间的参数 在什么时间完成
然后它要占用哪些资源
这是任务的相关属性
那这个属性
我们可以用这样一个图示来表示
首先在一个时刻发出任务请求
好 这时候呢我要来
由操作系统来做这件事情
然后呢 还有一个呢就是
操作系统的执行时间
我要来处理这个任务的时候
它需要多长时间
然后再有一个就是截止时间
截止时间呢 有准确的时刻
和从请求到截止中间这个长度
那分别是相对截止时间
和绝对截止时间
好 这是一个实时任务它的要求
然后通常情况下我们在实时系统里呢
它是处理周期性这种类似的任务
这叫周期实时任务
那对于周期实时任务呢
我们可以这样来描述
除了我在这里头有一个请求时间
截止时间和它的长度之外
那还有一个就是它的规律性的重复
那么有了这个规律性的重复之后呢
这件事情我们就会定义这样几个参数
一个是周期 它的这个间隔
第一次请求到第二次请求
然后它的执行时间
在这里呢要求是你最大的执行时间
因为中间有可能会快
如果你要想保证实时的话
你必须保证最坏的情况它能算出来
然后再有一个呢就是使用率
我这一块使用
占我整个CPU时间长度来讲
它能占多大比例
那最好是100%，
但实际上100% 很难保证它的实时性
那我多少能保证的
这是其中一个重要指标
好 然后在这种情况下
我们对满足实时要求呢
又把它按照要求的强烈程度不同
分成硬实时和软实时
硬实时是指
错过这个时间截止实现
那么这时候呢它就会有灾难性
或者非常严重的后果
所以这时候 对系统的要求是
必须验证 在最坏的情况下
能够满足这个实现的要求
而软实时呢
是指我系统通常情况下
能够满足任务的实现
如果不满足的话
系统可以降级提供服务
那这时候呢 要求系统
尽量保证满足系统任务的实现
但不是必须
好 那么我们在实时的系统上
要求系统周期性完成一系列的
周期性的任务
好 在这种情况下
我们来定义可调度性
也就相当于我的调度算法
在什么情况下
它是能够满足实现的要求
可调度表示一个实时系统
它能够满足任务的实现要求
那可调度系统呢
我们可以用这样一个图来表述
说我有三个周期性的任务
它们出现的频率
和执行时间是各不相同的
那现在的问题是
在这个系统里头
执行这样三类周期性的任务
它可调度吗
它可以满足这个实现的要求吗
好 那如何来判断这个呢
我就需要确定一个任务的执行持续
如果说你能给出一个任务的执行持续
满足所有的任务对实现的要求
那么这时候呢
这个系统就是可调度的
那这样一来我在这里头
给了这个任务之后
我如何能知道
它能不能满足这个可调度性的要求呢
那这时候就是我们这里说的调度算法
那在这儿呢我们有两类
一类是静态 一类是动态
静态是指 我事先把执行顺序排出来
然后你就照这个调度就行了
我可以从理论上保证
我一定能够满足你的要求
另一种呢动态
动态呢我没有办法事先给出你来
那这时候执行的过程当中我来给
那这时候呢 执行的过程当中
我也需要保证
我最后能不能达到它的要求
好 那对这两个算法呢
我们做一个简要的介绍
一个呢是静态的调度算法
那叫做速率单调调度算法
它的做法是什么呢
它根据你这个任务的周期
来安排它的优先级
频率越高 周期越短的
优先级越高
然后调度的时候呢是
周期越短的先执行
周期越长的后执行
那你说这个调度算法好像很简单
实际上它麻烦的地方在哪呢
麻烦的地方在于
我这个系统里到底
执行多少任务的时候 它是可调度的
好 那实际上呢我们在这里呢
你有相关的文献可以证明
你在一定的使用率的情况下
速率单调调度算法
是可以满足可调度性要求的
好 相关的证明呢
大家可以下去之后看相关的文献
第二种呢是动态调度算法
那这里是最早截止时间优先
那它的思路呢也很简单
告诉你说 我截止时间越早的
我优先级越高
那后面已经请求的这几个任务
到底哪一个的截止时间最早
那我先执行最早的
好 然后呢执行
截止时间最早的任务
那这个算法就清楚了
好 那这时候也有同样的问题
我在什么样的情况下
我有多少个周期性任务的时候
动态调度算法是可调度的
那这些问题呢我都只能是在这里提出
详细的内容
希望有兴趣的同学
下去之后阅读相关的文献
多处理机调度是指
在有多个处理器的系统当中
它的调度算法
那多处理器调度呢
它的特征有这样几条
首先第一个 它是针对
多个处理机组成的系统
然后在这上头呢
一条系统总线上连了多个物理的CPU
每个CPU里 可能有多个逻辑的核
然后在这里头
我们来做它的调度算法
那这个调度算法
可以在各个处理器之间呢
实现负载共享
好 那么我们现在
用的最多的一类系统呢
是对称多处理机系统
在对称多处理机系统上的调度算法呢
通常有这样一些特点
一个是说每个处理机
有自己的调度程序
各自进行调度
然后它们之间
访问共享的资源的时候需要同步
实际上对于多处理机调度来说
同步是其中很大的一个问题
多处理机调度算法
其中很重要一个问题就是进程分配
我们把一个进程
到底放到哪个处理机上运行
那在这里呢分配的办法有两类
一类叫做静态进程分配
那么这时候呢
进程是从一开始执行
就把它分配到一个固定的CPU上运行
一直到它结束
在这儿中间呢它不会切换
好 对于这种情况呢
每个处理机呢有自己的队列
也就相当于我在起头的时候有一个分配
然后就变成是一个单处理机的
系统上的调度算法了
好 这时候呢相对来说它的开销比较小
因为每一个进程在调度的时候呢
只需要管自己一个CPU
而且进程分配给它之后
它也不会再变了
好 那这时候呢可能出现的问题是
各个处理机它的繁忙程度会不均衡
有可能你分配到某个处理机上
里头的任务负载比较重
那它就会很繁忙
而在另外一个处理机上
它的负载比较轻
那这时候呢它就可能很空闲
好 那你说这种做法不是很好
那还有一类呢就是动态分配
那么进程并不一定
在某一个处理机上
从头到尾一直在上面执行
那它可以在中间的时候呢进行切换
到任意的空闲处理机上运行
这种做法呢
它要求各个处理机共享一个就绪队列
那这样的话
以便于我能从一个切到另一个
这就变成各个处理器共享的资源了
在这种情况下
你对它的访问就是需要进行同步了
好 那样一来的话
调度的开销就比较大
因为我每一次选择的时候
我都要去指定它到底在哪个处理机上
这时候呢它的好处是
我可以实现负载的均衡
所以在我们实际系统当中呢
这两种做法呢都是有采用的
好 这是我们对多处理机调度的
一个简要的介绍