五大操作系统调度算法：FCFS、RR、SJF、SRT、HRRN 手算与工程实践

1. 先弄清楚调度算法到底在抢什么资源1.1 一个被考试题掩盖的真实问题操作系统调度算法这五个字大部分人的第一反应是期末卷子上那道给定进程到达时间和服务时间求平均周转时间的题。FCFS、RR、SPNSJF、SRT、HRRN 背下来规则画个甘特图套公式算完就完事了。但我真正被这五个算法教育过是几年前给一个长时间运行的采集服务做任务排队策略的时候——线程池里堆了上千个任务有的几毫秒就跑完有的要跑好几秒用最朴素的先进先出结果是一堆小任务堵在一个大任务后面监控上的 P99 延迟直接炸了。那一刻我才意识到调度算法解决的问题一点都不抽象在资源有限、请求到达时间不确定、每个请求执行时间也不确定的前提下怎么决定下一个把资源给谁。CPU 是最经典的场景但线程池、数据库连接池、消息队列的消费顺序、甚至打印机的任务队列本质上都是同一道题。这篇文章把 FCFS、RR、SPNSJF、SRT、HRRN 这五个调度算法从头拆一遍。不是复述教材而是说清楚每个算法为什么被设计成那样、它在什么场景下真的有用、手算题里那些容易踩的坑以及用代码实现时哪些细节会让结果和手算对不上。不管你是正在准备操作系统考试的学生还是需要给系统设计排队策略的工程师这些内容都能直接用上。1.2 衡量一个调度算法好坏到底看哪几个指标在比较算法之前得先统一度量衡否则讨论谁更好就是抬杠。CPU 调度里最常用的四个指标我按实际重要性排一下周转时间Turnaround Time 完成时间 − 到达时间。这是最直观的指标代表一个任务从进门到走人总共花了多久。注意它包含等待时间和执行时间两部分。带权周转时间Weighted Turnaround Time 周转时间 ÷ 服务时间。这个指标比周转时间更公平因为它把任务本身的长度归一化了。一个服务时间是 1 的任务等了 10带权周转是 11一个服务时间是 10 的任务等了 10带权周转只有 2。前者体验极差后者还能接受。所以很多教材和面试题都用带权周转时间作为评判标准就是因为单纯比周转时间会偏向短作业。等待时间Waiting Time 周转时间 − 服务时间也就是任务在就绪队列里干等的时间。它和周转时间只差一个常数任务的服务时间所以在排序意义上两者等价。响应时间Response Time 首次获得 CPU 的时刻 − 到达时间。这个指标只关心第一次被服务有多快不关心总共跑了多久。分时系统和交互式系统最看重它因为用户敲一下键盘只要界面有反应就行不在乎后台那个任务是不是还没跑完。注意周转时间和响应时间是两个完全不同方向的指标一个衡量尽快做完一个衡量尽快开始。很多调度算法的取舍本质就是在这两个指标之间做交换。1.3 抢占与非抢占一条把算法分成两派的分界线在讲具体算法前必须先说清楚**抢占Preemptive和非抢占Non-preemptive**的区别因为它直接决定了算法的行为边界。非抢占的意思是一旦 CPU 分配给某个进程就必须等它自己跑完或者主动放弃比如发起 I/O 请求进入阻塞中途谁来了都不打断。FCFS、SPNSJF、HRRN 都属于这一类。抢占的意思是如果来了一个更该被优先处理的进程当前进程会被强行挂起让出 CPU。RR时间片用完就切和 SRT来了更短的作业就切属于这一类。抢占带来的第一个代价是上下文切换开销保存当前进程的寄存器、程序计数器、内存映射状态再恢复另一个进程的这一套动作本身要消耗几十到几百微秒。切得太频繁CPU 的时间就大量浪费在换人上而不是干活上。第二个代价是实现复杂度抢占式调度必须在每个可能发生抢占的时刻时钟中断、新进程到达、I/O 完成检查是否需要切换还要处理共享数据的一致性。非抢占式就简单得多只在进程结束时做一次决策。为了后面所有算法都能用同一组数据横向对比我统一用下面这五个进程。这套数据特意设计过能让每个算法的特征差异都暴露出来进程到达时间服务时间A06B13C32D43E51总服务时间 15 个时间单位。后面每一节的手算都基于这张表你可以拿它跟着一起算对照结果。2. FCFS最容易实现也最容易把自己坑死2.1 规则简单到一句话就能说完**FCFSFirst Come First Served先来先服务**的规则就一句话谁的到达时间早谁先上 CPU而且一旦上去就不下来直到跑完。它的数据结构就是一个简单的 FIFO 队列。进程到达时入队CPU 空闲时从队头取一个。没有优先级计算没有时间片管理没有抢占判断。用代码实现大概十行就够了def fcfs(procs): procs sorted(procs, keylambda p: (p.arrive, p.pid)) t 0 for p in procs: t max(t, p.arrive) # CPU 可能空闲等进程到达 p.start t t p.burst p.finish t return procst max(t, p.arrive)这一句很关键。如果当前进程结束的时间早于下一个进程的到达时间CPU 会有一段空闲期必须把时间推到下一个进程真正到达的时刻。手算的时候很多人忘了这一点导致整个时间轴前移后面全错。2.2 用手算数据跑一遍 FCFS时间轴推进过程如下进程开始时间完成时间周转时间带权周转时间A0661.00B6982.67C91184.00D1114103.33E14151010.00平均周转时间 (6 8 8 10 10) / 5 8.4平均带权周转时间 (1.00 2.67 4.00 3.33 10.00) / 5 4.20E 这个进程只有 1 个时间单位的服务时间却等了 9 个单位带权周转时间高达 10把平均值狠狠拉了一把。这就是 FCFS 最典型的问题。2.3 护航效应FCFS 的致命伤FCFS 最出名的问题是护航效应Convoy Effect一个执行时间很长的进程占据 CPU 的时候后面所有短进程都得排队干等。等它跑完短进程一拥而上快速处理完紧接着 CPU 又空闲了然后又来一个长进程又堵住一整队。这个场景在生活里有个特别形象的类比超市只开一个收银台前面那位顾客推着满满一车货慢慢结账后面拿着口香糖的人全都在等。收银台CPU没闲着但吞吐量极差用户体验也差。从上面的数据能看出来E 的等待时间是 9 个单位占它全部周转时间的 90%。如果换一个调度顺序把短的先做E 的等待可以压到 1 个单位以内。FCFS 的优势也很明确实现最简单不会有饥饿问题每个进程最终都会被服务上下文切换次数最少每个进程只切换一次对长作业友好适合批处理系统里那种任务本来就要跑很久、对延迟不敏感的场景。实操心得真正在生产环境里FCFS 很少单独出现但它经常作为默认行为潜伏在代码里——比如一个简单的queue.Queue() 单 worker 线程或者数据库的简单排他锁等待队列。如果你发现某个服务的尾延迟很高但 CPU 利用率并不高先去检查是不是这种隐式的 FCFS 在作怪。3. RR 时间片轮转分时系统的标准答案3.1 时间片是 RR 的灵魂也是它最大的调参难题**RRRound Robin时间片轮转**的规则是所有就绪进程排成一个循环队列CPU 从队头取进程给它一个固定的时间片 q。如果进程在 q 内跑完了正常结束如果没跑完它被挂起放到队尾CPU 给下一个进程。RR 的响应时间表现是所有算法里最好的之一因为它天然保证了每个进程每过一段时间就能摸一次 CPU。但它有一个必须回答的问题时间片 q 该设多大q 设得太大每个进程都能在一个时间片内跑完RR 直接退化成 FCFS响应时间优势荡然无存。q 设得太小上下文切换的频率急剧上升CPU 大量时间花在保存和恢复现场上。教材里有个经典的量化计算假设上下文切换一次耗时 0.1 ms我们要求的额外开销不超过 1%。设时间片为 q则切换开销占比约为0.1 / (q 0.1)。要求这个值小于 1%可以解出q ≥ 10 ms。也就是说时间片至少要等于切换开销的 100 倍才能把调度本身的开销压到 1% 以下。教材里一般给的结论是时间片应大于绝大多数进程的 CPU 突发长度让大部分进程能在一个时间片内完成同时又要足够小保证交互响应及时。实际系统里Linux 的调度粒度在毫秒到几十毫秒这个量级。3.2 RR 的手算入队顺序决定一切RR 手算最容易出错的地方是**时间片结束的瞬间正好有新进程到达该怎么排队**。不同教材处理方式不一样有的先放新到达的进程有的先放被抢占的进程。这不是算法性质问题但会让手算结果差好几个单位。本文统一采用新到达的进程先入队被抢占的进程后入队。取 q 1手工推演时刻事件就绪队列队头在左0A 到达A 运行 0→1剩 5[B, A]1B 到达A 时间片到A 入队尾[B, A]2B 运行 1→2剩 2[A, B]3C 到达B 时间片到入队尾[B, C, A]4A 运行 2→3剩 4D 到达[C, A, D, B]5B 运行 3→4剩 1E 到达[A, D, B, E, C]6C 运行 4→5剩 1[D, B, E, C, A]7A 运行 5→6剩 3[B, E, C, A, D]8D 运行 6→7剩 2B 运行 7→8 完成[E, C, A, D]9E 运行 8→9 完成[C, A, D]10C 运行 9→10 完成[A, D]11A 运行 10→11剩 2[D, A]12D 运行 11→12剩 1[A, D]13A 运行 12→13剩 1[D, A]14D 运行 13→14 完成[A]15A 运行 14→15 完成[]结果汇总进程完成时间周转时间带权周转时间首次响应时刻响应时间A15152.5000B872.3310C1073.5041D14103.3362E944.0083平均周转时间 (15 7 7 10 4) / 5 8.6平均带权周转时间 (2.50 2.33 3.50 3.33 4.00) / 5 3.13平均响应时间 (0 0 1 2 3) / 5 1.2对比 FCFSRR 的平均周转时间 8.6 反而比 FCFS 的 8.4 略差一点但平均响应时间从 5.4 直接降到 1.2差了四倍多。这说明 RR 不是用来优化吞吐的它是用吞吐时间换响应速度的。3.3 RR 的代码实现要点from collections import deque def rr(procs, q): procs sorted(procs, keylambda p: (p.arrive, p.pid)) t procs[0].arrive if procs else 0 i, n 0, len(procs) rq, done deque(), [] while i n or rq: while i n and procs[i].arrive t: rq.append(procs[i]); i 1 if not rq: # CPU 空闲跳到下一个到达时刻 t procs[i].arrive continue p rq.popleft() if p.start 0: p.start t # 记录首次运行时刻用于算响应时间 run min(q, p.remain) p.remain - run t run while i n and procs[i].arrive t: # 新到达者先入队 rq.append(procs[i]); i 1 if p.remain 0: rq.append(p) # 被抢占者后入队 else: p.finish t done.append(p) return done这段代码里有两个容易写错的地方。第一while i n and procs[i].arrive t在进程运行结束后又执行了一次这是为了模拟时间片内到达的新进程。第二新到达进程和被抢占进程的入队顺序必须和你手算的规则一致否则模拟结果对不上手工推演会让人怀疑代码写错了。提示真实系统里的 RR 不会傻等到时间片用完才看有没有新进程。比如有新进程在时间片中段到达内核通常会在它到达时立刻把它放进队尾而不是等当前进程跑完整个时间片再去清点。这属于事件驱动的实现细节模拟器为了可读性做了简化。4. SPN / SJF平均周转时间的理论最优解4.1 为什么最短的先做能把平均周转时间压到最低**SPNShortest Process Next**和 **SJFShortest Job First**指的是同一个东西非抢占式的最短作业优先。规则是每次 CPU 空闲时从所有已经到达的进程里挑服务时间最短的那个执行。这个算法有个很漂亮的数学结论在所有非抢占式调度算法中SJF 的平均等待时间是最小的。直觉上的解释是如果你把一长一短两个作业放在一起短作业先做两个作业的等待时间之和一定小于长作业先做的情况。用上面数据算一下先做 E1 个单位再做 A6 个单位总等待是 0 1 1反过来是 0 6 6。短先做省了 5 个单位的等待。这个结论可以推广到任意多个作业——通过不断交换相邻的长在前、短在后的组合总等待时间只会减少不会增加最优解就是把所有作业按服务时间升序排列。所以 SJF 是一个有理论保证的算法这也是它经常被拿来当基准线的原因。4.2 用手算数据跑一遍 SJF时间轴推进过程t 0 时只有 A 到达A 必须执行非抢占0 → 6 跑完完成时间 6周转时间 6。t 6 时B服务 3、C服务 2、D服务 3、E服务 1都已到达。按服务时间排序E(1) C(2) B(3) D(3)。B 和 D 长度相同按先来后到B 先。进程开始时间完成时间周转时间带权周转时间A0661.00E6722.00C7963.00B912113.67D1215113.67平均周转时间 (6 2 6 11 11) / 5 7.2平均带权周转时间 (1.00 2.00 3.00 3.67 3.67) / 5 2.67比 FCFS 的 8.4 和 4.20 明显好。但注意 E它只等了一个单位就跑了带权周转是 2看起来不错。而 D 的带权周转是 3.67比 E 差很多——这就是 SJF 的偏袒效应。4.3 两个绕不开的现实问题怎么知道未来以及饥饿SJF 有两个在真实系统里几乎致命的问题。第一个问题是它要求预知未来。要挑最短的作业你得先知道每个进程要跑多久。真实系统里没人能提前知道这一点。工程上的做法是用指数平均预测记录每个进程最近几次的 CPU 突发长度用加权平均预测下一次。公式是τ(n1) α · t(n) (1 - α) · τ(n)其中t(n)是第 n 次实际的 CPU 突发长度τ(n)是第 n 次之前的预测值α是权重通常取 0.5。举个数假设第一次预测 τ(1) 10实际第一次跑了 t(1) 6α 0.5。那么 τ(2) 0.5 × 6 0.5 × 10 8。第二次实际跑了 t(2) 4那么 τ(3) 0.5 × 4 0.5 × 8 6。把这个公式展开会发现历史数据前面的系数是 α、α(1−α)、α(1−α)²……指数衰减越久远的数据权重越小。这就是为什么它叫指数平均——它用固定大小的存储记住了整个历史而且越近的历史越重要。**第二个问题是饥饿。**如果源源不断地有短作业到达长作业可能永远排在队尾理论上可以被无限期推迟。这在批处理系统里未必是问题反正任务最终会跑完但在交互系统里就是灾难——用户提交了一个大任务等了一小时还没开始会直接投诉。4.4 SJF 的实现import heapq def sjf(procs): procs sorted(procs, keylambda p: (p.arrive, p.pid)) t, i, n 0, 0, len(procs) ready, done [], [] while len(done) n: while i n and procs[i].arrive t: heapq.heappush(ready, (procs[i].burst, procs[i].arrive, procs[i].pid, procs[i])) i 1 if not ready: # 没有就绪进程CPU 空转 t procs[i].arrive continue _, _, _, p heapq.heappop(ready) p.start t t p.burst p.finish t done.append(p) return done堆里的元组(burst, arrive, pid, obj)前三项保证不会比到最后的对象上。这是 Python 里用 heapq 存自定义对象时的标准套路——如果只放(burst, obj)当 burst 相同时 Python 会去比较两个对象直接抛TypeError。实操心得如果你在设计一个线程池想模拟 SJF 的效果别真的去预测任务时长——成本太高。更实用的做法是按任务的类型分桶比如查询类任务和计算类任务分到不同队列用不同的并发度。这是 SJF 思想在工程上更接地气的落地方式。5. SRT让 SJF 也能抢占5.1 抢占的门槛剩余时间更短才切SRTShortest Remaining Time是 SJF 的抢占版本规则是每当有新进程到达时比较新进程的服务时间和当前进程的剩余服务时间如果新进程更短就抢占。关键词是剩余。SJF 比的是原始服务时间SRT 比的是还剩多少没跑。这个区别让 SRT 在新进程不断到达的场景下有更好的平均周转时间但代价是上下文切换显著增多。注意一个容易搞错的细节如果新到达进程的服务时间恰好等于当前进程的剩余时间通常不抢占。因为抢占本身有代价收益为零的时候没必要切换。这个规则教材里有些版本写得含糊手算时按严格小于才抢占处理结果一般和标准答案对得上。5.2 用手算数据跑一遍 SRT推演过程t 0只有 A 到达A 开始运行剩余 6。t 1B 到达服务时间 3A 剩余时间 5。3 5抢占。B 开始运行剩余 3。t 3C 到达此时 B 已运行 1→3剩 1。C 服务时间 22 1不抢占。t 4B 运行到 4 完成周转 3。就绪队列有 C(2)、D(3)。选 C运行 4→6 完成周转 3。t 5E 到达C 正在运行剩 1。E 服务时间 1等于 C 的剩余 1不抢占。t 6C 完成。就绪有 D(3)、E(1)。选 E运行 6→7 完成周转 2。t 7选 D运行 7→10 完成周转 6。t 10A 剩余 5运行 10→15 完成周转 15。进程完成时间周转时间带权周转时间A15152.50B431.00C631.50D1062.00E722.00平均周转时间 (15 3 3 6 2) / 5 5.8平均带权周转时间 (2.50 1.00 1.50 2.00 2.00) / 5 1.80平均响应时间 (0 0 1 3 1) / 5 1.0这是五个算法里最漂亮的一组数据。SRT 的平均带权周转时间 1.80比 SJF 的 2.67 好了一大截。原因就是 t 1 那一刻的抢占如果按 SJF 不抢占A 会霸占 CPU 到 t 6B 的周转时间从 3 变成 8。5.3 SRT 的实现关键在事件点切分时间import heapq def srt(procs): procs sorted(procs, keylambda p: (p.arrive, p.pid)) t, i, n 0, 0, len(procs) ready, done [], [] while len(done) n: while i n and procs[i].arrive t: heapq.heappush(ready, (procs[i].remain, procs[i].arrive, procs[i].pid, procs[i])) i 1 if not ready: t procs[i].arrive continue _, _, _, p heapq.heappop(ready) if p.start 0: p.start t nxt procs[i].arrive if i n else float(inf) run min(p.remain, nxt - t) # 只跑到下一个事件点 p.remain - run t run if p.remain 0: heapq.heappush(ready, (p.remain, p.arrive, p.pid, p)) else: p.finish t done.append(p) return done这段代码的核心是run min(p.remain, nxt - t)。SRT 的决策点是新进程到达所以模拟时不能让当前进程一口气跑完必须精确地在下一个进程到达的时刻停下来重新决策。写这类事件驱动模拟器的时候nxt - t一定要保证非负。如果因为浮点误差或者逻辑漏洞导致它是 0程序就进入死循环了。一个实用的自检方法是跑完所有进程后把每条时间轴打印出来看看有没有重叠或者空洞。提示SRT 是所有算法里平均周转时间最优的可以证明在有抢占的算法中 SRT 的平均等待时间最小但它的抢占次数也是最多的。真实系统里如果一个进程刚被切下去没一会儿又要被切回来光是保存恢复现场的开销就可能吃掉全部收益。所以现实中的调度器通常会给抢占加一个宽限期比如进程运行不满一定时间就暂时不抢占它。6. HRRN给长作业留一条活路6.1 响应比一个能同时照顾短作业和等待时间的指标**HRRNHighest Response Ratio Next响应比高者优先**是非抢占式算法它每次挑进程的时候算一个响应比挑最大的那个。响应比的定义是R (等待时间 服务时间) / 服务时间 1 等待时间 / 服务时间这个公式设计得很巧妙。分母是服务时间所以短作业的等待时间/服务时间增长得快天然占优保留了 SJF 的短作业优先特性。但分子里有等待时间一个长作业等得足够久之后它的响应比会超过短作业从而被调度到。这就从机制上消除了饥饿。举个具体的数字对比一个服务时间为 1 的短作业等了 2 个单位R 1 2/1 3。一个服务时间为 10 的长作业等了 5 个单位R 1 5/10 1.5。这时候短作业优先。但如果长作业等了 30 个单位R 1 30/10 4就反超短作业了。6.2 用手算数据跑一遍 HRRNt 0 时只有 A 到达A 直接运行 0→6 完成周转 6。t 6就绪队列B到达 1服务 3等待 5、C到达 3服务 2等待 3、D到达 4服务 3等待 2、E到达 5服务 1等待 1。进程等待时间服务时间响应比B531 5/3 2.67C321 3/2 2.50D231 2/3 1.67E111 1/1 2.00B 的响应比最高选 B运行 6→9 完成周转 8。t 9就绪队列C等待 6、D等待 5、E等待 4。进程等待时间服务时间响应比C621 6/2 4.00D531 5/3 2.67E411 4/1 5.00E 最高选 E运行 9→10 完成周转 5。t 10就绪C等待 7、D等待 6。C 的 R 1 7/2 4.5D 的 R 1 6/3 3。选 C运行 10→12 完成周转 9。t 12只剩 D运行 12→15 完成周转 11。进程完成时间周转时间带权周转时间A661.00B982.67C1294.50D15113.67E1055.00平均周转时间 (6 8 9 11 5) / 5 7.8平均带权周转时间 (1.00 2.67 4.50 3.67 5.00) / 5 3.37结果介于 SJF 和 FCFS 之间。HRRN 的定位就是用一点平均性能换公平性它不追求最优的平均周转时间追求的是没有进程被饿死。6.3 实现和时间复杂度def hrrn(procs): procs sorted(procs, keylambda p: (p.arrive, p.pid)) t, done, done_ids 0, [], set() n len(procs) while len(done) n: ready [p for p in procs if p.arrive t and p.pid not in done_ids] if not ready: t min(p.arrive for p in procs if p.pid not in done_ids) continue p max(ready, keylambda x: (t - x.arrive x.burst) / x.burst) p.start t t p.burst p.finish t done.append(p) done_ids.add(p.pid) return done每次调度都要遍历所有就绪进程算响应比单次调度是 O(n)n 个进程总共 O(n²)。相比 SJF 用堆能做到 O(n log n)HRRN 的复杂度高一档。但在调度次数有限、进程数量不大的场景下这点开销完全可以接受。注意事项HRRN 的计算基准是当前时刻所以响应比是随时间动态变化的。手算的时候一定要在每个调度决策点重新算一遍不能沿用上一轮的数字。这是 HRRN 手算题最常见的错误来源。7. 五个算法放一起到底该怎么选7.1 一张表看清差异算法抢占性平均周转平均带权周转平均响应饥饿风险实现复杂度核心适用场景FCFS否8.44.205.4无极低批处理、打印队列RR是8.63.131.2无低分时、交互式系统SJF / SPN否7.22.674.2有中长任务为主的批处理SRT是5.81.801.0有中高短任务多、延迟敏感HRRN否7.83.374.8无中混合负载、需要公平这张表里有个很值得注意的现象平均周转时间和平均响应时间基本是反向的。RR 和 SRT 响应时间好但周转时间不占优FCFS 和 SJF 反过来。这不是巧合而是尽快开始和尽快完成这两个目标本身的矛盾——要让每个进程都能快速拿到 CPU就必须频繁切换切换的开销和被打断的代价最终会体现在总完成时间上。所以哪个算法最好这个问题本身就是错的。正确的问题是**你的系统更在意哪个指标**批处理系统在意吞吐量和总完成时间选 SJF 或 SRT交互式系统在意用户感知的响应速度选 RR负载混杂又怕长任务被饿死选 HRRN。7.2 真实操作系统里它们是怎么被组合起来的现实中没有哪个通用操作系统只用一个算法。Linux 的 CFS完全公平调度器用的是红黑树加虚拟运行时间vruntime本质上是vruntime 最小者优先可以理解为一种加权公平队列思想源头能追到 SJF 的短作业优先但通过权重和时间片动态化解决了饥饿问题。Windows 用的是多级反馈队列MLFQ把就绪进程分成多个优先级队列高优先级队列时间片短、低优先级队列时间片长进程用完时间片就降级等久了再升级。多级反馈队列其实是个缝合怪把前面几个算法的思路都用上了队列之间是优先级调度类似 SJF 的思想短任务留在高优先级队列队列内部是 RR进程等待太久会被提升优先级类似 HRRN 防饥饿。这也是为什么教材在讲完这五个基础算法之后一定会讲多级反馈队列——它是这些简单算法的工程化集成方案。如果你在设计自己的任务调度系统一个很实用的思路是别追求单一日志的完美做分层。第一层按业务类型分队列第二层在每个队列内部用 RR 保证响应第三层对超时任务做优先级提升防止饥饿。这个三层结构基本能覆盖大多数实际需求。7.3 影响范围这些算法影响的不只是 CPU 时间这几个算法的影响半径比大多数人想的要广。在操作系统层面它们直接影响交互延迟、吞吐量、上下文切换频率和 CPU 缓存命中率。在应用层面线程池的任务排队、数据库的锁等待队列、消息队列的消费顺序、甚至 CDN 的请求排队策略都是同一类问题的不同表现形式。一个具体的例子某个电商系统在大促期间的订单处理服务如果用的是隐式 FCFS那么一笔涉及大量商品的复杂订单会堵住后面几十笔简单的下单请求用户在页面上看到的就是转圈转了半天。把调度策略改成按订单商品数量分桶 桶内 FIFO效果立竿见影。这不是什么高深技术就是 SJF 思想最朴素的应用。8. 手算易错点和代码实现的坑一次说清8.1 手算题高频错误速查错误现象常见原因正确做法带权周转时间算出来特别大分母写成了周转时间分母是服务时间不是周转时间SJF 手算结果和答案差几个单位忽略了非抢占特性SJF 一旦开始就必须跑完即使中途来了更短的SRT 抢占时机判断错比的是原始服务时间比的是当前进程的剩余时间RR 时间轴对不上新到达进程和被抢占进程的入队顺序搞反明确统一一种规则全篇一致HRRN 算出多个最高响应比没有在每个决策点重算响应比随时间变化每次调度都要重新计算周转时间出现负值或过小忘记处理 CPU 空闲期当前进程结束早于下个到达时CPU 要空转等待8.2 代码模拟时最常踩的三个坑**第一个坑堆里存自定义对象。**用 Python 的heapq存(key, obj)这种元组时如果 key 相同Python 会去比较后面的 obj而自定义类默认不支持比较直接抛TypeError。解决办法是在元组里加一个唯一的、可比较的中间项比如(key, arrive, pid, obj)。**第二个坑事件驱动的模拟器出现无限循环。**SRT 这类抢占算法必须精确停在事件点上run min(remain, nxt_arrive - t)里的nxt_arrive - t如果因为浮点或者逻辑问题变成 0进程永远跑不完程序卡死。写完后一定要加一个总时间上限的断言超过就报错退出而不是死等到天荒地老。**第三个坑手算和代码结果不一致。**这种时候九成是入队顺序、抢占条件严格小于还是小于等于、或者 CPU 空闲期处理这三处之一和手算规则不一致。建议的做法是先把规则写在纸上代码里加注释标注跑完打印完整时间轴逐格对照。8.3 面试和考试里最常见的几个刁钻问法RR 的平均周转时间一定比 FCFS 差吗不一定。这个结论依赖于时间片大小和具体的到达/服务时间分布。如果时间片足够大到每个进程都能一次跑完RR 就等价于 FCFS两者结果完全相同。只有当时间片小于进程的服务时间、导致进程被切成多段执行时RR 的周转时间才可能变差。SJF 是不是平均周转时间最短的算法在非抢占式算法中SJF 的平均等待时间确实是最短的这个有严格证明。但如果不限定非抢占SRT 的平均等待时间可能比 SJF 更短因为抢占能让新来的短作业立刻获得服务。为什么实际系统不用 SRT因为它需要预知剩余时间而且抢占过于频繁切换开销会吃掉收益。真实系统通常用预测 宽限期的折中方案。HRRN 的响应比为什么是 1 等待时间/服务时间而不是直接 等待时间/服务时间因为加不加 1 只影响数值大小不影响排序结果。但写成 1 的形式能直观看出等待时间为 0 时响应比最小为 1这让响应比永远是个正数便于比较和理解。8.4 一个可以拿去直接用的验证清单写完任何调度模拟器之后我会跑这几个检查基本能筛出所有实现错误所有进程的finish - start之和等于总服务时间不多不少时间轴上没有重叠区间也没有空洞除非真的有 CPU 空闲期每个进程的remain在结束时恰好为 0抢占类算法里每次抢占都必须是更短的任务到达日志里能对上手工算一遍小规模数据三到五个进程和程序输出逐行对比这几个检查做完基本可以确信模拟器是正确的。调度算法本身不难难的是把边界条件写对。我自己的体会是这五个算法真正的价值不在于背规则而在于它们展示了一条清晰的思路演进从最朴素的 FCFS到为了响应速度引入 RR到为了效率引入 SJF为了兼顾效率与及时性引入 SRT最后为了公平性引入 HRRN。每一步都是在解决上一步暴露的问题同时也引入了新的代价。理解了这条演进线再去看现代操作系统里那些复杂的调度器就不会觉得它们是一堆看不懂的规则堆砌而是一系列权衡叠加的结果。