⏱️ 时序可预测性：实时嵌入式系统的地基（TECS 综述精讲）

这一篇在干嘛？

原文是 Building Timing Predictable Embedded Systems（Axer、Ernst、Falk、Girault、Grund 等 14 位作者，ACM TECS 13(4)，Article 82，2014 年，37 页），是一篇综述 + 路线图，不是某单个技术的论文。它要回答的核心问题是：当处理器为了”跑得快”引入了流水线、缓存、乱序执行、多线程、多核之后，我们还能不能在系统造出来之前就保证它”来得及”？文章依次从五个层面展开：可预测性的形式化定义 → 微体系结构（流水线/多线程/缓存/DRAM）→ 同步编程语言 → WCET 感知编译 → 多核与可靠性。最值得记住的结论有两条：其一，“可预测”是系统自身的固有属性，不是”某个分析工具能不能算出来”；其二，可预测性是用性能、面积、功耗换来的，没有任何一种手段是白拿的。

一、什么是”时序可预测”：平均快 ≠ 最坏可控

先从一个嵌入式工程师天天要面对的场景说起。

汽车里的安全气囊控制器，要求在碰撞信号产生后 10 毫秒内完成判断并点火。这个 10 毫秒就是** deadline（截止期）**。如果控制器平均只要 2 毫秒就能算完，听起来余量很大，是不是就安全了？

不。真正决定安全的是：在千万次运行里，最坏那一次用了多久。哪怕只有一次用了 12 毫秒，气囊就可能在错误的时刻弹出——这不是”有点慢”，这是事故。

于是我们有了三个必须分清楚的指标：

关键认知：实时系统关心的是 WCET，不是 ACET。 而后半句更要命——现代处理器架构几乎全部是围绕优化 ACET 设计的。缓存、分支预测、乱序执行、预取、DRAM 重排序……这些机制让平均性能提升了几倍甚至几十倍，却同时把”最坏情况”推到了一个非常难界定的地方。

这就是原文开篇那句”看似矛盾（paradoxically）“的话：

性能的提升，反而让时序保证变得更难给出。

1.1 为什么”留足余量”不是办法

工业界有一种自然的应对方式：超配（over-provisioning）——既然算不准最坏时间，就换一颗快十倍的芯片，总该够了。原文指出它有两个问题：一是保证不了，“我猜够了”和”我证明够了”是两回事，没有分析方法就不知道自己留的是 2 倍余量还是 0.8 倍；二是浪费资源，嵌入式系统常受功耗、成本、体积约束（想想电池供电的传感器节点），把芯片放大两倍可能根本不可行。

所以必须走另一条路：设计时就让系统的时序性质可被分析、可被证明。这就是可预测系统设计（predictable system design）。

1.2 时序要求会沿着系统层级向下传播

这是初学者最容易低估的一点——“实时性”不只是写调度器的人的事。一个”任务必须在 5 ms 内完成”的需求会逐级向下传导：系统级怎么划分和调度任务 → 软件级有没有不可控的循环、递归、动态内存分配 → 编译级生成的指令序列最坏路径是哪条 → 体系结构级这条指令在该流水线和缓存状态下最多花多少周期 → 电路级 DRAM 刷新与总线仲裁会不会插一脚。

任何一层不可预测，上层的所有分析全部失效。 这就是原文反复强调的”时序可预测性横切（cuts across）系统设计的全部层级”。

一句话心法

WCET 分析不能创造奇迹。它只能在被分析的机制本身是可预测的前提下，把这个可预测性算出来。如果硬件机制骨子里不可预测，再好的分析工具也只能给出一个巨大到没有意义的保守上界。

二、给”可预测性”下一个精确定义

原文第 2 节干了一件在此之前没人认真做过的事：给”可预测性”下一个形式化定义。

在此之前，大家判断”这个机制可不可预测”靠的是直觉。比如表 I：

这张表工程师一看就点头，但它是经验表，不是定义。凭什么 LRU 就比 FIFO 可预测？能不能量化？原文认为，如果没有精确定义，就会出两类问题：

• 研究者花大力气为本质上不可预测的系统开发分析工具（白费劲）；
• 研究者把本来就很可预测的部件拆掉重做（帮倒忙）。

2.1 可预测性的四个关键要素

原文提出，“可预测性”这个概念必须包含四件事：

要素一：要预测的属性（property）是什么。 系统的行为可以用一组（可能无限的）执行轨迹描述，但预测通常针对轨迹的派生性质——比如”这条轨迹有多长”（执行时间）、“某个事件有没有发生”。有的属性可预测，有的不可预测，所以必须先说清楚预测什么。

要素二：不确定性的来源（sources of uncertainty）是什么。 预测要对所有可能情况成立。对程序执行时间而言，不确定性来自两处：

• 程序输入（不同的输入走不同的分支、循环不同次数）；
• 初始硬件状态（缓存里装的是什么、流水线里有没有残留指令、分支预测器处在什么历史）。

要素三：预测的质量度量（quality measure）。 可预测性不该是布尔值（可预测/不可预测），而应该是一个连续的灰度，这样我们才能说”A 比 B 更可预测”。

要素四：固有性（inherence）。 这是原文最强调、也最有哲学味道的一点。

仅仅是”某个分析工具算不出 A 的性质、但能算出 B 的”，并不意味着 B 比 A 更可预测。可能只是这个工具恰好更适合 B，而 A 其实存在更好的分析方法。

也就是说：可预测性是系统自身的属性，不是”相对于某个分析工具”的属性。

综合四条，原文给出核心论点（Thesis 2.1）：

可预测性应当刻画：一个系统的某个指定属性，能否被”针对该系统而言最优的分析”预测出来，以及能精确到什么程度。真正限制精度的，是不确定性的来源。

2.2 可预测性模板

因为要素一、二、三都依赖具体系统，原文提出的是一个**模板（template）**而不是单一公式：

可预测性 = ( 待预测属性 , 不确定性来源 , 质量度量 )

落到”时序可预测性”这个具体实例上：

• 待预测属性：程序在一给定硬件平台上、不被打断地执行完所需的时间。
• 不确定性来源：程序输入 + 初始硬件状态。多核场景下还包括其他核对共享资源的竞争（原文把并发线程的状态和输入也归入前两者）。
• 质量度量：BCET / WCET 的比值，越接近 1 越好。
• 固有性：满足，因为 BCET 和 WCET 是系统固有的。

2.3 时序可预测性的形式化

设 $\mathcal{Q}$ 为所有硬件状态的集合，$\mathcal{I}$ 为所有程序输入的集合。记 $T_p(q,i)$ 为程序 $p$ 在初始硬件状态 $q\in \mathcal{Q}$、输入 $i\in \mathcal{I}$ 下的执行时间。

定义 2.2（时序可预测性）：给定初始硬件状态的不确定性集合 $Q\subseteq \mathcal{Q}$ 与程序输入的不确定性集合 $I\subseteq \mathcal{I}$，程序 $p$ 的时序可预测性为

$${\mathrm{Pr}}_p(Q,I):=\underset{q_1,q_2\in Q}{\min }\underset{i_1,i_2\in I}{\min }\frac{T_p(q_1,i_1)}{T_p(q_2,i_2)}$$

怎么读这个式子？分子取”最慢的那对（状态, 输入）“里最慢的吗？不是——双重 min 配一个比值，效果是：在所有状态对、所有输入对里，找出最慢执行时间与最快执行时间的比值最小的那一对。换句话说，它度量的是”最坏能比最好坏多少倍”的下界：

• ${\mathrm{Pr}}_p=1$：完美可预测，任何状态、任何输入下执行时间都一样；
• ${\mathrm{Pr}}_p\to 0$：极端不可预测，最坏情况比最好情况慢若干个数量级。

原文坦承：这个量对大多数系统是不可计算的（incomputable），就像停机问题一样不存在通用求解程序。但这不妨碍它成为一个有意义的定义——我们实际做的是计算它的上界/下界近似。

2.4 拆开看：硬件导致的 vs 软件导致的

把两个不确定性来源分开，能得到两个更有诊断价值的量。

定义 2.3（状态诱导的时序可预测性，SIPr）：固定输入，只让硬件状态变：

