基于优先级反转有界协调的容错实时系统并行任务调度方法

《ACM Transactions on Cyber-Physical Systems》：A Robust Approach for Ensuring Total Order Execution of Replicated Sporadic Tasks in Fault-Tolerant Multiprocessor Real-Time Systems

本文提出了一种在分布式实时系统中实现容错并行任务调度的创新方法，该方法通过动态协调各节点（处理器/核心）的执行顺序，确保即使存在拜占庭故障（Byzantine faults）和恶意攻击（如优先级反转注入攻击），所有健康节点上的任务仍能按时完成。核心思想是利用任务松弛时间（slack）作为优先级反转（priority inversion）的界限，通过非阻塞通信和进度更新算法（Update algorithm）来减少悲观估计，从而在不依赖严格时钟同步的前提下，保证任务执行的全局一致性和时限性（timeliness）。

　　

系统模型与威胁模型

文章研究的是事件触发的分布式实时系统，任务为偶发任务（sporadic tasks）。每个任务τ_{i由其最小释放间隔Ti、相对截止期Di（Di ≤ Ti）和最坏情况执行时间（WCET, Ci）表征。系统在m ≥ 2f + 1个节点（P1, P2, ..., Pm）上复制任务和实时操作系统（RTOS），以容忍最多f个拜占庭故障节点。故障节点可能表现出任意恶意行为，包括执行乱序、不执行任务、报告虚假进度数据或中断通信。文章假设通过内存隔离（如bank-aware内存分配器）和缓存分区等技术，可以防止故障节点直接干扰健康节点。通信方面，假设存在一个实时可靠广播协议，保证消息要么在最大时间Timeout内无篡改地送达所有健康节点，要么不送达任何节点。Timeout由最大预期网络延迟Cmsg和节点检测任务释放并分发其进度信息的最大估计延迟Csend组成。}

任务执行被划分为多个不可抢占的“块”（chunks），每个块对应任务内部的一个里程碑（milestone）。任务τ_{i的第l个块记为τ^li，其WCET为C^li。任务的WCET是其所有块WCET之和，即Ci = ∑^Lil=1 C^li。这种划分允许在不同变体（variants）的任务间比较进度，并限制了抢占点。}

协调复现执行的方法概述

该方法的核心目标是确保所有节点上任务执行的全局顺序一致，并限制优先级反转，使其不超过每个任务的松弛时间（slack），从而保证时限性。该方法无需节点间通信即可动态协调作业的执行顺序，通信仅用于改善作业响应时间，且是非阻塞的，不会延迟作业执行。方法满足以下属性：一致协议（Uniform Agreement）、无重复执行（No Re-Execution）、全局顺序（Total Order）、有限优先级反转（Limited Priority Inversion）和时限性（Timeliness）。

该方法主要由三个算法组成：调度算法（Scheduling Algorithm）、释放算法（Release Algorithm）和更新算法（Update Algorithm）。每个节点维护两个队列：就绪队列（Ready Queue, RQ_k）和块队列（Chunk Queue, CQ_k）。释放的任务首先插入就绪队列。调度算法负责将就绪队列头部的作业的块移动到块队列并执行，但前提是这样做不会导致任何即将到来的（imminent）高优先级任务因优先级反转超过其松弛时间而错过截止期。释放算法在任务释放时，确保所有节点在将其插入就绪队列之前，就已确定其执行顺序。更新算法则利用节点间通信来共享进度信息，以减少对后台运行节点（back-runner）进度的悲观估计，从而允许节点执行更多块而无需空闲等待。

关键定义与交互

Worst-Case Projection (WCP)：对于某个进度（progress）prog，其最坏情况投影ω(prog)表示后台运行节点（假设始终以块的WCET执行且未空闲）完成该进度对应块的最晚时间。它基于最近一次进度更新时间t_update和当前最小进度minProg计算得出：ω(prog) = t_update + ∑C^l_a（对所有在CQ_k中从minProg+1到prog的块τ^l_a求和）。

