3. 调度算法(上)：FCFS、SJF、RR 详解与对比
调度算法，说白了就是决定「下一个该谁跑」的规则。我做了这么多年 RTOS，见过不少因为选错调度算法导致系统崩溃的案例。今天咱们就把三个最基础的算法掰开揉碎讲清楚。
3.1 先来先服务（FCFS）
FCFS 是最直观的算法。任务按到达顺序排成一队，CPU 一个一个处理。就像银行柜台排队，先到先办。
我记得第一次在 8051 上写调度器时，用的就是 FCFS。当时觉得这算法太简单了，肯定不会出问题。结果呢？一个长任务占着 CPU 不放，其他任务全部超时。嗯，这就是 FCFS 的致命伤—— convoy effect（护航效应）。
FCFS 的数学特性
- 平均等待时间： 取决于任务到达顺序。短任务排在长任务后面时，等待时间会很长。
- 吞吐量： 低。长任务阻塞 CPU，短任务无法及时执行。
- 响应时间： 不可预测。最坏情况下，一个任务可能等所有前面的任务执行完。
| 指标 | FCFS 表现 | 原因 |
|---|---|---|
| 平均等待时间 | 高（长任务在前时） | 短任务被长任务阻塞 |
| CPU 利用率 | 高（无切换开销） | 非抢占式，无上下文切换 |
| 公平性 | 按到达顺序公平 | 先到先服务，逻辑简单 |
| 适用场景 | 批处理系统 | 任务执行时间相近时效果较好 |
3.2 短任务优先（SJF）
SJF 的思路是：谁执行时间短，谁先跑。你想想看，如果有一个 1ms 的任务和一个 100ms 的任务同时就绪，让短任务先跑，长任务等一会儿，整体等待时间是不是更短？
我个人习惯把 SJF 看作「最优平均等待时间算法」。从数学上讲，它确实能最小化平均等待时间。但实际项目中，我很少直接用纯 SJF。为什么？因为你根本不知道任务要跑多久。
非抢占式 vs 抢占式 SJF
- 非抢占式 SJF： 任务一旦开始执行，就跑到完。新来的短任务必须等当前任务结束。
- 抢占式 SJF（SRTF）： 新来的短任务如果比当前剩余时间还短，就抢占 CPU。这更灵活，但实现复杂。
我在一个电机控制项目里试过抢占式 SJF。当时想，让短任务优先处理急停信号，应该没问题。结果呢？一个长任务被频繁抢占，永远跑不完。这就是 starvation（饥饿）问题——长任务可能永远得不到 CPU。
3.3 时间片轮转（RR）
RR 算法把 CPU 时间切成固定大小的「时间片」，每个任务轮流跑一个时间片。跑完就换下一个。说白了，就是「每人吃一口，吃完换人」。
我最早接触 RR 是在学习 uC/OS-II 的时候。当时觉得这算法太优雅了——每个任务都能得到响应，没有任务会被饿死。但后来发现，时间片大小选不好，系统性能会崩。
时间片大小的选择
| 时间片大小 | 优点 | 缺点 |
|---|---|---|
| 太小（< 1ms） | 响应快，交互性好 | 上下文切换开销大，CPU 利用率低 |
| 适中（1-10ms） | 平衡响应和效率 | 需要根据任务特性调整 |
| 太大（> 100ms） | 切换开销小 | 响应慢，接近 FCFS |
RR 的上下文切换开销
每次切换都要保存当前任务的寄存器、堆栈指针，再恢复下一个任务的上下文。这个开销是固定的。如果时间片太小，切换开销占比会很高。
// 伪代码：RR 调度器的核心逻辑
void RR_Scheduler(void) {
while (1) {
Task *current = get_next_task_from_ready_queue();
if (current == NULL) {
idle(); // 没有任务就空闲
continue;
}
// 设置定时器为时间片长度
set_timer(TIME_SLICE_MS);
// 切换到当前任务
context_switch_to(current);
// 任务执行直到时间片用完或任务主动让出 CPU
// 定时器中断会触发下一次调度
}
}3.4 三种算法对比总结
| 特性 | FCFS | SJF | RR |
|---|---|---|---|
| 抢占性 | 非抢占 | 可抢占/非抢占 | 抢占式 |
| 平均等待时间 | 高 | 最低 | 中等 |
| 响应时间 | 差 | 中等 | 好 |
| 公平性 | 按到达顺序 | 偏向短任务 | 均匀分配 |
| 饥饿问题 | 无 | 长任务可能饿死 | 无 |
| 实现复杂度 | 最低 | 中等 | 中等 |
| 适用场景 | 批处理、简单系统 | 任务时间已知的系统 | 交互式、实时系统 |
选哪个算法？我的建议是：先看你的任务特性。如果任务执行时间都差不多，FCFS 就够用。如果任务时间差异大但你知道每个任务的时间，SJF 能优化平均等待时间。如果需要每个任务都响应及时，RR 是最稳妥的选择。