$${\mathrm{SIPr}}_p(Q,I):=\underset{q_1,q_2\in Q}{\min }\underset{i\in I}{\min }\frac{T_p(q_1,i)}{T_p(q_2,i)}$$

这个量刻画的是纯硬件带来的时间抖动——缓存冷启动 vs 热启动、流水线空 vs 满。

定义 2.4（输入诱导的时序可预测性，IIPr）：固定硬件状态，只让输入变：

$${\mathrm{IIPr}}_p(Q,I):=\underset{q\in Q}{\min }\underset{i_1,i_2\in I}{\min }\frac{T_p(q,i_1)}{T_p(q,i_2)}$$

这个量刻画的是纯软件带来的时间抖动——不同输入走不同分支、循环次数不同。

三者满足关系：

$${\mathrm{IIPr}}_p(Q,I)\cdot {\mathrm{SIPr}}_p(Q,I)\le {\mathrm{Pr}}_p(Q,I)\le \min ({\mathrm{IIPr}}_p(Q,I),{\mathrm{SIPr}}_p(Q,I))$$

推论很有用：只要 IIPr 或 SIPr 其中之一等于 1，那么整体的 Pr 就等于另一个。也就是说，如果你把软件写成”无论输入如何都走同一条指令序列”，那么剩下的不可预测性就全部来自硬件，可以专心治硬件；反之亦然。

2.5 四个判例

原文给了四个极简例子，值得逐一琢磨。

例 2.5：可预测的软件，IIPr 仍可能 < 1。 考虑一个”不管输入是什么都执行同一条指令序列”的程序。直觉上 IIPr 应该等于 1。但不一定——如果这个处理器有变延迟指令（最典型的是除法，除数和被除数的取值会影响迭代次数），而操作数又依赖输入，那么即使指令序列相同，执行时间还是会随输入变。

例 2.6：不可预测的软件。 一个循环，循环次数由输入值决定。如果输入集里既有让循环跑 1 次的、也有让循环跑 100 万次的，那么 IIPr 会接近 0。

这条直接推出一条工程铁律

实时代码里的循环必须有静态可知的（最好是有界的、甚至固定的）迭代次数。 这也是为什么航空、汽车领域的编码规范（如 MISRA C）明令禁止无界循环和递归。

例 2.7：可预测的硬件。 如果某微体系结构上，指令执行时间完全不依赖硬件状态（例如 PTARM，一种 precision-timed ARM 实现），那么 ${\mathrm{SIPr}}_p(Q,I)=1$ 恒成立。

例 2.8：不可预测的硬件。 考虑一段通过以太网发一个报文的程序。以太网冲突后采用二进制指数退避（binary exponential backoff）：第 $n$ 次冲突后，重传要随机等待 $[0,2^n-1)$ 个时隙。如果初始状态 $q_1$ 触发了一连串冲突，另一个初始状态 $q_2$ 没触发，那么 SIPr 会非常低。

2.6 执行时间的分布与”sound 但不精确”

图 1：执行时间的分布——从 BCET 到 WCET。 横轴是执行时间，纵轴是出现的可能性。真实系统在一个输入集、一个状态集上跑出来的执行时间会形成一条分布曲线，曲线的左端点就是 BCET，右端点就是 WCET。静态分析工具给出的下界 LB 与上界 UB 必须”包住”真实曲线（soundness，可靠性：LB ≤ BCET ≤ WCET ≤ UB），但两者之间往往存在间隙（incompleteness，不完备性）。LB 与 UB 的差距越小，说明分析越精确，也间接说明系统越可预测。

两个词的中文对照，别搞混

sound（可靠的）：分析结果不会低估真实最坏情况——“安全”。 precise / tight（精确的）：分析结果离真实值很近——“不浪费”。 一个分析可以”很安全但很不精确”（比如把所有循环都当成跑一亿次），这样的结果虽然正确，却会让系统严重超配。WCET 研究的全部努力，就是在保持 sound 的前提下尽量 tight。

三、微体系结构：性能的代价

指令集体系结构（ISA，Instruction Set Architecture）定义的是软硬件之间的契约：二进制格式 + 输入/输出语义。

注意：执行时间不在 ISA 的语义里。

这是当年一个有意为之的设计决定——它给了微体系结构设计者极大的自由，于是有了流水线、超标量、分支预测、缓存……也正因为如此，WCET 分析必须下沉到具体的微体系结构实现。同一个 ARM 指令集，不同实现可以有天差地别的执行时间。

对最简单的、无流水线无缓存的处理器，求一串指令的执行时间就是把每条指令的时间加起来。有了流水线和缓存之后：

• 相邻指令的执行时间相互重叠，不能孤立看待；
• 每条指令的时间依赖到达它之前发生了什么（执行历史）：
  • 紧跟在写同一寄存器后面的读，会引发流水线停顿（data hazard）；
  • 循环里第一次取指令是 cache miss，后面几次是 cache hit。

3.1 微体系结构的三分类

原文引用 Wilhelm 等人的分类，按**是否存在时序异常（timing anomaly）和多米诺效应（domino effect）**把微体系结构分成三档：

“可组合”（compositional）是什么意思？ 就是”整体的最坏 = 各部分最坏之合”。有了这个性质，分析可以分而治之、逐块求最坏然后相加，复杂度从指数级降到线性级。ARM7 甚至更友好：一旦发生时序意外（timing accident），整条流水线所有部件一起停住直到解决，所以缓存、总线占用等方面的惩罚可以分开算再直接加到 BCET 上。

3.2 时序异常：局部最坏 ≠ 全局最坏

时序异常（timing anomaly） 由 Lundqvist 和 Stenström 于 1999 年提出。直觉表述是：

局部的最坏情况，并不贡献到全局的最坏情况。

这听起来违反直觉，但看图 2 就明白了。

图 2：时序异常的两种典型情形（取自 Reineke et al. 2006）。左图是调度异常：把指令 A 缩短之后，整体调度反而变长了——因为 A 提前完成，让指令 B 有机会去阻塞”更重要”的指令 C。右图是推测异常：分支预测失败会导致不必要的取指，这些取指可能 miss 缓存；而在预测正确的情况下，处理器反而可能预取到更多指令。左右两图共同说明一件事：“让某一步变快”可能让”整体变慢”。

这个性质对分析工具的杀伤力是致命的。分析工具为了效率，最想做的事就是”每一步都只保留最坏的那个转移”（比如一律假设 cache miss、一律假设流水线停顿）。在存在时序异常的系统上，这种做法是不 sound 的——你必须保留所有可能的后继状态，状态空间随之爆炸。

3.3 多米诺效应：差距可以无限拉大

多米诺效应（domino effect） 比时序异常更凶。定义是：存在两个硬件状态 $q_1$、$q_2$，使得同一条程序路径从这两个状态出发的执行时间之差，与路径长度成正比——也就是说，不存在一个常数能把这个差距在所有可能的程序路径上界住。

形式化地：设 $p$ 是一个执行长度可任意长的程序（取决于输入），$I_n$ 表示使 $p$ 执行长度恰为 $n$ 的指令序列的那些输入。若

$$\underset{n\to \infty }{\lim }{\mathrm{SIPr}}_p(Q,I_n)<1$$

则系统存在多米诺效应。

PowerPC 755 上的实例（Schneider 2003）：该处理器有两个不对称的整数执行单元、一个贪心的指令分派器，加上一段带写后读依赖的指令序列。贪心分派器的决策使得：初始流水线为空时执行更慢，初始流水线半满时执行更快。而且这段序列执行完之后的流水线状态等价于初始状态，所以可以无限重复。连续执行 $n$ 次：

• 从状态 $q_1^{\ast }$ 出发：耗时 $9n+1$ 个周期；
• 从状态 $q_2^{\ast }$ 出发：耗时 $12n$ 个周期。

代入 SIPr 的定义：

$${\mathrm{SIPr}}_p(Q,I_n)\le \frac{T_p(q_1^{\ast },i^{\ast })}{T_p(q_2^{\ast },i^{\ast })}=\frac{9n+1}{12n}$$

取极限：

$$\underset{n\to \infty }{\lim }{\mathrm{SIPr}}_p(Q,I_n)\le \frac{3}{4}<1$$

