CPU调度算法详解：FCFS、SJF、优先级与RR对比实战

1. 先搞清楚CPU调度算法到底在解决什么问题

很多人第一次接触 CPU调度算法，都是在操作系统课的期末复习周，抱着 FCFS、SJF、优先级调度、RR 这四个名词背公式、套表格，考完就忘。我自己当年也是这样，直到后来做后端服务压测、调容器资源限制、看内核 trace 的时候，才发现这些算法压根不是纸上的东西——它们决定了你的接口在并发上来之后，尾延迟是 50ms 还是 5s。

这篇文章想干的事很明确：把 FCFS（先来先服务）、SJF（短作业优先）、优先级调度、RR（时间片轮转）这四个算法，从"考试题"还原成"工程问题"。会讲清楚它们各自的设计意图、会踩的坑、怎么手算出结果、怎么用 Python 把四种算法跑一遍做横向对比，最后给一份排查时间算错的速查表。适合两类人：正在学操作系统的同学，以及需要对任务调度做技术选型的开发、运维、嵌入式工程师。

1.1 从食堂打饭窗口理解就绪队列与调度时机

先抛开所有术语。想象一个食堂，只有一个打饭窗口（单核 CPU），一堆人排队（就绪队列），每个人要打的菜量不同（CPU 服务时间）。这时候你会发现几个现实问题：谁先打？能不能让只打一份汤的人插队？如果队伍里有个领导（高优先级）来了怎么办？如果一个人打得太多，后面的人是不是要等死？

这四个问题，恰好对应了四个算法的核心分歧点。FCFS 回答"谁先来谁先打"；SJF 回答"谁快谁先打"；优先级调度回答"谁重要谁先打"；RR 回答"每人只准打 30 秒，没打完回去重新排"。

从技术角度说，调度器要处理的就三件事：调度时机、选择策略、上下文切换。调度时机是指"什么时候该换人了"，典型触发点有四种——当前进程运行完毕、当前进程被阻塞（发起 I/O）、时间片用完、有更高优先级的进程到达。选择策略就是"从就绪队列里挑谁"，这正是四个算法的差异所在。上下文切换则是"换人的动作"，它不产生任何有效计算量，纯粹是开销，所以每次切换都要保存现场（PCB、寄存器、程序计数器），这个开销在后面的时间片计算里会反复出现。

注意：调度时机和选择策略容易被混为一谈。很多人算错 RR 的周转时间，根本原因不是时间片选错，而是搞不清楚"新到达的进程"和"时间片用完被抢占的进程"谁先入队。

1.2 评价算法好坏的四个指标：别只盯着"快不快"

算法好不好，不能凭感觉。行业里统一用几个量化指标来对比，我把它们和实际含义对应一下。

周转时间：从作业提交到作业完成的总时间，公式是周转时间 = 完成时间 - 到达时间。它衡量的是"用户等了多久才拿到结果"。

带权周转时间：带权周转时间 = 周转时间 / 服务时间。这个指标很有意思，它衡量的是"我的等待相对于我的工作量是否合理"。一个服务 1 秒的作业周转 3 秒，带权周转是 3，用户会觉得"怎么这么慢"；一个服务 100 秒的作业周转 120 秒，带权周转只有 1.2，用户反而觉得"可以接受"。这就是为什么短作业对延迟格外敏感。

等待时间：等待时间 = 周转时间 - 服务时间，也就是作业在就绪队列里干等的时间总和，不含实际执行时间。这个指标最能反映调度策略的公平性。

响应时间：从提交到第一次获得 CPU 的时间。对交互式系统来说，这个指标比周转时间重要得多——用户敲一下键盘，只要屏幕有反应就行，不关心后台那个批量任务什么时候跑完。

看这张表你会发现，任何单一算法都不可能四项全优。SJF 能把平均周转时间压到理论最低，但它的响应时间可能很难看；RR 的响应时间很漂亮，但平均周转时间往往不是最优。选型本质上是在做取舍，而不是找"最优解"。

1.3 四种算法的分工：批处理、交互式、实时场景各取所需

为什么教材里要同时讲四个算法而不是只讲一个最好的？因为它们的适用场景完全不重叠。

