操作系统论文导读（七）：Response-Time Analysis for Mixed Criticality Systems——混合关键系统的响应时间分析

目录

一、论文核心思想

二、案例引入

 三、基础定义

 四、分区关键性调度 (PC) 

 五、SMC调度

5.1 调度流程

5.2 响应时间分析（考虑EDF分配）

 5.3 优先级分配

六、AMC调度

6.1 调度流程

6.2 响应时间分析（考虑EDF分配）

6.3 AMC 的充分分析 - 方法 1

 6.4 AMC 的充分分析 - 方法 2（精度更高）

6.5 AMC优先级分配

 七、SMC和AMC对比

八、结论

一、论文核心思想

本文有两个基础点：

1.L=HIGH的任务在C(HIGH)执行时必须是可调度的

2.当以C(LOW)调度时所有任务应当均可调度

本文主要基于PC协议提出了两个混合关键系统的调度协议（关键性只有HIGH与LOW），SMC和AMC 并给出了详细的WCET分析和证明，后续证明AMC严格优于SMC。

二、案例引入

        混合关键系统的静态验证与安全关键系统的认证问题密切相关。 当前将多种功能集成到一个通用平台上的趋势，意味着即使在高度安全关键的系统中，通常也只有相对较小的一部分 整个系统实际上是关键功能，需要进行认证。

        为了证明系统是正确的，证书颁发机构 (CA) 必须对系统在运行时的最坏情况下的行为做出某些假设。 CA 往往非常保守，因此通常情况下，如果不需要认证，CA 所需的假设要比系统设计人员在系统设计过程中通常使用的假设悲观得多。

        然而，虽然 CA 只关心系统安全关键部分的正确性，但系统设计者希望确保整个系统的正确性，包括非关键部分。 用一个人为的例子来说明这一点。

示例 1：考虑一个要在抢占式固定优先级单处理器上实现的系统，它只包含三个作业 J1、J2 和 J3。 所有三个作业都在零时间释放。
作业 J1 的截止日期为时刻 2，而其他两个作业的截止日期为时刻 3.5。
作业 J2 和 J3 是高关键性的，需要认证，而 J1 是低关键性的，因此不需要。
系统设计人员确信每个作业的最坏情况执行时间 (WCET) 不超过 1。因此，只要 J1 未被赋予最低优先级，所有三个作业都将在截止日期前完成。
然而，CA 要求在认证过程中使用更悲观的 WCET 估计，并允许作业 J2 和 J3 可能各自需要 1.5 个时间单位的执行。 即使 J1 只执行 1 个时间单位，作业 J2 和 J3 只有在被赋予最高两个优先级时才可调度； 但如果这样做，即使 J2 和 J3 仅执行 1 个时间单位，J1 也将错过其截止日期。
因此，人们可能会得出结论，系统无法以系统设计者和认证机构都可接受的方式进行调度。 幸运的是，有一个可以满足双方的实施方案（和优先级分配）。 考虑优先顺序为 J2，然后是 J1，最后是 J3； 以及从时间 0 开始的以下运行时行为：
• 在 [0, 1) 上执行最高优先级的作业 J2。
• 如果 J2 在时间点 1 之前完成执行，则在 [1, 2) 上执行 J1，在 [2, 3) 上执行 J3，从而确保满足所有截止日期（因此，如果需要，J3 可以在 [2, 3.5) 上执行） .
• 如果J2 没有在时间点1 之前完成执行，则丢弃J1 并继续执行J2，然后在[1.5, 3) 上执行J3。
因此，如果系统设计者是正确的，则所有作业都执行 1 个时间单位并满足其截止日期。 如果 CA 是正确的，则两个高关键性作业各执行 1.5 个时间单位并满足它们的截止日期。 双方都很满意。

 三、基础定义

