CFS 的公平擅长分蛋糕,不擅长承诺时刻

第 94 篇讲过 CFS 怎么用 vruntime 分蛋糕:所有可运行任务按权重折算虚拟运行时间,调度器永远挑 vruntime 最小的那个。这套规则能保证长期份额精确公平,但对「什么时候轮到我」不给任何承诺——一个刚被唤醒的交互线程能不能立刻跑,取决于一簇补偿式的经验常数:唤醒抢占粒度、调度周期、最小时间片。这些旋钮彼此耦合,调好一个服务就要重调一遍,内核开发者背着它们维护了十几年。EEVDF(Earliest Eligible Virtual Deadline First,最早合格虚拟截止时间优先)1995 年就在论文里出现过,Linux 6.6 起正式取代 CFS 成为 fair class 的引擎,动机正是把「延迟」变成可推理的一等公民。
EEVDF 的关键一步,是把每个任务对调度器的诉求拆成显式的两项:权重(还是 nice 那一套,决定你该分多少)加上请求片(你这次申请跑多久)。权重决定份额与 lag 的恢复速度;请求片参与虚拟截止时间的计算——申请越短,截止越紧迫,越容易被插队执行。于是「先到先得」的公平变成了「欠得越多越有资格、越急着要越早跑」的公平:份额仍然长期精确,延迟则由任务自己声明的请求片控制,不再依赖一撮魔法常数。
lag:调度器欠你的账
理解 EEVDF 只需要盯住一个量:lag。定义极简——lag 等于「按你的权重本应得到的服务」减去「实际已得到的服务」。任务在等队里的每一刻,本应份额照涨、实际服务不动,lag 一路上涨;跑到 CPU 上的每一刻,实际服务涨得比本应份额快,lag 一路下降。lag 大于零,说明调度器欠你的账还没还清;lag 小于零,说明你已经多拿了。
eligibility(合格性)就建立在这本账上:lag 大于零的任务才有资格运行。这条规则的意义在于把「公平」从长期均值变成即时约束——调度器不会让任何一个多拿了份额的任务继续压着欠账的对手跑。实现上内核不去维护显式的 lag 字段,而是借道 vruntime:把 cgroup 队列上所有实体的 vruntime 按权重做加权平均得到「公平位置」,你的 vruntime 相对它的偏移乘上权重就是 lag 的符号。相关代码在 kernel/sched/fair.c 的 avg_vruntime 与 entity_eligible,用带符号的乘法避开除法,挂在每个调度决策的路径上。你不需要背公式,只需要记住结论:欠账者为王,多拿者靠边。
flowchart TB
A["唤醒或 tick 到来<br>调度点"] --> B{"最左节点 eligible<br>且 deadline 够早?"}
B -- 是 --> C["直接选它<br>一步命中"]
B -- 否 --> D["沿 min_deadline 缓存<br>下钻找 eligible 中<br>虚拟截止时间最早者"]
C --> E["运行至请求片耗尽<br>或被更早 deadline 抢占"]
D --> E
E --> F["lag 下降<br>deadline 推移<br>重新入树"]
F --> A
虚拟截止时间:把「急」翻译成可排序的数字
合格只是入场券,出场顺序由虚拟截止时间决定。规则是:截止时间 = 当前 vruntime 加上请求片的虚拟长度。请求片由基准片(sysctl_sched_base_slice,默认 750 微秒)结合任务权重换算,换算发生在虚拟时间轴上——权重的变化会同时改变你 vruntime 的累积速度与片的紧迫度,最终效果与份额规则自洽:重任务欠账快、资格恢复快,截止时间也更早到来。这么设计后,「谁先跑」这个问题变成了对一棵树的查询:在所有 eligible 的任务里挑虚拟截止时间最早的。
数据结构没有推倒重来。红黑树仍按 vruntime 排序,但每个节点额外缓存了子树内最小的 deadline(min_deadline),查询时先看最左节点——如果它合格且截止时间足够早,一步命中,这正是大多数调度的实际路径;否则沿缓存的 min_deadline 下钻,找全树里「合格且最早」的节点。挑选逻辑在 pick_eevdf。没有任务合格时(所有任务都超额拿了服务),退化成挑 vruntime 最小者,与 CFS 的直觉一致——欠账最多的人先还。这套设计保持 work-conserving:CPU 永远不会闲着陪公平性较劲。
请求片还有一个容易被误解的语义:它不是「独占保证」。任务持有 CPU 直到请求片耗尽,但期间随时可能被一个「更急」的任务打断——刚睡醒、lag 为正、虚拟截止时间更早的对手可以直接把当前任务按下去。片在这里的作用是控制 deadline 的推移速度与抢占判定的标尺,而不是 CFS 时代那种「最少跑这么久」的承诺。于是延迟变成显式可推理的量:一个任务从就绪到获得 CPU,最坏等待约为「比它急的所有合格任务的片长之和」,这个量随权重与片长变化,可算可测。
唤醒放置:睡眠攒下的 lag 是你的信用
EEVDF 对睡眠任务的处理是它延迟表现好的另一半原因。任务睡着的期间不跑,但按权重计算的本应份额照涨,lag 攒成一笔正账。醒来时内核做唤醒放置(place_entity):按这笔滞留的 lag 把它的 vruntime 摆到合适的位置,让它的资格与紧迫度如实反映「我饿了多久」。于是交互线程睡 100 毫秒醒来,天然带着正 lag 与较早的 deadline,直接获得先跑的机会——这不需要唤醒抢占常数的呵护,是算法本体的推论。批处理任务几乎不睡、lag 长期为零附近徘徊,自然让位于饿的对手。老 CFS 时代「交互任务靠唤醒粒度常数抢跑」的机制整体退场,sched_wakeup_granularity 与 sched_latency 这两个旋钮随之消失,留下来的 base_slice 管的是片的基准长度。
值得点名的是 lag 放置的防作弊设计:内核对放置位置做了边界钳制,防住两类极端——睡一觉就插到所有人前面的「假睡抢跑」,与睡太久 lag 巨大导致醒来一跑十几毫秒不撒手的「巨额补偿」。钳制边界与请求片挂钩,睡再久,醒来欠账的兑现速度也被片长约束住,不会形成延迟尖峰。这个细节决定了 EEVDF 在突发唤醒场景(大量连接同时醒来)下的表现比直觉平稳:信用能兑付,但按期兑付。
nice 的账没变,杠杆变多了
权重的底层映射原样保留:nice 0 对应权重 1024,每升一档 nice 权重乘约 1.25,这张表(sched_prio_to_weight)从 CFS 时代原封不动传给了 EEVDF。变的是这张表能撬动的东西:CFS 时代调 nice 基本只改份额,延迟靠调度器猜测;EEVDF 时代权重同时驱动 lag 恢复速度与 deadline 紧迫度,nice 一改,「分多少」与「多快轮到」一起变。实践里这带来两个可操作结论。其一,对延迟敏感的后台线程,与其留在 nice 0 和主力业务混跑,不如明确降到 nice 10 以上——它的欠账恢复被拉慢,主力业务的唤醒等待显著收窄,比 CFS 时代同样操作的效果更干净。其二,SCHED_BATCH 标志的价值下降:它原本帮调度器识别「无交互」负载,EEVDF 下睡眠行为本身就是信号,几乎不用再靠标签。
层级结构上没有新学的东西但有一处必须自查:cgroup 本身也是调度实体,EEVDF 的资格与 deadline 规则在每一层独立成立。父 cgroup 先按自己的权重在上一级排队,赢了才把 CPU 分给子 cgroup——于是「子组里最急的任务」未必能压过「别的父组里普通的任务」,跨组延迟问题要先看组间那一层的账本。排查时用 cat /proc/<pid>/sched 能直接读到该任务实体的 vruntime、累计运行时间、迁移次数等现值(需要内核开着 SCHED_DEBUG),把同一 cgroup 里几个线程的 vruntime 摆在一起比较,谁超额谁欠账一目了然,这是定位「组内某个线程饿死」最快的入口。
升级 6.x 之后:延迟形态变了怎么查
EEVDF 上线后,一部分负载的延迟分布发生了肉眼可见的变化,工程上值得备好一套排查动作。第一类是「唤醒到起跑」的时间分布整体收窄但毛刺点位移:以前靠唤醒抢占常数插队的线程,现在要靠 lag 与 deadline 竞争,如果它睡眠规律(周期性心跳线程),表现通常更稳;如果它频繁自旋睡醒,抢占可能比以前「客气」,P99 微涨。此时先看 perf sched latency 里各任务的调度延迟统计,再用 perf sched record 抓一段现场,对比唤醒时刻与真正上 CPU 时刻的差值——EEVDF 下这个差值的成因可解释:排队者都是合格的、且各自 deadline 可见。
第二类是容器与多租户场景的权重语义变化。cgroup 的 cpu.weight 落到调度实体权重上,它现在同时影响三件事:份额、lag 恢复速度与 deadline 紧迫度。给延迟敏感业务提高权重,不再只是「分得更多」,还有「更急、插队更快」的复合收益;反过来,低权重后台任务在满载机器上的调度延迟会比 CFS 时代更明显。把 cpu.weight 的调整纳入延迟调优的常规手段,是 6.6 以后的新功课。观测入口固定三件:/proc/schedstat 看每 CPU 的运行与均衡统计、debugfs 的 /sys/kernel/debug/sched/ 看每个实体挂载的 vruntime 与 deadline 现值(内核开启了 CONFIG_SCHED_DEBUG 才有)、perf sched 看端到端延迟。
第三类是带宽控制的联动错觉。6.6 换了调度器,但 cpu.max 配额层的记账与 throttling 原样保留(第 94 篇的结论不变)——不过配额耗尽后的恢复时机变了:以前解冻后全队按 vruntime 重新排队,现在按 deadline 与资格竞争,恢复瞬间的惊群感通常更缓和。如果升级后有人报「毛刺形态变了但 cpu.stat 数字没变」,先去对比 throttling 恢复窗口内的调度延迟明细,再怀疑新调度器,别急着回滚。
一个可运行的极简 EEVDF 模拟器
算法核心小到可以放进一段 python,用它跑三个权重不同的任务,直观看 lag 与 deadline 怎么轮流点名:
import heapq
TICK = 1.0 # 每个 tick 的真实时间
BASE = 3.0 # nice 0 的请求片(示意值)
def simulate(tasks, total=40):
# tasks: [(name, weight)],lag 全部从 0 开始
lag = {n: 0.0 for n, _ in tasks}
W = sum(w for _, w in tasks)
clock = 0.0
timeline = []
for _ in range(int(total / TICK)):
# eligible:lag > 0;deadline = -lag 换算的虚拟位置 + 片/权重(示意实现)
ready = [(n, w) for n, w in tasks if lag[n] > -1e-9]
if not ready:
ready = tasks[:]
pick = min(ready, key=lambda t: lag[t[0]] / t[1] - BASE / t[1])
name, w = pick
slice_used = min(BASE, TICK) # 实际跑一个 tick
fair = TICK * w / W # 本 tick 本应份额
lag[name] += fair - slice_used
for n, wt in tasks:
if n != name:
lag[n] += TICK * wt / W # 等待者欠账上涨
timeline.append(name)
return timeline
run = simulate([("交互", 2.0), ("后台", 1.0), ("重负载", 3.0)])
print("".join(x[0] for x in run))
跑一次能看到输出里「交互」「重负载」「后台」的出现频率大约是 2:3:1——这就是份额公平;而「交互」在两次出现之间几乎不会被「后台」隔太远,因为它的欠账涨得快、deadline 来得早——这就是延迟公平。把某项任务的睡眠周期模拟进去(跳过若干 tick 再回来),你会看到它回来后立刻连续被选中若干拍,把攒下的 lag 花掉为止,正是唤醒放置的行为写照。内核里的真实实现多了 cgroup 层级、Placement 钳制与带宽记账,但点名规则与本例同构。
收束
EEVDF 把调度承诺从「长期公平」升级成「欠账可查、急事可插」:lag 大于零才有资格跑,虚拟截止时间最早者先跑,请求片与权重决定份额与紧迫度。三句话带走:延迟不再是经验常数的产物,而是每个任务声明的请求片与 lag 状态的可推理结果;唤醒放置让睡眠攒下的 lag 变成兑现的信用,交互负载因此受益;升级 6.x 后做延迟调优,把 cpu.weight 当作同时影响份额与插队速度的旋钮,用 perf sched 与 debugfs 的 deadline 现值定位排队成因。CFS 十四年的江山在 6.6 交棒,分蛋糕的数学没有变,变的是叫号的方式。
读者留言
COMMENTS 暂无还没有留言,来说第一句?