3.2 调度算法与策略

3.2 调度算法与策略

本节摘要：调度决策决定「此刻谁运行」，而可调度性分析决定「这套任务集能否被承诺」。本节给出固定优先级调度的优先级分配规则、利用率判据与响应时间迭代算法，配合一个三项任务集的完整算例，把「感觉没超时」升级为「可以证明不会超时」。

一九七三年，两位学者 Liu 与 Layland 发表的论文给实时调度定了调：对一组周期性任务，按「周期越短优先级越高」分配静态优先级，是最优的固定优先级方案。这篇论文的结论今天仍写在每一本实时系统教材的第一章，也仍是 FreeRTOS、Zephyr 这类内核上开发者实际遵循的规则。本节在它的框架内展开：先讲怎么定优先级，再讲怎么验证可行，最后看动态优先级这条支线。

优先级分配：速率单调与例外

速率单调（RM）规则一句话说完：周期短的任务优先级高。直觉是周期短意味着同样时间内该任务被要求的次数多，拖延它的代价累积得更快。规则的最优性有严格证明，工程上照做即可。

两个例外值得记住。其一，截止期不等于周期的任务（比如周期 100 毫秒但要求 20 毫秒内完成），应改按截止期长短排优先级，称为截止期单调。其二，无论怎么算，确保没有两个关键任务共享同一优先级——同优先级要么靠时间片轮转（行为开始变得难分析），要么排成先后（先者可能长期压住后者）。让每个关键任务独占一档优先级，是可分析性的前提。

第一道闸门：利用率判据

优先级定好后，先做快速体检。处理器利用率是所有任务「执行时间除以周期」之和：

U = C1/T1 + C2/T2 + ... + Cn/Tn        （Ci 为最坏执行时间，Ti 为周期）
​

速率单调下，若 U 不超过上限，任务集必然可调度。上限随任务数变化：一个任务时为 1.0，两个任务约 0.828，三个任务约 0.780，任务数很多时趋近自然对数 2，约 0.693。注意这个判据是充分不必要：超过上限只说明「用判据证不出来」，任务集未必真的不可调度，此时需要第二道闸门精算。

第二道闸门：响应时间迭代

利用率判据偏保守，精确的最坏响应时间（WCRT）用不动点迭代求解。思路很直观：低优先级任务的响应时间等于自身执行时间，加上所有高优先级任务在这段时间内能抢占的次数乘以各自的执行时间；抢占次数又取决于响应时间本身，于是迭代到收敛：

输入：任务按优先级从高到低排列，参数为 Ci（最坏执行时间）、Ti（周期）、Di（截止期）
R := Ci
重复：
    R_next := Ci + 对每个优先级高于 i 的任务 j 累加：上取整(R / Tj) × Cj
    若 R_next 等于 R：收敛，R 即最坏响应时间，退出
    若 R_next 大于 Di：已注定超期，退出
    R := R_next
输出：任务 i 的最坏响应时间
​

上取整项的含义是「在我完成之前，高优先级任务 j 至少会来捣乱几次」——哪怕它只差一点到周期边界，也按来一次算，这正是「最坏情况」的口径。

完整算例：三个任务走一遍

某电机驱动板有三个周期任务，参数如下表（单位毫秒）：

按速率单调定优先级：电流环最高，解算次之，通信最低。总利用率 0.51，远低于三任务的判据 0.780，第一道闸门通过。再用迭代精算最低优先级的通信任务：

初始：R = 1.5
第一轮：R = 1.5 + 上取整(1.5/1)×0.2 + 上取整(1.5/5)×0.8
             = 1.5 + 0.4 + 0.8 = 2.7
第二轮：R = 1.5 + 上取整(2.7/1)×0.2 + 上取整(2.7/5)×0.8
             = 1.5 + 0.6 + 0.8 = 2.9
第三轮：R = 1.5 + 上取整(2.9/1)×0.2 + 上取整(2.9/5)×0.8 = 2.9，收敛
​

通信任务的最坏响应时间为 2.9 毫秒，小于截止期 10 毫秒，且余量充足。解算任务迭代收敛于 1.0 毫秒（自身 0.8 加被电流环抢占一次 0.2），电流环响应即其执行时间 0.2 毫秒。三项全部达标，这套任务集从「跑起来没发现问题」升级为「数学上可证安全」——这句话在客户审核与功能安全审计里的分量完全不同。

算例也顺便展示了三个工程细节。第一，迭代轮数极少（这里三轮收敛），在 MCU 上做在线自检都负担得起，第九章的运行时监控会用到。第二，若把通信任务周期缩到 4 毫秒，利用率升到 0.525 仍低于判据，但通信任务迭代会越过 5 毫秒的截止期吗？动手算一遍就知道：判据通过而迭代超期的情况是存在的，这就是「充分不必要」的实证。第三，若通信处理里有一段用互斥量保护的共享区，被低优先级任务持有期间会额外延长响应时间——这笔账要等第四章的优先级继承讲完才能算清。

动态优先级：最优但有代价

最早截止期优先（EDF）在每次调度点选择「截止期最近」的任务，理论上可以实现 100% 利用率仍不超期，是最优的动态算法。但工程上有三笔账：维护按截止期排序的就绪队列有对数级开销；某个任务偶尔超跑会连锁推迟后续所有任务的截止期判断，过载时行为雪崩；过载后哪些任务受害不可预测，这对安全系统近乎不可接受。因此商用 RTOS 以固定优先级为主流，EDF 思想则以受限形式渗透——比如在混合关键系统中给低关键任务动态降级。理解 EDF 的价值在于理解「为什么大家不用它」，这本身就是一种工程判断。

本节要点回顾

• 速率单调按周期分配优先级，截止期不等于周期时改用截止期单调；
• 利用率判据是快速体检：三任务上限约 0.780，通过即安全，不通过未必不安全；
• 响应时间迭代给出精确的最坏响应时间，每项都有明确物理含义；
• 算例演示了「从参数表到可证结论」的完整流程，应能在自己的项目上复现；
• 关键任务不共享优先级，是可分析性的前提而非风格偏好；
• EDF 理论最优但过载行为不可预测，商用内核因此以固定优先级为主。

常见问题

问：执行时间参数从哪来？ 三个来源按可靠度排序：静态分析工具对机器码的最坏路径推演、按硬件手册周期数的指令级估算、满负载下的实测加余量。小项目常用第三种，但要记住实测给的是「见过的最坏」，不是「可能的最坏」，余量要给足。

问：任务里访问共享外设，分析怎么算？ 把竞争外设的访问建模成一段临界资源：互斥量阻塞计入响应时间公式的阻塞项，第四章的继承协议保证阻塞有界；不加保护的总线仲裁则要看外设控制器的规格。本节的公式默认任务独立，资源竞争是它的第一号扩展。

问：利用率多少就该警惕？ 与任务数有关，但经验上系统总利用率超过七成，就应该为未来负载增长预留降级方案——余量不是浪费，是产品寿命。

问：周期抖动会破坏分析吗？ 速率单调分析假设周期恒定，轻微抖动（百分之一量级）被参数余量吸收；大抖动意味着任务模型选错了，该用偶发任务模型重新分析。

问：非周期事件怎么纳入分析？ 把偶发事件建模为「最小到达间隔的周期任务」（突发上限即间隔），这是实时理论处理不规律的通用手法——保守，但可分析。事件过于随机时，用排队论做容量估算，再用压力实测校核。