事件触发关键级提升的实时任务可调度性分析

摘要： 混合关键级(mixed criticality, MC)系统能够同时保证高效地资源利用与高关键任务的正确执行.当前，对混合关键级系统的研究多认为，从低关键级提升到高关键级的时机是高关键级任务执行超过其低关键级模式下时间预算的时刻.但在实际应用的嵌入式系统中，关键级模式的提升是由诸如所处环境变化、控制切换等系统外部事件触发的，即关键级的提升可能发生在任务执行过程中的任何时刻.在单处理器平台上，针对使用固定优先级调度策略的周期任务集，当外部事件触发关键级提升后，基于响应时间分析得出了可调度高关键级任务的必要条件；并对关键级提升后，高关键级任务可能通过优先级交换满足截止时限的条件进行了分析，得出了相应的优先级交换算法.仿真实验验证了事件触发关键级提升时高关键级任务的可调度性及优先级交换算法的有效性.

关键词： 关键级；事件触发；优先级；响应时间；截止时限

现代实时嵌入式系统，例如航空电子设备以及汽车系统的实际应用，正向着功能不断增加但所占空间更小、重量更轻、成本更低、能耗更少的方向发展.因此使用冗余硬件分层设计来实现任务之间隔离执行 [1] 的传统方法，正向着不同关键级的多种功能集成到一块物理平台上，共享硬件资源的研究方向转变.但这种以提高资源利用率为目的的共享可能会使低关键级(low criticality, LO)任务对高关键级(high criticality, HI)任务的正确执行产生干扰，导致HI任务错过截止时限、造成非常严重的后果.例如从高效利用处理器计算能力的角度，可以将汽车的防抱死制动任务与导航任务放在同一个处理器上执行，若导航任务未能按预设时间执行完毕，防抱死任务很可能就无法得以及时执行，从而导致重大安全事故 [2] .

既要确保HI任务的截止时限又要保证充分利用资源，是提出混合关键级(mixed criticality, MC)系统的初衷.文献[3]首先对混合关键级系统的调度与验证进行了讨论.无论是从过载角度考虑以增加系统运行的鲁棒性 [4] ，还是从静态验证、遵循更保守国际统一标准的角度出发 [5] ，MC系统的执行可分成若干关键级模式，处于不同关键级模式所确保执行的任务子集和任务属性均不同，即将待调度任务集划分为不同关键级：在高关键级HI模式和关键级LO模式下总是满足HI任务的截止时限；而LO任务只在低关键级模式下执行，不确保其在HI模式下满足截止时限.一般认为系统是从LO模式开始运行，MC系统执行从LO模式切换到HI模式的过程称之为关键级提升.

MC任务一个重要特点是除了截止时限(dead-line)、周期(period)、最差情况下执行时间(worst case execution time, WCET)、释放时间(release time)等传统时间参数之外，还增加了关键级(criticality)这一参数，且部分或全部的时间参数值依赖于关键级，即所谓关键参数：相较于LO模式，HI任务在HI模式下WCET更长、执行频率更高、截止时限更短 [6] .虽然有以文献[7]为代表的部分研究讨论不同关键级模式下基于弹性模型的周期变化，但当前以文献[8-11]为代表的大多数MC调度研究，包括最早提出MC调度的文献[3]，均是以WCET为关键参数.与周期、截止时限等其他时间参数比较，虽然实时任务的实际执行时间具有不确定性和动态持续性，但是作为实时任务时间参数之一的WCET则是可以通过预先估算获得.典型MC系统对于关键级的提升通常是这样描述的：HI任务在LO模式下执行时，若执行完毕其LO模式下预置的WCET时间预算，仍然没有结束执行，则认为此时系统应该切换到HI模式执行，同时通过挂起或抛弃LO任务以确保HI任务获得更多的处理器执行时间.这是从任务本身执行发生变化的角度来识别关键级模式提升时刻.

