CPU 调度算法：FCFS、SJF、RR 与优先级调度

CPU 调度算法：FCFS、SJF、RR 与优先级调度

上一篇我们立下了一条铁规矩：评判调度必须先看目标。现在带着那些指标——吞吐量、周转时间、等待时间、响应时间、公平性——来逐一审视四个最经典的调度算法。

这四个算法不是孤立的知识点，而是一条逐步打补丁的演进线：FCFS 最朴素，却暴露了"长任务拖垮短任务"的硬伤；SJF 用"短的先跑"修复了它，却带来了"得预知任务长度"和"长任务饥饿"的新问题；RR 用时间片解决了交互响应；优先级调度引入了"重要性"维度，又埋下饥饿的雷。看懂这条线，你就理解了下一篇多级反馈队列为什么要把它们缝合在一起。

这一篇对每个算法都先讲清运转机制（就绪队列怎么排、何时切换、用什么数据结构），用同一组任务手算指标看效果，再点明它优化了什么、牺牲了什么。

一、统一的实验设定

为了让四个算法可比，我们用同一组任务贯穿全文。设有四个任务同时（t=0）到达就绪队列，CPU 执行时间（burst time）如下：

任务	执行时间
P1	8
P2	4
P3	1
P4	3

我们主要看两个指标：平均周转时间（提交到完成）和平均等待时间（在就绪队列里干等的时长）。因为都在 t=0 到达，周转时间 = 完成时刻，等待时间 = 完成时刻 − 自身执行时间。盯着这组数字在不同算法下怎么变，比记定义有用得多。

二、FCFS：先来先服务，最朴素也最危险

FCFS（First-Come First-Served）的机制简单到极点：就绪队列就是一个普通的FIFO 队列，谁先到排谁前面，CPU 一次拿队头那个任务跑到底（非抢占），跑完再取下一个。

按到达顺序 P1→P2→P3→P4 执行，时间轴：

P1: 0────────8
P2:          8────12
P3:              12─13
P4:                 13────16

• 完成时刻：P1=8, P2=12, P3=13, P4=16
• 平均周转时间 = (8+12+13+16)/4 = 12.25
• 平均等待时间 = (0+8+12+13)/4 = 8.25

问题一眼可见：P3 只需要跑 1 个单位，却因为排在 8 个单位的 P1 后面，硬等了 12 个单位才完成。这就是 FCFS 臭名昭著的护航效应（convoy effect）：

一个长任务排在前面，会把后面一大串短任务全部拖住，像一辆慢车堵住整条单车道，后面的车再快也只能跟着爬。FCFS 的平均等待时间因此可能非常糟糕。

FCFS 唯一的优点是绝对公平（按到达顺序，无人饿死）且实现简单、无切换开销。但护航效应让它在混合负载下表现很差。它的存在价值更多是当"基准线"——后面的算法都是在修它的毛病。

三、SJF：短作业优先，平均等待时间的理论最优

既然护航效应源于"长任务挡在前面"，那把短的排前面不就行了？这就是 SJF（Shortest Job First）：每次从就绪队列里挑执行时间最短的任务来跑。

还是那组任务，按执行时间排序 P3(1)→P4(3)→P2(4)→P1(8)：

P3: 0─1
P4:   1───4
P2:      4────8
P1:          8────────16

• 完成时刻：P3=1, P4=4, P2=8, P1=16
• 平均周转时间 = (1+4+8+16)/4 = 7.25
• 平均等待时间 = (0+1+4+8)/4 = 3.25

对比 FCFS 的等待时间 8.25，SJF 直接砍到 3.25。这不是巧合：

SJF 在所有非抢占调度里，能取得理论上最小的平均等待时间。 直觉是：让短任务先走，它们快速腾空，只有少数长任务承受较长等待，总等待量最小。

SJF 还有个抢占式变体——SRTF（最短剩余时间优先）：当一个新任务到达，若它的执行时间比当前正在跑的任务剩余时间还短，就抢占。它进一步优化了有任务陆续到达时的等待时间。

但 SJF 有两个致命短板，恰恰是后续算法和工程要解决的：

1. 必须预知任务执行时间——可现实中调度器根本不知道一个任务要跑多久！这是 SJF 最大的不现实之处。工程上只能估计：用历史执行时间做指数加权移动平均来预测下一次，这正是多级反馈队列"用行为推断任务类型"的思想源头。
2. 长任务可能饥饿——只要短任务源源不断地来，长任务永远排在后面，可能永远跑不上。

四、RR：时间片轮转，为交互响应而生

FCFS 和 SJF 都是非抢占的，都有"短的等长的"或"长的被饿死"的毛病，而且都不适合交互——你总不能让用户的命令排在一个大计算后面干等。**RR（Round Robin，时间片轮转）**就是为分时/交互场景设计的。