FCFS 适合批处理系统中的长作业流，实现简单、绝对公平、不会有饥饿问题，缺点是一旦前面有个长作业，后面全堵着。SJF 适合已知或可预测服务时间的场景，比如后台的定时任务、数据批处理，它能显著压低平均周转时间，但必须解决"服务时间怎么预估"和"长作业会不会饿死"这两个问题。优先级调度适合有明确重要性分层的场景，比如实时系统中的控制任务、中断处理，重要的事必须先干。RR 则是分时系统和现代通用操作系统的基础，它牺牲了周转时间，换来的是每个任务的响应时间都有上界。

真实系统里几乎不会只用一种。Linux 的 CFS 用虚拟运行时间（vruntime）配合红黑树来选下一个任务，本质上是"带权重的公平分享"；实时调度类里用 SCHED_FIFO（先来先服务语义）和 SCHED_RR（时间片轮转语义）；多级反馈队列更是把优先级和 RR 缝在了一起。所以理解这四个算法，其实是在理解更复杂调度器的积木块。

2. FCFS先来先服务：实现最省事，但护航效应会咬人

FCFS 是所有调度算法里最好写的一个，也是唯一一个不需要额外数据结构就能实现的——它甚至不需要"就绪队列"这个概念，因为顺序就是到达顺序。

2.1 算法规则与一段最小实现

规则只有一句话：按作业到达的先后顺序依次执行，一旦开始执行就直到完成，中途不打断。这是典型的非抢占式调度。

用伪代码表达：

def fcfs(jobs): seq = sorted(jobs, key=lambda j: j.arrive) # 按到达时间排队 t = 0 finish = {} for j in seq: t = max(t, j.arrive) + j.service # 处理 CPU 空闲的情况 finish[j.name] = t return finish

注意max(t, j.arrive)这一句。很多人在算题时忘了 CPU 可能空闲——如果第一个作业到达时间是 5，那么在 0 到 5 这段时间 CPU 是闲着的，不能从 0 开始算。这个细节在连续作业的题目里看不出来，一旦出现空隙就会算错。

FCFS 的优点很实在：实现简单，没有额外开销，绝对不会饥饿。任何作业只要提交了就一定能被执行，只是早晚问题。这在实时性要求不高、但要求绝对确定性的场合很有价值。

2.2 手算推演：四个作业的周转时间怎么来的

我用一组贯穿全文的作业集合来演示，后面所有算法的对比都基于它：

FCFS 的执行顺序就是 J1 → J2 → J3 → J4，时间轴如下：J1 占用 0 到 7，J2 占用 7 到 11，J3 占用 11 到 12，J4 占用 12 到 16。

• J1：完成 7，周转 7 - 0 = 7，等待 7 - 7 = 0
• J2：完成 11，周转 11 - 2 = 9，等待 9 - 4 = 5
• J3：完成 12，周转 12 - 4 = 8，等待 8 - 1 = 7
• J4：完成 16，周转 16 - 5 = 11，等待 11 - 4 = 7

平均周转时间 = (7 + 9 + 8 + 11) / 4 = 8.75，平均等待时间 = (0 + 5 + 7 + 7) / 4 = 4.75。

这里有个容易被忽略的观察：J3 只服务 1 个时间单位，却等了 7 个时间单位，带权周转时间高达 8。对短作业来说，FCFS 的体验是灾难级的。

2.3 护航效应到底有多伤：一组极端数据

"护航效应"（Convoy Effect）是 FCFS 最著名的毛病：一个长作业在前，后面所有短作业都得陪着它走完全程，就像一艘慢船挡住了一整条航道。

举个极端例子。假设有三个作业同时到达：A 服务 100，B 服务 1，C 服务 1。FCFS 下，A 先跑完 100，B 和 C 分别等到 100 和 101。

• 平均周转时间 = (100 + 101 + 102) / 3 = 101
• 平均等待时间 = (0 + 99 + 100) / 3 ≈ 66.3

如果换成短作业优先，B、C 先跑，结果完全不同：

• 执行顺序 B(0-1)、C(1-2)、A(2-102)
• 平均周转时间 = (1 + 2 + 102) / 3 = 35
• 平均等待时间 = (0 + 1 + 2) / 3 = 1

平均周转时间从 101 降到 35，平均等待时间从 66.3 降到 1。这个差距不是优化，是降维打击。而且注意，这个例子里长作业 A 的周转时间几乎没变（102 对 100），它只是"稍微晚了一点点"，但短作业的体验天翻地覆。

实操心得：我在做批量任务调度的时候，会专门给"预计执行时间超过阈值"的任务打标记。因为这种任务一旦排在前面，整个队列的 P99 延迟都会被它拖垮。把它单独放到低优先级队列里，效果立竿见影。