系统被定义为一组有限的组件 K。每个组件都有一个关键级别（由负责整个系统的系统工程师定义）L，并且包含一组有限的零星任务。 每个任务 τi 由其周期（最小到达间隔）、截止日期、计算时间和关键级别定义：（Ti、Di、Ci、Li）。 然而，这些参数不是独立的，特别是最坏情况下的计算时间 Ci 将由关键级别决定的过程导出。 临界级别越高，验证过程越保守，因此 Ci 的值越大。

在运行时，任务将具有固定的 T、D 和 L 值。然而，它的实际计算时间是未知的； 它不是 L 的直接函数。任务将在可用硬件上执行，并且除了捕获和/或处理超限外，任务的实际关键级别不会影响硬件的行为。 相反，失败的概率（执行超过其截止日期）将随着 L 的更高水平而降低（由于 C 与 L 单调不递减）。

定义 1（行为）：在不同的运行过程中，任何给定的任务系统通常会表现出不同的行为：不同的作业可能会在不同的时刻被释放，并且可能有不同的实际执行时间。 让我们将行为的关键级别定义为最小的关键级别，以便在该关键级别下没有作业执行超过其 C 值。

静态验证。 从静态验证的角度来看，调度混合关键任务系统的算法所期望的正确性准则如下：对于每个关键级别L，所有关键度≥L的任务的所有作业将在任何关键度-L的截止日期前完成行为。

 四、分区关键性调度 (PC) 

分区关键性调度是一种标准方案，有时称为关键性单调优先级分配

在 Partitioned Criticality 中，优先级是根据关键性分配的，因此如果 L1 > L2，则所有关键性 L1 的作业都比所有关键性 L2 的作业具有更高的优先级。

在临界状态下，根据标准最优方案分配优先级，例如截止日期单调优先级分配（对于截止日期受限的任务，即相对截止日期不大于周期的任务：D≤T）。 假定每个作业的执行时间不超过其代表值。

这种分区方法的优点是低关键性作业中的计时错误（即，执行时间长于其代表性的“最坏情况执行时间”）不会影响任何更高关键性的作业。 不需要运行时监控。

然而，如果提供了运行时支持，那么在调度混合关键系统时可以做出的性能保证就会得到增强。 平台支持的一种重要形式是监控单个作业执行的能力，即能够确定特定作业执行了多长时间。

详细来讲：

Partitioned Criticality是一种分区调度算法，它将任务静态地映射到处理器或核心上，提供了一种稳定和可预测的实现方式，这对于安全关键的应用是可取的。在每个处理器或核心上，可以使用不同的任务调度算法来管理分区内的任务执行，例如固定优先级调度（FPT）或抢占阈值自适应混合关键性调度（PT-AMC）。分区调度算法可以保证每个分区获得一定量的CPU时间，如果一个分区内的任务超时运行，只会影响该分区内的其他任务，而不会影响其他分区内的任务。只要不同关键性等级的任务不被分配到同一个分区，这种分层调度方法就可以保证时间隔离。

Partitioned Criticality有一些优点和缺点。它的优点是：

• 它可以提供时间和空间上的隔离，保证高关键性任务不受低关键性任务的干扰。
• 它可以提供稳定和可预测的实现方式，便于安全认证和验证。
• 它可以减少上下文切换和迁移开销，提高系统效率。

它的缺点是：

• 它需要解决任务到处理器或核心的映射问题，这是一个NP难问题。
• 它可能导致处理器或核心的负载不平衡和资源浪费。
• 它可能无法适应动态变化的工作负载和环境。

（注：

任务到处理器或核心的映射问题是指如何将一个或多个任务分配到一个或多个处理器或核心上，以达到某些目标，例如最大化系统性能、最小化能耗、最优化通信开销、提高可靠性等。这是一个重要的设计和优化问题，尤其是在多处理器或多核系统中，因为不同的映射策略会对系统的行为和效果产生显著的影响。