它的机制是 FCFS + 时间片 + 抢占：就绪队列仍是 FIFO，但每个任务最多连续跑一个时间片（quantum）。时间片一到，时钟中断触发，当前任务被抢占、挂回队列尾部，CPU 给队头的下一个。如此轮转。

设时间片 = 2，任务按 P1→P2→P3→P4 排队，执行过程（每轮最多跑 2）：

P1(8) P2(4) P3(1) P4(3)
时间轴: P1 P2 P3 P4 P1 P2 P4 P1 P1
        0-2 2-4 4-5 5-7 7-9 9-11 11-12 12-14 14-16

逐段：t0-2 跑 P1(剩6)，t2-4 跑 P2(剩2)，t4-5 跑 P3(完成)，t5-7 跑 P4(剩1)，t7-9 跑 P1(剩4)，t9-11 跑 P2(完成)，t11-12 跑 P4(完成)，t12-14 跑 P1(剩2)，t14-16 跑 P1(完成)。

• 平均周转时间和等待时间都比 SJF 差（切换多、长任务被打散），但 RR 的杀手锏不是这些指标，而是响应时间：每个任务最多等"队列里其他人各跑一个时间片"就能获得 CPU，第一次响应来得很快。

RR 牺牲了一部分周转时间和吞吐（频繁切换有开销），换来了有界的、可预期的响应时间——这正是交互系统最需要的。没人会被一个长任务无限期挡在门外。

时间片大小是 RR 的命门，这是个经典权衡：

• 时间片太大：大到超过所有任务的执行时间，RR 就退化成了 FCFS，护航效应回来了；
• 时间片太小：上下文切换过于频繁，切换本身的开销（保存/恢复寄存器、刷新缓存）占比飙升，CPU 大量时间花在切换而非计算上；
• 经验法则：时间片应略大于一次典型的交互请求处理时间，让大多数交互任务能在一个时间片内完成响应，同时把切换开销控制在可接受比例（通常几毫秒到几十毫秒）。

五、优先级调度：引入"重要性"维度

前三个算法排序依据要么是到达时间、要么是执行长度，都没考虑"任务有轻重之分"。优先级调度（Priority Scheduling）给每个任务一个优先级数值，调度器总是选优先级最高的就绪任务运行。

• 它可以是非抢占的（高优先级任务来了，等当前任务跑完再上），也可以是抢占的（高优先级任务一到立刻抢占当前任务，实时系统常用）；
• 就绪队列通常用优先级队列（堆）实现，而不是简单 FIFO。

其实 SJF 可以看作优先级调度的一个特例——“执行时间越短优先级越高”。优先级调度把这个维度一般化了：优先级可以来自任务重要性、用户等级、截止时间紧迫度等任意标准。

它的核心问题非常出名——饥饿（starvation）/ 无限期阻塞：

如果高优先级任务源源不断，低优先级任务可能永远得不到 CPU。优先级调度把"按重要性分配"的好处和"低优先级饿死"的风险一起带来了。

解决饥饿的经典手段是老化（aging）：让任务的优先级随它在就绪队列里等待的时间逐渐升高。等得越久，优先级爬得越高，迟早会高到能被调度——这样既尊重了重要性，又保证了没有任务被永久遗忘。老化机制是下一篇多级反馈队列防饥饿的核心借鉴。

优先级调度还有一个著名陷阱——优先级反转（priority inversion）：低优先级任务持有一把锁，高优先级任务要这把锁只能等它，结果高优先级反被低优先级"压制"；若此时一个中优先级任务又抢占了低优先级任务，高优先级任务就被间接拖得更久。火星探路者号就栽过这个坑，解法是优先级继承（持锁的低优先级任务临时继承等锁者的高优先级）。

六、四个算法的横向对比

把四个算法按"机制—优点—硬伤"摆在一起，演进逻辑就一目了然：

算法	选择依据	抢占?	最优指标	主要硬伤
FCFS	到达顺序	否	实现最简、绝对公平	护航效应，等待时间差
SJF	执行时间最短	可选	平均等待时间理论最优	需预知时长、长任务饥饿
RR	轮流（时间片）	是	响应时间有界	周转/吞吐一般、切换开销
优先级	优先级数值	可选	体现任务重要性	低优先级饥饿、优先级反转