2.4 实操心得：FCFS什么时候还能用

别看 FCFS 毛病这么多，它在两种场合依然是正确选择。

第一种是服务时间高度同质化的队列。如果所有作业的服务时间都差不多（比如每个任务都是 10ms 左右的数据同步），护航效应就不存在，因为根本没有长短之分，FCFS 反而是最公平的。

第二种是需要严格确定性的场合。FCFS 的执行顺序完全可预测，这对调试、日志审计、故障复现非常友好。你在排查一个偶现问题时，如果调度策略本身带随机性，排查难度会成倍上升。

我踩过的一个坑是：早期做过一个日志聚合服务，用的是简单的 FIFO 队列。平时没问题，直到某天上游推送了一个 200MB 的历史日志补传包，整个队列堵了将近 4 分钟，实时日志全部延迟告警。后来加了"单任务最大处理时间 + 超长任务转后台队列"的机制才解决。这就是典型的护航效应在生产环境里的表现。

3. SJF短作业优先：平均周转时间的理论最优解

如果你只关心一个指标——平均周转时间——那 SJF 就是标准答案，而且是可以证明的最优解。这个结论在流水车间调度理论里被称为 SPT 规则（Shortest Processing Time），结论是：在所有非抢占式调度策略中，按服务时间递增的顺序执行，能让平均周转时间最小。

3.1 非抢占式SJF的贪心逻辑

非抢占式 SJF 的规则是：每当 CPU 空闲时，从已经到达的作业中挑选服务时间最短的那个执行，中途不打断。

这里有个关键限定词——"已经到达"。很多人算 SJF 时会挑整个作业集合里服务时间最短的，哪怕它还没到达，这就错了。SJF 是在线贪心，只能看到当前时刻已经到达的作业。

用代码表达：

def sjf_non_preemptive(jobs): pending = list(jobs) t = 0 finish = {} while pending: ready = [j for j in pending if j.arrive <= t] if not ready: # CPU 空闲，跳到下一个到达时刻 t = min(j.arrive for j in pending) continue cur = min(ready, key=lambda j: (j.service, j.arrive)) # 服务时间相同按到达时间 t += cur.service finish[cur.name] = t pending.remove(cur) return finish

key里带上j.arrive是为了处理服务时间相同的情况，保证结果稳定可复现。这一点在做对比实验时很重要——如果排序不稳定，同样的输入可能跑出不同的结果，你就没法判断差异到底来自算法还是来自排序的随机性。

用前面的作业集合手算：t=0 时只有 J1 到达，只能选 J1，J1 跑 0 到 7。t=7 时 J2、J3、J4 都到了，服务时间分别是 4、1、4，选最短的 J3，跑 7 到 8。接着服务时间为 4 的有 J2 和 J4，按到达时间选 J2，跑 8 到 12，最后 J4 跑 12 到 16。

• J1：完成 7，周转 7，等待 0
• J3：完成 8，周转 4，等待 3
• J2：完成 12，周转 10，等待 6
• J4：完成 16，周转 11，等待 7

平均周转时间 = (7 + 4 + 10 + 11) / 4 = 8.0，平均等待时间 = (0 + 3 + 6 + 7) / 4 = 4.0。

对比 FCFS 的 8.75 和 4.75，SJF 确实更优。但提升幅度没有前面那个极端例子那么夸张，原因是这组数据里 J1 是第一个到达的，SJF 拿它没办法。

3.2 抢占式SRTF：每个时间单位都要重新比一次

抢占式 SJF 又叫 SRTF（Shortest Remaining Time First），规则是：每来一个新作业，就比较它和当前运行作业的剩余服务时间，如果新来的更短，立刻抢占。

它的实现方式很简单粗暴——按单位时间推进，每个时间片都重新做一次选择：

def srtf(jobs): remain = {j.name: j.service for j in jobs} finish = {} t = 0 while len(finish) < len(jobs): ready = [j for j in jobs if j.arrive <= t and remain[j.name] > 0] if not ready: t += 1 continue cur = min(ready, key=lambda j: (remain[j.name], j.arrive)) t += 1 remain[cur.name] -= 1 if remain[cur.name] == 0: finish[cur.name] = t return finish

还是同一组作业，推演一遍：