任务到处理器或核心的映射问题通常是一个NP难问题，也就是说，没有已知的有效算法可以在多项式时间内找到最优解。因此，许多研究者提出了各种启发式算法或元启发式算法来近似求解这个问题，例如贪心算法、遗传算法、模拟退火算法、粒子群优化算法等。这些算法通常需要考虑多种因素，例如任务的特征（如执行时间、截止时间、优先级、关键性等）、处理器或核心的特征（如速度、功耗、故障率等）、任务之间的依赖关系（如数据传输、同步、互斥等）、处理器或核心之间的通信方式（如总线、网络等）等。

）

 五、SMC调度

5.1 调度流程

SMC的调度流程如下：

• 首先，根据系统的任务模型和处理器或核心模型，使用一个离线算法来解决任务到处理器或核心的映射问题。
• 其次，根据任务到处理器或核心的映射结果，使用一个离线算法来生成每个处理器或核心上的静态调度表，即确定每个任务在每个处理器或核心上的开始时间和结束时间，以满足任务的截止时间和关键性要求。
• 最后，根据静态调度表，在系统运行期间，使用一个在线算法来执行每个处理器或核心上的任务，并且在发生关键性模式切换时，根据预定义的规则来调整任务的执行优先级和预算。

预定义的规则：一个较低关键性的任务当干扰其他任务执行时执行时间不得超过C（LOW），若超过则此任务取消调度或将优先级调到最低以便于不会干扰其他任务。

5.2 响应时间分析（考虑EDF分配）

EDF分配：对于任意两个任务 τi 和 τj：Di <Dj ⇒ Pi >Pj。对于混合临界系统，这意味着一个任务可能会受到另一个具有更高优先级但较低临界级别的任务的干扰。 

为了测试可调度性，标准响应时间分析方法首先计算每个任务的最坏情况完成时间（其响应时间 R），然后将该值与任务的截止日期 D 进行比较（即测试对于所有任务 τi)，Ri ≤ Di)。 响应时间值从以下获得（其中 hp(i) 表示优先级高于任务 τi 的任务集）：

解释：本公式其实是一个递归公式，它的含义是任务i在执行期间内被高优先级任务抢占的最长时间加上任务i本身的最坏执行时间。

 但对于SMC来讲，这个等式可以进一步进行优化。需要考虑三种情况，具体取决于更高优先级任务 τj 是否具有与 τi相同、更高或更低的关键性。 对于每种情况，必须确定 Cj 的正确值：

1) 如果 Li = Lj 则任务处于相同的临界水平并且使用正常代表值 Cj。

2) 如果 Li < Lj 则不必使用 Cj 表示的计算时间的较大值，而是应使用与 τi 的临界级别相对应的较小数量（因为这是此任务所需的保证级别） . 因此 eqn (1) 应该使用 Cj(Li)。

3) 如果 Li > Lj 那么我们有临界反演。 这里的一种方法是再次使用 Cj(Li)，但这允许 τj 执行的时间远远超过任务在其自身关键级别下的假设执行时间。 此外，这将要求对所有低关键性任务进行最高重要性级别的验证，这将非常昂贵（并且在许多方面破坏了首先具有不同关键性级别的原因之一）。 相反，我们应该使用 Cj，但运行时系统必须确保 τj 的执行时间不会超过这个值。

于是，等式1优化如下：

在此进一步解释一下这个MIN的由来，

1）在Li=Lj的时候，min是无所谓的

2）在Li>Lj的时候，也就是i是高关键性任务，j是低关键性，当j抢占了i的时候，这个时候出现了关键性翻转，但是j也执行了，也就是说如果用C（HIGH）去执行这些任务不能保证i按时执行完毕（参考前边给出的文章两个基本立足点），所以需要选C（low）也就用了min

3）在Li<Lj的时候，也就是高关键性抢占低关键性，要保证i在截止日期前执行完毕，则自然而然应该采用C（low）

 最小值的使用意味着仅任务的关键级别和所有较低的关键级别需要 C 值。这与 Vestal最初定义的方案形成对比，在该方案中没有计算时间监控，因此还必须分析所有 LO 关键任务的 C(HI) 值。（这种将 LO 关键任务验证到与 HI 关键任务相同的保证级别的要求在实践中将非常昂贵。）