flowchart TD Q["就绪队列中有多个任务"] --> D{"按什么规则选下一个?"} D -->|按到达先后| F["FCFS<br/>→ 简单但护航效应"] D -->|按执行时间长短| S["SJF<br/>→ 等待最优但需预知/会饥饿"] D -->|轮流给时间片| R["RR<br/>→ 响应好但切换多"] D -->|按重要性| P["优先级<br/>→ 分轻重但会饥饿"] S -.补丁.-> A1["历史数据估计时长"] P -.补丁.-> A2["老化机制防饥饿"] F -.综合.-> M["多级反馈队列<br/>(下一篇)"] S -.综合.-> M R -.综合.-> M P -.综合.-> M

这张图揭示了本篇的主线：四个算法各占一个优化方向，但每个都有明显短板。现实系统不可能只用其中一个——于是下一篇的多级反馈队列把它们的优点缝合：用多个队列分层（优先级），队列内用 RR（响应），靠任务行为动态调整层级（近似 SJF 而不需预知），再用老化防饥饿。

没有任何单一算法是"最好"的。FCFS 公平却低效，SJF 高效却不现实且不公平，RR 响应好却吞吐一般，优先级灵活却易饥饿。理解每个算法的得失，才能明白为什么真实系统要做折中。

七、和工程实践 / 后端开发的联系

这些算法思想在后端系统里反复出现，认出它们能帮你设计任务系统：

• 线程池任务队列 = FCFS：默认的 LinkedBlockingQueue 就是 FIFO，先提交先执行。如果你的任务长短差异大，就会遭遇护航效应——一个慢任务堵住后面一片。解法是拆分队列或引入优先级。
• 优先级队列 = 优先级调度：PriorityBlockingQueue、消息队列的优先级分级、紧急任务插队，都是优先级调度。用它时务必警惕低优先级饥饿——加个"等待超时后提级"就是老化机制的工程版。
• SJF 的现实困境与近似：你通常无法预知一个请求要处理多久，但可以像 SJF 估计那样，用历史数据预测（比如某类接口的 P50 耗时），据此做超时设置或队列分流。这正是 SJF "预测执行时间"思想的落地。
• 时间片思想 = 协作式让出：协程/Goroutine 调度、Nginx 事件循环里"处理一会儿就让出"，本质是 RR 时间片的变体——防止单个任务长期霸占执行权、保证整体响应性。
• 优先级反转是真实事故源：在加锁的高低优先级任务混跑场景，优先级反转会导致难以理解的延迟。理解它，遇到"高优先级任务莫名很慢"时才能想到去查它是不是在等一把被低优先级任务持有的锁。

学习这一部分最容易踩的坑

1. 以为平均等待时间最优 = 用户体验最好

SJF 平均等待时间最优，但它会饿死长任务、且无法预知时长，根本不适合交互系统。指标最优只在它对应的目标下才有意义。用户体验往往取决于响应时间和尾延迟，而不是平均等待。

2. 优先级调度不配老化

只要用了优先级队列，就必须考虑低优先级饥饿。不加老化（或等待提级）机制，低优先级任务可能永远跑不上。这是优先级调度最常被忽略、上线后才暴雷的隐患。

3. 以为时间片越短越好

时间片短确实响应快，但切换开销会急剧上升——CPU 大量时间耗在保存/恢复上下文而非干活。时间片太长又退化成 FCFS。要在响应性和切换开销之间找平衡点，不是越短越好。

4. 把这四个算法当成互斥的选择题

现实系统几乎从不单用某一个，而是组合使用（多级反馈队列就是明证）。把它们理解成"各有所长的零件"，而不是"四选一"，才能看懂真实调度器的设计。

总结

FCFS、SJF、RR、优先级调度构成一条"打补丁"的演进线，每个算法针对前者的缺陷又引入新权衡。核心要点：

• FCFS 用 FIFO 排队、非抢占，简单公平但有护航效应——长任务拖垮一串短任务；
• SJF 让短任务优先，平均等待时间理论最优，但需预知执行时间、且长任务会饥饿；
• RR 用时间片 + 抢占换来有界响应时间，时间片大小是命门（太大退化成 FCFS、太小切换开销飙升）；
• 优先级调度引入重要性维度，但会导致低优先级饥饿（解法是老化）和优先级反转（解法是优先级继承）；
• 没有单一算法全能，每个只在特定指标上发力、在另一指标上失分；
• 工程上线程池是 FCFS、优先级队列要配老化、SJF 思想体现在用历史数据预测耗时。

四个算法各有短板，自然引出一个问题：能不能把它们的优点揉到一起？下一篇的多级反馈队列就是这个问题的经典答案。

参考资源：

• 《操作系统导论》（Operating Systems: Three Easy Pieces）调度章节
• 《现代操作系统》（Andrew S. Tanenbaum）
• OSTEP - Scheduling
• 《操作系统概念》（Operating System Concepts，恐龙书）CPU 调度章节