t=0 到 2，J1 独跑，剩余 5。t=2 时 J2 到达，剩余 4，比 J1 的 5 短，抢占。t=2 到 4，J2 跑 2 个单位，剩余 2。t=4 时 J3 到达，剩余 1，比 J2 的 2 短，抢占。J3 在 t=5 完成，周转 1。t=5 时 J4 到达，剩余 4；候选是 J2 剩余 2、J4 剩余 4、J1 剩余 5，选 J2。J2 在 t=7 完成，周转 5。接着 J4 剩余 4 比 J1 剩余 5 短，J4 跑 7 到 11 完成，周转 6。最后 J1 从 11 跑到 16，周转 16。

• 平均周转时间 = (16 + 5 + 1 + 6) / 4 = 7.0
• 平均等待时间 = (9 + 1 + 0 + 2) / 4 = 3.0

SRTF 把平均周转时间压到了 7.0，是这四种算法里最低的。但代价也很明显——J1 被连续抢占两次，实际执行被打断得七零八落，而且它的周转时间从 7 涨到了 16。抢占式算法的平均值更漂亮，但个体方差更大，这是所有抢占式策略的通病。

3.3 同一组作业四种算法横向对比

把目前算出来的结果整理一下，后面 RR 的计算结果也一并放进来对比：

这张表里最值得玩味的是 SRTF 那一行。它的平均值最优，但 J1 的周转时间 16 是最差的一列。如果 J1 是一个用户直接等待的请求，那这个调度策略就是把整体指标做好了，把单用户体验做烂了。这也是为什么真实系统里很少用纯 SRTF，而是用它的加权版本。

3.4 饥饿问题与老化补偿

SJF 和优先级调度都有一个致命的共同问题：饥饿。如果一个长作业后面源源不断地来短作业，这个长作业可能永远等不到 CPU。

举个具体的：J1 服务 100，到达 t=0。之后每隔 1 个时间单位就来一个服务时间为 1 的短作业。在 SRTF 下，当前作业剩余时间是 100、99、98……而每个新来的短作业剩余时间都是 1，永远比它短。结果就是 J1 一直被打断，永远跑不完。

解决思路叫老化（Aging）：让等待时间长的作业优先级逐渐提升。实现上有两种常见做法。一种是"等待时间折算"，把优先级定义为priority = base_priority - wait_time / K，K 是老化系数，等待越久数值越小（优先级越高）。另一种是"饥饿计数器"，作业每被跳过 N 次，就强制提升一级优先级。

老化系数 K 的取值需要根据实际负载调。K 太小，老化过快，调度退化成 FCFS；K 太大，老化太慢，解决不了饥饿。经验做法是先统计系统内作业的平均服务时间，让 K 大致等于这个量级，这样老化速度和服务时间尺度匹配。

3.5 服务时间怎么估：指数平均法的工程做法

SJF 的前提是知道服务时间，但现实中你根本不知道下一个请求要跑多久。工程上的解法是用历史预测未来，最经典的公式是指数平均：

预测值(n+1) = α × 实际值(n) + (1 - α) × 预测值(n)

α 取值在 0 到 1 之间。α 越接近 1，越相信最近一次的观测；越接近 0，越依赖长期历史。通常取 α = 0.5，兼顾响应性和稳定性。

比如一个进程前三次实际运行时间是 6、4、8，初始预测值设 5：

• 第一次预测 5，实际 6，新预测 = 0.5×6 + 0.5×5 = 5.5
• 第二次预测 5.5，实际 4，新预测 = 0.5×4 + 0.5×5.5 = 4.75
• 第三次预测 4.75，实际 8，新预测 = 0.5×8 + 0.5×4.75 = 6.375

这个方法的妙处在于实现成本极低——每个进程只需要存一个预测值，一次乘加就能更新。Linux 里估算进程"交互性"的思路和它本质相同，都是靠历史行为推断未来。

注意：用预测值做 SJF 时，必须在预测值后面加一个最小保护值。否则一个预测为 0 的进程会反复抢占 CPU，造成所谓"预测偏差自激"——它跑得越短，预测值越低，越容易被选中，越容易被观测到短时间。

4. 优先级调度算法：把"重要性"翻译成数字

FCFS 和 SJF 都是把"时间"当作唯一尺度，但现实中的任务重要性并不由时间决定。中断处理程序可能只需要 10 微秒，但它的重要性远超一个跑 10 秒的批处理任务。优先级调度解决的就是这个问题。

4.1 静态与动态优先级的取舍

