时间触发的操作系统通常按照时间顺序分配时间槽来调度实时任务。文献[4]提出了一种改进型的Slot-shifting算法，在为时间触发任务预留时间槽的基础上，为事件触发任务动态分配执行时间。当预留给时间触发任务的时间槽没有用完时，剩下的部分可以分配给事件触发的任务；时间触发任务的执行时间还可以在预先定义的时间和离线计算的时间间隔内前后移动，以此来提高任务调度的灵活性。然而，这种方法的任务可调度性分析高度复杂，系统实现很困难。文献[5]为了在静态调度中适当安排事件触发任务，提出了一种轮询的方式在固定的时间点为事件触发任务分配时间。文献[6]和文献[7]分别提出了基于“super loop”和“Sandwich Delay”的时间触发合作式调度机制，可以加强系统的确定性并提高系统利用率，但对于非抢占式内核显然会降低系统的灵活性，且对安全关键任务的支持不够。文献[8]以时间触发总线和时间触发协议为基础，研究了计算机系统架构，探讨了时间触发操作系统的特点。文献[9]通过对μC/OS-Ⅱ操作系统的内核进行扩展，在μC/OS-Ⅱ的任务管理机制中增加了对时间触发任务的支持。系统主要根据预先安排的时间槽进行时间触发任务的调度，在空闲时刻进行基于原μC/OS-Ⅱ系统的事件触发任务的调度。这种设计很好地解决了时间/事件混合触发机制的问题，但是这种扩展只在时钟中断时进行时间/事件触发任务的切换，且时间触发任务被抢占后只能在下一调度周期才能恢复，系统利用率较低。

本文基于文献[9]设计了一种新的任务调度机制，将时间调度机制融入到μC/OS-Ⅱ中，提出一种CDBP的调度算法，不仅满足了时间和事件双重触发的任务，而且利用任务结束到时钟中断之间的时间来处理事件触发任务，提高了系统的利用率，保证了安全关键任务的执行。

时间/事件双重触发系统要求能够同时支持TT (time triggered) 任务和ET (event triggered) 任务。为此，将系统调度器设计为时间触发调度模块和事件触发调度模块两大部分，并以时间触发调度部分为上层主要模块，事件触发调度部分为下层基础模块划分为层次性架构。当系统只有TT任务而没有ET任务时，系统调度器则可以关闭ET任务调度，在空闲时间执行Idle任务。

度器作为系统内核的主要部分，时间触发模块和事件触发模块都向上提供系统服务API，向下都能和硬件通信交互。时间触发模块包括TT任务间的同步与通信、中断管理以及任务超时等错误处理。事件触发模块包括ET任务间的同步与通信、中断管理、资源管理、内存管理与警报等。系统调度器原型如图 1所示。

图  1  时间/事件双重触发系统调度器原型

安全关键系统中的任务具有4个重要属性：发布时间、时限、关键级别和最坏执行时间。其中最坏执行时间是1个多维向量，向量值与任务的关键级别相关，各元素表示任务在各个级别下的最坏执行时间^[10]。下面对多关键级别的安全关键任务模型进行形式化的定义。

定义1   在1个有K个关键级别的安全关键系统中，关键级别最低为1，最高为K，任务表示为${{J}_{i}} $，则有${{J}_{i}}=({{X}_{i}}, {{A}_{i}}, {{D}_{i}}, {{\mathit{\boldsymbol{C}}}_{i}}) $。其中，X_i表示任务J_i的关键级别；A_i表示任务的发布时间；D_i表示任务的时限；C_i表示任务的最坏执行时间，C_i是一个向量，$ {{\mathit{\boldsymbol{C}}}_{i}}=({{C}_{i}}(1), {{C}_{i}}(2), \cdots, {{C}_{i}}(K))$，C_i(1) 表示任务J_i在关键级别为1时的最坏执行时间，C_i(2) 表示任务J_i在关键级别为2时的最坏执行时间，C_i(K) 表示任务J_i在关键级别为K时的最坏执行时间。若K>X_i时，有${{C}_{i}}(K)={{C}_{i}}({{X}_{i}})$。本文的研究的方法是基于状态切换的，研究的对象只限定在两个关键级别的系统中，即任务只具有一高一低两种安全关键级别。在一个具有2个关键级别的系统中，低关键级别为1，高关键级别为2，任务表示为${{J}_{i}}=({{X}_{i}}, {{A}_{i}}, {{D}_{i}}, {{C}_{i}}(1), {{C}_{i}}(2)) $。

