混合关键性系统调度：从确定性到概率性模型与多核分区算法实践

1. 混合关键性系统调度：从确定性到概率性的思维跃迁

在嵌入式实时系统，尤其是汽车电子、航空航天这些领域，我们常常面临一个核心矛盾：系统里既有“性命攸关”的高关键性任务，比如刹车控制、飞行姿态调整，必须保证万无一失；也运行着大量“锦上添花”的低关键性任务，比如娱乐信息显示、日志记录，我们希望它们跑得越多越好。这就是混合关键性系统要解决的根本问题——如何在确保高关键性任务绝对可靠的前提下，尽可能多地“挤”出资源给低关键性任务，提升整体效率。

传统的调度方法，比如经典的EDF-VD，思路很直接：系统默认运行在低关键性模式，所有任务按低关键性最坏执行时间调度。一旦监测到某个高关键性任务的实际执行时间超过了其低关键性预算，系统立即切换到高关键性模式，并丢弃或延缓所有低关键性任务，以确保高关键性任务能完成。这种方法安全、直观，但过于“悲观”。它假设高关键性任务随时可能“发飙”用过载，并为此预留了最坏的资源。在实际中，任务过载往往是小概率事件，这种一刀切的切换策略会导致大量低关键性任务被“误伤”，系统资源利用率低下。

于是，概率模型进入了我们的视野。它不再把任务过载看作一个“非黑即白”的确定性事件，而是承认其随机性，用一个概率参数来描述。这就像天气预报从“明天有雨”变成了“明天降水概率70%”，虽然增加了不确定性，但信息量更大，也为我们做更精细的决策提供了可能。基于概率，我们可以计算系统处于不同模式（低关键性阶段、高关键性阶段）的“期望时间”，进而评估低关键性任务到底能获得多少执行机会。今天要深入探讨的，正是如何将这种概率思维，从单处理器调度算法，延伸到多处理器的任务分区策略中，构建一套从理论分析到工程实践的完整解决方案。

2. 核心基石：概率混合关键性模型与O-EDF-VD算法

2.1 PMC模型：为不确定性建模

我们首先需要一套描述任务的数学语言。概率混合关键性模型在传统模型基础上，为每个高关键性任务Ti增加了一个关键参数：过载概率ωi。这个概率表示任务Ti的任何一个作业在实际运行时，其执行时间超过其低关键性最坏执行时间C_LO_i的可能性。

• 任务参数：一个任务Ti通常由周期Di、低关键性最坏执行时间C_LO_i、高关键性最坏执行时间C_HI_i（C_HI_i >= C_LO_i），以及关键性等级χi（LO或HI）定义。在PMC模型中，对于HI任务，额外赋予其过载概率ωi。
• 系统行为：系统启动时处于LO模式。只要所有HI任务的实际执行时间都不超过其C_LO_i，系统就持续保持在LO模式，所有任务（包括LO和HI）都按其LO模式参数调度。一旦任意一个HI任务的某个作业执行时间超过了C_LO_i，系统立即切换到HI模式。在HI模式下，调度器只保证HI任务的执行（使用其C_HI_i参数），LO任务将被暂停或丢弃。
• 核心挑战：我们的目标是，在系统设计时（离线阶段），就能基于这些概率参数，预测系统运行时在LO模式和HI模式分别会花费多少“期望时间”，从而评估LO任务能获得多少执行量。

2.2 O-EDF-VD：一种更“温和”的模式切换策略

EDF-VD算法在模式切换时是“急刹车”式的：一旦触发切换，所有HI任务立刻开始以高关键性虚拟截止期运行。O-EDF-VD（优化的EDF-VD）则提出了一种“顺序切换”的策略，旨在减少对LO任务的冲击。