优先级可以是静态的——创建时确定，运行期间不变；也可以是动态的——随运行状态变化。

静态优先级的优点是简单、可预测、开销低，适合嵌入式实时系统。缺点是它无法应对运行时的情况变化，如果一开始优先级设错了，就只能错到底。而且静态优先级特别容易造成低优先级任务长期饥饿。

动态优先级灵活得多，但引入了一个新问题：优先级怎么变？常见的动态规则包括：等待时间越长优先级越高（抗饥饿）、占用 CPU 越多优先级越低（防止霸占）、I/O 密集型的进程优先级升高（因为它们通常会很快让出 CPU）。

在实现上，动态优先级的更新需要一个触发时机。最简单的是每次调度时重算一遍，成本高但效果好；更常用的做法是定时器周期更新，比如每 10ms 扫一遍就绪队列做衰减。

4.2 优先级反转：一个真实会出事的场景

这是优先级调度里最容易出事的地方，也是我在实际项目里真正被坑过的。

场景是这样的：有三个任务，高优先级 H、中优先级 M、低优先级 L。H 和 L 需要访问同一个互斥锁保护的资源。执行序列：L 先拿到锁，正在临界区里干活；此时 H 到达，抢占 CPU，尝试拿锁，失败，被阻塞；然后 M 到达，因为 H 已经被阻塞、L 优先级又低，M 抢到了 CPU 开始长时间运行。

结果就是：H 明明优先级最高，却在等 M 跑完，而 M 的优先级比 L 高、比 H 低。高优先级任务被中优先级任务间接拖住了。这就是优先级反转。

解决方法是优先级继承：当 H 因为等锁而阻塞时，持有锁的 L 临时继承 H 的优先级。这样 M 就无法抢占 L 了，L 能尽快跑完临界区释放锁，H 也就能尽快被唤醒。另一种方案是优先级天花板：给锁设定一个天花板优先级，任何持有该锁的任务自动提升到天花板级别，简单粗暴但更保守。

实操心得：优先级反转不是理论玩具。我在一个多线程数据采集程序里遇到过，采集线程（高优先级）被日志写入线程（中优先级）拖住了将近 200ms，原因是采集线程在等一把被配置读取线程持有的锁，而配置读取线程的优先级最低。排查了两天才定位到。如果你的系统里有"高优先级任务偶发性卡顿"的现象，优先怀疑这个。

4.3 多级反馈队列：把优先级和RR缝在一起

真实系统里用得多的是多级反馈队列（MLFQ），它把优先级调度和 RR 结合起来，同时用动态调整来兼顾响应和吞吐。

基本结构是多个就绪队列，优先级从高到低排列。规则大致是四条：新任务进入最高优先级队列；同一队列内按 RR 轮转；任务用完整时间片还没结束就降到下一级队列；在低优先级队列里等待过久的任务提升回高优先级（老化）。

时间片设置也有讲究，通常是队列优先级越低，时间片越长。比如第一级 8ms、第二级 16ms、第三级 32ms。这个设计逻辑很清晰：交互式任务通常很快就能结束，放在高优先级、短时间片里能获得极低的响应时间；而长计算任务会一路下沉到低优先级、长时间片，避免频繁切换浪费 CPU。

MLFQ 的精妙之处在于它不需要预先知道任何任务的类型。I/O 密集型任务因为频繁让出 CPU，会一直留在高优先级队列；CPU 密集型任务会自动下沉。这种"用行为自动分类"的思路，比人工打标签靠谱得多。

5. RR时间片轮转：交互流畅度的守门员

如果前面几个算法都在优化"总时间"，RR 优化的是完全另一个维度：让每个任务等待的时间都有上界。

5.1 算法规则与那道绕不开的入队顺序题

RR 的规则：所有就绪任务排成一个队列，轮流执行一个固定长度的时间片。时间片用完还没结束的任务，回到队尾重新排队。这是抢占式算法。

规则听着简单，但有一个细节会直接决定计算结果——时间片用完的时刻，和被抢占的任务、新到达的任务，谁先入队？

常见约定有两种，我采用教材里最通用的那种：时间片到期时，先把在此时刻及之前到达的新任务按到达顺序插入队尾，再把当前被抢占的任务插入队尾。换句话说，新来的排在被抢占的前面。

另一种约定是"被抢占的先入队、新来的后入队"，算出来的周转时间会不一样。所以做题或者写代码之前，一定要先确认用的是哪种约定，否则和标准答案对不上还会怀疑自己算错了。

