第4章：固定优先级调度（RM）——速率单调调度原理、可调度性测试与局限性
大家好，我是你们的老朋友。今天我们来聊聊实时调度里一个非常经典的话题——速率单调调度，也就是RM算法。
说实话，RM算法是我个人非常喜欢的一个算法。它简单、直观，而且有严格的理论支撑。我在做嵌入式实时系统那几年，跟它打过不少交道。今天就把我的一些经验和踩过的坑，一并分享给你。
4.1 速率单调调度（RM）原理
RM算法的核心思想，说白了就是一句话：周期越短的任务，优先级越高。
你想想看，一个任务每5ms就要跑一次，另一个任务每100ms才跑一次。哪个更紧急？当然是周期短的那个。RM就是这么干的——它根据任务的周期来分配固定优先级，周期越短，优先级越高。
这里有个关键点：优先级是固定的。任务一旦创建，它的优先级就定死了，不会像EDF那样动态调整。这也是为什么RM被称为“固定优先级调度”的代表算法。
核心原则：
- 每个任务有一个固定的周期 Ti
- 每个任务有一个最坏情况执行时间 Ci
- 优先级与周期成反比：Ti 越小，优先级越高
- 任务必须在下一个周期到来前完成（截止时间 = 周期）
举个例子吧。假设我们有三个任务：
| 任务 | 周期 T (ms) | 执行时间 C (ms) | RM优先级 |
|---|---|---|---|
| τ₁ | 5 | 1 | 最高 |
| τ₂ | 10 | 2 | 中 |
| τ₃ | 20 | 3 | 最低 |
按照RM规则，τ₁周期最短，拿最高优先级。τ₃周期最长，优先级最低。调度器会优先执行τ₁，只有当τ₁空闲时，才会去执行τ₂或τ₃。
嗯，这里要注意：高优先级任务会抢占低优先级任务。如果τ₁在τ₂执行到一半时被激活了，τ₂会被挂起，等τ₁执行完再继续。
4.2 可调度性测试：Liu & Layland 定理
光知道怎么分配优先级还不够。你还需要回答一个问题：这组任务到底能不能被调度？
1973年，Liu和Layland两位大神给出了一个简洁而优美的答案。这就是著名的Liu & Layland 定理。
Liu & Layland 充分条件：
对于 n 个独立、周期性的实时任务，如果满足：
Σ (Ci / Ti) ≤ n · (21/n - 1)
那么这组任务在RM调度下一定是可调度的。
这个公式看着有点吓人，其实理解起来不难。左边是所有任务的CPU利用率之和。右边是一个关于任务数量n的边界值。
我算几个值给你看看：
| 任务数 n | 边界值 n·(21/n - 1) | 近似值 |
|---|---|---|
| 1 | 1.0 | 100% |
| 2 | 2·(√2 - 1) | 82.8% |
| 3 | 3·(∛2 - 1) | 77.9% |
| 4 | 4·(⁴√2 - 1) | 75.6% |
| →∞ | ln 2 | 69.3% |
看到了吗？当任务数趋于无穷时，边界值收敛到 ln 2 ≈ 69.3%。这意味着，如果所有任务的CPU利用率加起来不超过69%，那RM调度基本稳了。
我的经验：在实际项目中，我一般把CPU利用率控制在60%以内。为什么？因为Liu & Layland定理只是一个充分条件，不是必要条件。利用率超过边界值不代表一定不可调度，但风险会急剧上升。我曾经在一个项目中把利用率压到75%，结果系统在峰值负载下频繁丢任务……那次教训挺深刻的。
我们拿前面的例子算一下：
U = 1/5 + 2/10 + 3/20 = 0.2 + 0.2 + 0.15 = 0.55
n=3时，边界值 = 3·(21/3 - 1) ≈ 0.779
0.55 < 0.779，满足条件。所以这组任务是可调度的。
4.3 实际应用中的局限性
理论很美好，现实很骨感。RM算法在实际应用中，有不少坑等着你。
4.3.1 利用率上限问题
我刚才说了，RM的理论利用率上限只有约69%。这意味着，即使你的CPU还有30%的空闲，RM也可能调度不过来。相比之下，EDF可以达到100%的利用率。这是RM的一个硬伤。
4.3.2 任务间依赖关系
Liu & Layland定理假设任务之间是相互独立的。但实际系统中，任务经常需要共享资源、传递数据。一旦引入互斥锁、信号量这些东西，就可能出现优先级反转的问题。
避坑指南：我曾经在一个无人机飞控项目中，遇到过高优先级任务被低优先级任务阻塞的情况。原因是它们共享了一个I2C总线。高优先级任务想访问总线，但总线被低优先级任务占着，而低优先级任务又被中等优先级任务抢占了CPU……结果高优先级任务活活等了好几个周期。这就是典型的优先级反转。
解决方案是引入优先级继承协议或优先级天花板协议。这个我们后面章节会详细讲。
4.3.3 任务周期与截止时间不匹配
RM假设任务的截止时间等于周期。但很多实际场景中，截止时间可能小于周期。比如一个传感器任务每10ms采集一次数据，但要求在8ms内完成处理。这种情况下，RM的原始理论就不适用了。
4.3.4 任务执行时间不稳定
RM要求你知道每个任务的最坏情况执行时间（WCET）。但说实话，这个值很难精确测量。我在项目中经常遇到的情况是：测试时一切正常，上线后某个任务因为数据量突增，执行时间翻了好几倍，直接把系统搞崩了。
我的建议：给每个任务的WCET留出20%-30%的余量。别卡得太死。实时系统最怕的就是“刚好够用”。
4.3.5 任务数量变化
RM是固定优先级调度。一旦任务数量变化，你需要重新计算所有任务的优先级。这在动态系统中是个大麻烦。比如一个智能驾驶系统，不同驾驶模式下激活的任务集完全不同，用RM就得准备多套优先级方案。
4.4 知识体系总览
为了帮你理清思路，我画了一张图，把RM的核心知识点串起来：
这张图把RM的核心脉络理清楚了。从左到右，从上到下，你可以看到：原理是什么、怎么测试、有什么好处、有什么坑。
4.5 小结
RM算法是实时调度领域的基石之一。它简单、可靠，特别适合那些任务周期固定、数量不多、负载可控的系统。但它也有明显的短板——利用率上限低、对任务依赖关系敏感、依赖WCET的精确性。
我个人觉得，RM最适合的场景是：任务数量少（比如3-5个）、周期差异大、对可预测性要求极高的系统。比如一些工业控制器、简单的传感器采集系统。
如果你的系统任务数量多、负载波动大，或者任务间有复杂的资源共享，那就要考虑更高级的调度策略了。比如后面我们会讲到的EDF、优先级继承协议等。
好了，这一章就到这里。记住一句话：RM不是万能的，但在它擅长的领域，它是最可靠的。
公众号:蓝海资料掘金营，微信deep3321