其核心思想是：在HI模式下，并非所有HI任务都立刻切换到高关键性状态。调度器会按照HI任务作业的释放顺序，逐个地将那些实际发生了过载的HI任务切换到高关键性状态（使用其C_HI_i和更紧的虚拟截止期），而其他未过载的HI任务暂时仍按LO模式处理。这样可以更精细地利用HI模式下的处理器带宽，为尚未被丢弃的LO任务争取更多的执行机会。

注意：O-EDF-VD的可调度性分析与EDF-VD相同，即对于一个处理器上的任务集，需要满足max(U_LO, U_HI) <= 3/4，其中U_LO和U_HI分别是所有任务在LO和HI模式下的处理器利用率总和。这意味着算法优化并未牺牲可调度性保障。

2.3 执行期望分析：预测系统的“时间账”

这是整个概率调度理论中最精妙也最核心的部分。我们需要计算，在一个完整的“周期”（从系统启动LO模式开始，到HI模式结束所有HI任务为止）内，系统处于LO阶段和HI阶段的期望长度。

2.3.1 LO阶段期望长度E_LO

LO阶段结束于第一个导致关键性切换的HI作业过载时刻。假设这个时刻为t*。t*是一个随机变量。我们可以计算在时间[0, t]内没有任何HI任务发生过载的概率。这个概率是所有HI任务在[0, t]时间内释放的所有作业都未过载的概率乘积。

对于一个HI任务Ti，它在[0, t]时间内大约释放ceil(t/Di)个作业。每个作业不过载的概率是(1 - ωi)。因此，Ti的所有作业在[0, t]内都不过载的概率约为(1 - ωi)^ceil(t/Di)。那么，所有HI任务都不过载的概率P_no_overload(t)就是它们各自概率的乘积。

LO阶段的期望长度E_LO，可以理解为第一个过载事件发生的“平均时间”。这可以通过积分所有时间点t处系统仍未切换的概率来估算：E_LO ≈ ∫ P_no_overload(t) dt，积分范围从0到无穷。在实际计算中，由于概率衰减很快，我们通常计算到一个足够大的时间界t_LO，使得P_no_overload(t_LO)已经非常小，可以近似认为E_LO ≈ t_LO * P_no_overload(t_LO) + ∫ P_no_overload(t) dt在[0, t_LO]上的值。原文中的公式(5)和(11)给出了更严谨的数学表达。

2.3.2 HI阶段期望长度E_HI

HI阶段从t*开始，到所有HI任务在当前HI模式下产生的所有工作负载完成时结束。分析HI阶段期望E_HI更为复杂，因为需要区分不同的过载场景。原文将其分为三种情况来分析一个HI任务Ti在HI阶段[t*, tf]内的执行时间期望：

1. 情况1：Ti自身释放了那个触发系统切换的“肇事”作业。在这种情况下，该作业在t*过载，此后Ti在HI阶段将以HI模式执行。其执行时间期望上界为C_HI_i * ceil((tf - t*)/Di)。
2. 情况2：Ti没有释放触发切换的作业，但它在HI阶段[t*, tf]内自身发生了过载。这需要计算它第一个过载作业出现在第k个的概率，以及对应产生的总执行时间（前k-1个作业按C_LO_i执行，第k个及以后按C_HI_i执行），并对所有可能的k求和求期望。
3. 情况3：Ti在整个HI阶段都未发生过载。那么它所有的作业都按C_LO_i执行。

分别计算出这三种情况发生的概率P_HI(Ti, 1),P_HI(Ti, 2),P_HI(Ti, 3)，以及对应的执行时间期望E_HI(Ti, 1),E_HI(Ti, 2),E_HI(Ti, 3)。那么Ti在HI阶段的总执行期望E_HI(Ti)就是这三者的加权和：E_HI(Ti) = Σ P_HI(Ti, k) * E_HI(Ti, k)。

最后，HI阶段的期望长度E_HI就是所有HI任务执行期望的总和，因为HI模式下处理器只为HI任务服务，且假设处理器一直繁忙：E_HI = Σ_{所有HI任务} E_HI(Ti)。这形成了一个关于E_HI（隐含在tf - t*中）的方程，需要求解其最小正解。

