3. 单处理器调度算法：FCFS、SJF、RR、优先级调度、EDF、RMS
调度算法，说白了就是操作系统怎么决定「下一个该谁跑」。单处理器环境下，CPU 只有一个，任务却有一堆。谁先上？谁后上？谁该被抢断？这背后就是调度策略在起作用。
我这些年做嵌入式项目，踩过不少调度上的坑。有时候你觉得算法选对了，跑起来却各种翻车。嗯，今天咱们就把六种经典算法掰开揉碎讲清楚。
3.1 FCFS（先来先服务）
FCFS 是最朴素的算法。谁先到，谁先跑。就像排队买奶茶，先来的先拿到。
核心逻辑：非抢占式。任务按到达时间排序，CPU 一旦分配给某个任务，就一直跑到它结束。
优点：实现简单，公平感强。
缺点：平均等待时间可能很长。尤其是一个长任务堵在前面，后面短任务全得等。
我曾经在一个数据采集项目里用过 FCFS。传感器数据采集任务很短，但被一个日志写入的长任务堵住了。结果采集延迟飙升，数据丢包。后来我换成了别的算法。
避坑指南：我曾经以为 FCFS 最公平，结果发现它只对「先来」公平，对「短任务」极不公平。如果你的系统里任务执行时间差异很大，慎用 FCFS。
3.2 SJF（最短作业优先）
SJF 的思路很直接：谁执行时间短，谁先跑。你想想看，短任务先跑完，后面的长任务等的时间也短，整体平均等待时间就降下来了。
两种变体：
- 非抢占式 SJF：任务一旦开始，就跑到结束。新来的短任务只能等下次调度。
- 抢占式 SJF（SRTF）：新来的短任务如果比当前任务剩余时间还短，就抢断。
优点：理论上平均等待时间最小。
缺点：需要提前知道任务执行时间。这在嵌入式系统里往往做不到。而且长任务可能一直得不到 CPU，造成「饥饿」。
我记得有个电机控制项目，任务执行时间基本固定，我就用了 SJF。效果不错。但如果是任务时间不确定的场景，比如网络数据包处理，SJF 就不好使了。
我的习惯：如果任务执行时间能通过 profiling 测出来，SJF 是个好选择。否则别碰它。
3.3 RR（时间片轮转）
RR 是 FCFS 的改进版。每个任务分一个时间片，时间片用完就换下一个。大家轮流来，谁也别想独占 CPU。
关键参数：时间片大小。
- 时间片太大 → 退化成 FCFS。
- 时间片太小 → 上下文切换开销太大。
优点：响应时间短，公平性好。
缺点：上下文切换开销不可忽视。时间片设置需要经验。
我建议时间片设为 10-100ms 之间。具体看你的任务切换开销有多大。我曾经在一个 RTOS 项目里把时间片设成 5ms，结果切换开销占了 20% CPU，得不偿失。
避坑指南：我曾经犯过一个错误——在中断密集的系统里用 RR。中断一来，时间片就被打断，调度效果大打折扣。后来我改成了优先级调度。
3.4 优先级调度
每个任务有个优先级。高优先级的任务先跑。可以是非抢占式，也可以是抢占式。
常见问题：
- 优先级反转：低优先级任务持有资源，高优先级任务等它释放。结果中等优先级任务插进来，高优先级任务反而被「反转」了。
- 饥饿：低优先级任务永远得不到 CPU。
解决方案：
- 优先级继承协议：低优先级任务临时提升到高优先级，防止反转。
- 优先级天花板协议：任务访问共享资源时，优先级提升到最高可能值。
我记得在一个无人机飞控项目里，遇到过优先级反转。姿态控制任务优先级高，但被一个低优先级的传感器校准任务堵住了。结果无人机差点翻车。后来加了优先级继承，问题解决。
我的建议：优先级调度很灵活，但一定要处理好反转和饥饿。否则系统会出大问题。
3.5 EDF（最早截止时间优先）
EDF 是实时系统里的明星算法。谁离截止时间最近，谁先跑。动态优先级，每个时刻都在变。
核心思想：
- 任务到达时，计算它的截止时间。
- 调度器每次选截止时间最早的任务。
- 抢占式：新任务截止时间更早，就抢断当前任务。
优点：理论上 CPU 利用率可以到 100%。
缺点：实现复杂。需要精确的时钟和排序。过载时性能急剧下降。
我曾经在一个视频编码项目里用 EDF。任务都是周期性的，截止时间明确。效果很好，CPU 利用率跑到 95% 都没丢帧。但有一次任务突发增多，系统直接崩溃。嗯，EDF 过载时确实脆弱。
避坑指南：EDF 适合任务数稳定、截止时间明确的场景。如果任务会突发增多，建议加一个过载保护机制。
3.6 RMS（速率单调调度）
RMS 是固定优先级调度的一种。周期越短的任务，优先级越高。说白了，跑得越快的任务，越优先。
核心定理：
- 对于 n 个周期性任务，如果 CPU 利用率 ≤ n(2^(1/n) - 1)，则所有任务可调度。
- n 很大时，这个值趋近于 ln2 ≈ 69.3%。
优点：实现简单，固定优先级，不需要动态计算。
缺点：CPU 利用率上限只有 69.3%（理论上限）。实际更低。
我建议 RMS 用在任务周期已知、且 CPU 利用率不高的场景。比如传感器采集系统，任务周期固定，RMS 就很好用。
我的习惯：RMS 和 EDF 怎么选？如果任务周期固定、数量不多，我选 RMS。如果任务周期变化大、需要高利用率，我选 EDF。
3.7 算法对比总结
| 算法 | 抢占式 | 优先级 | 适用场景 | 缺点 |
|---|---|---|---|---|
| FCFS | 否 | 无 | 批处理系统 | 平均等待时间长 |
| SJF | 可选 | 无 | 任务时间已知 | 饥饿、需要预知时间 |
| RR | 是 | 无 | 分时系统 | 切换开销大 |
| 优先级 | 可选 | 固定 | 实时系统 | 反转、饥饿 |
| EDF | 是 | 动态 | 硬实时系统 | 过载脆弱 |
| RMS | 是 | 固定 | 周期性任务 | 利用率上限低 |
选型建议：
- 任务简单、数量少 → FCFS 或 RR。
- 任务时间已知 → SJF。
- 实时性要求高 → 优先级调度或 RMS。
- 高利用率、动态截止时间 → EDF。
最后说一句：没有完美的调度算法。每个算法都有它的脾气。你得多试、多调、多踩坑，才能找到最适合你项目的那个。
嗯，这一章就到这里。下一章咱们聊聊多处理器调度，那又是另一番天地了。