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

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

EDF 总是调度作业集中具有最早截止期限的作业,已经被证明为单处理器上最优的作业调度方法,其可调度的
条件是系统利用率 U≤1.
2 混合关键级作业的动态需求边界

2.1 动态需求边界的定义
在传统实时调度理论中,需求边界函数(demand boundary function,简称 DBF)是测试作业集可调度性的重
要方法,主要思想是:通过计算作业在一段时间内的最大需求(需求边界),来判断该作业在其时限前是否可以获
得足够多的执行时间.在传统实时调度理论中,作业的需求边界由两个部分组成:(1) 作业在时间片内可能需要
的最长执行时间,即作业的 WCET;(2) 其他所有可能阻塞该作业执行的作业的执行时间.显然,如果在一段时间
片内,作业的需求边界小于该时间片的长度,那么该作业是可调度的.
但在混合关键级中,由于以下原因,需求边界函数无法直接应用.
(1) 模型的改变.传统实时作业模型中,作业的 WCET 是一个数值,表示作业的执行时间的最大可能值.但
混合关键级作业的 WCET 是与关键等级相关的矢量,在不同关键级下有不同的 WCET.因此,在考虑混
合关键级作业的需求边界时,必须考虑到关键等级的影响.
(2) 关键级阻塞.在混合关键级作业系统中,作业除了被具有更高优先级的作业阻塞之外,还可能被具有
更高关键等级的作业阻塞,以保证高关键级作业的优先完成.因此,相对于传统实时系统中的需求边
界,混合关键级作业的阻塞情况更为复杂.
(3) 关键级切换.在混合关键级系统中,当系统关键级出现切换,调度的目标随之变化.典型的一种情况是:
当系统关键级升高,系统可能丢弃所有低关键级作业,使待调度的作业集发生变化.特别地,关键级的
切换总是发生在运行时,这使得混合关键级作业的需求边界具有了动态的特性.
因此,本文考虑混合关键级系统的特性,构建了适用于混合关键级作业系统的动态需求边界函数(dynamic
demand boundary function,简称 DDBF).DDBF 在传统需求边界的基础上,首先定义了作业在不同关键级上的不
同需求边界;然后考虑了需求边界在运行时可能受到的动态影响,把 DDBF 定义为一个与系统执行情况相关的
动态值.本文定义 DDBF 如下.
定义 4. 在混合关键级作业系统中,一个作业 J i 的动态需求边界函数 ddbf χ ()t 被定义为:当系统处于关键级
i
χ(χ≤χ i )时,J i 在时刻 t 的时间需求的上界.
2.2 动态需求边界的构成
根据定义 4,混合关键级作业的动态需求边界需考虑以下几方面的内容.
χ
()
(1) 作业 J i 在给定关键级χ的执行时间 et
i
在给定的关键级χ上,在时刻 a i 之前,作业 J i 未就绪,作业所需的执行时间为 0.当作业 J i 在时刻 a i 就绪,系统
要求该作业在 d i 之前完成.根据定义 4,若作业的自身关键级χ i 满足χ i ≥χ,J i 将被分配的执行时间是其在关键级χ
χ
χ
() C=
()
下的 WCET,即 et i ( )χ ;反之,若χ i <χ,则在关键级χ下,J i 的完成并非系统保证的目标,那么 et = .因此,
0
i
i
C (), χ ⎧ χ χ≥ ∧ t ≥ a
χ
et i i i (1)
() = ⎨
i
⎩ 0, otherwise
χ
()
(2) 作业 J i 在给定关键级χ下的优先级阻塞 bt
i
本文采用 EDF 算法作为基本调度策略,截止时间早的作业具有更高的优先级.在给定关键级χ下,作业 J i 被
另一个作业 J j 阻塞的条件是:a) 作业 J j 的关键级χ j 不低于给定关键级χ,因为任何自身关键级低于χ的作业都不
会被考虑;b) 作业 J j 具有高于作业 J i 的优先级,即 d j ≤d i .满足该条件的作业 J j 最多可能阻塞作业 J i 的时长为其
在系统关键级χ下的 WCET,即 C j (χ).因此,
χ
() =
bt ∑ C j ( )χ (2)
i
: j Jd ≤ j i d ∧ j χ χ ≥