📚 课程目录第4章实时调度基础方法

4. 实时调度基础方法

星务软件运行在资源受限的星载计算机上，任务往往带有明确的周期和截止期约束。调度方法要回答两个问题：按什么规则决定谁先运行，以及这组任务在当前处理器上是否一定来得及完成。本节围绕周期任务模型，介绍优先级调度、速率单调调度（RMS）、最早截止期优先调度（EDF），并给出可行性判定与响应时间分析的基本方法。

一、周期任务模型与调度假设

实时调度分析通常先把任务抽象为周期任务。一个任务 τ_i 用四个参数描述：执行时间 C_i、周期 T_i、相对截止期 D_i、释放时刻相位 φ_i。若 D_i = T_i，称为隐含截止期；若 D_i < T_i，称为约束截止期。星务软件中，姿态控制周期任务、遥测采集任务、遥控指令解析任务都可以按此模型描述。

分析前需明确几条假设：任务之间相互独立、不主动阻塞；任务可被抢占；上下文切换和调度开销忽略或计入 C_i；所有任务在单处理器上运行。若实际系统存在共享资源互斥、中断嵌套或不可抢占区，需要额外引入阻塞时间，不能直接套用下面的判据。

二、优先级调度与速率单调调度

优先级调度是最基本的实时调度框架：每个任务分配一个固定优先级，调度器始终运行就绪队列中优先级最高的任务。固定优先级调度的优点是实现简单、行为可预测，适合星务软件这类需要长期稳定运行的场景。

速率单调调度（Rate Monotonic Scheduling，RMS）是固定优先级调度中最经典的分配规则：周期越短，优先级越高。其直觉是周期短的任务释放更频繁，若被长周期任务阻塞，容易在短时间内连续错过截止期。RMS 在 D_i = T_i 且任务可抢占的条件下是最优的固定优先级分配策略——如果存在一种固定优先级分配能使任务集可调度，那么 RMS 也能使其可调度。

RMS 的充分判据是利用率上界：当 n 个任务满足

U = Σ (C_i / T_i) ≤ n · (2^(1/n) − 1)

时任务集一定可调度。n 增大时该上界趋近 ln2 ≈ 0.693。注意这是充分条件而非必要条件：利用率超过上界时任务集仍可能可调度，需要用响应时间分析进一步判断。

三、最早截止期优先调度

最早截止期优先调度（Earliest Deadline First，EDF）是动态优先级调度：每次调度时选择绝对截止期最近的任务运行。任务的优先级随释放时间动态变化，而不是固定不变。

EDF 在单处理器、任务可抢占、D_i = T_i 的条件下是最优的动态优先级调度算法，其可调度充要条件是利用率不超过 1：

U = Σ (C_i / T_i) ≤ 1

相比 RMS，EDF 能利用更多处理器能力，但代价是优先级动态变化、实现和验证更复杂，且过载时行为不易预测——一旦超载，可能引发连锁错过截止期。星务软件中，安全关键任务常采用固定优先级，非关键或软实时任务可考虑 EDF。

四、可行性判定与响应时间分析

利用率判据只能给出粗略结论。更精确的方法是响应时间分析（Response Time Analysis，RTA）。对固定优先级任务，任务 i 的最坏响应时间 R_i 满足：

R_i = C_i + Σ_{j∈hp(i)} ⌈R_i / T_j⌉ · C_j

其中 hp(i) 表示优先级高于 i 的任务集合。该式是递归的，可用迭代法求解：从 R_i⁽⁰⁾ = C_i 开始，反复代入计算，直到收敛或超过 D_i。若最终 R_i ≤ D_i，则任务 i 可调度；若迭代过程中 R_i 超过 D_i，则不可调度。

下面给出一个星务软件教学示例。假设三个周期任务运行在单处理器上，参数如下（示例数据，用于说明方法）：

任务	功能	C_i/ms	T_i/ms	D_i/ms
τ₁	姿态控制	2	10	10
τ₂	遥测采集	3	20	20
τ₃	遥控解析	5	50	50

计算利用率：U = 2/10 + 3/20 + 5/50 = 0.2 + 0.15 + 0.1 = 0.45。RMS 上界为 3×(2^1/3−1) ≈ 0.780，U = 0.45 小于上界，因此 RMS 下可调度。

再用 RTA 精确验证。按 RMS，优先级 τ₁ > τ₂ > τ₃。对 τ₃：

R_3^(0) = 5
R_3^(1) = 5 + ⌈5/10⌉·2 + ⌈5/20⌉·3 = 5 + 2 + 3 = 10
R_3^(2) = 5 + ⌈10/10⌉·2 + ⌈10/20⌉·3 = 5 + 2 + 3 = 10

收敛于 R₃ = 10 ms ≤ D₃ = 50 ms，τ₃ 可调度。τ₁、τ₂ 的响应时间更短，同样满足。若把 τ₃ 的 C₃ 增大到 30 ms，则 U = 0.2 + 0.15 + 0.6 = 0.95，超过 RMS 上界，但 RTA 会给出 R₃ 是否仍 ≤ 50 ms 的精确结论——这正是 RTA 相对利用率判据的价值。

五、方法选择与工程注意点

在星务软件中，选择调度方法要结合任务关键性和实现约束。安全关键、周期固定的任务适合 RMS，因为优先级静态、行为可预测、便于形式化验证；对处理器利用率要求高、任务截止期差异大的场景可考虑 EDF，但必须处理超载保护。无论采用哪种方法，都应先用利用率判据快速筛选，再用响应时间分析精确验证，尤其当 U 接近上界或任务存在约束截止期时。

工程提示：若任务间存在共享资源（如总线、寄存器组），需在响应时间公式中加入阻塞时间 B_i，即 R_i = C_i + B_i + Σ⌈R_i/T_j⌉·C_j。忽略阻塞会低估响应时间，导致实际运行中错过截止期。

注意：利用率判据是充分条件，不是必要条件。U 超过 RMS 上界不代表一定不可调度，必须用 RTA 确认；反之，U 低于上界也不能保证存在共享资源时仍可调度。

掌握上述方法后，面对一组星务周期任务，可以按“建模 → 选策略 → 算利用率 → 做 RTA → 判断是否满足截止期”的路径完成调度可行性分析，为后续任务划分与资源分配提供依据。