2.3.3 周期总期望与LO任务执行率

一个完整周期的期望长度E_All由两部分组成：一是系统始终处于LO模式的情况（概率为P(null)，长度为t_LO），二是系统经历了LO和HI两个阶段的情况（概率为1-P(null)，长度为E_LO + E_HI）。因此E_All = P(null)*t_LO + (1-P(null))*(E_LO + E_HI)。

对于一个LO任务Ti，它只能在LO阶段执行。它在单个周期内的期望执行时间为δ(Ti) = u_LO_i * E_LO，其中u_LO_i = C_LO_i / Di是其LO模式利用率。而如果它能独占处理器，在一个周期长度E_All内本可以执行ε(Ti) = u_LO_i * E_All的时间。因此，它的期望执行率Υ(Ti)定义为实际期望执行时间与潜在最大执行时间的比值：Υ(Ti) = δ(Ti) / ε(Ti) = E_LO / E_All

这个公式直观地揭示了核心：LO任务的执行效率，直接取决于LO阶段在总周期期望中所占的比例。我们的所有优化，无论是调度算法还是分区策略，最终目标都是最大化E_LO / E_All这个比值。

3. 从单核到多核：概率感知的分区算法设计

当目标平台从单处理器扩展到多处理器时，问题从“如何调度”变成了“如何分配”——即任务分区问题。我们需要将n个混合关键性任务分配到m个同构处理器上，每个处理器独立运行O-EDF-VD调度器。分区策略的好坏，直接决定了所有处理器上E_LO / E_All比值的整体水平。

3.1 分区问题的挑战与目标

混合关键性任务分区比普通任务分区更复杂，因为它需要同时考虑两种关键性模式下的可调度性约束（max(U_LO, U_HI) <= 3/4），并且优化目标不是简单的负载均衡，而是最大化LO任务的执行机会。这带来了两个层面的挑战：

1. 可调度性约束：分配给每个处理器的任务子集，必须同时满足其在LO模式和HI模式下的利用率约束。这要求我们在分配任务时，必须同时考虑任务的C_LO和C_HI。
2. 优化目标耦合：我们的目标是最大化所有处理器上LO任务的总体验证执行率。但每个处理器上LO任务的执行率Υ = E_LO / E_All依赖于该处理器上所有HI任务的概率分布和参数，这是一个全局的、非线性的优化目标，无法像传统负载均衡那样简单地将任务按利用率大小排序分配。

3.2 PPDC算法：一种贪心启发式策略

由于精确求解该分区问题是NP难的，原文提出了PPDC算法——一种基于概率的、双重贪心策略。

3.2.1 任务排序策略

• HI任务排序：不能单纯按u_HI或u_LO排序。PPDC定义了一个综合利用率u_m_i = ωi * u_HI_i + (1 - ωi) * u_LO_i。这个定义很有道理，它反映了HI任务在“平均”意义上对处理器的占用程度，同时考虑了过载概率。HI任务按u_m_i降序排列，优先处理平均负载高的HI任务。
• LO任务排序：LO任务按其在LO模式的利用率u_LO_i降序排列。优先分配大块头的LO任务，有助于减少碎片。

3.2.2 处理器选择策略：贪婪因子的设计

这是PPDC算法的精髓。当为一个HI任务Ti选择目标处理器Pr时，不能只看当前处理器是否还能塞下它（即满足max(U_LO(Pr)+u_LO_i, U_HI(Pr)+u_HI_i) <= 3/4），还要看塞进去之后，对处理器未来执行LO任务的“潜力”影响有多大。

为此，PPDC为每个候选处理器Pr计算一个贪婪因子H_i(Pr)：H_i(Pr) = (3/4 - U_LO_HI(Pr)) * (E_LO(Pr) / E_All(Pr))

