Page 348 - 《软件学报》2020年第11期

曾理宁 等:一种基于动态需求边界的混合关键级作业调度算法 3663

χ
χ
需要说明的是,作业的松弛时间 s 和系统的松弛时间 S 都是动态的,都会根据系统关键级的变化而更新.
i
1
以例 1 中的作业集为例,在时刻 3 之前, ddbf 1 1 (2) = ,因此 t = 2,s = 1 1 d − 1 t = 1 1 1,s = 1 2 d − 2 t = 1 2 2 ,故 S = 1 min( , ) 1s s = 1 1 1 2 .
2
1
相应地, S = 2 s = 2 2 1.此时,无论系统关键级是 1 或 2,在保证系统正确的前提下,都还有 1 个时间单位的冗余时间.
在时刻 3,作业 J 2 过载,使作业的边界和松弛时间都发生动态了变化.作业 J 1 由于具有更高的优先级,不会因 J 2
的过载而改变其需求边界与松弛时间.但对于作业 J 2 ,在关键级 1 下, ddbf 2 2 (5) 5,t= 1 2 = 5,s = 1 2 d − 2 t = 1 2 0 ,因此
S = 1 min( , )s s = 1 1 1 2 0 ,这意味着在时刻 3,如果系统按照关键级 1 执行,系统可以保持正确,但没有冗余时间;在关键
2
级 2,由于作业 J 2 的执行并未超过其在关键级 2 下的 WCET,因此 S =1 保持不变,如果系统按照关键级 2 执行,
系统保持正确的前提下还有 1 个时间单位的冗余.
系统在各关键级下的松弛时间,表示系统能否保持正确性以及在当前时刻保持该关键级下的正确性之外
的冗余时间.在混合关键级作业系统的调度中,系统在各关键级下的松弛时间可以作为调度的重要参数.

3 基于动态需求的关键级切换算法

本节根据混合关键级作业系统中作业在给定关键级下的动态需求边界以及松弛时间的定义,提出了一种
新的混合关键级作业调度算法:基于动态需求边界的关键级切换算法(criticality switch based on dynamic
demand boundary,简称 CSDDB).对于一个给定的混合关键级作业集τ,CSDDB 的处理方式是:在实时更新的作业
动态需求边界及其对应的关键级松弛时间的基础上,总是在所有不小于 0 的关键级松弛时间中,选择最小值所
对应的关键级作为系统的执行关键级;如果出现多个关键级松弛时间同时最小的情况,选择其中最高的关键级
作为系统的执行关键级.在运行的过程中,按照 EDF 的策略调度.

3.1 算法描述
首先定义系统的执行关键级χ s .在 CSDDB 中,选择χ s 作为系统的执行关键级,意味着在接下来的时间片中,
系统仅仅调度作业集中满足χ i ≥χ s 的作业.χ s 的选择基于各关键级的松弛时间.显然,当某个作业集上的松弛时
χ
χ
间 S <0,那么系统运行于该关键级上是不可调度的;反之,当 S ≥0,松弛时间越短就意味着该关键级上的容错能
力越低,因此应该提前执行.值得注意的是,系统的事件如作业到达、作业完成、作业超载等,都可能引起各作业
的动态需求边界的变化,进而造成各关键级的松弛时间变化,影响到系统执行关键级的选择.因此,设计 CSDDB
算法如算法 1 所示.
算法 1. 基于动态需求边界的关键级切换算法(CSDDB).
输入:作业集τ.
输出:τ的一个调度.
χ
1. 对所有的作业 J 以及所有的关键级χ,计算 ddbf i χ ()t 以及松弛时间 s ;
i
χ
2. 对所有的关键级χ,计算关键级松弛时间 S ;
3. 系统关键级初始化:χ s =0;
4. FOR t=0 to t=max(d i ) do
i χ
5. χ s χ = : S ≥ 0 ∧ min(S i χ ) ;
6. IF (χ s ==0) return False;
7. J e =J i :t∈[a i ,d i ]∧min(d i );
8. execute(J e );
9. EventHandle(⋅);
10. t++;
11. END FOR;
如算法 1 所示,CSDDB 的算法分为静态部分与运行时部分.其中,静态部分为伪代码的第 1 行~第 3 行.对于