📚 课程目录第3章任务建模与调度问题形式化

3. 任务建模与调度问题形式化

要让星务软件在有限的计算资源下稳定运行，第一步不是写调度器，而是把“任务”和“约束”用统一的数学语言描述清楚。任务建模与调度问题形式化，就是把卫星上分散的功能需求，抽象成一组可计算、可比较、可验证的参数与目标函数。只有形式化之后，我们才能判断一个任务集是否可调度、响应时间是否满足要求、能耗是否在预算之内，也才能进一步分析问题的复杂度并选择合适的求解方法。

一、任务属性：从功能需求到可计算参数

星务软件中的任务通常对应一段周期性或事件触发的处理逻辑，例如姿态数据采集、遥测组帧、遥控指令解析、载荷数据存储等。形式化建模时，每个任务 τ_i 至少需要以下属性：

执行时间 C_i：任务在最坏情况下的处理器占用时间，单位通常为毫秒或微秒。工程上取最坏执行时间（WCET），而不是平均值。
周期 T_i：任务被释放的最小时间间隔。周期任务在每个周期内至少到达一次。
相对截止期 D_i：从任务释放到必须完成的时间上限。常见约定 D_i ≤ T_i，若 D_i = T_i 称为隐式截止期。
优先级 P_i：静态或动态分配的调度优先级，数值越大通常表示越优先。
释放抖动 J_i：任务实际释放时刻相对理想周期的偏差，反映中断响应和时钟精度的影响。
依赖关系：任务之间的先后约束，如 τ_a → τ_b 表示 τ_b 必须在 τ_a 完成后才能开始。

以某卫星星务计算机为例，假设其任务集如下（示例参数，用于说明建模方法）：

任务	功能	C_i/ms	T_i/ms	D_i/ms	优先级
τ₁	姿态数据采集	2	20	20	高
τ₂	遥测组帧	4	50	50	中
τ₃	遥控指令解析	1	100	30	高
τ₄	载荷数据存储	6	200	200	低

这组参数中，τ₃ 的截止期小于周期，属于“截止期小于周期”的约束，调度时必须优先保证。τ₁ 与 τ₂ 之间存在数据依赖：姿态数据采集完成后才能组帧，因此 τ₁ → τ₂ 是一条依赖边。

二、资源约束：处理器之外的限制

星务软件的任务不仅竞争 CPU 时间，还竞争其他资源。形式化时，资源约束通常分为以下几类：

处理器资源：单核或多核 CPU 的可用时间。多核时还需考虑任务到核的绑定关系。
共享资源：总线、存储器、外设接口等。多个任务访问同一资源时可能产生阻塞，需要引入互斥信号量或优先级继承协议。
能量约束：卫星在光照区和阴影区能量预算不同，任务调度需考虑功耗峰值和平均功耗。
通信带宽：遥测下行、遥控上行、星间链路的数据速率限制。

资源约束在形式化模型中通常表示为：任务 τ_i 在执行期间需要占用资源集合 R_i，任意时刻同一资源不能被两个任务同时占用。若存在资源冲突，则需在调度模型中引入阻塞时间 B_i，它会影响响应时间分析。

三、调度目标：可调度性、响应时间与能耗

调度问题不是单一目标优化，而是多目标约束满足。常见目标包括：

可调度性：是否存在一种调度方案，使所有任务都能在截止期前完成。这是最基本的可行性目标。
响应时间：任务从释放到完成的最坏时间 R_i，要求 R_i ≤ D_i。响应时间分析是实时调度理论的核心。
能耗：在满足可调度性的前提下，最小化总能耗或峰值功耗。常用动态电压频率调节（DVFS）与任务调度联合优化。
资源利用率：处理器利用率 U = Σ(C_i/T_i)，是判断可调度性的重要指标。

对于上表任务集，单核利用率 U = 2/20 + 4/50 + 1/100 + 6/200 = 0.1 + 0.08 + 0.01 + 0.03 = 0.22，即 22%。利用率不高，但 τ₃ 的截止期较紧，仍需检查响应时间。

四、问题分类与复杂度

任务调度问题可按多个维度分类：

按任务到达方式：周期任务、偶发任务、非周期任务。
按截止期：隐式截止期（D=T）、约束截止期（D<T）、任意截止期。
按优先级：静态优先级（如 RM）、动态优先级（如 EDF）。
按处理器：单核、同构多核、异构多核。
按依赖：独立任务、有向无环图（DAG）任务、带资源互斥的任务。

复杂度方面，单核周期任务在隐式截止期下的可调度性判定，RM 算法有经典利用率上界 n(2^1/n−1)，EDF 在 U ≤ 1 时可调度。但一旦引入任意截止期、多核、DAG 依赖或能耗约束，问题往往变为 NP 难。例如，多核全局 EDF 的可调度性判定是 NP 难的，带资源约束的响应时间分析也常需近似或迭代求解。因此，工程上常采用“先形式化建模，再选择可判定子类或启发式算法”的策略。

上图把任务属性、资源约束、调度目标、问题分类和复杂度放在同一张关系图中。可以看到，形式化建模不是孤立地列参数，而是把“任务—资源—目标—复杂度”串成一条分析链：先定义 τ_i 的属性，再叠加资源约束，然后明确要优化的目标，最后根据问题分类判断它属于可判定子类还是 NP 难问题，从而决定采用精确算法还是启发式方法。

建模提示：在星务软件工程中，建议先建立任务参数表，再标注依赖边和共享资源，最后写出目标函数。参数表应包含 WCET、周期、截止期、优先级和资源需求；依赖边用有向图表示；目标函数至少写出可调度性约束和响应时间约束。这样得到的模型可以直接用于后续的调度算法设计与验证。

总结来说，任务建模与调度问题形式化的核心是：用 C_i、T_i、D_i、P_i 等参数描述任务，用资源集合和阻塞时间描述约束，用可调度性、响应时间和能耗描述目标，再按到达方式、截止期、优先级、处理器和依赖关系分类，最后根据复杂度选择求解路径。这一形式化框架是后续所有调度算法、仿真验证和工程实现的共同基础。