这个因子由两部分乘积构成：

1. 剩余LO容量：(3/4 - U_LO_HI(Pr))。这里U_LO_HI(Pr)是处理器上所有HI任务的LO模式利用率之和（注意，不是所有任务的LO利用率）。这部分代表了在满足HI任务LO模式需求后，处理器还能为LO任务提供的最大利用率空间。值越大，意味着塞入LO任务的潜力越大。
2. 当前LO执行效率：(E_LO(Pr) / E_All(Pr))。这就是当前该处理器上HI任务集所决定的LO阶段占比。它反映了现有HI任务集对LO任务的“友好程度”。比值越高越友好。

贪婪因子的设计思想是：优先将HI任务分配到那个既能容纳它，又能在容纳后依然保持较高LO任务容纳潜力和较高LO阶段占比的处理器上。它同时考虑了静态的容量空间和动态的概率行为影响。

3.2.3 算法步骤详解

1. 准备阶段：分别对HI任务集（按u_m_i降序）和LO任务集（按u_LO_i降序）进行排序。
2. 分配HI任务： a. 遍历排序后的HI任务。 b. 对于当前HI任务Ti，遍历所有处理器。对于每个处理器Pr，检查加入Ti后是否仍满足可调度性条件。如果满足，则根据该处理器当前的任务负载，计算其贪婪因子H_i(Pr)；如果不满足，则设H_i(Pr) = -1。 c. 选择贪婪因子最大且大于0的处理器，将Ti分配给它。如果找不到这样的处理器，则分区失败。
3. 分配LO任务： a. 遍历排序后的LO任务。 b. 对于当前LO任务Ti，遍历所有处理器。对于每个处理器Pr，检查加入Ti后是否仍满足可调度性条件（此时HI任务已固定，只需检查LO利用率约束U_LO(Pr)+u_LO_i <= 3/4，同时HI利用率U_HI(Pr)不变且早已满足<= 3/4）。如果满足，则计算该处理器当前的E_LO(Pr) / E_All(Pr)比值；如果不满足，则设比值为-1。 c. 选择E_LO / E_All比值最大且大于0的处理器，将Ti分配给它。如果找不到，则分区失败。
4. 成功：所有任务分配完毕，返回成功。

实操心得：在实现PPDC算法时，计算E_LO和E_All（进而得到E_LO/E_All）是性能瓶颈。因为每次评估一个任务加入处理器时都需要重新计算，而计算涉及复杂的概率公式和方程求解。工程上通常采用预计算表或近似公式来加速。例如，可以为不同的U_LO_HI、U_HI和平均过载概率预先离线计算好E_LO/E_All的近似值，在线查找，这能极大提升分区速度。

3.3 与经典分区算法的对比

为了理解PPDC的优势，需要看看它解决了哪些传统方法的问题：

• MC-Partition：一种最基础的分区算法。它简单地按某种顺序（如任务索引）遍历任务，将每个任务分配到第一个能满足可调度性条件的处理器上。它只关心“能否塞下”，完全不考虑不同关键性任务的特性和优化目标。
• Hybrid Partition：一种针对混合关键性的改进算法。它对HI任务采用Worst-Fit Decreasing策略（优先放入当前HI利用率最小的处理器），以平衡各处理器的HI负载；对LO任务采用First-Fit Decreasing策略（优先放入第一个能容纳的处理器），以快速填充LO容量。它考虑了关键性差异，但仍然是基于静态利用率的启发式，没有利用任务的概率信息。

PPDC的先进性在于，它首次将任务执行的概率期望引入到分区决策中。贪婪因子和处理器选择标准都直接指向了最终的优化目标——最大化LO任务的执行率。这使得它在进行分配时，能够做出更“聪明”的预测性决策。

4. 仿真实验：理论的有效性与算法优势

任何调度理论都需要通过实验来验证。原文设计了一套完整的仿真流程来评估O-EDF-VD和PPDC。