但实际上，与系统关键级回落 [12] 不同，系统关键级模式从低到高的切换并不是由正在执行的任务引发的，而是由外部事件触发的.文献[13]中指出现代汽车系统随着行驶环境的变化发生关键级变化，例如从Street(城市街道)执行模式进入Highway(高速公路)执行模式时，其悬架控制功能从LO切换成HI模式执行.又例如，从权威机构标准认证角度考虑MC系统时，经常以无人机为典型实例，文献[14]中指出当军用无人机飞入民航区域，涉及飞行安全的相关功能必须遵循更保守的时间限制，例如WCET增加等，可见关键级的提升也是由系统所处外部环境变化引起的.因此，系统执行从LO模式提升到HI模式，不是由任务本身触发这种关键级提升，而是由外部环境变化、人为控制等事件的发生才引发系统关键级提升.任务实际执行时间超过低关键级WCET只是关键级提升的表现和需要.

不同于当前以HI任务超出低关键级WCET作为关键级提升时刻的思路，本文基于外部事件触发(event-trigger)系统关键级提升的观点，对关键级提升期间HI任务的可调度性进行分析.由于在不同关键级下需确保执行的任务集在系统设计时就已经确定好了，即可以离线确定系统静态处于某一关键级模式下的调度策略，保证具有相应关键级参数的任务截止时限 [15] .所以要确保HI任务的正确执行，问题聚焦在从LO提升到HI这个模式动态切换期间如何满足HI任务的截止时限.本文基于响应时间分析，针对在单处理平台上执行的混合关键级实时周期任务集，讨论了其从LO模式切换到HI模式的关键级提升期间的可调度性，得出了相关必要的可调度条件.

在已公开发表的文献中，涉及关键级提升后优先级是否可交换的研究仅有文献[16]从抖动的观点进行了讨论.本文针对事件触发关键级提升后，MC任务可能通过优先级交换获得正确调度的条件进行了分析，并设计了相应的优先级交换算法.

1 任务模型与示例

本节对本文所使用的MC任务模型及相关术语进行定义.引入一个MC任务集运行示例，为后文的优先级可交换分析做准备.

为讨论方便，暂时仅考虑系统只有HI和LO两个关键级的情形.在单处理器平台上，MC任务集 τ 由互不相关、允许抢占的有限个同步周期任务组成： τ

{ τ 1 , τ 2 ,…, τ m }，其中 m 表示任务个数.以执行时间为关键参数，定义任务 τ i

, T i , D i , l i )，其中

是任务 τ i 在LO模式时的

是在HI模式时的WCET.从保守验证的角度而言，

和

分别是任务 τ i 在LO和HI模式下能够获得的最大执行时间预算.虽然一个实时任务的实际执行时间

是无法预知的，但总是不超过其WCET.即，对于LO任务而言有

，对于HI任务则有在LO模式时

，在HI模式时

且

. T i 和 D i 分别是任务 τ i 的周期和相对截止时限，其值在任何关键级均不变化，且 D i ≤ T i .当任务 τ i 的关键级 l i =HI时，表示其为HI任务，其

≤ D i ；若 l i =LO，则表示任务 τ i 是LO任务.当系统处于HI模式，不确保其正确执行，因此LO任务的

不设确定值.任务 τ i 的利用率通常使用

计算获得.显然在不同关键级模式下，HI任务有不同利用率，LO模式下，有

；HI模式下，有

响应时间是指任务从释放到执行完毕这一段时间间隔 [17] .常用于分析固定优先级任务可调度性.一般实时任务 τ i 的响应时间为

其中 hp ( τ i )是指优先级高于任务 τ i 的所有任务.稍后将讨论关键级对于任务响应时间的影响.

在实际嵌入式应用中，尤其是涉及硬实时的应用，具有可预测性的固定优先级调度被使用得更为广泛 [11] .在无模式切换发生的静态LO模式和HI模式下，可采用Audsley的最佳优先级分配(optimal priority assignment, OPA)算法 [18] 分配任务的优先级，算法描述如下：

输出：系统模式为 χ 时，依据优先级从高到低排列的可调度任务序列.

