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

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

3
ddbf = 4 ,此时, S = 1 s = 1 1,S = 2 s = 2 0 ,S =1,因此,χ s =2,选择执行的作业为 J 2 .
2
2 1 2
(5) 在时刻 4,作业 J 2 完成,但由于其在执行关键级 2 上执行了一个时间单位,因此,所有在关键级 1 上的边
2
界都必须加上这一个时间单位的动态增量,因此, ddbf 1 1 (4) = 6,ddbf 3 1 (3) = 7,S = 1 s = 1 1 0 .S =0 保持不变.
但由于 J 2 的自身关键级为 2,因此其执行会影响关键级 3 上的需求边界, d 3 3 (3) 1= ,因此, ddbf 3 3 (3) = 7 ,
S = 3 s = 3 3 0 .系统关键级χ s =3,选择执行的作业为 J 3 .
(6) 在时刻 5,如果 J 3 完成,那么 J 1 得以在时刻 6 完成;如果 J 3 未能完成,即 c 3 >2,那么作业 J 1 将错过时限,
但 J 2 与 J 3 都能完成.

Table 2 An example of mixed-criticality jobs set with 3 criticalities
表 2 一个具有 3 个关键级的混合关键级作业集实例
J i a i d i χi C i (1) C i (2) C i (3)
J 1 0 6 1 3 3 3
1 4 2 1 2 2
J 2
J 3 2 7 3 2 3 4

3.3 算法复杂度分析
可以从算法的静态部分以及运行时部分来分别说明 CSDDB 算法的复杂度.给定一个具有 n 个作业和 k 个
关键级的混合关键级作业集τ.在静态部分,算法需要计算所有作业在各关键级上的动态需求边界函数.由于
ddbf χ () t 的静态部分只取决于作业本身的执行时间与该作业可能遇到的阻塞,因此,每一个边界的计算都最多
i
2
需要计算 n 个作业的执行时间,这样的计算需要 n×k 次,因此,计算需求边界函数的复杂度为 O(n k).而无论是作
业的松弛时间还是关键级的松弛时间,都只与需求边界函数相关,不会带来更高的复杂度,因此,算法静态部分
2
的复杂度是 O(n k).显然,这是多项式级别的.
在运行时,在每一个时刻都需要更新系统的状态.但从算法的描述中可知,系统中的任何一个事件,都最多
给每一个需求边界函数带来一次计算.因此,最多需要 n×k 次;同时,在任何一个时刻可能出现的事件只与作业本
2
身相关,其复杂度为 O(n),因此,运行时部分的复杂度为 O(n)×O(n×k)=O(n k),显然也是多项式级别的.
因此,CSDDB 的复杂度是多项式级别的.
值得说明的是,在实际运行时,CSDDB 算法的执行代价是可接受的,这是因为:
(1) 在实际应用中,作业的数量 n 和关键级数量 k 是受限的.由于混合关键级作业的运行平台通常以嵌入
式平台为主,受限于平台的计算资源以及作业所需计算资源越来越大的实际情况,平台可调度的作业
数量 n 是可控的,在绝大多数情况下,n≤50.此外,在现有的混合关键级的应用和标准中,关键级数量通
常满足 k∈[2,7],以航空软件认证标准 DO-178 B/C 为例,该标准把航空器中的功能按关键级划分为 A
到 E 的 5 个等级,因此,关键级的数量不会过大的影响算法运行的开销.
(2) 在 CSDDB 中,对动态需求边界函数 ddbf i χ ()t 在运行前计算,因此无需考虑其对运行时的影响.在运行
时, ddbf i χ () t 的动态部分需要根据系统运行时发生的事件(如作业到达、作业完成、作业过载等)实时
更新,这部分计算是 CSDDB 算法的主要开销.考虑在某时刻 t′,算法需要更新 ddbf i χ () t′ .需要注意的是,
此时需要更新需求边界函数的只有处于未完成状态的作业,而已完成和未到达的作业不受影响.在最
2
坏情况下,即在时刻 t′,每一个作业都处于未完成,且每一个作业在 t′触发事件,算法需要进行 n ×k 次动
2
态需求边界函数的更新.但在实际运行中,每个事件发生时需要进行的更新计算次数远小于 n ×k 的最
坏值.
(3) 由于动态需求函数是一个关于时间点和关键级的离散函数,在运行时,算法为每一个作业 J i 维护一个
二维数组 db i [t][χ],表示在时刻 t,作业 J i 在关键级χ下的动态需求边界函数值.当系统中发生事件,引起
需求边界函数的动态变化时,需要修改 db i [t][χ]的值.根据公式(4),修改的方式是为当前的值加上由于
过载、完成等事件带来的动态变化值,该计算方法并不复杂,不需要占用过多的计算资源.