4. 调度算法基础：先来先服务、短作业优先、时间片轮转、优先级调度
调度算法这东西，说白了就是操作系统怎么决定「下一个该谁上 CPU」。我早年刚接触调度时，觉得不就是排个队嘛，后来被线上问题狠狠教育过——选错算法，吞吐量能差一个数量级。今天咱们把这四种最经典的算法掰开揉碎讲清楚。
4.1 先来先服务（FCFS）—— 最朴素的排队逻辑
先来先服务，英文叫 First-Come, First-Served，简称 FCFS。它的逻辑跟银行排队一模一样：谁先到，谁先办。操作系统维护一个就绪队列，新进程来了就排到队尾，调度器每次从队头取一个进程上 CPU。
这个算法有个特点——非抢占式。一旦进程拿到 CPU，除非它自己主动放弃（比如等待 I/O 或执行完毕），否则没人能把它赶下来。
但 FCFS 的缺点也很明显——护航效应。你想想看，如果一个长作业先到，后面所有短作业都得等着。平均等待时间会变得非常长。
举个例子：三个进程 P1（24ms）、P2（3ms）、P3（3ms），按 P1→P2→P3 顺序到达。平均等待时间 = (0 + 24 + 27) / 3 = 17ms。如果反过来 P2→P3→P1 到达，平均等待时间 = (0 + 3 + 6) / 3 = 3ms。差了将近 6 倍！
4.2 短作业优先（SJF）—— 追求最短平均等待
短作业优先，Shortest Job First，SJF。它的核心思想很简单：谁预计执行时间短，谁先上 CPU。这就像超市收银台开了个「购物少于 5 件」的快速通道。
SJF 有两种变体：
- 非抢占式 SJF：进程拿到 CPU 后一直运行到结束，期间即使来了更短的作业也不切换。
- 抢占式 SJF（也叫最短剩余时间优先，SRTF）：新进程的剩余时间比当前进程的剩余时间短，就立即抢占 CPU。
从理论上讲，SJF 能给出最优的平均等待时间。这是有数学证明的——在所有非抢占式调度算法中，SJF 的平均等待时间最小。
但 SJF 有个致命问题：你怎么知道一个进程要跑多久？ 操作系统没法预知未来。实际工程中，我们通常用历史执行时间来预测——比如指数平均法。
// 指数平均预测下一个 CPU 突发时间
τₙ₊₁ = α · tₙ + (1 - α) · τₙ
// 其中：
// τₙ₊₁ = 下一次预测值
// tₙ = 最近一次实际执行时间
// τₙ = 上一次预测值
// α = 平滑因子（通常取 0.5）
SJF 的另一个问题是饥饿。如果不断有短作业到达，长作业可能永远得不到 CPU。这在交互式系统中是不可接受的。
4.3 时间片轮转（RR）—— 公平的轮流坐庄
时间片轮转，Round Robin，RR。这是分时操作系统的标配算法。它的逻辑像打牌轮流出牌：每个进程分配一个固定时间片（time quantum），时间片用完了就强制切换到下一个进程。
RR 是抢占式算法。时钟中断是它的驱动力——每次时钟滴答，调度器检查当前进程的时间片是否用完。
时间片的选择是个艺术：
- 时间片太大：退化成 FCFS，响应时间变差。
- 时间片太小：上下文切换开销太大，CPU 的有效利用率下降。
我建议的工程经验：时间片通常设为 10-100ms。Linux 的默认时间片是 100ms，但会根据优先级动态调整。
| 时间片大小 | 响应时间 | 上下文切换开销 | 适用场景 |
|---|---|---|---|
| 1-10ms | 极好 | 高（可能占 10%+ CPU） | 硬实时系统 |
| 10-50ms | 好 | 中（约 1-5%） | 通用分时系统 |
| 50-200ms | 可接受 | 低（<1%） | 批处理系统 |
| >200ms | 差 | 极低 | 接近 FCFS |
RR 的优点是公平——每个进程都能得到 CPU，不会饿死。缺点是吞吐量不如 SJF，因为上下文切换有开销。
4.4 优先级调度—— 让重要的事先办
优先级调度，Priority Scheduling。每个进程有一个优先级，调度器总是选择优先级最高的进程运行。优先级可以是静态的（创建时固定），也可以是动态的（运行时调整）。
优先级调度也有抢占式和非抢占式两种：
- 非抢占式：高优先级进程到达后，等当前进程主动放弃 CPU 再切换。
- 抢占式：高优先级进程一到，立即抢走 CPU。
优先级调度的最大问题是饥饿——低优先级进程可能永远得不到 CPU。解决方案是老化（Aging）：随着时间推移，逐渐提高等待进程的优先级。
优先级调度的难点在于优先级反转——一个高优先级进程等待的资源被低优先级进程持有，而低优先级进程又被中优先级进程抢占。结果高优先级进程反而被低优先级进程阻塞了。
4.5 四种算法的选择策略
说了这么多，到底该用哪种？我总结了一个简单的选择框架：
- 批处理系统，任务长度差异不大 → FCFS，简单可靠。
- 批处理系统，任务长度差异大，且能预估执行时间 → SJF，追求高吞吐量。
- 交互式系统，需要快速响应 → RR，时间片设 20-50ms。
- 任务有明确的重要程度差异 → 优先级调度，配合老化机制防饥饿。
- 混合负载 → 多级反馈队列（下章会讲），综合各家之长。
实际生产环境中，很少有系统只用单一算法。Linux、Windows 这些通用操作系统，用的都是混合策略。但理解这四种基础算法，是理解复杂调度器的前提。