Step3. 若除 τ i 之外，所有 l j ≥ χ 的任务 τ j 均先于 τ i 执行， τ i 的响应时间不迟于其截止时限，即 R i ≤ D i ，则最低优先级 k 分配给 τ i ，即 p i = k ，且将 τ i 移出 τ ，其他任务重复本步骤依次分配从 k -1到1的优先级；

在每一个关键级模式内使用如上OPA算法对任务进行固定优先级分配.OPA算法将确定优先级分配序列的可调度性测试复杂度从 n !降低到 n ( n +1)

如表1所示，待调度的混合关键级任务集共包括4个任务，分别属于HI和LO两个关键级.其中， τ 1 和 τ 2 是HI任务，其在HI模式和LO模式有不同的WCET值； τ 3 和 τ 4 是LO任务，仅在LO模式时确保执行.设系统最开始运行于LO模式，使用前述OPA算法，这4个任务的优先级分配结果为 p 3 > p 4 > p 1 > p 2 ，在LO模式时调度序列如图1所示.

Table 1 An Example of Scheduling Mixed Criticality Task Set

表1 待调度混合关键级任务集示例

Fig. 1 Scheduling MC tasks in Table 1 in low criticality mode
图1 表1示例MC任务集在LO模式的部分调度序列

此时，按照

参数，所有任务的截止时限均能得到满足.下面依据目前传统MC系统关键级提升时刻设定，分别对2个HI任务 τ 1 和 τ 2 的可调度性进行讨论：

1) 对于HI任务 τ 1 ，若在其执行完低关键级时间预算

后仍然继续执行，依据目前传统MC系统的一般设定，即在时刻

=12发生关键级提升，此时即使立刻终止执行LO任务 τ 3 和 τ 4 ，此后处于HI模式的任务 τ 1 剩余5个执行时间单元，尚未执行的任务 τ 2 尚有

=8个待执行时间单元，总计剩余13个待执行时间单元，并未超出处理器能够提供的总执行能力，但是由于 p 1 > p 2 ，导致 τ 1 先于 τ 2 获得继续执行，直至时刻17才执行 τ 2 ，不能满足 τ 2 的截止时限.

在此例中，可以发现若能在发生模式切换的当前周期内交换2个HI任务的优先级即可以确保满足截止时限.这需要在时刻12之前获知关键级需要提升才能对优先级交换进行预计.由此可见，一个HI任务的截止时限是否能够得到满足，会受到相对较高优先级任务，包括较高优先级的HI任务以及较高优先级的LO任务的影响，也会受到关键级模式切换时刻的影响.

2) 对于HI任务 τ 2 ，在执行完毕其低关键级时间预算的时刻，恰好也达到了其截止时限，已获得相对质量较低的执行结果，由于 T ≥ D ，在当前周期内任务 τ 2 的此次执行已经结束.

因此，在以执行时间为关键参数的MC系统中，当前常用的以高关键级任务执行时间超过其低关键级WCET的时刻即为关键级提升时刻的设定，可视为是一种延迟关键级模式切换，即直到HI任务达到其 C LO 时间预算后才进行关键级模式从LO到HI的提升.

下面从外部事件触发关键级提升的观点，对关键级提升期间HI任务的可调度问题以及HI任务之间优先级可交换的问题进行探讨.

2 关键级提升期间的响应时间分析

定义1. 关键级提升期.设引发关键级提升的外部事件发生时刻为

，而在时刻

之前释放的HI任务中最迟的截止时限时刻为

，则

)这一段时间称之为关键级提升期.

在关键级提升期之前，LO任务可能已经释放或开始执行，一旦进入关键级提升期，则立即挂起LO任务；HI任务，则至多执行

个时间单元，且要尽可能确保其截止时限.与处于静态HI模式——即所有任务释放时均处于HI模式——执行不同，关键级提升期的HI任务响应时间可能受到

之前开始执行的LO任务的影响.

Fig. 2 A HI task executing example during a period
图2 一个HI任务的执行示例

图2中的 a i 是任务 τ i 的释放时间，绝对截止时限 d i = a i + D i . τ i 实际开始执行时间为

，完成时间为

，其中