设想系统中有两个任务，其中J₁的关键级别为1，J₂的关键级别为2。当系统处于1级关键级别而J₂未能在C₂(1) 时间内执行完时，系统会提升至2级关键级别，以保证J₂在C₂(2) 时间内能完成执行，这时J₁的执行情况则不再重要。因此，对于低关键级别的任务J₁来说，系统不会允许它的执行时间超过C₁(1)。

由上述分析，可以得出两点结论：

1) 对于所有的任务J_i，都有$ {{C}_{i}}(2)\ge {{C}_{i}}(1)$；

2) 如果任务J_i的$ {{X}_{i}}=1$，那么$ {{C}_{i}}(2)={{C}_{i}}(1)$.。

对于两级安全关键任务的系统I，需要设计关键级别不同的两张调度表，低关键级别状态下的S₁和高关键级别状态下的S₂。两张调度表的时间均从第一个任务的发布时间开始，到最后一个任务的时限结束，即$[{{\min }_{{{J}_{i}}\in I}}\{{{A}_{i}}\}, {{\max }_{{{J}_{i}}\in I}}\{{{D}_{i}}\}] $。对于任意时刻$ t\in [{{\min }_{{{J}_{i}}\in I}}\{{{A}_{i}}\}, {{\max }_{{{J}_{i}}\in I}}\{{{D}_{i}}\}]$，S₁(t) 和S₂(t) 分别表示调度表中t时刻应该运行的任务。在系统运行过程中，对任务的调度执行遵循下列规则：

1) 系统当前所处的关键级别用Γ表示，而系统刚开始运行时，Γ=1。

2) 当Γ=1时，在每一时刻t，任务S_i(t) 执行。

如果当前运行的任务J_i在C_i(1) 时刻还未结束，那么系统在低关键级别下的调度表已经无法按计划完成了，这时系统需要提升关键级别，令Γ=2，也就是说此时将进行状态切换。

3) 当Γ=2时，在每一时刻t，任务S₂(t) 执行。

如果对于两级安全关键任务系统I，能设计出满足上述规则的两张调度表S₁和S₂，则说I是时间触发可调度的 (TT schedulable)^[11]。

现有一个两级混合关键系统I，系统中有3个任务，其相关属性如表 1所示。

对于这个安全关键系统来说，图 2为一种可行的任务调度表。开始系统处于低关键级别，根据调度表S₁来进行任务调度：时刻0，任务J₁到达，即可触发调度器进行调度；时刻1，任务J₂触发，此时任务J₁尚未执行完毕即被J₂抢占，J₂开始执行；时刻2，任务J₃触发，如果J₂完成执行 (即J₂运行时间小于等于C₂(1))，那么J₃即可按时执行；到时刻3，当J₃执行完时，此时系统处于空闲，可恢复之前因被抢占而挂起的任务J₁。所有任务均正常执行，没有超过时限。

图  2  示例任务调度表

这是系统运行顺利情况下的任务调度。如果到时刻2，J₂运行时间已等于低关键级别的最坏执行时间C₂(1)，仍未执行完时，系统会将关键级别从1提升至2，并进行状态切换，调度器使用的调度表由S₁切换到S₂。J₂会保持运行直到时刻3。在系统处于高关键级别时，不再对低关键级别的任务J₃提供任何保障。到时刻3，J₂运行时间达到高关键级别下最坏执行时间C₂(2)，完成运行后，系统恢复之前因被抢占而挂起的任务J₁。

本文研究的是时间/事件触发的安全关键任务的调度，时间触发要求系统确定性好，使用资源预留的方法提前创建调度表，有利于提高系统的确定性。而事件触发则希望调度过程可以发生任务抢占，以此来保证高关键级别任务和紧急任务。为此，本文研究的调度方法，将时间预留和优先级抢占方法结合起来。创建调度表的时候首先根据任务在该级别下的最坏执行时间，为各个任务分配好时间槽；然后再给各个任务分配优先级，允许高优先级任务对低优先级任务进行抢占。