差距随 n 线性增长，永不收敛。 这就是为什么 PowerPC 755 被归为”不可组合”——你必须完整地跟踪流水线状态，不能做任何局部化近似。

原文还提到 Berg (2006) 发现的另一个多米诺效应：缓存的 PLRU 替换策略也会产生多米诺效应。这在 3.5 节会看到量化结果。

3.4 流水线的分析复杂度

对无流水线架构，把基本块内各指令时间相加即可得到界。有了流水线，必须把指令作为一个整体、连同相互作用一起分析。

分析方法基于流水线的抽象模型：一次状态转移对应处理器的一个机器周期。所有影响时序的部件都必须被保守地建模。

复杂度来自哪些地方？原文列得很清楚：

• 超标量 + 乱序 → 可能的交错（interleaving）数量暴涨；
• 缓冲区越大（取指缓冲、重排序队列……）→ 历史事件的影响持续得越久；
• 动态分支预测、类缓存结构、分支历史表 → 历史依赖性更强。

抽象状态可能缺少某些部件（缓存、队列、预测器）的具体信息，导致本来确定性的流水线在抽象模型里变成非确定性的。此时如果不加考虑地只挑”局部最坏转移”，在时序异常存在时就不 sound。

一个反直觉的实验结果

Maksoud 与 Reineke (2012) 发现：缩小 load-store 单元的缓冲区，有时能同时改善性能和分析时间。这说明”更复杂的硬件 = 更快”这个假设本身在实时场景里就不成立——复杂性带来的分析代价可能远超它换来的那点性能。

一种工程上的折衷（Rochange & Sainrat, 2005）是：在每个基本块开始时规整化流水线中的指令流，从而切断基本块之间的时序依赖，让 WCET 分析可以对每个基本块独立进行。作者们还给出了一个很实用的可预测性判据：

如果计算 WCET 所需的计算量或存储量达到”令人望而却步”的程度，那么这个处理器就可以被判为不可预测的。

也就是说：可预测性不只看”能不能算”，还要看”算不算得起”。

3.5 多线程：从互相干扰到时间隔离

多线程/多核带来了新的干扰源，但也带来了新的机会（单线程的时序模型往往更简单）。原文梳理了三条路线：

路线 A：改造同时多线程（SMT）。 Barre 等 (2008)、Mische 等 (2008) 修改线程调度策略，让一个实时线程优先于所有非实时线程，于是实时线程感受不到干扰，可脱离上下文独立分析。代价：只保证了实时线程的时间隔离；若要跑多个实时任务，还得在实时线程内部再分时。

路线 B：虚拟多处理器（virtual multiprocessor）。 El-Haj-Mahmoud 等 (2005) 的静态方案：把处理器切成不同的时间片和超标量通路（way），由调度器离线构造线程执行时间表。好处是为所有线程提供时间隔离，代价是任务必须事先确定。

路线 C：PTARM（线程交错流水线）。 PTARM 是 PRET（Precision-Timed，精确计时）机器的一员，实现 ARM 指令集，采用含 4 个硬件线程的五级线程交错（thread-interleaved）流水线：不做动态线程调度，而用可预测的 round-robin，每周期从不同线程取一条指令，从而自然消除来自流水线资源的数据相关停顿，流水线利用率达 100%——但单个硬件线程的性能被限制在 1/4。由于硬件线程之间互不影响彼此的调度，任务不必事先绑定到某线程，且所有硬件线程都能用于实时任务（不像路线 A 只有一个）。

3.6 缓存：WCET 分析的头号障碍

处理器与大容量存储器之间的速度差有几个数量级，于是必须有存储层次。缓存是这个层次的关键一环，而替换策略（replacement policy）被硬连线在硬件里，与上面跑的应用无关。

缓存替换策略的可预测性

类比 SIPr，可以定义状态诱导的缓存可预测性（SICPr）。设 $M_p(q,s)$ 为替换策略 $p$ 在初始缓存状态 $q$ 下、访问长度为 $n$ 的序列 $s$ 所产生的 miss 次数，$B_n$ 为所有长度为 $n$ 的访问序列集合：

$${\mathrm{SICPr}}_p(n):=\underset{q_1,q_2\in Q_p}{\min }\underset{s\in B_n}{\min }\frac{M_p(q_1,s)}{M_p(q_2,s)}$$

原文用工具 RELACS 自动计算了 ${\lim }_{n\to \infty }{\mathrm{SICPr}}_p(n)$，结果如下（相联度从 2 到 8；PLRU 只在 2 的幂次上有定义）：

这张表是全文最有说服力的量化结果之一，值得逐行读：

• LRU（Least Recently Used，最近最少使用）：全部为 1。 意味着 LRU 缓存不存在缓存多米诺效应——初始状态对长期 miss 次数的影响可以被完全界住。1 是最优值，没有策略能做得更好。
• FIFO：1/k（k 为相联度）。 相联度越高越糟糕。FIFO(k) 在不同初始状态下，miss 数最多能差 k 倍。
• PLRU（Pseudo-LRU，伪 LRU）：高相联度下直接掉到 0。 相联度为 2 时 PLRU 与 LRU 等价（所以是 1），但从 4 路开始，从一个状态出发的 miss 次数根本无法用另一个状态出发的 miss 次数去界定。这就是 Berg 发现的 PLRU 多米诺效应的量化体现。
• RANDOM：全 0。 完全不可预测，毫不为奇。

工程启示

如果你的实时平台允许选缓存替换策略，选 LRU。PLRU 因为硬件实现更省面积被大量商用处理器采用（包括很多 PowerPC、ARM），但从可预测性角度看它是灾难性的——相联度 8 路的 PLRU 缓存，理论上初始状态的影响可以无界放大。

共享缓存上的干扰

更糟的是：缓存本身不提供时间隔离。同一个应用、同样的输入，仅仅因为开始执行时缓存里装的东西不同（而这取决于之前跑过的应用访问了什么），性能就可能天差地别。用原文的措辞：一个应用的时间行为依赖于其他应用执行了哪些内存访问。

便签存储器（SPM）：把控制权交回软件

便签存储器（Scratchpad Memory, SPM） 是缓存的替代品：

• 物理介质相同（都是 SRAM，静态随机存取存储器，访问延迟恒定且低）；
• 但内容由软件控制：SPM 是可寻址存储空间的一部分，软件负责在 SPM 与下层存储之间搬运指令和数据；
• 访问 SPM 的延迟低、可预测且可重复。

代价是：就像寄存器文件一样，正确使用 SPM 的责任落到了编译器（或程序员）头上。这在 SPM 要被多个应用共享时尤其困难。

但机会也在这里：SPM 的管理可以针对具体应用量身定制，而不像缓存那样被硬连线的替换逻辑锁死。

3.7 DRAM：存储层次里最不可预测的一环

再往下一层是 DRAM（Dynamic RAM，动态随机存取存储器）。容量远大于 SRAM，代价是延迟更高、且变化更大。

常规 DRAM 控制器完全不提供时间隔离，原因有四：

1. 访问延迟依赖历史：前面访问过哪些行、哪些 bank，决定这次要多久；
2. 需要周期性刷新：DRAM 单元会漏电，每一行必须定期刷新，刷新期间不能发出读写，而且刷新还会改变访问历史，进而影响未来访问的延迟；
3. 控制器会重排访问：为了少开行、降低延迟，现代控制器会重排请求顺序；
4. 共享总线的竞争：数据总线和命令总线被所有 bank 共享，需要仲裁；刷新命令的插入时机从客户端角度看也不可预测。

近年出现的可预测 DRAM 控制器用两类手段解决：

• 混合静态/动态访问方案，大幅消除访问时间的历史依赖，从而界定单次请求的延迟；
• 可预测的仲裁机制：Predator 项目的 CCSP、AMC 的 TDM（时分复用），都能界定不同客户端之间的干扰；
• 刷新按保守假设计入（假设任何事务都可能与刷新冲突）；
• Reineke 等 (2011) 的做法是按 DRAM 器件内部结构划分物理地址空间（bank privatization），从根上消除器件内共享资源的竞争，并用”低延迟的手工行访问”替代专用刷新命令，进一步压低最坏延迟。