，而任务 τ i 的响应时间

- a i .参考图1中示例的HI任务的执行，若处于LO模式，即使在

]期间HI任务也可能被较高优先级的LO任务抢占而间断执行.引发关键级提升的外部事件发生时刻

可能出现任意时段，将任务 τ i 的执行分成3个部分，分别讨论HI任务 τ i 在关键级提升期的响应时间：

1) 当

)时，HI任务 τ i 已经释放但尚未开始执行.在关键级提升期，可能对任务 τ i 的响应时间产生影响的任务包括：

① 在时刻

之前开始，优先级比任务 τ i 高的任务子集 hp ( τ i )，它们可能已经执行完毕也可能正在执行，那么在最差情况下其对 τ i 响应时间的影响为

② 在时刻

之后释放，优先级比任务 τ i 高的HI任务为 hp ( τ i )∩ hc ( τ i )，其中 hc ( τ i )表示关键级高于任务 τ i 的任务子集，其对 τ i 响应时间的影响为

2) 当

]时，任务 τ i 正处于执行阶段，对其产生影响的任务包括：

① 在时刻

之前开始，优先级比任务 τ i 高的任务子集 hp ( τ i )，这些任务已经执行完毕，其对 τ i 响应时间的影响为

② 在时刻

之后开始，且优先级比任务 τ i 高的HI任务 hp ( τ i )∩ hc ( τ i )，此类任务必然是在时刻

之后释放且周期相对于 τ i 较小的高优先级HI任务，其对 τ i 响应时间的影响与 I 2 相同.

以上2种情况，在关键级提升周期内，满足截止时限的HI任务 τ i 的利用率均为

3) 当

, d i ]时，在当前周期内，HI任务 τ i 在确保截止时限的条件下，已经使用完其LO模式的预设最大可用处理器时间

，获得了一个LO模式下的计算结果.换而言之，HI任务在从LO模式切换到HI模式的执行并非简单等同于

阶段加上

阶段.与LO模式时的执行相比，HI任务本身的功能并没有变化，仅是出于安全等因素的考虑，其执行时的计算精度、递归次数等要求更高，从而导致HI模式时的执行时间更长 [19] ，从而获得更精确、质量更高的计算结果.因此当时刻

发生在HI任务在LO模式的响应时间之后，那么该HI任务在其下一个执行周期按照HI模式调度执行.此种情况下，在关键级提升周期内该HI任务的利用率

从本节前述分析可知，若事件触发关键级提升时刻

发生在HI任务在LO模式执行完毕之后，则该HI任务在当前周期内不会切换到HI模式，即

]时，才会引发此HI任务在当前周期内执行模式变化.

根据式(2)可得，在时刻

立即发生关键级提升时HI任务 τ i 的响应时间，那么据此可以推断在关键级提升期内：

① 若

> d i ，即由于在时刻

之前有过多较高优先级低关键级任务的干扰，该HI任务 τ i 无法满足截止时限；

② 若

= d i ，则该HI任务 τ i 恰好满足其截止时限，可成功调度；

③ 若

< d i ，则意味着该HI任务 τ i 满足截止时限，且还有空闲的时隙可能供给LO任务执行.

对于在时刻

正在执行或尚没开始执行的HI任务根据优先级从高到低依次进行前述判定.

3 关键级提升期内优先级可交换

由第2节可知，受到外部事件驱动关键级提升影响的HI任务，在时刻

的HI任务尚未执行完毕的时间预算

)有且只有2种情况：

在关键级提升期内，一个 R LO→HI > d 的HI任务通过与邻近较高优先级任务交换优先级，正如1.2节中例子所示，可能使二者的截止时限均能得到保证.根据固定优先级调度的特点：若较低优先级 p = k 的任务和较高优先级 p = k -1的任务交换优先级执行，对其他任务的调度执行没有影响 [19] .据此关键级提升期内的优先级交换可尝试在优先级相邻的2个任务间进行.

通过式(2)可知，构成任务 τ i 的

的3个部分中，只有时刻

之后的由较高优先级HI任务抢占产生的