（ Vestal方案请参考操作系统论文导读（六）：Preemptive Scheduling of Multi-Criticality Systems with Varying Degrees of Execution……_管二狗赶快去工作！的博客-CSDN博客）

等式进一步简化：

 5.3 优先级分配

截止日期单调优先级分配对于任务具有多个“最坏情况执行时间”的方案不是最优的。

因此，SMC 通过应用 Audsley 优先级分配算法的改版来分配优先级。 也就是说，它首先确定一些可能被分配最低优先级的任务； 这样做之后，该任务从任务系统中删除，并为其余任务递归地获得优先级分配。但对于混合关键系统来说，这种分配方式会更直接。

（Audsley算法详见操作系统论文导读（五）：On priority assignment in fixed priority scheduling —— Audsley算法_管二狗赶快去工作！的博客-CSDN博客）

定理 1：存在最优优先级排序，所有具有相同关键性的任务都按截止日期单调优先级顺序分配优先级。（证明略，比较容易理解）

解释：其实就是先对关键性划分等级，为每个等级分配特定的一个优先级段，然后再采用EDF分配算法为其分配优先级，这样时间复杂度可达到O(n)对比于Audsley算法的O（n方）

六、AMC调度

6.1 调度流程

Adaptive Mixed Criticality (AMC) 调度思想大致如下：

• AMC基于固定优先级抢占式调度（FPPS），根据任务的截止时间来分配优先级（本文采用的是EDF分配方式）
• AMC假设每个任务有两个最坏情况执行时间（WCET）参数，分别对应于正常模式和异常模式。在正常模式下，系统按照较小的WCET参数来调度任务。在异常模式下，系统认为高关键性任务可能会超过较小的WCET参数，而低关键性任务可能会被抢占或丢弃，以保证高关键性任务的截止时间。
• AMC根据任务的执行情况来判断是否需要从正常模式切换到异常模式。如果一个任务的执行时间超过了较小的WCET参数，那么系统就会切换到异常模式，并重新分配优先级。如果一个任务在到达时就能够预测它会使用哪个WCET参数，那么系统就可以提前切换到异常模式。

流程如下：

R1：有一个关键性级别指标Γ，初始化为LO。

R2：While (Γ ≡ LO)，在每个时刻，最高优先级的任务生成的等待作业被选择执行。

R3：如果当前正在执行的作业在没有发出完成信号的情况下执行其 LOcriticality WCET，则 Γ ← HI。

R4：一旦（Γ ≡ HI），关键性级别L ≡ LO 的作业将不会执行。 因此，从此以后，在每个时刻，都选择由具有最高优先级的 HI-criticality 任务生成的等待作业来执行。

R5：附加规则可以指定 Γ 重置为 LO 的情况。 例如，如果在某个时刻没有 HI-criticality 作业处于活动状态，则可能会发生这种情况。

6.2 响应时间分析（考虑EDF分配）

分析采用的形式分为三个阶段：
1) 验证 LO-临界模式的可调度性，
2) 验证 HI-临界模式的可调度性，
3) 验证临界变化本身的可调度性。
请注意第三阶段是必要的，因为它不能从稳定模式的可调度性中推断出来 。 对于这些稳定模式，可以应用标准响应时间分析。

解释：当Γ=LO时，所有任务按优先级的顺序先后执行，执行的最长时间是C（LOW），其中 hp(i) 是优先级高于任务 τi 的所有任务的集合。

 解释：当Γ=HI时，所有低关键性任务停止执行，高关键性任务按照优先级次序执行，执行的最长时间是C（HIGH），其中 hpH(i) 是一组优先级高于或等于任务 τi 的 HI 关键任务。