5.2 时间片取多大：一个可以算出来的区间

时间片的大小是 RR 最核心的参数，它直接决定了两件事：响应时间和切换开销。

时间片太小，切换次数剧增，CPU 大量时间浪费在上下文切换上。假设一次上下文切换开销是 0.1ms，时间片是 1ms，那就有接近 9% 的 CPU 时间被浪费掉了，这个比例相当吓人。时间片太大，RR 就退化成 FCFS，短作业又要挨护航效应的打。

工程上的经验区间是这样的：时间片应该大于 80% 的 CPU 突发长度，同时让上下文切换开销占比控制在 5% 以内。如果一次上下文切换耗时 c，时间片是 q，那么开销占比约为c / (q + c)。要让这个值小于 5%，需要q > 19c。

以典型 Linux 环境为例，一次上下文切换的开销在 1 到 5 微秒量级，那么时间片应该在 20 到 100 微秒以上。历史上经典的分时系统时间片设置在 10ms 到 100ms 之间，现代系统因为切换开销更低，倾向取更小的值来提升交互性。

5.3 手算推演RR的完整过程

用前面的作业集合，取时间片 q = 2，按"新到达先入队"的约定推演。

t=0，就绪队列 = [J1]。J1 执行 0 到 2，剩余 5。t=2 时 J2 到达，入队；然后 J1 入队尾。队列 = [J2, J1]。

J2 执行 2 到 4，剩余 2。t=4 时 J3 到达，入队；J2 入队尾。队列 = [J1, J3, J2]。

J1 执行 4 到 6，剩余 3。t=5 时 J4 到达，t=6 时入队；然后 J1 入队尾。队列 = [J3, J2, J4, J1]。

J3 执行 6 到 7，服务时间只有 1，完成于 7，周转 3，等待 2。队列 = [J2, J4, J1]。

J2 执行 7 到 9，剩余 2 减到 0，完成于 9，周转 7，等待 3。队列 = [J4, J1]。

J4 执行 9 到 11，剩余 2，入队尾。队列 = [J1, J4]。

J1 执行 11 到 13，剩余 1，入队尾。队列 = [J4, J1]。

J4 执行 13 到 15，剩余 0，完成于 15，周转 10，等待 6。队列 = [J1]。

J1 执行 15 到 16，剩余 0，完成于 16，周转 16，等待 9。

平均周转 = (16 + 7 + 3 + 10) / 4 = 9.0，平均等待 = (9 + 3 + 2 + 6) / 4 = 5.0。

注意 J3 的结果：它在 RR 下的完成时间只比 SRTF 晚 2 个单位，但比 FCFS 早了 5 个单位。短作业在 RR 下不会因为排在长作业后面而无限期等待，这正是 RR 的价值。

5.4 上下文切换开销的账要这么算

我做一个真实的场景估算。假设系统有 50 个活跃进程，时间片 10ms，一次上下文切换开销 3 微秒。

单个进程完成一轮需要 50 × (10 + 0.003) ≈ 500.15ms。切换开销占比 = 0.003 / 10.003 ≈ 0.03%，可以忽略。

但如果是另一个极端：50 个进程，时间片设成 0.1ms。单轮时间 = 50 × 0.103 = 5.15ms，切换开销占比 = 0.003 / 0.103 ≈ 2.9%。看起来还能接受，但实际的影响不止于此——过于频繁的切换会严重破坏 CPU 缓存局部性，导致缓存命中率骤降，实际性能损失远超理论计算值。这是纸面公式算不出来的隐性成本。

注意：调整时间片时，除了算公式，一定要看实际的缓存未命中率和上下文切换次数的监控指标。vmstat里的cs列（上下文切换次数）如果持续在每秒几十万次以上，即使理论开销占比不高，实际吞吐也会明显下降。

6. 用Python把四种算法跑一遍：一套可复现的仿真

纸上推演容易出错，也难验证。我用一套统一的代码框架把四种算法实现出来，保证统计口径一致，输出可以直接互相比较。

6.1 数据结构和统计口径设计

统一用 dataclass 定义作业，把"静态属性"和"运行时状态"分清楚。静态属性是到达时间、服务时间、优先级，运行时状态是剩余时间、完成时间。这样做的好处是算法之间可以共享同一份作业定义，不用为每个算法重新构造数据。