4.1 实验设置与任务集生成

实验通常在随机生成的任务集上进行，以模拟真实场景的多样性。关键参数包括：

• 处理器数量 m：通常在2到8之间。
• 平均处理器利用率 U_avg：设置在0.2到0.7之间。过低（<0.2）利用率下算法差异不明显，过高（>0.75）则可能超出可调度范围。
• HI任务比例 HI_Rate：控制任务集中高关键性任务的占比。
• 平均过载概率 AOP：这是核心变量，所有HI任务的过载概率ωi围绕AOP呈正态分布。
• 利用率参数：分别指定LO任务和HI任务的典型利用率范围，以及HI任务C_HI与C_LO的比值λ。

任务生成器会随机生成任务参数，直到总利用率接近U_avg * m，并确保每个处理器子集满足可调度性条件。

4.2 O-EDF-VD vs. EDF-VD

在单处理器上对比两种调度算法，主要看两个指标：

1. HI阶段占比：系统运行在HI模式的时间占总时间的比例。这个比例越低，意味着LO任务被中断的时间越短。
2. LO任务完成率：实际完成的LO作业数量与LO作业释放总数的比值。

仿真结果趋势表明：

• 随着AOP增加，HI阶段占比上升，LO任务完成率下降，这符合直觉。
• 在AOP约为0.35时，这种变化速度达到峰值。这可能是因为在此概率附近，系统行为处于从“以LO为主”到“频繁切换”的临界状态，对调度策略最为敏感。
• O-EDF-VD在所有AOP值下，均优于EDF-VD。LO任务完成率有5%-10%的提升，HI阶段占比有约10%的降低。这验证了顺序切换策略的有效性，它确实通过更精细的资源管理，为LO任务争取了更多机会。

4.3 期望计算的有效性验证

将第2.3节中推导的E_LO和E_HI数学期望公式的计算结果，与长时间仿真（如1000个周期，重复100次取平均）得到的实际平均LO/HI阶段长度进行对比。实验数据显示，理论期望值与仿真平均值之间的误差在5%以内。这强有力地证明了概率模型和期望分析方法的准确性，为基于期望进行离线分区决策提供了坚实的理论依据。

4.4 PPDC分区性能对比

在多处理器场景下，将PPDC与MC-Partition、Hybrid Partition进行对比。评价指标是系统整体的LO任务完成率。

实验结果清晰地显示了一个性能排序：PPDC > Hybrid Partition > MC-Partition。

• 相比于Hybrid Partition + O-EDF-VD的组合，PPDC + O-EDF-VD能带来5%-10%的LO任务完成率提升。
• 相比于最基础的MC-Partition + EDF-VD，PPDC的提升幅度可达15%左右。
• 更重要的是，这种优势随着AOP的增大而更加明显。当系统不确定性增加（AOP变大）时，基于概率模型进行“预见性”规划的PPDC算法，相比只基于静态最坏情况规划的算法，优势愈发突出。这证明了在不确定性高的环境中，概率化设计的巨大价值。

5. 工程实践中的挑战与应对策略

将概率混合关键性调度从论文公式落地到实际系统，会面临一系列工程挑战。

5.1 过载概率的获取与校准

整个理论大厦的基石是HI任务的过载概率ωi。这个参数从何而来？

1. 历史统计：对于已有类似系统或原型，可以通过大量测试和运行日志，统计任务执行时间的分布，估算其超过C_LO_i的概率。
2. WCET分析结合概率模型：最坏情况执行时间分析工具可以给出执行时间的概率分布（pWCET），从中可以导出超过某个阈值的概率。
3. 设计阶段指定：在系统设计时，由工程师根据任务特性和安全要求，保守地指定一个概率上界。

