4、调度算法基础：固定优先级调度（RMS、DMS）、动态优先级调度（EDF、LLF）、调度可行性分析
各位同学，今天我们聊聊调度算法的基础。这部分内容，说白了就是实时系统的"交通规则"。你想想看，多个任务抢着用CPU，谁先跑、谁后跑，跑不跑得完——这些都得靠调度算法来管。
我个人习惯把调度算法分成两大类：固定优先级和动态优先级。前者像老派的排班表，任务一出生优先级就定死了；后者像灵活的急诊室，谁更紧急谁先上。两种思路各有千秋，咱们一个一个说。
4.1 固定优先级调度
固定优先级调度，顾名思义，每个任务的优先级在系统启动时就定好了，运行过程中不会变。这玩意儿实现简单，开销小，在嵌入式系统里用得特别多。
4.1.1 速率单调调度（RMS）
RMS是固定优先级调度里最经典的算法。它的规则很简单：任务的周期越短，优先级越高。为什么？因为周期短的任务往往更紧迫，你想想看，一个每10ms就要跑一次的任务，和一个每100ms跑一次的任务，哪个更容易错过截止时间？显然是前者。
我在项目中遇到过一件事。有个同事给三个任务分配优先级，他按任务的重要性来排，结果系统跑起来总是丢数据。我一看，周期最短的任务优先级反而最低，这不就乱套了嘛。换成RMS之后，问题立马解决。
RMS的可行性条件（充分条件）：
对于n个独立任务，如果总利用率U满足：
U = Σ(Ci/Ti) ≤ n(2^(1/n) - 1)当n→∞时，上界趋近于ln2 ≈ 0.693。也就是说，RMS最多能保证69.3%的CPU利用率。
嗯，这里要注意：这个条件是充分非必要的。什么意思？就是说即使U超过了这个上界，系统也可能可调度。但反过来，如果U没超过，那一定可调度。我在做航天项目时，一般会留20%的余量，不敢卡着上限跑。
4.1.2 截止时间单调调度（DMS）
DMS和RMS很像，但规则换了一下：任务的相对截止时间越短，优先级越高。对于周期任务来说，如果截止时间等于周期，那DMS和RMS就是一样的。但如果截止时间小于周期，DMS就更合理了。
举个例子：任务A周期100ms，截止时间50ms；任务B周期80ms，截止时间80ms。按RMS，B优先级高；按DMS，A优先级高。哪个对？我建议你仔细想想——A虽然周期长，但留给它的时间窗口其实更窄，所以DMS更合理。
| 算法 | 优先级依据 | 适用场景 |
|---|---|---|
| RMS | 周期越短，优先级越高 | 截止时间=周期的周期任务 |
| DMS | 截止时间越短，优先级越高 | 截止时间≠周期的周期任务 |
4.2 动态优先级调度
固定优先级虽然简单，但有个硬伤：它没法根据系统当前状态灵活调整。动态优先级调度就是来解决这个问题的。说白了，就是"看情况办事"。
4.2.1 最早截止时间优先（EDF）
EDF的思路特别直观：谁的截止时间最近，谁就先跑。每次调度时，系统检查所有就绪任务，挑出截止时间最近的那个。
EDF有个很漂亮的特性：它是最优的。什么意思？就是说如果存在某种调度方案能让所有任务都满足截止时间，那EDF也一定能做到。而且EDF的利用率上界是100%，比RMS的69.3%高出一截。
我的经验：EDF虽然理论上很完美，但在实际系统中要注意一个问题——过载时的行为。当CPU过载时，EDF会同时错过多个任务的截止时间，这叫"多米诺效应"。而RMS至少能保证高优先级任务不受影响。所以，如果你对系统负载没把握，RMS可能更安全。
4.2.2 最小松弛度优先（LLF）
LLF比EDF更进一步。它不光看截止时间，还考虑任务还需要跑多久。松弛度的计算公式是：
松弛度 = 截止时间 - 当前时间 - 剩余执行时间松弛度越小，说明任务越"紧张"，优先级就越高。我曾经在一个视频处理项目里用过LLF，效果不错，但有个麻烦——频繁切换。因为松弛度一直在变，任务优先级也跟着变来变去，上下文切换开销很大。
注意：LLF在实际嵌入式系统中用得不多，主要就是因为切换开销太大。除非你的硬件特别强，或者任务数量很少，否则我建议优先考虑EDF。
4.3 调度可行性分析
好，算法讲完了。但光有算法还不够，你得先确认：这组任务到底能不能被调度？这就是可行性分析要干的事。
4.3.1 利用率测试
最简单的办法就是算CPU利用率。对于RMS，用前面提到的公式：
U ≤ n(2^(1/n) - 1)对于EDF，条件更宽松：
U ≤ 1但说实话，利用率测试只是充分条件。通不过不代表不可调度，只是说没法保证。我在实际项目中，一般先用利用率测试做个快速筛选，通不过的再上更精确的方法。
4.3.2 响应时间分析
这个方法更精确。它计算每个任务在最坏情况下的响应时间，然后跟截止时间比。公式长这样：
R_i = C_i + Σ(j∈hp(i)) ⌈R_i / T_j⌉ × C_j其中hp(i)是优先级比i高的任务集合。这个方程需要迭代求解，直到R_i收敛或者超过截止时间。
我记得第一次手算这个公式时，迭代了七八次才收敛。后来我写了个小脚本，几毫秒就出结果。嗯，工具该用还是得用。
4.3.3 忙周期分析
对于更复杂的场景，比如任务有资源共享、有释放抖动，前面的方法就不够用了。这时候可以用忙周期分析。它模拟系统从某个时刻开始持续忙碌的最长时间，然后检查所有任务在这个窗口内的行为。
这个方法比较重，但很强大。我在做汽车电子项目时，ECU上有几十个任务，各种依赖关系，最后就是用忙周期分析搞定的。
总结一下我的建议：
- 任务少、周期规整 → 用利用率测试快速判断
- 任务中等规模 → 用响应时间分析
- 任务复杂、有依赖 → 上忙周期分析
- 实在搞不定 → 仿真跑一遍，看实际表现
4.4 知识体系总览
下面这张图是我画的调度算法知识体系，帮你理清脉络：
这张图把调度算法的脉络理得很清楚。你从上往下看，先选大类，再选具体算法，最后用可行性分析验证。我在做系统设计时，基本就按这个流程走。
好了，调度算法的基础就讲到这里。记住一句话：没有最好的算法，只有最合适的算法。RMS简单可靠，EDF利用率高，LLF适合特殊场景。选哪个，得看你的任务特性和系统约束。