统计函数独立出来，接收作业列表和一个"完成时间字典"，统一算出周转、带权周转、等待三个指标。统计口径统一了，结果才有可比性。

6.2 完整仿真代码

from dataclasses import dataclass from collections import deque @dataclass class Job: name: str arrive: int service: int prio: int = 0 # 数值越小优先级越高 def build_jobs(): return [ Job("J1", 0, 7, 3), Job("J2", 2, 4, 2), Job("J3", 4, 1, 4), Job("J4", 5, 4, 1), ] def report(title, jobs, finish): n = len(jobs) tot_turn = tot_wait = 0.0 print(f"--- {title} ---") print(f"{'作业':<6}{'到达':<6}{'服务':<6}{'完成':<6}{'周转':<6}{'带权周转':<10}{'等待':<6}") for j in jobs: f = finish[j.name] turn = f - j.arrive wait = turn - j.service tot_turn += turn tot_wait += wait print(f"{j.name:<6}{j.arrive:<6}{j.service:<6}{f:<6}{turn:<6}{turn / j.service:<10.2f}{wait:<6}") print(f"平均周转时间 = {tot_turn / n:.2f} 平均等待时间 = {tot_wait / n:.2f}\n") def fcfs(jobs): seq = sorted(jobs, key=lambda j: j.arrive) t, finish = 0, {} for j in seq: t = max(t, j.arrive) + j.service finish[j.name] = t return finish def sjf(jobs): pending = list(jobs) t, finish = 0, {} while pending: ready = [j for j in pending if j.arrive <= t] if not ready: t = min(j.arrive for j in pending) continue cur = min(ready, key=lambda j: (j.service, j.arrive)) t += cur.service finish[cur.name] = t pending.remove(cur) return finish def srtf(jobs): remain = {j.name: j.service for j in jobs} finish, t = {}, 0 while len(finish) < len(jobs): ready = [j for j in jobs if j.arrive <= t and remain[j.name] > 0] if not ready: t += 1 continue cur = min(ready, key=lambda j: (remain[j.name], j.arrive)) t += 1 remain[cur.name] -= 1 if remain[cur.name] == 0: finish[cur.name] = t return finish def priority_np(jobs): pending = list(jobs) t, finish = 0, {} while pending: ready = [j for j in pending if j.arrive <= t] if not ready: t = min(j.arrive for j in pending) continue cur = min(ready, key=lambda j: (j.prio, j.arrive)) t += cur.service finish[cur.name] = t pending.remove(cur) return finish def rr(jobs, quantum=2): seq = sorted(jobs, key=lambda j: j.arrive) remain = {j.name: j.service for j in seq} finish, ready = {}, deque() t, idx, n = 0, 0, len(seq) if n == 0: return finish t = seq[0].arrive ready.append(seq[0]) idx = 1 while ready: cur = ready.popleft() run = min(quantum, remain[cur.name]) t += run remain[cur.name] -= run # 新到达的作业先入队 while idx < n and seq[idx].arrive <= t: ready.append(seq[idx]) idx += 1 if remain[cur.name] == 0: finish[cur.name] = t else: ready.append(cur) # 被抢占的后入队 if not ready and idx < n: # CPU 空闲 t = seq[idx].arrive ready.append(seq[idx]) idx += 1 return finish if __name__ == "__main__": jobs = build_jobs() report("FCFS", jobs, fcfs(jobs)) report("SJF 非抢占", jobs, sjf(jobs)) report("SRTF 抢占", jobs, srtf(jobs)) report("优先级 非抢占", jobs, priority_np(jobs)) report("RR 时间片=2", jobs, rr(jobs, 2))

6.3 跑出来的结果与验证

直接运行，输出如下：

--- FCFS --- 平均周转时间 = 8.75 平均等待时间 = 4.75 --- SJF 非抢占 --- 平均周转时间 = 8.00 平均等待时间 = 4.00 --- SRTF 抢占 --- 平均周转时间 = 7.00 平均等待时间 = 3.00 --- 优先级 非抢占 --- 平均周转时间 = 9.50 平均等待时间 = 5.50 --- RR 时间片=2 --- 平均周转时间 = 9.00 平均等待时间 = 5.00

和手算结果完全一致，说明实现没有偏差。这一步很关键——如果你手算和代码跑出来的结果对不上，八成是三个地方出了问题：入队顺序约定不一致、忘了处理 CPU 空闲、或者抢占判断的临界条件写错了（比如该用<=写成了<）。

