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

3666 Journal of Software 软件学报 Vol.31, No.11, November 2020

综上所述,CSDDB 在运行时的开销是可以接受的.
3.4 算法的正确性分析
由于 CSBBD 总是试图在满足高关键级可调度的情况下选择最紧急(松弛时间最少)的关键级作为系统的
执行关键级,CSDDB 的运行总是满足以下定理.
定理 2. 如果一个混合关键级作业集τ在其最高关键级下是可调度的,那么该作业集在 CSDDB 下总是能够
保证其最高关键级正确.
证明:对于一个已知的混合关键级作业集τ,如果在其最高关键级下可调度,那么根据作业动态需求边界的
定义,至少在时刻 0,所有作业的松弛时间都不小于 0,因此 S χ max ≥ 0 .在运行过程中,CSDDB 总是选取关键级松
弛时间中不小于 0 的最小值对应的关键级作为系统的执行关键级,且在有多个关键级的松弛时间相同时,取最
高关键级作为执行关键级.那么在任意时刻,一旦 S χ max = 0 ,系统关键级χ max 会马上被选为执行关键级,且能够保
证即使在最坏情况下,作业集τ在最高关键级χ max 上是正确的. □
引理 1. 对于一个双关键级作业集τ,如果在其高关键级下可调度,那么τ在 CSDDB 上可获得正确的调度.
证明:根据定理 1,双关键级作业集τ在高关键级下是可调度的,也就是说,τ总能够保证高关键级的作业完成.
在保证高关键级作业完成的前提下,CSDDB 通过松弛时间选择系统的执行关键级,把系统切换至更高关键
级的时间点尽可能延后,从而为低关键级作业提供更多的执行时间.此外,即使有低关键级作业错过时限,通过
关键级松弛时间的更新,系统依然有可能选择低关键级作为系统的执行关键级,从而使低关键级作业的错误率
降低. □
我们在下一节对 CSDDB 进行仿真,并与其他已有混合关键级作业调度算法进行比较,以证明其优越性.

4 算法仿真与分析

本文将通过仿真实验来比较 CSDDB 算法与现有的其他混合关键级作业调度算法的性能.实验针对混合关
键级作业系统,运行在可抢占单处理器平台上.本文实现了文献[15]中的 Bailout Protocol 算法(BP)、经典的
OCBP 算法 [11] 以及最基本的关键级即优先级(criticality as priority,简称 CaP) [11] 算法,并将其改写成适应于混合
关键级作业系统的版本.以这些算法为参照,比较 CSDDB 算法在系统关键级与作业完成率方面的性能,从而评
价 CSDDB 的有效性.
4.1 作业集的生成
在仿真中,本文采用文献[11]中生成混合关键级任务集的方法,并将其改变为混合关键级作业集的生成方
式.考虑的参数主要包括:
(1) 作业的到达时间 a i 和时限 d i .对于一个长度为 T 的时间片,a i ∈[0,T)是在整个时间片上的随机值,
d i ∈(a i ,T]是在 a i 之后的时间片上的随机值.
(2) 作业的关键等级χ i .根据文献[10],设关键级χ i ∈[1,5]是一个随机值,且服从概率 P χ =P i+1 /P i ,即选择更高
的关键级的概率总是 P χ .
(3) 作业在自身关键级上的负载最大值 l max .作业 J i 在自身关键级上的负载 l i i χ = C i ()/(dχ i i − a i ) 是被设定
为在(0,l max ]上的随机值,从而作业在自身关键级上的 WCET 也被限定.
(4) 作业在不同关键级的 WCET 之间的比例 P e .P e 限定了作业在较低关键级上的 WCET 与较高一个关键
级的 WCET 的最大比例,即 C i (χ)/C i (χ+1)≤P e .在本文的实验中,P e 取[0.4,0.9]之间的随机数.
(5) 作业超载的概率 P χ .作业超载至更高一个关键级的概率为 P χ ,即关键级越高,作业在该关键级上运行
的概率越低.
(6) 作业集的最大负载 l s .作业集的最大负载被定义为在时间片[0,T]之内,作业在各关键级上的执行时间
⎧ ⎫ ⎪ ⎪
l
的最大值与时长的比例,即 max ⎨ C i ( )χ ⎬∑ T ≤ .在本文的实验中,l max 取值为(0.25,0.85).
s
χ∈ [1,5] ⎪ i J τ∈ ⎪ ⎩ ⎭