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

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

另外,混合关键级作业调度已经被扩展到了多处理器平台.但多处理器上的混合关键级作业调度通常包括
作业的划分以及单处理器上的调度等两个部分.其中,单处理器上的调度算法是调度的基本策略,直接影响作业
在多处理器上的划分.因此,研究单处理器上的调度策略,对于主流的多处理器平台上混合关键级调度的研究,
依然具有重要的意义.
本文以混合关键级作业系统为研究对象,提出了面向混合关键级作业的动态需求边界函数,以矢量形式表
述作业在各关键级下的需求边界,充分考虑作业在运行时的实际执行对需求边界的动态影响.在动态需求边界
的基础上,提出以关键级松弛时间为主要参数的关键级切换算法.通过对需求边界的动态更新,提前对系统关键
级进行切换,从而在不影响高关键级作业运行的情况下,尽可能地为低关键级作业提供更多的执行机会,以提升
任务集的整体执行率.
本文第 1 节介绍混合关键级作业系统模型和相关的定义.第 2 节引入传统实时调度理论中的需求边界函
数,并针对混合关键级作业系统的特征,重新定义混合关键级作业的动态需求边界函数,以及基于动态需求边界
的关键级松弛时间.第 3 节提出基于动态需求边界的关键级切换算法(criticality switch based on dynamic
demand boundary,简称 CSDDB).第 4 节对 CSDDB 算法进行仿真和分析.最后,第 5 节对全文进行总结.

1 系统模型与相关定义

在混合关键级作业系统中,一个作业是一段有限的可执行的代码.在一个由 n 个互不关联的作业构成的具
有 L 个关键等级的混合关键级作业集τ={J 1 ,J 2 ,…,J n }中,每一个作业 J i 都可以表示为四元组 J i =(a i ,d i ,χ i ,C i ).其中,
• a i 是作业的到达时间,即作业从时刻 a i 开始就绪可执行.
• d i 是作业的截止期限.
• χ i (1≤χ i ≤L)是作业的自身关键等级,χ i 越大,关键等级越高.当系统关键级χ>χ i ,系统不要求作业 J i 完成.
相应地,当χ≤χ i ,J i 必须完成.
• C i 是一个矢量,表示为:C i =(C i (1),C i (2),…,C i (L)),其中,C i (k)表示作业 J i 在关键级 k 上的 WCET.C i (k)满足
以下两条性质:
(1) C i (k)随 k 单调非减,如果 k 1 ≤k 2 ,则 C i (k 1 )≤C i (k 2 ).这是因为作业的关键级代表对作业 WCET 估计
的保守程度,作业的关键级越高,WCET 的估计就越保守,对应的值越大.
(2) 当 k≥χ i 时,C i (k)=C i (χ i ).即当系统的关键级超过了作业自身的关键等级,作业的 WCET 不再随系
统关键级的增加而增加.
在一个混合关键级作业系统中,定义 c i 为作业 J i 在时间片[a i ,d i ]之内完成所使用的实际执行时间.需要说明
的是,c i 是一个与作业在运行时的实际情况相关的值,无法被提前预知,当且仅当该作业的代码已经执行完毕,作
业向系统发出完成信号时,c i 的值才能够确定.在本文的模型中,作业在自身关键级下的执行时间总是足够保守,
因此 c i ≤C i (χ i )总是成立的.
定义 1. 混合关键级作业集τ的一个实例 I 是当该作业集被调度时,每一个作业获得的实际执行时间(c 1 ,
c 2 ,…,c n )的集合.
定义 2. 在混合关键级作业系统的一个实例 I 中,作业 J i 的执行关键级是满足 c i ≤C i (k)的关键级 k 的最小值.
定义 3. 在混合关键级作业系统的实例 I 中,系统关键级χ s 是指对于所有满足χ i ≥χ s 的作业 J i ,都能在时间片
[a i ,d i ]内完成,且满足执行时间 c i ≤C i (χ s )的关键级χ s 的最小值.如果不存在这样的关键级χ s ,那么该实例是不可调
度的.
通过以上定义可知,作业的实际执行时间是与实际运行情况相关的.因此,随着实际执行情况的变化,作业
集的实例也会随之变化.因此,实例是无穷的.混合关键级作业调度的目标就是:寻找某种策略,使得作业集产生
的任意实例,都能够获得一个具有系统关键级χ s 的正确调度,且χ s 的值尽可能地小,使系统能保证更多关键级下
的作业完成.
本文中的作业都运行在可抢占单处理器上,采用经典的 EDF(earlist deadline first)算法作为基本调度策略.