一般来说，如果关键时刻是明确的（并且理想情况下是所有任务一起发布时）并且最坏情况发生在零星任务以其最大速率到达时，则通常可以进行精确易处理的响应时间分析。 不幸的是，AMC 并非如此。

AMC 的精确分析不太可能容易处理（因为所有零星任务的所有释放模式都需要测试）。事实上，即使对于周期性任务模型，也存在关键时刻无法直接计算的问题。 因此，后续会将重点放在充分的分析上。

推导出两种形式； 一个是基于SMC的分析进行推导，另一个考虑了可能发生临界变化的许多不同点，并采用从这些点中的每一个点获得的最大值。

6.3 AMC 的充分分析 - 方法 1

一种简单的充分分析形式可以从前面描述的 SMC 方法中推导出来。 考虑重新排列方程式 (2) 以分离出两个关键级别：

 解释：这个公式实际上就是把上边的公式2拆分成了不同关键度

在关键度变化期间，我们只关心 HI 任务（因为此时LOW任务不允许执行），因此对于 Li = HI：

 解释：这个公式实际上就是把上边的公式3拆分成了不同关键度

 SMC 的这个等式对于 AMC 来说是保守的，因为它没有考虑到 LO 关键任务无法在 HI 模式下的高关键任务的整个忙碌期间执行这一事实。 必须在 RLO i 之前更改 HI-criticality，因此等式 (6) 可以修改为以下内容：

 解释：这个公式更新和限制了来自 ​​LO 关键任务的干扰，也就是说当系统参数变为HI的时候LO级别的任务均不允许执行，在该公式中优化掉了公式6中当系统参数改变后LO级别但优先级比i高的任务的执行 。该分析的一个明显特性是，在 SMC 下可​​调度的任务系统在 AMC 下也是可调度的。 除了减少来自 LO 关键任务的干扰的“上限”之外，SMC 的分析是相同的。

 6.4 AMC 的充分分析 - 方法 2（精度更高）

在这种方法中，如果任务 τs 调用的关键性变化发生在任意时间 s，我们推导出对 HI 关键任务的最大干扰的表达式。

关键性变化由任何执行时间超过 C(LO) 的任务触发。 如果这个事件对任务τi有影响，则s到达的时间比Ri早，并且τs的优先级必须等于或大于τi； 否则任务 τi 将在关键性变化发生之前完成。 Rs i 的公式是根据它所经历的不同形式的干扰构建的。

 解释：Ci是任务i执行的最坏时间， IL(s) 是来自低关键任务的干扰，IH (s) 是来自具有更高或同等关键任务的干扰。

 在这个公式8中，我们可以区分优先级大于 τs 的任务和优先级较低的任务。 那些优先级大于 τs 的人一定已经完成了这个当前工作（因此只为 C(LO) 执行），而那些优先级等于或小于 τs 的人可能还没有完成，因此必须假设他们当前的工作需要 C(HI ). 

低关键性任务被阻止在 s 之后执行，因此它们的最坏情况干扰受限于：

 解释：使用值 floor + 1 而不是上限函数是因为需要在任何低关键性任务发布后立即包括干扰。 IL(s) 的这个公式是一个上限，要准确计算这个值，需要在计算 s 之前完成的计算量。 

 有许多可能的方法可以得出 IH (s) 的足够（最小）值。 在这里，假设在时间 s 执行的所有作业都为 C(HI) 执行。 因此，只有截止日期在 s 之前的作业才会贡献 C(LO) 值。 然而分析是保守的，需要考虑这些工作的最坏情况分阶段。

考虑在时间 t 时来自任何此类任务 (τk) 的干扰，其中 t>s。 τk 的最大释放次数为

可放入长度为 t − s 的区间内的最大发布次数受限于（对于 T = D 的任务）： 

如果 D<T 则可以改进此值，因为强制存在一个时间间隔（对于可调度系统），其中 τk 不执行 - 即其截止日期和下一次发布之间的时间，因此上述值变为（假设 (t − s) > (Tk − Dk)):

