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

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

system. To deal with this problem, this paper expands the traditional demand boundary analysis theory to the mixed-criticality systems,
presenting the concept of dynamical demand boundary for mixed-criticality jobs, which represents the dynamical demand of jobs in
run-time as a vector. And then, based on the concept of slack time for mixed-criticality jobs and the criticality of system, the paper
presents an algorithm CSDDB (criticality switch based on dynamical demand boundary). The algorithm chooses the criticality with the
minimum slack time as the execution criticality of the system to take full advantage of system resources and to guarantee the execution of
jobs with lower criticality without affecting the schedulability of high criticality jobs. Experiments with randomly generated workload
show that CSDDB makes more than 10% of progress in guaranteeing the system criticality and the completion of jobs set compared with
the existing research.
Key words: mixed-criticality; criticality switch; real-time scheduling; demand boundary function; slack time

实时嵌入式系统的一个发展趋势,是把具有不同关键等级的功能集成到一个共享的硬件平台上.这种具有
多种关键等级的系统被称为混合关键级系统.其中,关键等级是系统为了防止功能运行失败而提供的安全保障
机制,其高低取决于功能失效时系统可能受到的后果的严重性.在混合关键级系统中,更高的关键级通常对应着
优先的系统资源,如更多的预留执行时间、更优先的计算资源分配等.目前,包括汽车电子系统、飞行器等领域
在内的多数嵌入式系统都在朝着混合关键级系统的方向发展,以满足系统在成本、空间、重量、功耗、热量等
方面的要求.
混合关键级系统中的一个基本问题是:如何在计算资源有限的前提下,保证系统中具有更高关键等级的功
能完成.显然,传统的实时调度理论由于没有考虑系统作业的关键级属性,无法解决这一问题.因此,混合关键级
系统调度开始成为一个重要的研究方向.文献[1]最先提出了一种混合关键级模型,随后被不断深入研究 [2−4] .该
模型改变了传统实时调度理论中作业的最坏执行时间(worst case execution time,简称 WCET)的描述,认为一个
作业的 WCET 并非一个固定的值,而是一个与关键等级相关的矢量,不同的关键级对应不同保守程度的 WCET
估计.其中,更高的关键等级意味着更保守的估计及更大的 WCET 值.在运行时,如果某作业的实际运行时间超
过了相应较低关键级下的 WCET,则称该作业在该关键级过载.当过载发生时,系统关键级将提升,以应对更高关
[8]
[9]
键级下的更大 WCET.在这种模型下,很多算法被提出 [5−14] .其中,典型的如 OCBP 算法 、EDF-VD 算法 以及
zero-slack 算法 [10] 等.这些算法都运用了以下基本策略.
• 系统初始化运行在最低的关键级下,若所有作业的执行都没有过载,系统始终保持在当前关键级内;
• 当且仅当系统检测到在当前关键级下有作业过载,系统切换至更高的关键级;
• 当系统运行于某关键级时,所有自身关键级低于系统关键级的作业都被丢弃;
• 系统不会主动切换到更低的关键级,直到系统空闲,系统关键级才被重新初始化为最低等级.
然而,上述的基本策略在实际应用中可能造成以下两个问题.
(1) 当系统处于高关键级时,低关键级作业总是被简单放弃.但低关键级不等于不重要,丢弃低关键级作
业会不可避免地造成系统功能的缺失和用户体验的下降.
(2) 系统关键级的向下切换仅发生在系统空闲时,这使得在系统空闲之前,所有自身关键级低于当前系统
关键级的作业都无法正常执行.
针对上述两个问题,研究者开始关注混合关键级调度中低关键级作业的执行,对混合关键级系统的研究重
点逐步转变为如何在保证高关键级作业完成的前提下,尽可能好地执行低关键级作业.文献[15,16]提出了一种
补偿协议 Bailout Protocol(BP),该协议改变了双关键级系统中系统的关键级行为模式,定义了多种系统状态及
其转换条件,通过在一定条件下主动调整关键级,在不损害高关键级作业执行的前提下,尽可能为低关键级作业
提供运行时间.文献[17]提出了一种运行时机制,可以发现并使低关键级任务在弹性活动模式中安全的切换.文
献[18]通过动态地执行预算管理,回收作业在高关键级下的冗余执行时间,并分配给低关键级作业.文献[19]从
概率角度分析了作业的实际执行时间,并通过尽可能延后低关键级向高关键级的切换时间,来为低关键级作业
提供更高的服务保证.文献[20]提出了一种以截止时间为关键参数的混合关键级调度算法,通过对任务的截止
时间进行动态调整,优化低关键级任务的调度.然而,这些方法在系统关键级高时,通常充分考虑最坏情况,使关
键级向下迁移的条件极为严格,仍然影响了低关键级作业的执行.