第 3 章 · 处理机调度

上一章算过一笔账:时间片太碎,切换开销吃掉 CPU。但调度器要操心的远不止这一件事。同一批任务,按不同规则排队,平均等待时间能差出一个数量级,不信就用同一组数据排给你看。设三个进程先后到达:P1(到达 0,需要跑 24)、P2(到达 1,需要 3)、P3(到达 2,需要 3)。

按先来先到(FCFS):P1 独占 CPU 跑完 24,P2 从 1 等到 24,P3 从 2 等到 27。等待时间 0 + 23 + 25,平均 16。

按最短优先(SJF):虽然 P1 先来,如果调度器「未卜先知」,知道 P2、P3 更短……P1 还是先到的,先跑?非抢占的 SJF 拿 P1 没辙,结果和 FCFS 一样。但如果 P2 先到达,或允许抢占,短任务插队:P2、P3 各跑 3,P1 最后跑完 30。等待 0 + 0 + 1(P1 的 24 被推后但它是长任务),平均(24 + 0 + 1)÷ 3 ≈ 8.3,比 FCFS 砍半。

同一批活,16 和 8.3 的差别全部来自排队规则。本章讲清楚:调度器到底在优化什么指标、经典算法各自的招式和死穴、以及真实系统(Linux CFS)最终怎么解的。

3.1 优化什么:四个互相打架的指标

调度目标天生内讧,先认清每个指标疼的是谁:

周转时间:提交到完成的总时长。批处理系统的命根子。
响应时间:从发请求到首次响应的时长。交互系统的命根子(你敲键盘到字符出现的延迟)。
吞吐量:单位时间完成的任务数。
公平:不让任何任务饿死。

矛盾的典型:想让短任务快(SJF),长任务就得等,公平受损;想响应快(时间片切细),切换开销吞吞吐吐。调度器的艺术全在平衡,而平衡点因场景而异:服务器和手表的最优解根本不同,所以没有「最好的调度算法」,只有「为某类负载调好的算法」。

还有一个前置分类:抢占式(内核可以随时把 CPU 从你手里抢走)和非抢占式(你跑到让为止)。现代通用系统清一色抢占式,理由很硬:不能让一个死循环把整机拖死。下面的算法默认在抢占式语境下讨论。

3.2 四个经典算法,各自的招式与死穴

FCFS(先来先服务)。按到达顺序排队,简单到没有争议,也没法反驳它的死穴:护航效应。开头那个 24 对 3 的例子就是:一个长任务带三个短任务,全体短任务陪着耗。真实事故版:一个普通请求后面排着一坨日志同步,后面所有轻请求全部超时。

SJF(短作业优先)。数学上可证:平均等待时间最优。它的问题不是效果,是可行性:调度器怎么知道作业多长?批处理时代可以拿上次运行时长预估,交互系统里连用户自己都不知道这个进程要跑多久。于是它更多以「思想」存在,落到实践里变成长下面这样的形态。另外它是饿死长任务的惯犯:短任务源源不断,长任务永远排不上。

RR(时间片轮转)。就绪队列排好,每人跑一个时间片 q,用完回队尾。响应时间极好:n 个任务,最坏等 (n-1)×q 就能上。q 的取值是纯权衡:q 大过所有任务的运行时长就退化成 FCFS;q 太小,上一章算过,切换税吃掉一切。经验值是让「一次切换的开销占比 1% 以内」,毫秒级。

多级反馈队列(MLFQ):不预知运行时长,靠「观察 + 升降级」猜。规则值得原样背下来:

1. 新任务进最高优先级队列
2. 在某级队列跑满一个时间片还没完 → 降一级(它像个 CPU 密集任务)
3. 时间片没用完就主动让出(等 IO)→ 留在原级(它像个交互任务)
4. 高级队列空了才轮到低级;高级任务随时可抢占低级

效果:交互任务(IO 多、时间片用不完)一直待在高层,响应飞快;CPU 密集任务层层下沉,让出 CPU。整个过程不需要预知任何时长,全靠行为特征分类,这是它比 SJF 高明的地方。它也有自己的毛病:恶意或倒霉的任务可以「在时间片将尽时发一次无用 IO」骗留高层(课程作业里管这叫 gaming the scheduler);防御手段包括给每级记账(总配额用完就强制降级)、以及周期性把所有任务提回最高层(优先级提升,顺带防饿死)。

3.3 Linux CFS:完全公平调度器

真实系统给出了另一种答案。Linux 长期用 CFS(Completely Fair Scheduler;近年部分场景换了 EEVDF,思想相通):给每个进程记一个虚拟运行时间 vruntime,谁跑得少谁的 vruntime 小,调度器永远挑 vruntime 最小的上 CPU。所有进程的 vruntime 趋于相等,「完全公平」。数据结构是红黑树(数据结构课的出场时刻),插入删除 O(log n),最小值随时可查。

CFS 的聪明处在于「记账而不是猜测」:不给任务分类,不预估时长,只记账,公平自动浮现。IO 多的任务跑得慢,vruntime 小,自然被优先照顾,MLFQ 想用一堆规则模拟的效果,它用一个变量实现了。nishang 细节还有 nice 值(用户指定的权重,映射成 vruntime 的流速而非硬优先级)和新进程的初始 vruntime 处理(放队尾防新任务插队刷公平)。读它的源码注释是件赏心悦目的事,调度器是内核里少有的「带设计哲学」的模块。

3.4 优先级的坑:火星车死机事件

只要系统里有优先级,就有一个必考的陷阱:优先级反转。低优先级任务 L 拿着锁,高优先级任务 H 来抢锁被挂起;这时中优先级任务 M 上 CPU 狂跑,把 L 挤得下不来台;L 不释放锁,H 就永远等不到,实际效果是 M 骑在了 H 头上。

这不是纸面推演,是真把火星车干趴下过的 bug。1997 年火星探路者号着陆后几天,系统频繁莫名重启:飞船上有一个高优先级信息管理任务、一个低优先级气象任务,两者共用一把互斥锁;中优先级的通信任务一忙起来就触发反转,看门狗以为系统死了,整船重启。地面团队在实验室复现、打上优先级继承补丁(持锁的低优先级任务临时继承 H 的优先级,先跑完放锁),危机才解除。这件事后来写进了无数实时系统教材,结论记两条:用锁就要考虑反转;实时系统要用优先级继承或优先级天花板协议。

常见错误

在应用层自己造「高优先级线程」却共享锁。用户态优先级和内核调度器对不上号,反转照样发生;要么小心设计锁的粒度,要么干脆按队列解耦。
把 nice 值当硬优先级。nice 只是权重,重负载下 -20 和 19 的差距会缩小;实时性需求要用调度策略(SCHED_FIFO/RR)而非 nice。
时间片拍脑袋设小。「切得快 = 响应快」只对到切换开销可忽略为止,上一章那道计算题的教训。

练习

手算:五个进程 P1~P5,到达时间 0/1/2/3/4,运行时长 8/1/3/2/6。分别用 FCFS、非抢占 SJF、RR(q=2) 算平均周转时间,排出名次。
手算:上题若 SJF 会饿死哪个任务?在什么到达模式下 SJF 的饥饿是无限的?
手算:MLFQ 三级队列,时间片 4/8/16。一个任务总时长 30、纯 CPU,画出它的完整时间线,算总周转;再算它每次「在时间片剩 1 时发 IO」能骗到的收益。
思考:CFS 的 vruntime 为什么用「虚拟」二字?提示:nice 值不同的进程,同样跑 1ms,vruntime 加的一样多吗?查一下「weight 和 vruntime 的换算」。