但如果 s 很小并且 Dk 接近 Tk，那么等式 (10)的优化度可能不如最开始的那个等式。因此我们定义

 时间 t 处的干扰项变为

 因此

最后，对于这种方法，我们需要定义需要考虑的 s 值。可能的 s 值的总区间从 0 到 RLO i ，即任务到达时间大于0小于任务i的最大响应时间。

方法 1 和方法 2 的正式比较表明，任何被方法 1 视为可调度的任务集也将被发现可由方法 2 调度。这是从调度方程式的直接比较得出的。 方法 1 假设 LO 关键任务可以在整个区间 [0,RLO i ) 内与 HI 关键任务同时执行（在它们的 C(HI) 级别执行）。 方法 1 还假设 HI 关键性任务在所有长度为 t) 的时间间隔内针对 C(HI) 执行。 方法 2 可能会减少其中一个或两个值； 但是，它们都受到方法 1 中使用的值的上限。因此，方法 2 支配方法 1。

6.5 AMC优先级分配

 由于 AMC 是 SMC 的扩展，因此截止日期单调优先级排序也不是最优的。幸运的是，Audsley 的算法再次适用。 对于这种情况，可调度性测试（在下面称为 S）必须遵守以下条件 ：

• 条件 1：根据测试 S，任务 τk 的可调度性可能取决于任务的任何独立属性优先级高于 τk 的任务，但不依赖于那些依赖于它们的相对优先级排序的任务的任何属性。

• 条件2：根据测试S，任务τk 的可调度性可能取决于优先级低于τk 的任务的任何独立属性，但不取决于那些依赖于它们的相对优先级排序的任务的任何属性。

• 条件3：当任意两个相邻优先级任务的优先级交换时，根据测试S，被赋予更高优先级的任务不能变得不可调度，如果它之前是可调度的低优先级任务。 （作为推论，被分配较低优先级的任务不能根据测试 S 变得可调度，如果它以前在较高优先级不可调度）。

对两种 AMC 方法的调度方程的检查表明这些属性成立。 因此可以采用 Audsley 算法。 此外，定理 1 中嵌入的属性对于两种可调度性测试（方法 1 和 2）也是有效的，因此最多需要 2n-1 次测试才能找到可行的优先级顺序（如果存在的话）。

 七、SMC和AMC对比

总结 SMC 和 AMC 之间的主要区别：
在 SMC 中，如果执行时间超过 Cl(LO)，若任务i关键级别为LO，则会被取消调度。
在 AMC 中，如果任何作业（来自任何任务 τa）的执行时间超过 C(LO)，则所有 LO 关键任务都会被取消调度。
如果 HI-critical 作业 (τh) 的执行时间超过 Ch(LO)（但不大于 Ch(HI)），那么在 SMC 下，LOcritical 任务会继续执行，但可能会错过它们的截止日期； 但在 AMC 下，他们停止执行。

由此可见，AMC 的行为包含了 SMC 的行为。 任何在 SMC 规则和优先级分配方案下可调度的零星任务系统也可在 AMC 规则和优先级排序下调度。 AMC支配SMC。

八、结论

由于安全关键嵌入式系统执行的功能的复杂性和多样性迅速增加，获得此类系统认证的成本和复杂性正迅速成为一个严重的问题 。 我们认为，在混合关键系统中，这些认证考虑因素会带来基本的新资源分配和调度挑战，传统的实时调度理论无法充分解决这些挑战。

在本文中，我们考虑了基于抢占式单处理器的固定优先级 (FP) 调度，混合关键系统可以使用零星任务模型的混合关键泛化来建模。

我们研究了两种调度算法：一种假定对混合关键性 (SMC) 的运行时支持有限，另一种是 AMC，它需要额外的运行时支持，但在提供任务模型时能够提供卓越的可调度性/可认证性保证包括阻塞和任意截止日期。