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

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

χ
()
(3) 运行时的动态影响 dt
i
*
在运行时,若某作业 J j 在时刻 t 之前执行,那么其执行关键级χ 会给作业 J i 的需求边界带来动态的影响.在
给定关键级χ上,需要考虑两种情况.
*
*
*
1) χ >χ.对于作业 J j ,当χ >χ时,C j (χ )>C j (χ).因此,对于给定关键级χ,J j 的执行消耗了更多的时间,增加值
*
为 C j (χ )−C j (χ).该部分增加的时间会使作业 J i 的需求增加,因此也应该计算到其需求边界中.
*
*
*
2) χ <χ.对于作业 J j ,当χ <χ时,C j (χ )<C j (χ).因此,对于给定关键级χ,J j 的执行事实上并未消耗在给定关键
*
级χ下的预期执行时间 C j (χ).因此,其“提前”完成降低了作业 J i 的需求,降低的时长为 C j (χ)−C j (χ ),即需
*
求上界的边界增量为 C j (χ )−C j (χ).
事实上,任何在时刻 t 之前执行的作业都可能因为关键级的变化给作业 J i 在时刻 t 的需求边界带来影响.
*
定义τ 为在时刻 t 之前执行的作业的集合,那么系统在其他关键级上的影响因子可以表述为
t
χ
dt ∑ (C j (χ * ) C− j ( ))χ (3)
( ) =
i
j J ∈ * t τ j χ ∧ χ ≥
χ
( )
这里, dt 的值总是与在时刻 t 之前执行的其他作业的执行关键级相关,只能在运行时更新.
i
(4) 到达时间的影响
最后,还需要考虑作业 J i 的到达时间 a i .当作业 J i 在时刻 a i 就绪,如果系统处于空闲状态,说明其他可能阻塞
J i 的作业都已经执行完成,J i 可以直接执行,因此,J i 在时刻 a i 的需求上界为 te+ i x ()t ;否则,系统中还有其他作业执
x
() b+
行,此时,J i 的需求上界为 et i x ()t + d i x ().t
i
综合考虑上述情况,当系统关键级为χ时,作业 J i 在时刻 t 的需求边界可以表述为
() max( b t+
x
ddbf χ () t = e t x () d t a+ x (), ) (4)
i i i i i
2.3 动态需求边界示例
为了说明混合关键级作业的需求边界函数,考虑以下例子.
例 1:给定一个具有 2 个关键级的混合关键级作业系统,见表 1.
Table 1 An example of mixed-criticality jobs system
表 1 混合关键级作业系统实例
J i a i d i χi C i (1) C i (2)
1 3 1 1 1
J 1
0 5 2 2 4
J 2
根据公式(4),可以计算出两个作业在不同关键级下的需求边界函数,如图 1 所示.
从图 1 可以看出,一个作业的需求边界是关于时间的阶梯函数.以 ddbf 2 1 ()t 为例,作业 J 2 在时刻 0 就绪,需要
2
在时间片[0,4]内被分配 1 个时间单位的执行时间,因此, ddbf 2 1 (0) = e 1 2 (0) = ;在时刻 1,作业 J 1 就绪,由于 J 1 的时
限 3 早于 J 2 的时限 5,根据 EDF 算法思想,J 1 的优先级高于 J 2 ,因此 J 1 可以阻塞 J 2 , ddbf 2 1 (1) = e 1 2 (1) b+ 1 2 (1) = 2+
C 1 (1)=3.相应地,在时刻 1,J 1 就绪,没有其他作可以阻塞其执行,但需要考虑其到达时间的影响,其需求边界为
ddbf 1 (1) = e 1 (1) max( (1)b+ 1 + d 1 (1),1) = 2.
1 1 1 1
然后,如图 2 所示,假设在时刻 3,作业 J 2 已经执行了 2 个时间单位,但未声明完成,即 J 2 发生了过载,需要系
4 2
统为其分配比 C 2 (1)更多的执行时间.此时, d 1 (3) C= (2) C− (1) =−= 2 .因此, ddbf 1 ()t 在时刻 3 发生了动态变
2 2 2 2
化,增加了 2 个单位.对于作业 J 1 ,由于 d 2 >d 1 ,J 2 的优先级低于 J 1 , ddbf 1 1 ()t 的值不会因为 J 2 的过载发生变化.
t
动态需求边界函数对于判断某个作业在给定关键级上的可调度性是有效的.当 ddbf i χ ()t = ,作业在时刻 t
可以获得足够的执行时间以完成,如果时刻 t∈[a i ,d i ],意味着该作业可以在时限之前获得足够的执行时间,该作
业是可调度的.在例 1 中,对于作业 J 1 , ddbf 1 1 (2) = ,这意味着如果系统关键级为 1,J 1 将在时刻 2 之前获得足够多
2
的执行时间.显然,当系统关键级为 1 时,J 1 是可调度的.对于作业 J 2 ,从图 1 可知,由于 ddbf 2 1 (3) 3= ,如果系统始终