3.8 小结：微体系结构层面的现状

• 已经能识别出一类允许高效分析的微体系结构（如完全时序可组合架构），但目前分类仍然靠资深工程师的信念；
• 只有遵循极简时序模型的架构（如 PTARM）能被高置信度地归类；
• “时序可组合性”的精确形式化定义、以及判定给定架构是否可组合的有效方法，至今仍然缺失；
• 单个部件（私有缓存、内存控制器）的情况稍好一些；
• 如何从可预测部件组装出”既可组合又真正高性能”的微体系结构，目前还没有章法。

四、同步编程语言：把”时间”写进语言

前面三节都在硬件层打转。原文第四节上移一层：能不能让程序员直接在语言层面控制时间？

两条技术路线：

• 路线一（第五节）：保留传统做法——任务各自用 C 写，由静态时序分析工具给程序片段标注时间信息。好处是解放程序员（不用手工估 WCET），但调度、协调、避免竞争与死锁仍然要人来做。
• 路线二（本节）：基于同步编程语言（synchronous programming languages）——用显式构造表达并发活动的协调、通信与对外交互，语言自带形式语义，保证确定性执行、无竞争、无死锁。

4.1 同步抽象：假装处理器无限快

同步语言的核心武器是逻辑节拍（logical tick）：

一个同步程序以一串**离散的反应（reaction / tick）**对外界做出响应；同一个 tick 内的计算被视为瞬时完成、彼此同步。

也就是说，同步程序表现得好像执行它的处理器无限快。

这个抽象和硬件设计里的**同步电路（synchronous circuit）**如出一辙：在 HDL 的抽象层级上，电路也是以离散反应推进的，逻辑门表现得好像电子跑得无限快。

同步 vs 异步并发，本质区别在哪？

Esterel 的例子：every 60 second emit minute 表示信号 minute 与信号 second 的第 60 次出现严格同步。同步语言还有第二个特征：它们是有限状态的——不允许任意循环或递归，这是可预测性的又一前提。

这套思路在工业上极其成功：Lustre 的工业版本 Scade 被广泛用于民用飞机（Airbus）和轨道交通领域。

4.2 同步抽象怎么落地？算 WCRT

当然没有处理器真能无限快，它只需要比环境快。同步程序被嵌在一个周期性执行循环里：

loop {
    read inputs;   // 读输入
    react;         // 反应
    write outputs; // 写输出
} each tick

设计者必须验证同步抽象成立，步骤是：

1. 计算程序的 WCRT（最坏反应时间），定义为上述周期循环体的 WCET；
2. 检查 WCRT 是否小于系统需求施加的实时约束。

这个 WCRT 也叫”节拍长度（tick length）”。

为了让抽象成立，同步语言对一次反应内部的控制流施加限制，最典型的一条：反应内部不允许循环——每个循环体内必须有一个节拍屏障（tick barrier），比如 Esterel 的 pause、PRET-C 的 EOT。编译器通常要能静态验证这一点。

这不只是保守措施，它还是两件事的前提：

• 证明程序是因果的（causal），即不同求值顺序不会导致不同结果；
• 把程序编译成有界时间、有界内存的确定性顺序代码。

对时序可预测性而言，还需要更多：光知道循环次数上界不够，必须精确知道次数才能算出精确执行时间。

另外，为了让工业界接受，同步语言必须提供与通用语言相当的数据操作能力。这就是为什么原文介绍的两个语言——PRET-C 和 Synchronous C (SC)——都是基于 C 的。

语言的”负面清单”（与安全关键领域 C 编码规范高度一致）：

• 指针
• 递归数据结构
• 动态内存分配
• 带副作用的赋值
• 递归函数
• 变长循环

理由很朴素：人类容易审读的代码，WCRT 分析器也容易分析。

4.3 PRET-C 与 Synchronous C：用 C 写同步程序

Berkeley-Columbia PRET 语言与 DEAD 指令

图 3(a)：生产者-消费者-观察者（PCO）例子的 Berkeley-Columbia PRET 版本（取自 Lickly et al. 2008）。三个线程（Producer / Consumer / Observer）共享一个整型变量 buf，通过特殊的 DEAD(t) 指令调度：DEAD(t) 的行为是——线程执行的第一条 DEAD(t) 在”自线程启动起至少经过 t 个指令周期”时结束；后续 DEAD(t) 在”自前一条 DEAD(t) 结束起至少经过 t 个指令周期”时结束。图中三个线程用 DEAD 指令保证 Producer 跑在前面，并让三个线程以每 26 个指令周期一次迭代的方式严格同步（lockstep）地穿过 for 循环。

注意 DEAD 指令的语义细节：它只能强制执行时间的下界（“至少要花 t 个周期”），不能强制上界。但只要给 DEAD 赋一个相对于 WCET 而言保守的值，就能设计出可预测的多线程系统——竞争条件靠 DEAD 造成的确定性交织被消除。

这种做法的优点是：利用 PRET 架构的可预测时序，不需要操作系统或语言提供显式的调度/同步设施。 缺点是：这是一种脆弱的、低层的、不可移植的调度风格——一旦换了处理器，所有 t 值都要重算。

而这个”lockstep”的并发线程执行方式，恰恰就对应着同步语言里的逻辑节拍概念。于是自然可以改用同步语言来写，不需要低层显式同步。

Synchronous C（SC）

图 3(b)：同一个 PCO 例子的 Synchronous C（SC）版本。 调度需求改用**显式的线程优先级（1–4）**表达。扩展后的 PCO 例子增加了两项行为：当 buf 达到 10 时重启线程，当循环下标 k 达到 20 时终止线程。main() 里的循环反复调用 tick() 函数，后者实现一个逻辑节拍的反应行为：MainThread 以优先级 1 运行，包含状态 PCO 和 Done；状态 PCO 用 FORK3 派生出另外三个线程。响应式控制流由 SC 的运算符管理：FORKn（以指定优先级派生 n 个线程）、TRANS（中止子线程并转移控制）、TERM（终止线程）、PAUSE（挂起线程直到下一个节拍）。线程的执行状态静态存放在 sc.h 声明的全局变量里。

关键点：SC 程序最终是一个普通的、完全确定性的、无竞争、不依赖操作系统的顺序 C 程序。 PRET-C 同理。

对比两图，可以看到 SC 版本的两个改进：

• 增加了**抢占（preemption）**功能；
• 物理时间与功能分离：用引用逻辑节拍的 PAUSE，取代引用指令周期的 DEAD。

不过两者都保留了”由程序员指定一个节拍内线程执行顺序”的做法——即 FORK3 里给出的优先级顺序（Producer 优先级为 4，依此类推）。

两者的差异：

4.4 响应式处理器：把同步语义做进指令集

同步语言既能描述软件也能描述硬件。响应式处理器（reactive processor）走中间路线：把同步程序编译成机器码，跑在一个指令集直接实现同步响应式控制流构造的处理器上。

可预测性上的核心好处：ISA 直接支持语言的关键特性（抢占、同步、线程间通信），从而能对”每条高级指令需要多少个机器周期”做到非常精细的控制。

“语言特性”与”处理器/ISA”协同设计这个思路，正是 Berkeley-Columbia PRET 方案的出发点。一句话总结两者的对偶关系：

面向同步编程的 ISA 在”执行平台层”提供可预测性，同步语言构造在”语言层”提供可预测性。

实例：

• 第一个响应式处理器是 REFLIX（Salcic 等, 2002）；
• ARPRET（Auckland Reactive PRET）把响应式处理器概念适配到 PRET-C：围绕一个定制的 MicroBlaze 软核，通过两条快速单工链路连接一个”功能可预测单元（Functional Predictable Unit）“来维护各并行线程的上下文，使线程上下文切换能在常数个时钟周期内完成（调度器受 CEC 调度器启发）。基准测试显示：相比独立 MicroBlaze，WCRT 降低 26%；
• KEP（Kiel Esterel Processor） 包含一个 Tick Manager，用于最小化反应时间抖动并检测超时。

4.5 同步程序的 WCRT 分析

比普通 WCET 分析更难的地方：这里包含并发和抢占，而经典 WCET 计算通常把并发/抢占分析甩给操作系统。