OCBP算法^[12]的思想是如果调度可以顺利进行，每次找出剩余任务中优先级最低的任务，当所有任务都被指派优先级或者剩余的任务在当前的优先级都不能被调度时，算法终止。该算法的缺陷有两个：一是任务分配过程中主要考虑任务的关键级别，与任务优先级无关；二是如果找不到最低优先级任务时，该算法就失败了。而本文提出的CDBP算法则全面考虑了任务的关键级别和紧急程度，且调度表的创建不会因为找不到最低优先级任务而终止。

定义2   相对关键度$ {{\rho }_{i}}$，是指在具有n个任务的系统I中，任务J_i相对于其他任务的关键级别的重要程度。用$ {{\rho }_{i}}=\frac{{{x}_{i}}}{\sum\limits_{j=1}^{n}{{{x}_{j}}}}$来表示，其中x_i和x_j是各任务在系统某个统一时刻的关键级别^[13]。

假设系统中有4个任务，关键级别分别为1，2，1，2，则${{\rho }_{i}} $分别为$\frac{1}{6}, \frac{1}{3}, \frac{1}{6}, \frac{1}{3}$。

定义3   关键额度${{\delta }_{i}} $，是指在具有K个关键级别的系统I中，J_i当前所处级别在当前系统的关键级别k下所具有的关键份数。用$ {{\delta }_{i}}=\frac{{{x}_{i}}}{k}$来表示，其中x_i是任务的当前关键级别。假设系统中有两个任务J₁和J₂，其中X₁=1，X₂=2，则K=2。当系统关键级别k=1时，任务J₁和J₂的当前关键级别x₁和x₂也都是1，则$ {{\delta }_{1}}={{\delta }_{2}}=1$；当系统关键级别k=2时，x₁=1和x₂=2，则$ {{\delta }_{1}}=\frac{1}{2}, {{\delta }_{2}}=1$。

定义4   时限紧急度d_i是指任务时限的先后对任务的紧急程度的影响，用$ {{d}_{i}}=\frac{1}{D_{i}^{2}}$来表示。在同等情况下，时限更早到来的任务应该具有更高的优先级。

定义5    K关键级别下的关键度$ \theta _{i}^{k}$是指在K关键级别下，任务J_i的一次执行相对于其他任务的一次执行在所处关键级别的重要程度以及利用率的一种度量。用$\theta _{i}^{k}={{\rho }_{i}}{{\delta }_{i}}{{d}_{i}} $来表示。

从关键度$ \theta _{i}^{k}$的定义可以看出，它充分体现了任务J_i的关键级别相对于其他任务的重要程度和它在系统处于某一关键级别时在整个系统中的关键程度，以及该任务的时限对紧急程度的影响。以它为基础来为系统处于某一关键级别时的各任务分配优先级，能充分体现出任务优先级的特点，在系统处于低关键级别时，也减少了不必要的任务切换，提高了系统利用率。

根据CDBP算法为任务分配优先级的流程如图 3所示。

图  3  CDBP算法优先级分配流程图

在CDBP的算法中，在K关键级别下关键度越大的任务具有的优先级越高。在两个任务关键度相同的情况下，若系统处于低关键级别或者两个任务的关键级别相同时，时限越早的任务优先级越高；若两个任务关键级别不同且系统处于高关键级别，则关键级别高的任务优先级高。

本文是在嵌入式应用的开发平台Xilinx Virtex-5 FXT FPGA ML507上进行的实验，所设计的调度器也最终移植到该平台上进行了测试。

测试用例任务集有3个ET任务和4个时间触发的安全关键任务，其中ttTask2和ttTask4是高安全关键级别任务，ttTask1和ttTask3是低关键级别任务。图 4和图 5显示了往ttTask2添加额外负载前后的运行情况对比，从图中可看出，开始ttTask2能够在低关键级别下的1个单位的时间内执行完毕，添加额外负载后，ttTask2无法按时完成，这时为了保证ttTask2能正常执行完，系统提升关键级别，ttTask1和ttTask3的执行不再得到保证，最终系统保证ttTask2、ttTask4和etTask1、etTask2、etTask3顺利执行完毕。该实验说明实现的多级调度表达到了设计要求，调度表成功切换，为高关键级别任务提供了保障。

图  4  低关键级别调度示意图

图  5  高关键级别调度示意图