可以通过交换优先级减少.而被交换的较高优先级(设若 p k = k )的HI任务 τ k 一定有

< d k ，否则该高优先级HI任务也不能被延迟完成.由于 p k > p i ，那么必然在 τ k 执行完毕之后 τ i 紧接着 τ i 才得以执行完毕.若其他任务的优先级顺序不变，而任务 τ k 剩余的空闲时隙足以容纳相邻低优先级( p i = k +1)任务 τ i 未执行的部分，即

)，那么这2个相邻优先级任务的优先级可以交换： p k = k +1， p i = k .若交换后获得较高优先级任务 τ i 的新的响应时间仍然大于 d i ，则可以和优先级为 k -1的更高优先级任务重复上述过程，直至满足

≤ d i 为止；或者无法找到可交换优先级的较高优先级HI任务，那么任务 τ i 在关键级提升期内无法正确调度，即总是无法满足其截止时限.

输入：依据优先级递减顺序排列的在关键级提升期未满足调度条件的HI任务子集 τ ′、可调度的HI任务子集 τ o ；

Step2. 取 τ ′中优先级最高的任务 τ i ，则其优先级为 p i = k +1；

Step3. 若

= d k ，则算法结束，无法为 τ i 找到可交换的优先级的任务;

PE算法的时间开销主要在递归计算响应时间

和

以及据此计算获得的

)上，而响应时间分析是伪多项式时间复杂度 [20] ，因此本算法的时间复杂度也是伪多项式时间的.

4 仿真与评估

本节对第2节和第3节基于外部事件引发关键级提升的MC系统的可调度性进行测试，并对优先级可交换的算法进行了仿真验证.

借鉴当前MC调度研究的大多数仿真所采用的任务生成方式，使用文献[8]的方法，测试中所使用的待调度MC任务如下随机产生：

1) 对于任务利用率 U i ，使用UUnifast算法 [21] 在0.025～0.975之间产生均匀分布的利用率值；

2) 对任务周期 T i ，根据对数正态分布生成任务周期，最小和最大任务周期相差100倍，例如最小任务周期为10 ms，最大任务周期为1 s，大部分是硬实时应用的任务均有类似属性；

5) 任务HI模式的执行时间是其LO模式执行时间的固定倍数 cf ，即

× cf (例如 cf =2.0)；

6) 生成的任务由参数 cp 确定其可能为HI任务的可能性，例如 cp =0.5.

文献[9]认为一旦HI任务执行超过LO模式时的WCET，即认为是关键级提升的时刻出现，其混合关键级调度算法AMC的结果将作为我们主要的比对、分析对象.

1) AMC.某一个HI任务超出LO模式WCET时，即认为系统关键级提升的时刻出现.

2) MC-et.指本文所述的基于外部事件触发关键级提升的MC调度，由于关键级提升时刻

是影响任务可调度性的重要因素之一，因此在实验中，我们在同一个HI任务的一次执行周期内随机选择10个时刻

，并计算这10组时刻

的可调度任务数目的均值，作为一个对比数据.

依据4.1节中的方法共计产生1 000个待调度的任务，其中一半为HI任务( cp =0.5)，每个HI任务在HI模式时的WCET是其LO模式时WCET的2倍( cf =2.0).

分别使用AMC和MC-et对上述任务集进行可调度测试，图3显示了可调度任务比率的对比.可以观察到同样是只关注关键级提升后的HI任务的正确执行，MC-et可调度的HI任务比率要高于AMC，且AMC能够调度的任务MC-et均能够调度，反之却不一定.

Fig. 3 Percentage of schedulable tasks
图3 可调度任务占总任务数的百分比

Fig. 4 Varying cf to change the value of affecting schedulable tasks
图4 调整参数cf来改变值的可调度任务比率

类似文献[8]的仿真实验，我们还通过改变任务的参数比较加权可调度性 [22] .图4是改变 cf 参数，即调整HI模式WCET的时长后可调度任务比率；图5是改变 cp 参数，即调整HI任务数目后可调度任务比率.从结果可看到，随着 cf 或 cp 的值增加，AMC和MC-et的可调度任务比率呈现类似的下滑趋势，但MC-et能够调度更多的任务，在多数情况下具有约10%的优势，且不受时刻