但两个因素使紧估计成为可能：同步的确定性语义 + 编码规则（如禁止无节拍屏障的循环）。

具体工作：

• SC / KEP：开发了含 WCRT 分析的编译器（Boldt 等, 2008），后用模块化代数方法改进，把信号取值纳入考虑以排除不可行路径；
• PRET-C / ARPRET：把控制流图（CFG）用”在 ARPRET 上执行所需的机器周期数”装饰，再用模型检查工具 UPPAAL 计算 WCRT；把抽象状态空间与表达力强的数据流信息结合，可以丢弃不可行路径；
• Esterel / CEC 编译器：Ju 等 (2008) 用**整数线性规划（ILP）**消除生成 C 代码中的不可行路径，从而生成更可预测的代码。

4.6 小结与挑战

PRET-C 和 SC 的同步语义直接提供了设计复杂可预测系统所必需的若干性质：确定性、线程安全通信、因果性、无竞争条件等等，把设计者从异步并发的诸多苦恼中解放出来。

不过原文的判断很清醒：

同步概念何时能进入实时系统的主流编程，与其说是同步语言本身或其综合/分析过程是否成熟的问题，不如说是”如何把它们嵌入今天已经根深蒂固的编程与架构范式”的问题。

可能的出路有两条：一是用一小组同步/响应式操作增强 C 这样的广泛使用语言；二是从编程层上移到建模层——那里并发与抢占本来就已经是内建的。

五、WCET 感知编译：让编译器看见时间

嵌入式软件开发普遍用 C（常由 Matlab/Simulink 之类工具自动生成）。C 编译器有大量优化，但它们的目标是降低 ACET，而且根本没有时序模型。

一个常被忽视的事实

编译器的优化可能严重恶化 WCET。 比如激进的循环展开能降低平均时间，却可能让代码体积膨胀、把热点代码挤出缓存。

于是工业界常见做法是关掉大部分甚至全部优化，再把产出代码手工喂给时序分析器——只有走到设计流程最后一步才能验证时序约束是否满足，不满足就回去改图形化设计，希望重新生成的代码 WCET 更低。

这是三重浪费：没有工具帮助设计者有目的地降低 WCET；因为用未优化代码，硬件资源被严重超配；整个流程手工、迭代、靠运气。

WCET 感知编译器（WCET-aware compiler） 的三重收益：

1. 引入形式化的最坏情况时序模型，让编译器对程序最坏行为有清晰概念；
2. 该模型被专门的优化所利用，从而降低 WCET——于是可以用未优化代码 → 可以用更便宜的硬件 → 免去了手工降低自动生成代码 WCET 的苦差；
3. 手工 WCET 分析不再需要，由编译器透明完成。

5.1 WCET 感知编译器的基础设施

关键认识：光开发新的激进优化是不够的，WCET 感知优化严重依赖一整套提供形式化时序模型、控制流模型、硬件模型的基础设施。

（1）把静态 WCET 分析集成进编译器

最早的尝试（Zhao 等, 2005a）把一个自研 WCET 分析器集成到操作于低级中间表示（IR）的编译器里。控制流信息传给分析器，分析器算出路径、循环、函数的最坏时序再回传。问题：

• 粒度太粗：只有路径/循环/函数的 WCET，没有基本块或单条指令的，无法优化更小的单元；
• 信息缺失：基本块执行频度、寄存器取值范围、预测的缓存行为等都拿不到；
• 层次太低：时序数据不在源代码层提供，无法做源代码层的 WCET 优化。

这些缺陷在 WCC（WCET-aware C Compiler） 中被解决：编译器后端集成了静态 WCET 分析器 aiT。机制是：

• aiT 分析时把程序和结果存在一种叫 CRL2 的 IR 里；
• WCC 把自己的汇编级 IR 双向翻译成 CRL2；
• 编译器产出 CRL2 文件 → 透明调用 aiT → 把结果导回编译器。

回传的信息包括：整个程序/单个函数/单个基本块的 WCET；函数或基本块的最坏执行频度；寄存器值的近似；每个基本块的 cache miss 数。

（2）存储层次的规格说明

很多系统的性能由存储子系统主导，时序估计严重依赖存储器。因此 WCET 感知编译器必须向时序分析器提供存储层次的详细信息——这件事在传统编译流程里是链接器干的。

WCC 的做法：允许直接描述存储层次——每块物理内存可定义基地址、长度、访问延迟等属性；缓存可定义大小、行大小、相联度等。内存分配由编译器而非链接器完成，把函数、基本块或数据分配到这些区域。编译器算出的物理地址还会被用于 WCET 分析（跳转目标从符号块标签翻译成物理地址），从而大幅提高精度。

（3）流事实的规格说明与变换

程序的执行时间很大程度上取决于控制流（循环、条件分支）。循环迭代次数对精确 WCET 至关重要，而它一般无法自动算出，必须由分析器的用户指定——这种用户提供的标注叫流事实（flow facts）。

核心难题：编译器优化会重组代码，从而使高层流事实失效。

历代方案：

WCC 的流事实种类：

• 循环边界流事实：限制常规循环的迭代次数；相比前人，WCC 允许同时指定最小和最大迭代次数，从而可以标注数据依赖的循环；
• 流限制（flow restrictions）：用于不规则循环或递归，把某条 C 语句的执行频度与其他语句关联起来。

WCC 最关键的设计：所有创建、删除、移动语句或基本块的 IR 操作都会内在地更新流事实。因此无论优化在何时、以何种方式修改 IR，流事实始终是安全且精确的。

5.2 三种 WCET 感知优化及实测效果

原文介绍了三类，全部有量化结果。

优化一：SPM 分配与缓存锁定（cache locking）

SPM 和锁定缓存的时序完全可预测，是 WCET 中心优化的理想目标。

• Suhendra 等 (2005)：第一个 WCET 感知 SPM 分配方案，用 ILP（整数线性规划）建模函数 CFG 结构，常数表示基本块分配到慢速 flash 或快速 SPM 时的最坏时间。缺点：无法把代码分配到 SPM，且有多项限制使其无法用于真实代码。
• Falk & Kleinsorge (2009)：补上了代码分配、跳转惩罚、全局控制流，使 ILP 能感知整个程序中执行时间最长的那条路径，从而最优地最小化程序 WCET。类似方法也可支持缓存锁定。

实测（Infineon TriCore TC1796，来自 UTDSP / MediaBench / MiBench 的 73 个基准）：

优化二：代码布局（code positioning）

代码布局是改善 I-cache 行为的经典优化：把代码片段连续地映射到内存，避免缓存组重叠，从而减少冲突 miss。

WCC 的做法（Falk & Kotthaus, 2011）：

1. 建立缓存冲突图（conflict graph, CG）：节点是函数或基本块；两节点在缓存中互相干扰（可能互相驱逐）时连一条边；
2. 用集成的时序分析能力计算边权重，近似该 CG 节点执行期间可能产生的 cache miss 数；
3. 在冲突图上跑启发式：每轮把权重最大的边连接的两个基本块/函数连续放置；
4. 每做一步就重跑一次时序分析——WCET 下降就保留，否则撤销。

实测（Infineon TC1797，18 个真实基准）：

优化三：面向多任务系统的缓存分区（cache partitioning）

前两类优化无法处理带抢占式调度的多任务系统，因为上下文切换期间的缓存行为难以预测。

缓存分区的思路：给系统中每个任务独占分配一个缓存分区，任务只能驱逐属于自己分区的缓存行。于是多任务之间在上下文切换时不再通过缓存互相干扰，每个任务可以独立地做静态时序分析。整个系统的 WCET = 各任务在给定分区大小下的最坏时序 + 调度与上下文切换开销。

WCC 的实现（Plazar 等, 2009）用 ILP 最优地确定各任务的分区大小。

实测： 应用于 5、10、15 个任务的任务集，相比朴素的”按代码大小分配”启发式，WCET 最高降低 36%。一般规律：缓存越小收益越高，任务集越大优化潜力越大。

5.3 小结与挑战

上述优化之所以有效，本质上都是提升了状态诱导的时序可预测性（SIPr）——它们大幅减少了对缓存（缓存锁定与分区、代码布局）和 flash（SPM 分配）硬件状态的不确定性。

