🛡️ 混合关键度系统：让安全关键任务和非关键任务挤在同一块板子上

这一篇在干嘛？

论文出处：Domitian Tămaș-Selicean & Paul Pop（丹麦技术大学 DTU），Design Optimization of Mixed-Criticality Real-Time Embedded Systems，ACM TECS 14(3)，Article 50，2015 年 4 月，29 页。核心矛盾是：飞控这种”出错会死人”的功能和娱乐系统这种”出错顶多重启”的功能想共用一块硬件，但认证标准强制要求它们互相隔离，而隔离会白白浪费大量 CPU 时间。论文的解决思路是把任务映射、分区划分、SIL 分解、分区切片排序与大小、调度表这五件事放在一起联合优化，用禁忌搜索（Tabu Search）在”时间 + 空间分区”的框架下搜索，必要时允许不同关键度的任务共享分区（代价是把低关键度任务提升到高关键度，开发成本上升），同时用 SIL 分解（把一个高等级任务拆成几个低等级冗余任务）把成本再降回来。主要结论：映射与分区联合优化比分开做，可调度性指标最多提升约 27647%；在联合优化也调度不下去的场景，允许共享分区 + 分解后能调度全部应用，额外付出的开发成本在 19～470 千欧之间；在可穷举的小算例上，禁忌搜索 480 分钟跑出的结果与全局最优解成本相同。

一、背景：为什么”一个板子跑两种关键度”这么难

1.1 什么叫”关键度”

先建立一个最直觉的画面。一架现代客机上，机舱里至少跑着两类完全不同的软件：

• 飞控 / 发动机控制 / 襟翼收放：算错一个数、晚一毫秒，可能机毁人亡。
• 乘客娱乐系统 / 客舱灯光 / Wi-Fi：卡一下、崩一次，最坏结果是乘客抱怨和重启。

这两类功能的关键度（criticality）天差地别。安全标准用安全完整性等级（Safety Integrity Level，SIL）来量化这种差别：等级越高，意味着这个功能一旦失效后果越严重，因此开发它时必须遵循的流程越严格、要写的文档越多、要做的测试越狠、要请的独立评审越贵。

IEC 61508 定义了四级，SIL 4 最严、SIL 1 最松；本文额外用 SIL 0 表示”完全非关键”。不同行业标准名字不同但思路一致：

记住这条金线

本文说的”关键度”不是一个模糊的形容词，而是一个会直接换算成钱和流程的等级标签。所有的优化，本质上都是在跟这个标签打交道。

为什么等级一涨，钱就飞涨？因为标准会逐级加码（以 DO-178B 为例）：

• SIL 1 / DAL E：跟普通质量管理（ISO 9001）差不多。
• SIL 2：要更多的评审与测试；独立性要求上升到”独立部门”。
• SIL 3：难度显著上升，要求”半形式化”方法；要求”独立组织”来评估。
• SIL 4：往往强制形式化方法；DO-178B 中 DAL A 需要独立满足 66 个目标中的 25 个，而 DAL B 只需独立满足 14 个。

IBM Rational 的一份白皮书给出的数字是：认证成本会让项目总成本增加 25% 到 100%。这就是整篇论文想省的钱。

1.2 从”一功能一盒子”到”集成架构”

最早期的做法很朴素：每个功能单独放一个硬件节点（一个 ECU、一个 LRU）。飞控一个盒子、娱乐一个盒子、导航一个盒子……互不干扰，天然隔离。但代价是整车/整机上的节点数量爆炸，重量、线缆、功耗、成本全部失控。

于是产业界转向集成架构（integrated architecture）：把多个功能塞进同一个节点。航空电子领域管这叫 IMA（Integrated Modular Avionics，综合模块化航电），其操作系统层面的分离机制由 ARINC 653 标准规定。类似的分区机制在汽车、工业控制里也都有。

麻烦立刻来了。认证标准有一条硬规矩：

如果不同关键度的功能共享同一资源、而你又证明不了它们之间的”充分独立性”（sufficient independence），那么它们全都得按其中最高的那个 SIL 来开发和认证。