优先级那一行的数据可以手工验证一下：J1 到达 0，独跑 0 到 7。t=7 时已到达的作业有 J2（优先级 2）、J3（优先级 4）、J4（优先级 1），数值最小的是 J4，所以 J4 跑 7 到 11。接着比 J2（2）和 J3（4），选 J2 跑 11 到 15，最后 J3 跑 15 到 16。周转分别是 7、13、12、6，平均 9.5。没错。

6.4 改参数做实验：把时间片从1扫到8

既然代码写好了，顺手做个小实验，看看时间片对 RR 的影响。把quantum从 1 扫到 8，同一组作业的结果如下：

这组数据有个反直觉的地方：q=4 的结果居然比 q=2 和 q=1 都好，甚至比 FCFS 都好。这不是 bug，也不是普遍规律，而是特定输入下的巧合——这组作业的到达时间和剩余时间刚好和 q=4 形成了较优的错位，让 J2 能一次跑完。

我在实际调参时总结出的经验是：时间片和负载特征强耦合，没有通用最优值。真的要调，就收集自己系统真实的到达时间分布和服务时间分布，用这段仿真代码扫一遍参数空间，看哪个值在你的负载下平均指标最好。凭感觉设一个"10ms"是偷懒，不是工程。

另外注意，平均指标好不代表体验好。生产环境里我一般会同时看 P95 和 P99 的周转时间和响应时间，因为平均值会被大量短任务拉低，掩盖掉长尾问题。这也解释了一个常见困惑：为什么监控面板上平均延迟很漂亮，用户却在投诉卡顿——因为你在优化平均值，用户在体验长尾。

7. 常见问题与排查实录

算这类题目或者写这类调度逻辑，出错的地方高度集中。我把这些年踩过的坑和帮别人排查过的问题整理成一份速查表。

7.1 算错时间的六种典型情况速查表

关于最后一条补充一句：服务时间为 0 的作业在真实系统里是存在的（比如空转的定时器回调），做除法前一定要加保护，否则程序直接抛除零异常。我见过一个批处理框架因为这个问题在凌晨崩溃，排查了一整晚，最后发现是某个定时任务在特定条件下服务时间被估算成了 0。

还有一个不那么常见但很折磨人的问题：时间片大于所有作业的服务时间。这时候 RR 完全退化成 FCFS，如果你在对比实验里把 q 设成了 100，会得到 RR 和 FCFS 完全一样的结果，然后误以为代码写错了。这是预期行为，不是 bug。

7.2 调试这类题目的三个习惯

第一个习惯是画时间轴。不要只在脑子里推演，拿张纸画一条横线，标出每个时刻发生了什么。我见过太多人算错是因为脑子里同时跟踪了太多状态——谁在跑、剩余多少、队列里还有谁、下一个谁到。画出来，一个时刻一个时刻标，错误率会大幅下降。

第二个习惯是反向验证。算完之后用总量校验一遍：所有作业的总执行时间加起来，应该等于最后一个作业的完成时间减去第一个作业的开始时间，再减去 CPU 的空闲时间。如果不相等，说明一定算错了。这个检查特别适合交叉验证抢占式算法的结果，因为抢占式最容易出现"时间凭空多出来或少了"的情况。

第三个习惯是先写代码再手算。这个顺序听起来反了，但对我很有效。因为写代码的过程会强迫你把所有边界条件想清楚——CPU 空闲怎么办、多个作业同时到达怎么排序、时间片正好用完且作业正好完成怎么算。代码写完了，手算时脑子里已经有完整的规则模型，反而不容易错。

补充一个检查技巧：把 SJF 的结果和 SRTF 的结果放在一起看。SRTF 的平均周转时间一定小于等于 SJF，因为抢占式总是在非抢占式的可选集合里多了一个更优的选择。如果你的代码跑出 SRTF 比 SJF 还差，那一定是 SRTF 的实现有问题。

我把这四种算法反复实现过好几遍，最大的体会是：调度算法的难点从来不在算法本身，而在于规则边界的精确定义。FCFS、SJF、优先级、RR 这四个的逻辑，一页纸就能写完，但每一次实现都会在"同时到达怎么排""时间片和完成时刻重合怎么算""CPU 空闲要不要推进时间"这些细节上卡住。这些细节没有标准答案，取决于约定，但必须自洽。所以如果你在做技术选型，先别急着比较谁的指标更好，先把边界约定写下来，否则后面所有的对比都是空中楼阁。