最大的未解难题：一旦进入多任务或多核系统，这些方法大多失效。 共享资源（流水线、缓存、存储器、总线）使得一个任务的时序会随其他任务（甚至其他核上的任务）的活动而变化。这些干扰目前还没有在代码生成与优化阶段被妥善处理，只有非常初步的工作涉及含共享资源系统的时序分析与代码优化。

六、多核：干扰、隔离与调度

多核为高性能、低功耗嵌入式应用带来巨大机会，但当前多核架构的设计是由性能驱动的，不是由时序可预测性驱动的。

典型多核架构：单芯片上集成越来越多核，每核带一级或两级私有缓存；众核与外设共享包含 L2/L3 缓存和 DRAM/Flash 的存储层次；互连网络提供核、I/O 外设与共享内存之间的通信——可以是共享总线（如 ARM Cortex-A9 MPCore），也可以是更复杂的片上网络（NoC），如 mesh（Tilera Tile64）或交叉开关（Freescale P4080）。

无论哪种，来自不同核或 DMA 外设的共享内存访问冲突必须在网络或内存控制器中仲裁。

两类共享资源，处理方式不同

存储资源（storage resources）：如缓存，信息会保留若干周期。 带宽资源（bandwidth resources）：如总线、互连，通常每周期重新分配。 存储资源可以用”分区”来隔离；带宽资源除非用 TDMA 类仲裁协议，否则很难分区——这是多核可预测性的核心痛点。

6.1 时序干扰与隔离

多核上一个任务的时间行为，严重依赖共享资源的仲裁机制以及其他任务对资源的使用：

• 带宽资源上与其他请求冲突 → 指令延迟被拉长，甚至可能无界；
• 存储资源（尤其缓存）内容被别的任务破坏 → miss 数增加。

要得到安全的 WCET 估计，必须把并发任务的干扰计入。两类解法：

解法 A：联合分析（joint analysis）

把竞争共享资源的全部任务放在一起考虑，推导每个任务所受延迟的界。

• 优点：可能得到更紧的 WCET 界；
• 缺点：计算复杂；且只在所有并发任务都静态已知时才适用。

具体技术：

• 静态识别并发任务共享的缓存行，把它们视为已被破坏（corrupted）；
• 对单次使用的缓存行旁路 L2，减少冲突、提高精度（Hardy 等, 2009）；
• 考虑任务生命周期：由于调度算法或任务间依赖而不会并发执行的任务，不应被视为可能冲突；
• Li 等 (2009) 提出迭代方法估计共享 L2 缓存任务的 WCET 界；
• Lv 等 (2010) 用抽象解释 + 模型检查建模分析缓存访问时序；
• 估计内存总线竞争带来的额外执行时间（Andersson 等, 2010；Schliecker 等, 2010）；
• 把内存延迟估计与流水线行为分析解耦可以增强可分析性——但这只对完全时序可组合的系统是安全的。

解法 B：空间与时间隔离（spatial and temporal isolation）

确保任务在共享资源上互不干扰，于是可以用与单核相同的分析技术得到 WCET。隔离既可由软件控制（从而可用 COTS 商用多核），也可由硬件强制（对应用透明）。

隔离不是免费的

原文明确指出：避免缓存干扰不是没有代价的——显式管理缓存空间给调度增加了一个新维度，并使分析复杂化。

6.2 系统级调度与分析

系统可预测性在很大程度上取决于工作负载在系统层如何被调度。

单处理器平台有成熟技术（如速率单调调度 RM），写进了教科书和 POSIX 这类工业标准。但多处理器调度（把任务映射到并行架构）要难得多，且缺乏成熟技术。

全局调度（global scheduling）

允许所有任务在所有核上竞争执行。得益于片上共享缓存等硬件机制，多核上的任务迁移开销远小于传统松耦合多处理器，使全局调度成为现实选项。

但它比单处理器调度难得多。 Liu 与 Layland (1973) 早就指出：

一个任务即使有多个处理器空闲时也只能用其中一个——这个简单事实，给多处理器调度增加了惊人的难度。

精确分析全局调度的最大障碍是：不存在已知的”临界时刻”（critical instant）。

单处理器固定优先级调度里的临界时刻是明确定义的：所有干扰任务同时释放各自的第一个实例，后续实例尽可能早地释放。这个情形给出了最大系统负载，直觉上很强。

可惜在全局固定优先级调度中，这个时刻不一定导致最坏情况（Lauzac 等, 1998）。因此全局调度的分析只能依赖近似技术，大量工作致力于通过排除不可能的系统行为来收紧负载估计。

Guan 等 (2009b) 建立了全局固定优先级调度的抽象临界时刻（abstract critical instant）概念：任务的最坏响应时间出现在”除至多 M−1 个（M 为处理器数）之外的所有更高优先级任务，都按单处理器临界时刻的方式释放”的情形下。抽象临界时刻虽不给出精确的释放模式，但把分析限制在了显著更小的状态空间子集内。

分区调度（partitioned scheduling）

长期以来的主流智慧：把系统划分成若干子集，每个子集在单个处理器上调度。

优点：一旦划分完成，每个子系统/处理器就退化成单处理器问题，可直接套用传统单处理器实时调度与分析技术。 缺点：类似装箱问题（bin-packing），存在因碎片导致的资源浪费。随着多核向”更多、更弱的核”演进、单任务相对单核算力变得更重，这种浪费会更显著。

理论上的硬伤：无论每个处理器上用什么局部调度算法，分区调度的最坏情况利用率界都无法超过 50%（Carpenter 等, 2004）。

半分区调度（semi-partitioned scheduling）

为了突破 50% 这个理论上限：让大部分任务固定分配到一个核，只让少数任务可以在不同核上运行——类似任务迁移，但由于迁移任务是静态映射到特定核的，所以是可控、可预测的。

Guan 等 (2010) 的一个重要结果：把著名的 Liu & Layland 单处理器固定优先级利用率界

$$U_{\text{bound}}=N(2^{1/N}-1)$$

推广到了多核——通过一个在每个核上使用 RM 的半分区调度算法达成。

实现与评估：LITMUS-RT

LITMUS-RT（Calandrino 等, 2006）是一个基于 Linux 的实时多处理器调度测试平台，用于把各种多处理器调度算法的实测运行时开销计入理论分析。

主要运行时开销：

• 调度器延迟（Linux 中通常为几十微秒）；
• 缓存相关代价，取决于应用的工作集特征，从几微秒到几十毫秒不等。

研究结论：分区调度和全局调度各有优劣，但对硬实时应用，分区调度表现更好；后续对半分区调度的评估表明它确实是多核实时系统一个有前景的调度范式。

6.3 小结与挑战

在多核平台上，要预测单个任务的时序，必须考虑所有核上所有任务的全局行为，以及资源仲裁机制。

• 要用可组合性和可预测性换性能下降，可以对共享资源分区；
• 存储资源可用页着色避免冲突、保证有界延迟；
• 但不清楚如何对带宽资源分区——除非使用 TDMA 类仲裁协议；
• 已开发的大量多处理器调度技术，全部依赖安全的任务 WCET 界；没有恰当的空间与时间隔离，这样的界似乎无法获得；
• 据作者所知，当时还没有工作把 WCET 分析与多处理器调度桥接起来；
• 未来挑战还包括：把**不同关键等级（criticality）**的实时应用集成到同一平台上——让低关键级应用充分利用算力，同时为高关键级应用提供时序保证。

七、可靠性：当硬件会出错时，还能谈可预测吗

前面所有章节都有一个前提假设：硬件不出错。错误被视为异常，靠空间或时间冗余来处理。

这个假设正在被动摇。半导体工艺持续微缩，导致器件对辐射、电磁干扰、晶体管参数涨落越来越敏感，瞬态错误率预计每一代工艺都会上升（Borkar, 2005）。

麻烦在于：瞬态错误由统计故障模型描述，而这些模型的取值范围是无限的——任意多次错误总有一个非零概率。这与”可预测性 = 无不确定性地界定系统行为”这一通常理解存在根本冲突。

怎么办？安全标准给出了出路：定义正确行为的概率阈值。

