3. 调度算法（上）：RMS 与 DM 原理，以及那个让人头疼的优先级反转
各位好，咱们今天聊聊实时调度里最基础、也最绕不开的两个算法——RMS 和 DM。说实话，我刚入行那会儿，觉得调度嘛，不就是给任务排个序？后来在项目里被坑过几次，才明白这里面的门道有多深。
你想想看，一个嵌入式系统里跑着十几个任务，有的要每 10 毫秒采集一次传感器，有的要 50 毫秒处理一次数据，还有的偶尔才跑一次。怎么保证它们都能按时完成？这就是调度算法要解决的问题。
3.1 RMS（速率单调调度）—— 周期越短，优先级越高
RMS 的全称是 Rate Monotonic Scheduling，中文叫速率单调调度。它的核心思想特别简单：任务的周期越短，优先级就越高。
为什么？因为周期短的任务，留给它的时间窗口也短，自然得优先处理。这就像你同时要回一封紧急邮件和准备下周的汇报——邮件半小时内要回，汇报三天后交，你肯定先处理邮件。
RMS 的核心规则：
- 所有任务必须是周期性的
- 任务之间相互独立，没有资源竞争
- 任务的截止时间等于它的周期
- 优先级在系统启动时就定好了，运行期间不变
我在一个工业控制项目里用过 RMS。当时有 3 个任务：一个 10ms 的传感器采集，一个 50ms 的控制计算，还有一个 200ms 的数据上报。按 RMS 规则，采集任务优先级最高，控制计算次之，上报最低。跑起来很稳，从来没丢过数据。
但 RMS 有个前提——你得先算算系统能不能撑得住。这就引出了 RMS 可调度性分析。
3.1.1 可调度性判定：别等跑起来才发现不行
RMS 有一个经典的充分条件，叫 Liu & Layland 定理。对于 n 个独立周期任务，如果所有任务的 CPU 利用率满足下面这个公式，那系统一定是可调度的：
U = Σ(Ci / Ti) ≤ n × (2^(1/n) - 1)其中 Ci 是任务的最坏执行时间，Ti 是周期。当 n 趋向无穷大时，这个上限会收敛到约 69.3%。
嗯，这里要注意——这个 69.3% 是充分条件，不是必要条件。也就是说，即使利用率超过了 69.3%，系统仍然可能是可调度的。我见过不少项目，利用率跑到 80% 甚至 85%，照样跑得好好的。但反过来，如果利用率低于 69.3%，那一定没问题。
| 任务数 n | 利用率上限 | 说明 |
|---|---|---|
| 1 | 100% | 单任务，随便跑 |
| 2 | 82.8% | 两个任务，还有余量 |
| 3 | 77.9% | 三个任务，开始紧张 |
| 4 | 75.6% | 四个任务，要小心了 |
| 5 | 74.3% | 五个任务，逼近极限 |
| →∞ | 69.3% | 理论极限 |
我的经验：实际项目中，我一般把 RMS 利用率控制在 75% 以下。超过这个数，我会用更精确的响应时间分析法再算一遍，而不是只看 Liu & Layland 的结论。
3.2 DM（截止时间单调调度）—— 更灵活的 RMS
DM 的全称是 Deadline Monotonic Scheduling。它和 RMS 很像，唯一的区别是：任务的截止时间越短，优先级越高。
你可能会问：RMS 不是已经按周期排优先级了吗？DM 和它有什么区别？
区别大了。RMS 假设截止时间等于周期，但实际项目中，很多任务的截止时间比周期短。比如一个传感器每 100ms 采集一次数据，但要求 80ms 内必须处理完。这时候 RMS 就不太合适了，因为它的优先级只跟周期有关，不关心截止时间。
DM 正好解决了这个问题。它直接按截止时间排序——谁的时间更紧，谁先跑。
DM 的核心规则：
- 任务的优先级与截止时间成反比
- 截止时间可以小于或等于周期
- 同样属于静态优先级调度
- RMS 是 DM 的一个特例（当 Di = Ti 时）
我记得在一个汽车电子项目里，有个任务周期是 20ms，但截止时间只有 10ms——因为它的输出要驱动一个快速响应的执行器。如果用 RMS，它的优先级跟其他 20ms 周期的任务一样，但实际它更紧急。换成 DM 后，问题就解决了。
3.2.1 DM 的可调度性分析
DM 没有像 RMS 那样简洁的利用率公式。常用的方法是 响应时间分析（Response Time Analysis, RTA）。简单说，就是计算每个任务在最坏情况下的响应时间，看它能不能在截止时间前完成。
公式长这样：
R_i = C_i + Σ(⌈R_i / T_j⌉ × C_j) （其中 j 是优先级高于 i 的任务）这个公式需要迭代计算，直到 R_i 收敛或者超过截止时间。我一般用 Excel 或者写个小脚本算，手算太容易出错了。
注意：DM 的可调度性分析比 RMS 复杂，但换来的是更灵活的截止时间设置。如果你的任务截止时间都等于周期，直接用 RMS 就行，省事。如果有些任务的截止时间比周期短，那就得上 DM。
3.3 优先级反转——静态调度的阿喀琉斯之踵
好，前面讲的都是理想情况——任务之间没有资源竞争。但现实世界不是这样的。任务要访问共享数据、要操作硬件、要等待信号量。这时候，一个经典问题就来了：优先级反转。
什么叫优先级反转？简单说就是：高优先级任务被低优先级任务阻塞，而中优先级任务趁机抢跑。
我画个图帮你理解：
你看这个图：
- t0 时刻，低优先级的任务 C 拿到了一个共享资源的锁
- t1 时刻，高优先级的任务 A 来了，它也要用这个资源，但锁在 C 手里，只能等着
- 这时候中优先级的任务 B 来了——它不需要那个资源，但它优先级比 C 高，直接把 C 抢占了
- 结果呢？任务 A 明明优先级最高，却要等任务 B 跑完，再等任务 C 释放锁，才能继续执行
这就是优先级反转。高优先级任务被低优先级任务间接阻塞，中优先级任务反而先跑完了。
我曾经踩过的坑：在一个无人机飞控项目里，我用了 RMS 调度，所有任务都算得好好的，利用率才 60%。但一跑起来，高优先级的姿态控制任务偶尔会超时。查了两天才发现，是一个低优先级的日志任务持有了 I²C 总线锁，中间还被几个中优先级任务打断。姿态任务等锁等到黄花菜都凉了。
3.3.1 怎么解决？优先级继承与优先级天花板
解决优先级反转，主流有两种方法：
| 方法 | 原理 | 优点 | 缺点 |
|---|---|---|---|
| 优先级继承 | 低优先级任务持有锁时，临时提升到等待该锁的最高优先级任务的优先级 | 实现相对简单，只在必要时提升 | 可能发生链式阻塞，需要嵌套锁支持 |
| 优先级天花板 | 每个资源有一个预设的优先级天花板，任务访问资源时自动提升到天花板优先级 | 避免链式阻塞，死锁风险低 | 需要预先分析所有资源的访问关系 |
我个人更倾向于优先级天花板协议。虽然前期分析工作多一些，但运行时的行为更可预测。在 FreeRTOS 和 VxWorks 里，这两种协议都有现成的实现，直接用就行。
避坑指南：如果你用优先级继承，记得检查你的 RTOS 是否支持嵌套锁的优先级继承。有些轻量级 RTOS 只支持单层继承，嵌套锁场景下会出问题。我曾经在一个项目里因为这个原因，不得不自己实现了一个简单的优先级天花板协议。
3.4 小结：RMS vs DM，你该怎么选？
说了这么多，最后给个实用的选择建议：
- 所有任务的截止时间都等于周期 → 用 RMS，简单可靠
- 部分任务的截止时间比周期短 → 用 DM，更灵活
- 任务之间有资源竞争 → 不管用 RMS 还是 DM，都要加上优先级继承或天花板协议
- 系统利用率超过 70% → 别只看 Liu & Layland 的公式，做响应时间分析
嗯，调度算法这个话题，今天先聊到这儿。RMS 和 DM 是实时系统的基石，理解透了，后面讲 EDF 和混合调度策略的时候，你会觉得轻松很多。优先级反转这个问题，我建议你在自己的开发板上搭个实验，亲眼看看反转是怎么发生的——比看十遍文章都管用。