也就是说，娱乐系统的代码如果跟飞控代码挤在同一个处理器上又没隔离，你就得用写飞控的流程去写娱乐系统——那基本等于把成本乘以好几倍。

反过来，标准也给了出路：只要能证明同时存在空间隔离和时间隔离，就可以让不同关键度共存。这就是分区（partitioning）。

1.3 一个贯穿全文的例子

论文用三个应用 ${\mathcal{A}}_1,{\mathcal{A}}_2,{\mathcal{A}}_3$ 组成的小系统做示范，后面几乎所有图都围绕它。

图 1(a)：三个不同关键度的应用（有向无环图），节点是任务，边上的数字是消息大小，图下方标注周期与截止期，任务旁标注 SIL。

注意几个细节：

• 每个任务是 DAG（有向无环图）里的一个节点 ${\tau }_j$，边表示数据依赖：前驱算完，后继才能开始。
• 同一个应用内部，任务的关键度也可以不同（比如 ${\mathcal{A}}_2$ 里混着 SIL 1 和 SIL 3 的任务）。
• 不同应用之间本文假设不通信。
• 通信还有一条限制：一个任务只能从关键度不低于自己的前驱那里接收输入。这条规则后面会在”关键度提升”里反复咬人。

所有任务在两个处理单元 $N_1,N_2$ 上的最坏执行时间（WCET）如下，N/A 表示该任务不允许映射到这个 PE：

表：图 1(b) 的 WCET 与映射限制

开发成本（单位：千欧元）随 SIL 变化的表格是本文的”钱袋子”，务必看懂它的形状：

表：图 1(c) 的开发成本（kEuro）

看 ${\tau }_{20}$ 这一列：SIL 1 是 2 千欧，SIL 2 是 4，SIL 3 是 9，SIL 4 是 16。每升一级，成本大致翻倍甚至更多。看 ${\tau }_{22}$：3 → 4 → 8 → 15。这就是”成本随 SIL 急剧上升”的量化含义，也是后面所有权衡的底层驱动力。

常见坑 1：把"关键度"当成"优先级"

优先级（priority）只是调度器排序用的一个数，改一下不影响认证。关键度（criticality / SIL）是写进认证档案的等级，改一下意味着整套开发流程、测试覆盖率、独立评审机构都要跟着换。论文里的”提升”（elevation）指的是后者，代价极大。

二、应用模型与开发成本：把”钱”也建模进去

2.1 应用模型：一张 DAG 加三个时间参数

系统里所有应用的集合记作 $\Gamma$。每个应用是一个有向无环图：

$${\mathcal{G}}_i({\mathcal{V}}_i,{\mathcal{E}}_i)\in \Gamma$$

其中每个节点 ${\tau }_j\in {\mathcal{V}}_i$ 是一个任务，每条边 $e_{jk}\in {\mathcal{E}}_i$ 表示”${\tau }_j$ 的输出是 ${\tau }_k$ 的输入”。

映射到哪个处理单元由函数 $M$ 决定，而这正是本文要优化的东西之一：

$$M:{\mathcal{V}}_i\to \mathcal{N}$$

$\mathcal{N}$ 是处理单元（PE）集合。对每个任务 ${\tau }_i$，它在候选 PE $N_j$ 上的 WCET $C_i^{N_j}$ 是已知输入（静态分析或测量得到）。

时间约束有三个：

• 周期 $T_{{\mathcal{G}}_i}$：应用多久跑一次。
• 截止期 $D_{{\mathcal{G}}_i}\le T_{{\mathcal{G}}_i}$：从应用启动到最后一个任务（汇点）完成，不得超过这个时间。
• 消息传输时间 $s_{m_i}$：跨 PE 通信时，消息在总线上占的时间，已知。

本文全部采用静态循环调度（Static-Cyclic Scheduling，SCS），非抢占。为什么？因为 SCS 是高度关键系统的首选：所有调度决定离线算好、烧进表里，运行期没有任何不确定性。这是可认证性最高的方案。（论文也提到固定优先级抢占调度 FPS 同样可以纳入框架，只是本文为简化讨论只用 SCS。）

2.2 SIL 分解：两个”半吊子”顶一个”高等级”

这是全文最有意思、也最反直觉的一个杠杆。