选取的影响.

Fig. 5 Varying cp to change the number of HI tasks
affecting schedulable tasks
图5 调整参数cp来改变HI任务数目的可调度比率

Fig. 6 Exchanging the priorities between MC
tasks affecting schedulable tasks
图6 交换优先级对可调度任务比率的影响

目前已发表文献中，涉及关键级提升后任务优先级可交换研究的仅有文献[16]中的PMC，将本文的优先级交换算法PE与其进行比较.如图6～8所示，本文的PE算法在可调度任务数目上大于PMC，且总是优于不使用优先级交换的调度；随着HI模式下WCET增加，PE算法与PMC类似，与没有优先级交换时相比可调度任务数目改善不太明显，但是随着HI任务数目的增加，PE在增加可调度任务数目上改善相较于PMC更为明显，也侧面说明触发关键级提升的外部事件发生时刻

在任务执行期间的位置对于可调度任务数目是有实际影响的.

Fig. 7 Exchanging the priorities between varying cf of
MC tasks affecting schedulable tasks
图7 交换优先级对调整cf值的可调度任务比率影响

Fig. 8 Exchanging the priorities between varying cp of
MC tasks affecting schedulable tasks
图8 交换优先级对调整cp值的可调度任务比率影响

5 结论

对于混合关键级系统而言，由低关键级模式到高关键级模式的转换不是由任务执行地变化产生，而是由外部事件引发的，关键参数的变化只是关键级提升的表现.在以任务执行时间为关键参数的混合关键级系统中，不论是从确保高关键级任务正确执行的鲁棒性角度考虑，还是从满足保守的统一标准验证的要求考虑，关键级提升可能发生在高关键级任务在低关键级模式下释放后直至当前周期结束的任何时刻.

对于固定优先级的调度方案，基于外部事件触发关键级模式切换的考虑，本文仅关注高关键级任务截止时限的确保，尤其是系统关键级模式提升期间，基于响应时间分析得出了高关键级任务的可调度条件；并对关键级提升期间，可能发生优先级相邻任务交换优先级满足截止时限的条件进行了讨论分析，并设计了优先级交换算法.仿真实验验证了前述分析与算法的有效性.

在后续工作中，将对动态优先级调度方案和多处理器平台上事件触发关键级提升的混合关键级任务调度进行研究.

[1]Burns A, Davis R. Mixed criticality systems—A review[R]. Yorkshire, UK: Department of Computer Science, University of York, 2013

[2]Niz D d, Lakshmanan K, Rajkumar R. On the scheduling of mixed-criticality real-time task sets[C]

Proc of IEEE RTSS 2009. Piscataway, NJ: IEEE, 2009: 291-300

[3]Vestal S. Preemptive scheduling of multi-criticality systems with varying degrees of execution time assurance[C]

Proc of IEEE RTSS 2007. Piscataway, NJ: IEEE, 2007: 239-243

[4]Lakshmanan K, Niz D d, Rajkumar R. Mixed-criticality task synchronization in zero-slack scheduling[C]

Proc of IEEE RTAS 2011. Piscataway, NJ: IEEE, 2011: 47-56

[5]Baruah S, Li H, Stougie L. Towards the design of certifiable mixed-criticality systems[C]

Proc of IEEE RTAS 2010. Piscataway, NJ: IEEE, 2010: 13-22

[6]Burns A, Baruah S. Timing Faults and Mixed Criticality Systems[M]. Berlin: Springer, 2011

[7]Su H, Zhu D. An elastic mixed-criticality task model and its scheduling algorithm[C]

Proc of DATE 2013. San Jose, CA: EDAA, 2013: 147-152

[8]Baruah S, Burns A, Davis R I. Response-time analysis for mixed criticality systems[C]

Proc of IEEE RTSS 2011. Piscataway, NJ: IEEE, 2011: 34-43

