第4章任务调度与实时性设计

第4章：任务调度与实时性设计

各位同学，今天我们来聊聊实时系统的核心——任务调度。说实话，我在做自动驾驶项目时，最头疼的往往不是算法本身，而是怎么让这些算法在正确的时间点跑起来。你想想看，一个控制指令晚了几毫秒，车可能就偏了一个车道。

4.1 固定优先级调度：RMS与DMS

固定优先级调度，说白了就是给每个任务分配一个固定的优先级，系统运行时永远让优先级最高的任务先执行。这里面有两个经典算法：RMS（速率单调调度）和DMS（截止时间单调调度）。

4.1.1 RMS：周期越短，优先级越高

RMS的思路很简单：任务的周期越短，优先级就越高。为什么？因为周期短的任务往往对实时性要求更苛刻。我举个例子：

// 两个周期性任务
Task A: 周期 T=10ms, 执行时间 C=4ms
Task B: 周期 T=20ms, 执行时间 C=6ms

// RMS分配：A的优先级高于B
// 利用率 U = 4/10 + 6/20 = 0.4 + 0.3 = 0.7

RMS有一个重要的可调度性判定条件：

RMS可调度性定理：对于n个独立任务，如果总利用率U满足：

U ≤ n(2^(1/n) - 1)

当n→∞时，U的极限约为0.693

嗯，这里要注意，这个定理给出的是充分条件，不是必要条件。也就是说，即使U超过了这个值，系统也不一定不可调度。我在项目中遇到过U=0.85的情况，通过精细调整还是跑起来了。

4.1.2 DMS：截止时间越紧，优先级越高

DMS和RMS很像，但它的判断依据是任务的截止时间（Deadline），而不是周期。当任务的截止时间不等于周期时，DMS比RMS更合理。

算法	优先级依据	适用场景
RMS	周期（Period）	截止时间=周期
DMS	截止时间（Deadline）	截止时间≠周期

我个人习惯在自动驾驶的感知模块用RMS，因为传感器数据采集周期是固定的。但在控制模块，我更喜欢DMS，因为控制指令的截止时间往往比采集周期更短。

4.2 EDF调度算法

EDF（最早截止时间优先）是另一种思路：谁的时间最紧迫，谁就先跑。它不像RMS那样固定优先级，而是动态调整的。

EDF的核心思想：每次调度时，选择当前截止时间最早的任务执行。这是一个最优的动态优先级调度算法，理论上利用率可以达到100%。

但EDF有个坑——过载问题。当系统过载时，EDF会表现出「多米诺骨牌效应」：一个任务错过截止时间，可能导致一连串任务都错过。我曾经在一个项目中吃过这个亏，后来加了个过载检测机制才解决。

// EDF调度示例（伪代码）
void edf_schedule() {
    task_t *ready_queue = get_ready_tasks();
    task_t *earliest = NULL;
    
    for each task in ready_queue {
        if (earliest == NULL || task.deadline < earliest.deadline) {
            earliest = task;
        }
    }
    
    if (earliest != NULL) {
        dispatch(earliest);
    }
}

4.3 优先级反转与解决

优先级反转，这是实时系统里最经典的坑。说白了就是：一个高优先级任务被一个低优先级任务阻塞了，而中间还有个中等优先级任务在捣乱。

4.3.1 问题场景

假设有三个任务：

Task H（高优先级）：需要访问共享资源R
Task M（中优先级）：不需要R，纯计算
Task L（低优先级）：已经占用了R

运行过程是这样的：

L先运行，拿到了R
H就绪，抢占L，但发现R被L占着，只能等待
M就绪，抢占L（因为L被阻塞了），M开始运行
H还在等...等M跑完，等L释放R

你看，H明明优先级最高，却被M和L联手「欺负」了。这就是优先级反转。

4.3.2 解决方案：优先级继承

优先级继承协议的做法是：当高优先级任务被低优先级任务阻塞时，低优先级任务临时「继承」高优先级任务的优先级。

优先级继承规则：

任务L持有资源R时，如果被任务H阻塞，L的优先级临时提升到H的级别
L释放R后，优先级恢复原值
这样可以防止M这样的中等优先级任务插队

我在写VxWorks的驱动时就用过这个机制。说实话，刚开始觉得这玩意儿多此一举，直到有一次在实车上复现了优先级反转导致的控制延迟...嗯，从那以后我再也不敢小看它了。

4.3.3 解决方案：优先级天花板协议

优先级天花板协议更激进一些：每个共享资源都有一个「天花板优先级」，等于所有可能访问该资源的任务中的最高优先级。任何任务访问资源时，优先级自动提升到天花板级别。

两种协议的对比：

优先级继承：只在发生阻塞时才提升优先级，实现复杂但更灵活
优先级天花板：提前设定好天花板，实现简单但可能导致不必要的优先级提升

我个人建议：在资源少、任务关系明确的系统中用天花板协议；在复杂系统中用继承协议。

4.4 调度分析工具

光靠脑子想是不行的，得用工具。我常用的几个工具：

4.4.1 响应时间分析（RTA）

RTA是计算任务最坏情况响应时间的经典方法。公式如下：

// 任务i的响应时间Ri
Ri = Ci + Σ(ceil(Ri / Tj) * Cj)  // 对所有优先级高于i的任务j

// 迭代计算，直到Ri收敛或超过截止时间
R_i^(n+1) = Ci + Σ(ceil(R_i^n / Tj) * Cj)

这个公式看着复杂，其实说白了就是：任务的响应时间 = 自己的执行时间 + 被高优先级任务抢占的时间。

4.4.2 调度仿真工具

我常用的几个：

MAST：开源，支持RMS、EDF等多种调度分析
Cheddar：图形化界面，适合教学和快速验证
SimSo：Python写的，可以自定义调度策略

记得有一次，我用Cheddar仿真一个8任务的系统，发现RMS理论分析说不可调度，但仿真跑下来却没问题。后来一查，原来是任务之间有资源依赖，理论分析过于保守了。所以我的建议是：理论分析 + 仿真验证，两手都要硬。

4.4.3 时序分析工具

在实际的嵌入式系统中，我还会用Trace工具来抓取任务的运行时序：

// Trace32脚本示例
; 设置任务切换跟踪
TRACE.METHOD TaskSwitch
TRACE.List TASK.*
; 开始记录
TRACE.Start
; 运行一段时间后停止
WAIT 5.s
TRACE.Stop
; 查看结果
TRACE.View

通过Trace工具，你可以看到每个任务什么时候开始、什么时候结束、被谁抢占了。这对于排查调度问题特别有用。

我的调试经验：

遇到调度问题时，先别急着改代码。先用Trace工具抓一段时序，看看任务的实际运行情况。很多时候，问题出在「你以为的」和「实际发生的」不一样。

小结

这一章我们聊了：

固定优先级调度（RMS/DMS）的原理和适用场景
EDF调度算法的优势和过载问题
优先级反转的成因和两种解决方案
调度分析工具的使用方法

下一章我们会深入讨论任务间通信与同步机制，包括信号量、消息队列、共享内存这些在实际项目中天天用的东西。到时候我会分享一些在自动驾驶项目中踩过的坑，敬请期待。

公众号:蓝海资料掘金营，微信deep3321

📚 课程目录