例如 IEC 61508 的 **SIL（Safety Integrity Level，安全完整性等级）**分类、ISO 26262（道路车辆功能安全）的最大事故率。

两类冗余：

• 空间冗余：直接映射到额外硬件资源和机制，以足够高的概率屏蔽错误。昂贵（芯片成本、功耗）。
• 时间冗余：检错 + 出错重做。系统设计中更受青睐。

两者不互斥，Izosimov 等 (2006) 给出了组合二者的设计综合方法，构造能容忍任意时刻给定数量错误的健壮调度。

时间冗余与 WCET 的冲突

用重做来纠错会增加执行时间，从而使已预测的最坏执行时间失效。直观想法是”把 WCET 加上纠错所需时间”——但在统计错误模型无界的前提下，重做次数无法用一个有保证的 WCET 界定。

这个两难的解法与空间冗余那边的解法同构：引入概率阈值。这样，即使在存在硬件错误的情况下，可预测性也能以”适合设计和验证安全与时序关键系统”的形式被重新建立起来。

7.1 案例：CAN 总线

**CAN（Controller Area Network，控制器局域网）**是最重要的汽车总线标准，连接车内任意数量的电子控制单元（ECU）。工作在电气噪声环境中，报文可能被错误破坏，平均错误率强烈依赖当前环境。

CAN 协议用**循环冗余校验（CRC）**检测传输错误，随后用全自动的错误信令机制通知发送方，以便重传原报文。

这套错误处理机制以两种不同方式影响可预测性：

情形一：错误被检出，触发重传。 受损报文的延迟因重传而增加；未受影响的报文也可能因调度效应被延迟。→ 错误影响了 CAN 总线上的整体时序。

情形二：错误未被检出，报文被认为正确接收。 由于 CAN 的错误检测不能提供全覆盖，这种情况在极罕见时确实会发生。→ 错误直接影响了系统的逻辑正确性。

两种情形都会因错误的随机发生而导致系统失效——前者是时序失效（错过约束），后者是逻辑失效（把无效数据当成有效）。

要预测 CAN 总线无逻辑/时序失效地传输数据的概率，必须给出统计错误模型（错误的概率分布及其相关性），并把它同时纳入时序预测和错误覆盖率分析。这样才能计算无失效运行的概率，通常表示为一个时间相关函数：

$$R(t)=\mathrm{P}(\text{no failure in }[0,t])$$

逻辑失效（CRC 保护数据传输的残留错误率）自 1980 年代起就有研究：应用线性分组码理论推导不同长度 CRC 的残留错误概率。Charzinski (1994) 专门针对 CAN 做了研究，结果表明：即使在 $10^{-5}$ 这样很高的比特错误率下，CAN 上的残留错误概率也小于 $10^{-16}$。

时序失效方面：

Sebastian & Ernst 的工作还有一个有价值的结论：不同关键等级报文的可靠性分析可以解耦，每个关键等级可按照自己的安全需求来验证。

7.2 面向容错架构的可预测性

CAN 只是”提供概率阈值形式可预测性”的容错架构的一个例子。一般而言，处理容错必须小心其时序影响，原因有二：

1. 静态开销：容错要加额外信息或计算，即使在无错运行时也有时间开销。这部分通常可以静态界定，不影响可预测性，但会延迟计算或数据传输，影响调度的可行性。
2. 随机开销：因（随机）硬件错误而显式执行的恢复措施带来的时间开销。这种情况下基于最坏情况假设的可预测性不再成立，必须替换为概率阈值。

容错机制可按”屏蔽 vs 检测+恢复”分成两大类：

类别一：无随机开销的错屏蔽（error masking）

TMR（Triple Modular Redundancy，三模冗余）：三个相同硬件单元以 lockstep 方式执行相同软件，用**表决器（voter）**纠正单个部件错误。

• 对时序的唯一影响是表决延迟，通常是常数，出错时也不变 → TMR 架构的时序是完全可预测的；
• 缺点：资源与功耗浪费巨大（系统放大 3 倍）；
• 另一个隐患：表决器是单点失效（single point of failure），因此其可靠性必须比被表决器件至少高一个数量级。

FEC（Forward Error Correction，前向纠错）/ ECC（Error Correcting Code，纠错码）：利用信息冗余给数据块插入附加比特，使出错时仍可解码。主要用于存储器和通信系统，也可加固硬件状态机中的寄存器；相比 TMR 硬件和功耗开销更小，但错误覆盖有限——例如汉明距离为 3 的汉明码每块只能纠 1 比特错误，因此主要用于内存加固和总线通信（单比特错误假设合理），可配合内存刷洗（memory scrubbing）周期性纠错防累积。可能遭受突发错误的通信系统必须用更强的 ECC（如 Reed-Solomon 码），但这会显著提高编解码复杂度和静态传输开销。

类别二：检错 + 恢复（时间冗余）

DMR（Double Modular Redundancy，双模冗余）：两个相同硬件单元 lockstep 执行，比较器持续比较输出，不一致即报错，由部件启动（通常耗时的）恢复。

• 纯硬件方案，保护整个处理单元，检错延迟接近零（持续比较，可立即报错）；
• 硬件开销大，昂贵。

N 版本编程（N-version programming）：并行执行同一功能的多个独立实现，各版本结束后比较结果。

• 同时覆盖随机硬件错误和系统性设计错误（软件 bug）；
• 但结果比较带来新挑战：例如结果若是浮点值，可能并非因为出错而不等，而是浮点运算固有的精度损失依赖于运算顺序；
• 解决方案是非精确表决（inexact voting），但这又对高可靠系统的适用性提出新问题。

简化变体：多次执行同一个实现——可在同一 CPU 上时间复用（re-execution），或利用空间冗余（replication）。相比 DMR，这些技术可以更细粒度地采用（只保护选定的任务），从而大幅节省成本。

Fingerprint（指纹）技术（Smolens 等, 2004）：在处理器流水线中增加一个指纹寄存器，对经过的所有指令和操作数在线做哈希。这个哈希可作为定期表决的依据（例如每退休若干条指令表决一次）。核心思想是：只要不出错，所有冗余执行的指纹值必然相同。由于指纹由专用硬件计算，无错情况下几乎不引入额外时间开销。

FGTR（Fine-Grained Task Redundancy，细粒度任务冗余）（Axer 等, 2011）：只复制选定的任务，执行期间定期做错误检查，检查用上述指纹方法在硬件中完成。

• 无错且采用可预测调度策略时，行为也是可预测的（没有引入额外不确定性）；
• 每次比较成功就创建一个检查点（checkpoint）；若因指纹不一致检出错误，就回滚到最近的检查点；
• 在”定期建检查点的静态开销”与”出错时的随机开销”之间提供折衷；
• 分析 FGTR 下错误引起的时序效应的方法，与 CAN 总线上出错帧的分析非常相似，只是协议和开销参数不同。

7.3 小结与挑战

通过应用 DMR、TMR 和编码机制，可以使单个部件对瞬态错误和永久错误都具备加固能力。把这些方法系统地应用到计算、片上通信、片外通信，仍然可以设计出一个可预测系统，并附上一个保守界定的安全度量（如 MTTF）——这足以满足安全标准的要求。

剩下的主要挑战：

1. 错误模型的表达力。要得到保守的界，必须有准确反映现实的错误模型。在恶劣环境中假设标准的单比特错误模型可能是乐观的；而如果错误模型过于复杂（例如状态很多的隐马尔可夫模型），又很可能导致状态空间爆炸。
2. 可分解性。由于部件之间存在功能和时序上的依赖，不容易把一个”错误感知的系统分析”分解成独立的部件分析。因此系统分析通常是整体式（holistic）的，无法随系统规模扩展。

八、总结与开放挑战

原文第 8 节的结论可以这样概括：

已经做到的：

