嵌入式系统之实时系统调度算法

基本概念：

调度：将任务分给处理器，使得所有的任务都可以完成

达到时间：（arrival time or release time ri）可以开始执行的时间

计算时间：所需的CPU时间

DDL：一个任务需要在这个时间之前被做完

开始时间：真正开始执行的时间

结束时间：一个任务执行完的时间

延时：L = f（结束时间） - d（DDL）

超时时间（tardiness or exceeding time）E = max（0，L）

最迟开始时间：（laxity or slack time） X = d - a - C

任务i：同一活动的无限序列称之为实例或者作业，被激活的周期是Ti。最开始的实例叫做相位

feasible：一个调度可以完成它的一系列的约束

schedulable：至少存在一个算法使得它是feasible

optimal：一个算法是最优的，它的开销函数比较小

heuristic：趋向于最优但不是最优

抢占式算法：可以抢走正在执行的任务的CPU

非抢占算法：直到任务结束才可以释放CPU

静态算法：有固定的参数，和现在的序列状态无关

基本计算：

举栗子：

接下来介绍两种经典的周期任务调度算法：

RM和EDF

RM：任务在执行之前就已经赋好了优先级，并不会改变（静态优先级赋值）。本质就是一种抢占式，会被更高优先级抢占。Ti = Di

任意给定两个周期任务，若对任意的优先级赋值都是feasible，那么对于RM的每一个都是feasible。

RM模型可调度：

CPU使用率：

EDF：

动态赋予优先级

抢占式

Di <= Ti

算法描述：当前任务会被别的实例抢占如果它的deadline更早来。如果EDF都不能调度，那么别的就更不能调度。

判断条件：平均CPU使用率：

栗子如下图：

混合任务集合：

任务类型：

周期任务；非周期任务；零星任务（minimum interrival time）

后台调度（background scheduling）：

RM——Polling Server

优先级不是周期性的，是按照其任务来赋予。

可以完成其执行·的充分条件：

周期性任务可以在DDL之前完成的条件（充分非必要）：

非周期任务在DDL之前完成的条件：

EDF——Total Bandwidth Server

举个栗子：