认证标准允许这样一件事：一个 SIL 3 的安全功能，你不必用单个 SIL 3 任务去实现，而可以用两个冗余的、更低等级的任务联合实现，比如一个 SIL 2 + 一个 SIL 1。因为两者互相备份，整体可靠性反而可能更高。

ISO 26262 Part 9 Section 5 给出的分解指南（论文表 I）：

表 I：ISO/DIS 26262 的 SIL 分解方案

这张表本质上是一套 SIL 代数：安全功能的 SIL 等于各冗余任务 SIL 之”和”。

$$SIL(\text{安全功能})=\sum _{k}SIL({\tau }_k^{\text{冗余}})$$

分解还能递归：比如 SIL 3 的那个子任务，可以继续拆成两个 SIL 1。

但这里有个致命前提：软件多样性（diversity）。如果几个冗余任务共用同一份代码，那么一个 bug 会让它们同时失效——这不是冗余，这是自我安慰。所以标准推荐用不同的实现，常见的做法是其中一个冗余任务用更简单、精度略低的算法。

来看论文的具体例子。图 4 是一个只有两个应用的小系统，用来专门演示分解：

图 4(a)：两个应用 ${\mathcal{A}}_1$ 与 ${\mathcal{A}}_2$，用于演示 SIL 分解

图 4(b)：这些任务在两个 PE 上的 WCET

图 4(c)：对应的开发成本（kEuro）

其中 ${\mathcal{A}}_1$ 的 ${\tau }_{11}$ 是 SIL 4 任务，设计师在分解库 $\mathcal{L}$ 里给了两个备选方案：

图 5(a)：任务 ${\tau }_{11}$ 的两个分解选项 $D_1$ 与 $D_2$

• $D_1$：拆成 ${\tau }_{11b}$（SIL 3）+ ${\tau }_{11c}$（SIL 1）。
• $D_2$：拆成 ${\tau }_{11f}$（SIL 2）+ ${\tau }_{11g}$（SIL 2）。

注意一个工程细节：分解后的任务不是凭空挂上去的，而是通过两个连接任务（connecting task）接回原图——${\tau }_{11a}$ 负责把输入分发给各个冗余副本，${\tau }_{11d}$ 负责收集输出（$D_2$ 对应 ${\tau }_{11e}$ 分发、${\tau }_{11h}$ 收集）。连接任务自身的 SIL 由工程师按标准确定。

分解后各任务的 WCET 与成本：

表：图 5(b) 分解后各任务的 WCET

表：图 5(c) 分解后各任务的开发成本（kEuro）

这里藏着一个非常现实的教训：分解并不总是省钱。${\tau }_{11}$ 不分解是 60 千欧；走 $D_1$（SIL3+SIL1）是 ${\tau }_{11b}$ 33 + ${\tau }_{11c}$ 9 = 42，加上连接任务开销，看着是省了；但走 $D_2$（SIL2+SIL2）是 14 + 13 = 27，明显更省。可是——分解会增加任务数量，而多出来的任务要挤进本就紧张的调度表，可能反而把系统搞成不可调度。这个”省钱 vs 可调度”的拉扯，正是后文优化算法要处理的核心。

2.3 开发成本模型

定义开发成本函数 $DC({\tau }_i,SILj)$：把任务 ${\tau }_i$ 按 SIL $j$ 开发并认证所需的成本。这个数由工程师根据经验和标准给出（论文指出，安全关键系统的开发流程高度结构化，因此这种估算是可行的；常用的成本模型如 COCOMO II）。

于是应用级成本就是求和：

$$DC({\mathcal{A}}_i)=\sum _{{\tau }_j\in {\mathcal{V}}_i}DC({\tau }_j,SIL({\tau }_j))$$

整个系统的开发成本是：

$$DC(\Gamma )=\sum _{{\mathcal{A}}_i\in \Gamma }DC({\mathcal{A}}_i)$$

为什么成本模型这么简单？

因为本文的重点不是”怎么估算软件成本”（那是另一个研究领域），而是在成本已知的前提下怎么优化。把成本当作一张查表，问题就变成了纯粹的组合优化。

三、系统模型：分区是怎么把任务”隔开”的