• 在处理器架构部件层面，我们已经理解了流水线、存储系统等的多种可预测性性质，并以此为基础形成了可预测性的设计原则；已经出现了把时序纳入指令集语义的处理器设计；
• 在多核平台层面，对”如何为程序执行提供可预测性保证”这个难题已有较好理解和部分解法——核心思路是资源分区 + 尽可能隔离各任务之间的干扰。可惜当前商用多核处理器对这些解法的支持相当有限；
• 在工具链集成层面，编译与 WCET 分析的集成（WCC）提供了一个平台，可以系统地研究各种常见编译优化对可预测性的影响，以及平均执行时间与最坏执行时间之间的权衡；把执行时间分析嵌入同步 C 方言（PRET-C / SC）是另一个成功集成的例子；
• 在可靠性层面，可预测性的定义已经被扩展到能容纳网络系统中固有的不可靠性，并与安全标准对接。

总体判断：在单处理器平台上，研究成果已经足以构建可预测系统。

仍然开放的挑战：

常见坑：初学者最容易犯的几个错

1. 把”平均快”当成”实时”。 优化 ACET 的优化（激进循环展开、激进预取）可能让 WCET 变差。实时系统的第一指标永远是 WCET/WCRT。
2. 以为”算不出来”等于”不可预测”。 可预测性是系统的固有属性；某工具算不出来，可能只是工具不行。反过来，也不要因为”工具能算”就以为系统可预测——它可能只是给了一个极松的界。
3. 把 BCET/WCET 比值当成全部。 有的系统比值接近 1 但绝对时间很长（慢而稳），有的系统比值很小但绝对时间很短。质量度量只是”抖动程度”，不是”性能”。
4. 以为缓存一定比 SPM 好。 缓存硬件自动管理、对程序员透明，但 LRU 之外的策略（尤其 PLRU、RANDOM）在可预测性上极差；SPM 需要软件管理，但延迟恒定可重复。
5. 关掉所有编译优化以求安全。 这确实”安全”，但代价是硬件严重超配。正解是用 WCET 感知编译器——它既有形式化时序模型，又能主动优化 WCET。
6. 以为多核隔离是免费的。 分区、页着色、TDMA 全都以性能和调度复杂度为代价。而且带宽资源不像存储资源那样好分区。
7. 忘了可靠性会摧毁 WCET。 一旦引入”出错重做”，基于最坏情况的可预测性就不复存在，必须换成概率阈值（SIL、MTTF 那一套）。

通关标准

• 能区分平均执行时间（ACET）与最坏执行时间（WCET），并说明为什么实时系统只关心后者
• 能解释缓存为什么是 WCET 分析的主要障碍，以及 SPM 为什么更可预测
• 能列出三种重建时序可预测性的手段及其代价
• 能说清”时序异常”和”多米诺效应”的区别，以及它们为什么让分析必须遍历所有路径
• 能说明多核上”存储资源”与”带宽资源”在隔离手段上的根本差异

自测 1：为什么"提升处理器性能"反而会让实时系统的时序保证更难给出？

答案要点：性能提升靠流水线、乱序执行、分支预测、缓存、DRAM 重排序等机制，它们的共同点是让一条指令的执行时间依赖到达它之前发生了什么。 ① 指令时间不再可加（相互重叠）； ② 出现时序异常——局部最坏不贡献全局最坏，“只沿局部最坏路径走”的分析不 sound； ③ 出现多米诺效应——初始硬件状态造成的执行时间差随路径长度线性增长，无法用常数界住，只能完整跟踪状态； ④ 状态空间爆炸，分析代价可能”望而却步”——按 Rochange & Sainrat 的判据，这样的处理器就该被判为不可预测。 而 ISA 语义本来就不含执行时间，这给了微体系结构自由，也把可预测性的责任推给了分析者。

自测 2：LRU、FIFO、PLRU、RANDOM 四种缓存替换策略，从"状态诱导的缓存可预测性"角度看排序如何？为什么会这样？

答案要点：排序是 LRU > FIFO > PLRU ≈ RANDOM。

• LRU 在所有相联度（2–8）上 ${\lim }_{n\to \infty }\mathrm{SICPr}=1$，即不存在缓存多米诺效应，初始状态对长期 miss 数的影响可以被完全界住（这是理论最优值）。
• FIFO 为 $1/k$（$k$ 为相联度）：相联度越高越差，不同初始状态下 miss 数最多差 $k$ 倍。
• PLRU 在相联度 2 时与 LRU 等价（=1），但 4 路及以上直接掉到 0：从一个状态出发的 miss 数无法用另一状态出发的 miss 数界定（Berg 发现的 PLRU 多米诺效应）。
• RANDOM 全为 0，完全不可预测。 工程含义：PLRU 因省面积被大量商用处理器采用，但从可预测性看是灾难；实时平台应优先选 LRU 或改用 SPM。

自测 3：SPM（便签存储器）比缓存更可预测，为什么没有全面取代缓存？它的代价是什么？

答案要点： 为什么可预测：SPM 用同样的 SRAM 介质（恒定低延迟），但内容由软件控制——它是可寻址空间的一部分，软件显式搬入搬出；不存在”命中/失效”的二元不确定性，也不受替换策略影响。 代价：① 管理责任转移——像寄存器文件一样，正确高效使用 SPM 是编译器（或程序员）的责任；② 多应用共享时尤其困难；③ 代码分割在 SPM 与慢速存储之间会引入跳转惩罚；④ 失去缓存”对软件透明、自动适应”的便利。 机会：正因由软件管，就能针对具体应用定制（如用 ILP 最优地把最坏路径上的基本块放进去）。实测：仅能装 10% 代码的小 SPM 就能降 7.4% WCET，最大平均降幅 40%（TriCore TC1796，73 个基准）。

自测 4：多核上要重建可预测性，有"联合分析"和"隔离"两条路，各自的适用条件和代价是什么？为什么带宽资源比存储资源更难处理？

答案要点： 联合分析：把所有竞争共享资源的任务放在一起分析，推导每个任务所受延迟的界。优点是界更紧；代价是计算复杂，且只在所有并发任务都静态已知时适用。技术包括：把共享缓存行视为已破坏、对单次使用行旁路 L2、按任务生命周期排除不可能冲突、抽象解释+模型检查、把内存延迟估计与流水线分析解耦（但这只对完全时序可组合的系统安全）。 隔离：确保任务在共享资源上互不干扰，于是可复用单核的分析技术。手段包括轮转仲裁、分离相位、可预测执行模型（PEM：预取阶段 + 不会 miss 的执行阶段）、TDMA 时隙、列化/bank 化缓存分区、页着色。代价是性能下降、调度维度增加、分析复杂化。 为什么带宽资源更难：存储资源（缓存）里信息会保留若干周期，可以用”分区”（分配不同的 way / bank / 物理页颜色）长期隔离；带宽资源（总线、互连）通常每周期重新分配，除非用 TDMA 类仲裁协议，否则很难分区——而 TDMA 出于性能原因在商用多核上并不常见。原文直言：“不清楚如何对带宽资源分区”。

自测 5：为什么说"出错重做"会摧毁基于最坏情况的可预测性？出路是什么？

答案要点： 冲突所在：时间冗余（检错 + 重做）使执行时间因错误变长，令已预测的 WCET 失效。直观想法是”把 WCET 加上纠错时间”，但统计故障模型取值范围无限——任意多次错误总有非零概率，重做次数无法用有保证的 WCET 界定（对比 CAN 的二进制指数退避：冲突越多，等待时隙区间越大）。 出路：与空间冗余那边同构——引入概率阈值。不再追求”绝对不出错、绝对不超时”，而给出”在 $[0,t]$ 内无失效”的运行概率 $R(t)$ 与 MTTF 等度量，并用安全标准规定的阈值（IEC 61508 的 SIL 目标失效率、ISO 26262 的最大事故率）验证。 两类机制的取舍：TMR 时序完全可预测（只有常数表决延迟），但 3 倍资源/功耗，且表决器是单点失效；FEC/ECC 开销小但覆盖有限（汉明距离 3 只纠 1 比特），突发错误需 Reed-Solomon（复杂度高）；DMR / N 版本 / 重执行的开销随机发生，只能给概率阈值；Fingerprint + FGTR 用硬件哈希在线比对，无错时几乎零开销，在”定期建检查点的静态开销”与”出错时的随机开销”之间折衷。 遗留挑战：错误模型的表达力（太简单→乐观，太复杂→状态空间爆炸），以及系统分析因部件间功能/时序依赖而无法分解、无法随规模扩展。