Maximum Allowed Progress (MAP)：这是一个进度阈值，任何健康节点的块队列尾进度prog^tail_k绝不能超过MAP。MAP是通过将块从就绪队列移动到块队列来确定的，直到就绪队列为空，或者对于至少一个即将到来的高优先级任务τ_{i，不等式ω(prog^tailk) + C^nextaa ≤ ρi(t) + slacki不再成立。这里，ρi(t)是任务τi在时间t可能的最早释放时间，slacki是其松弛时间。该不等式保证了即使后台运行节点在执行新释放的高优先级任务τi之前，先执行了当前块队列中的块以及就绪队列头部作业的下一个块，τi的截止期也能得到满足。}

调度算法：执行块时的优先级反转界限

调度算法决定节点是应该执行下一个块还是保持空闲。该算法确保节点的进度prog^tail_k始终不超过MAP。算法只在块队列中有块时才执行它们。在将块从就绪队列移动到块队列之前，它会验证上述不等式对所有即将到来的高优先级任务是否成立。如果不等式对某个任务不成立，算法会计算一个时间t‘，即最早满足不等式的时间（θ(τ_{i) = ω(prog^tailk) + C^nextaa - slacki），然后节点空闲直到t‘。这种空闲时间利用了任务执行时间可能少于其WCET所产生的动态松弛，而不会引起截止期错过。}

释放算法：在有限优先级反转下协调作业插入

释放算法在任务释放时运行，确保所有节点将新释放的作业插入到其就绪队列中的相同位置。算法首先检查后台运行节点是否已经空闲（即RQ_k为空且ω(prog^tail_k) ≤ t）。如果是，则更新minProg和t_update。然后，它启动非阻塞通信，向其他节点发送本节点的进度。接着，算法通过移动块来找到MAP，并将释放的作业根据其优先级插入到就绪队列中。通过确保所有节点基于相同的MAP和任务释放信息构建就绪队列，该方法保证了执行顺序的一致性。

更新算法：通过通信减少悲观性

在实际运行中，节点通常比块的WCET更早完成块，这使得基于WCP的MAP计算过于悲观。更新算法利用通信来跟踪健康后台运行节点的实际进度。在任务释放时，节点广播其进度信息。在超时（Timeout）后，节点运行更新算法，使用接收到的信息更新minProg和t_update。这降低了对后台运行节点进度的悲观估计，从而提高了MAP，允许节点将更多块移动到块队列执行，减少了空闲时间。该算法还能检测故障的后台运行节点（例如，报告进度过低且其WCP小于释放时间的节点），并忽略其信息，从而抵御优先级反转注入攻击。

扩展到粗粒度时钟同步

文章进一步将方法扩展到时钟粗粒度同步的场景，考虑了事件时间戳与节点本地时钟接收时间之间的最大差值Δ，以及节点读取时钟值之间的最大差值δ。通过对释放算法（设置t_update = r_e + Δ）、调度算法（考虑从t - Δ开始的最早任务释放）和更新算法（设置t_update = r_e + Timeout + Δ，并调整C_send和Timeout以考虑时钟偏差）进行适当修改，方法仍然能够保证时限性。关键点在于，算法执行依赖于事件时间戳而非节点的本地时间，并且通过调整参数来补偿时钟不同步的影响。

时限性保证

该方法保证，只要任务集在单个节点上使用相同的调度算法（如速率单调调度RM或最早截止期优先EDF）是可调度的，并且每个任务的松弛时间至少等于其低优先级任务（对于RM）或截止期大于等于它的任务（对于EDF）的非抢占块的最大WCET，那么所有健康节点上的所有作业都能在其截止期前完成。调度、释放和更新算法的交互确保了优先级反转始终受到任务松弛时间的限制，并且所有节点就作业的执行顺序达成一致。通信的使用是可选的，用于提高性能，但即使没有通信或通信延迟/丢失，方法也能保证安全性（即时限性）。