注意事项：ωi的准确性直接影响调度和分区的效果。如果估计过于乐观（实际概率大于ωi），可能导致HI任务在HI模式下无法满足时限，违反高关键性保障，这是不可接受的。因此，在实践中倾向于采用保守估计，即给出的ωi略大于预期的真实概率，为系统留出安全余量。但这会牺牲一部分LO任务的性能。

5.2 在线监控与模式切换

O-EDF-VD算法需要在运行时检测任务过载。这通常通过执行时间监控来实现。

• 实现机制：每个HI任务作业开始执行时启动一个计时器，阈值为C_LO_i。如果执行时间超过该阈值，则触发过载异常，调度器执行模式切换逻辑。
• 开销考虑：计时和异常处理会引入运行时开销。需要确保监控机制本身是确定性的，且开销足够小，不影响任务的可调度性分析。通常会将监控开销计入任务的最坏执行时间C_HI_i中。

5.3 分区算法的实时性与可扩展性

PPDC算法是一个离线分区算法，在系统集成阶段执行。但随着系统动态变化（如任务集更新），可能需要重新分区。

• 计算复杂度：PPDC的核心复杂度在于为每个任务评估每个处理器时，需要重新计算贪婪因子或E_LO/E_All比值，这涉及复杂的期望计算。对于大规模任务集（几十上百个任务）和多核平台（几十个核心），计算时间可能很长。
• 工程优化：
  • 增量计算：当向一个处理器添加或移除一个任务时，尝试增量更新E_LO和E_All，而不是从头计算。
  • 查表法/拟合公式：如前所述，预先计算好常见参数组合下的比值，运行时直接插值查找。
  • 分层分区：对于非常多核的系统，可以先按功能或关键性将任务分组，组内再用PPDC分区，减少每次计算的规模。

5.4 容错与边界情况处理

实际系统总会遇到模型未覆盖的情况。

• 连续过载与模式震荡：如果系统刚进入HI模式，很快又有新的HI任务过载，理论上O-EDF-VD可以处理。但需要防止频繁的模式切换带来的开销。可以设置一个最小HI模式持续时间或切换迟滞。
• LO任务的恢复：HI模式结束后，如何恢复被丢弃或挂起的LO任务？简单的策略是丢弃当前周期的LO作业，等待下一个周期。更复杂的策略可能需要为LO任务维护一个队列，并在HI模式结束后以某种策略（如补偿）执行积压的作业，但这需要额外的调度分析和资源预留。
• 概率模型失效：如果实际运行中过载频率远高于模型预测（即发生了“黑天鹅”事件），系统可能长期处于HI模式，LO任务几乎得不到执行。这时需要更高层的系统健康管理机制介入，例如触发降级模式或告警。

6. 未来展望：从双关键性到多关键性

当前模型和算法主要针对LO和HI两种关键性等级。但工业标准如AUTOSAR或ISO 26262定义了更多等级（如ASIL A到D）。将PMC模型和PPDC算法扩展到多关键性系统是自然的下一步，但也面临更大挑战：

1. 概率模型复杂化：一个任务在不同关键性等级下可能有不同的执行时间分布和超越概率。需要定义一组概率ωi(L)，表示任务Ti的执行时间超过其L级关键性预算的概率。系统状态切换也将从一个阈值触发变为多个阈值触发。
2. 期望分析维度爆炸：系统可能从LO模式切换到CL1模式，再切换到CL2模式……需要分析在所有可能模式序列下的期望行为。状态空间和计算复杂度将呈指数级增长。
3. 调度与分区策略革新：EDF-VD/O-EDF-VD需要扩展为支持多级虚拟截止期。分区算法的贪婪因子需要重新设计，以权衡多个关键性等级下任务的执行保证。

尽管挑战巨大，但概率化、定量化的设计思想是混合关键性系统发展的必然趋势。它使得我们在“绝对安全”和“高效利用”之间，找到了一个可以量化分析和优化的平衡点。从确定性的最坏情况设计，走向概率性的期望性能优化，这不仅是技术的进步，更是设计思维的进化。