[9]Baruah S, Bonifaci V, D’Angelo G, et al. Mixed-Criticality Scheduling of Sporadic Task Systems[M]. Berlin: Springer, 2011

[10]Schneider R, Goswami D, Masrur A, et al. Multi-layered scheduling of mixed-criticality cyber-physical systems[J]. Journal of Systems Architecture, 2013, 59(10): 1215-1230

[11]Buttazzo G C. Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications[M]. New York: Springer Science & Business Media, 2011

[12]Santy F, George L, Thierry P, et al. Relaxing mixed-criticality scheduling strictness for task sets scheduled with FP[C]

Proc of IEEE ECRTS 2012. Piscataway, NJ: IEEE, 2012: 155-165

[13]De-Niz D, Phan L T X. Partitioned scheduling of multi-modal mixed-criticality real-time systems on multiprocessor platforms[C]

Proc of IEEE RTAS 2014. Piscataway, NJ: IEEE, 2014: 111-122

[14]Triquet B. Mixed criticality in avionics[C

OL]

Proc of European Commission Workshop on Mixed-Criticality Systems. 2012 [2012-09-11]. http:

cordis.europa.eu

fp7

ict

embedded-systems-engineering

presentations

triquet.pdf

[15]Barhorst J, Belote T, Binns P, et al. A research agenda for mixed-criticality systems[R]. Brookings, Washington DC: Department of Computer Science and Engineering, Washington University in St Louis, 2009

[16]Baruah S, Burns A, Davis R I. An extended fixed priority scheme for mixed criticality systems[C]

Proc of IEEE RTCSA 2013. Piscataway, NJ: IEEE, 2013: 18-24

[17]Joseph M, Pandya P. Finding response times in a real-time system[J]. The Computer Journal, 1986, 29(5): 390-395

[18]Audsley N C. Optimal Priority Assignment and Feasibility of Static Priority Tasks with Arbitrary Start Times[M]. York, England: University of York, Department of Computer Science, 1991

[19]Burns A. System mode changes-general and criticality-based[C]

Proc of the 2nd WMC 2014. Piscataway, NJ: IEEE, 2014: 3-8

[20]Liu J W S. Real-Time Systems[M]. Upper Saddle River, NJ: Prentice Hall, 2000

[21]Bini E, Buttazzo G C. Measuring the performance of schedulability tests[J]. Real-Time Systems, 2005, 30(1

2): 129-154

[22]Bastoni A, Brandenburg B, Anderson J. Cache-related preemption and migration delays: Empirical approximation and impact on schedulability[C]

Proc of OSPERT 2010. Duesseldorf, Germany: Euromicro, 2010: 33-44

Huang Lida, born in 1978. Lecturer and PhD candidate. Her main research interests include real time scheduling and embedded software.

Li Renfa, born in 1956. Professor and PhD supervisor. His main research interests include computer architecture and computer application technology.

The Schedulable Analysis of Real-Time Tasks After Event-Triggered CriticalityLevel Transition

( College of Computer Science and Electronic Engineering , Hunan University , Changsha 410082)

Abstract： Both effective resource utilization and meeting the deadlines of high-criticality tasks are objectives of mixed-criticality systems. Currently, it is considered the moment that any of high-criticality tasks execute for their low-critical worst case execution time without completing the system switch from low to high-criticality mode immediately. However, in real embedded applications, the increasing criticality is event-triggered which includes outer circumstance changing, control switching, and so on. That is why the time of raising criticality level can be occurred before, during, or after a task implementation. In this paper we center on that the time of event-triggered increasing criticality is how to influent the scheduling of high-criticality and fixed priority periodic tasks, which is based on the response time analysis. A sufficient condition of scheduling high criticality tasks is derived. Then we discuss when and how to exchange priorities between two high-critical tasks in order to meet their deadlines at the same time, and propose an algorithm of exchanging priorities. Evaluations illustrate the benefits of the schedulable condition and the priority exchanging algorithm.

基金项目： 国家自然科学基金项目(61173036) This work was supported by the National Natural Science Foundation of China (61173036).