EEVDF取代CFS？Linux内核调度器这30年到底在卷什么

EEVDF取代CFSLinux内核调度器这30年到底在卷什么2024年Linux 6.6合入EEVDF调度器时Linus Torvalds在MAILING LIST上说了句“I’m not entirely happy, but let’s merge it.” 这么一个内核调度器的换代事件外面没几个人注意到。今天我把它扒干净。一、从O(n)到O(1)到CFS到EEVDF——一条timeline不想讲无聊的历史课但4个关键节点能帮你理解为什么又要换1992: Linux 0.01 —— round-robin每个进程轮流跑一个tick2002: Linux 2.4 —— O(n)调度器每次调度遍历所有进程找优先级最高的2003: Linux 2.6 —— O(1)调度器用bitmap优先级数组O(1)复杂度2007: Linux 2.6.23 —— CFS (Completely Fair Scheduler)红黑树vruntime统治了17年2024: Linux 6.6 —— EEVDF (Earliest Eligible Virtual Deadline First)一个新的开始CFS统治了17年够猛了吧但为什么还是被换了因为硬件变了负载变了CFS的公平定义满足不了需求了。二、CFS干了什么为什么管了17年CFS的核心就一句话每个进程应该得到CPU时间的N分之一其中N是竞争进程数。实现手段追踪每个进程的vruntime虚拟运行时间。当一个进程被调度走时它的vruntime增加下一次调度时选vruntime最小的那个。所以CFS的调度就是while(1){nextrb_tree.min()// 从红黑树取最左侧节点vruntime最小context_switch(current,next)current.vruntimedelta_exec*nice_weight rb_tree.update(current)// 重新插入红黑树}这看起来完美对吧问题是CFS是work-conserving的——它只保证所有进程分到公平的时间不保证单个进程的延迟。三、CFS的死穴延迟敏感型进程被打爆了考虑一个场景进程A交互式计算编辑器、游戏、UI线程 进程BCPU密集型编译gcc -j8CFS下当进程B长时间运行它的vruntime增长很快。如果进程A突然被唤醒用户敲了个键A的vruntime远小于B所以CFS立刻抢断B让A跑。这看起来没问题但在高负载下会翻车。A被唤醒 → 插入红黑树最左边B被抢断 → B的vruntime还没赶上AA跑了一个tick → A的vruntime增加了但还有C、D、E、F……都在等CPU结果A再次被调度时发现它的vruntime又不是最小的了A的响应延迟完全取决于竞争进程的重量更致命的是CFS没有明确的延迟边界。它只能保证越等越有机会被调度但不保证最多等多久。四、EEVDF的基本原理EEVDFEarliest Eligible Virtual Deadline First来自1995年的一篇论文Stoica et al.)但因为实现复杂一直没进内核。直到2022-2023年Peter Zijlstra内核调度维护者重写了一遍。它的核心思想每个进程有一个eligible time最早可调度时间和一个virtual deadline虚拟截止时间。调度器永远选eligible且deadline最早的进程。进程P的调度参数 weight: 优先级权重同CFS的nice值 lag: 当前落后于公平份额的程度 slice: 时间片长度由weight和系统负载决定 Eligible time: 如果P的lag 0落后了立即eligible 如果P的lag 0超前了等到lag0才eligible Virtual deadline: eligible_time sliceYes, 落后了No, 超前了进程就绪队列计算每个进程eligible timelag 0?eligible noweligible now abs(lag)virtual deadline eligible slice选择 deadline 最早的eligible 进程运行该进程进程时间到/被抢占更新 lag 和 slice这里最关键的概念是lag:lag 进程实际获得的CPU时间 - 应该获得的公平时间 lag 0: 这个进程占便宜了跑得比应得的多了 lag 0: 这个进程吃亏了跑得比应得的少了Eligibility规则是占便宜的等一会儿再跑吃亏的立刻就能跑。这就自然实现了补偿性调度——而且比CFS的vruntime更精确因为lag是和全局公平线对比的不是和其他进程对比。五、EEVDF vs CFS关键区别维度CFSEEVDF调度依据vruntime最小eligible且deadline最早公平定义所有进程vruntime趋于相等每个进程lag≈0延迟保证无明确边界有明确的deadline抢占粒度取决于负载不可预测slice固定可预测唤醒延迟取决于红黑树深度取决于队列中eligible进程数大量短进程场景红黑树频繁插入删除开销大可以用特殊优化实现复杂度相对简单更复杂lag追踪、deadline管理六、lag的加减博弈——EEVDF最难实现的地方lag的实现比看上去复杂一万倍。为什么因为进程在动态变化新进程fork出来、进程退出、nice值变化、cgroup权重调整……每一次变化所有进程的lag都要重新计算相对于新的公平线。Peter Zijlstra在patch里有一段代码我看了一下午才看懂// kernel/sched/fair.c 中的 place_entity 函数简化理解版staticvoidplace_entity(structcfs_rq*cfs_rq,structsched_entity*se,intflags){u64 vslicecalc_vslice(se);// 基于weight计算虚拟时间片u64 vlag0;if(flagsENQUEUE_WAKEUP){// 被唤醒的进程保留之前的lag但不能太大vlagdiv_s64(se-vlag,se-load.weight);se-vlagmin_vlag(vlag,se-load.weight);}// EEVDF的核心放置entityse-deadlinese-vruntimevslice;if(se-vlag0){// 落后了→立刻eligiblese-eligible_timese-vruntime;}else{// 超前了→等lag消掉才eligiblese-eligible_timese-vruntimese-vlag;}}这看着也还好问题是这个vlag在以下场景都会变进程状态变化睡眠→唤醒、fork、exit优先级变化reniceCPU频率变化涉及scalingcgroup权重调整SMT/超线程协同调度每一次变化都要重新计算所有受影响进程的lag还要保证lag总量守恒所有进程lag之和为0。如果加起来不是0系统就会逐渐失去公平性。七、EEVDF配上的新基础设施0-lag 迁移EEVDF还带来了一个我特别喜欢的设计0-lag迁移。在多核系统中进程在不同CPU之间迁移时CFS的做法是把vruntime拉到目标CPU的公平线附近。这会导致进程的历史欠账丢失。EEVDF的做法是迁移时确保lag0。如果一个进程在CPU0上欠了1mslag-1ms迁移到CPU1时目标CPU上的调度器会认这笔账。CPU 1CPU 0CFS 迁移EEVDF 迁移进程Plag -1ms落后1ms进程Plag after migrateCFS: lag≈0历史丢失进程Plag after migrateEEVDF: lag-1ms历史保留这对延迟敏感型负载比如数据库事务、网络服务是大福音——进程的历史惩罚/补偿不会因为迁移而丢失。八、实际表现怎么样Phoronix做过EEVDF vs CFS的基准测试我挑几个有意思的结果数据库负载PgBenchCFS: 9500 TPS延迟P9942msEEVDF: 10200 TPS延迟P9928ms延迟降低33%吞吐提升7%编译负载Linux kernel defconfig, -j32CFS: 完成时间 128sEEVDF: 完成时间 131s退化约2%——因为EEVDF为了保证短进程的延迟牺牲了一点吞吐混合负载编译 交互进程CFS: 交互进程平均响应 45msP99210msEEVDF: 交互进程平均响应 12msP9938ms响应延迟提升3-5倍这个tradeoff是很明显的EEVDF牺牲了纯吞吐场景的2-3%换来了延迟敏感场景3-5倍的改善。在云原生、实时容器、游戏服务器场景下这个交换太值了。九、EEVDF没解决的问题写东西要客观EEVDF也不是银弹cgroup交互复杂度——EEVDF cgroup v2 CPUSET的组合下lag计算会变得极其复杂已经有多个kernel bug上报功耗管理干扰——intel_pstate频率缩放和EEVDF的deadline计算有微妙交互某些场景下deadline会误判内核开销略增——每次调度多算一次deadline和eligibility检查在百万级线程的极端场景下调度延迟多出约5-8%实时的硬实时仍然不够——EEVDF提供的是软实时保证不是硬实时。真正的硬实时还是得靠PREEMPT_RT SCHED_DEADLINE十、总结如果你只是在服务器上跑批处理任务模型训练、批处理SQL、离线分析EEVDF对你几乎没影响。但如果你是做数据库/缓存中间件Redis、MySQL、MongoDB游戏服务器Web服务/API网关实时音视频处理云端容器编排边缘计算那EEVDF带来的延迟改进会让你爽到。你的进程不会再被公平地塞到队列末尾而是在lag负了之后立刻获得补偿。我第一次读到EEVDF patch的时候心里想的是“CFS那个vruntime最小就调度原来不是一个唯一解啊……”转头想想17年的调度器被换掉内核社区不是闲得慌是真的需要变。“CFS是个好调度器但它不是个好实时调度器。”——这就是EEVDF存在的全部理由。内核调度器不止有CFS/EEVDF还有RT实时、DEADLINE硬deadline、IDLE空闲这几个调度类。EEVDF替换的是CFS这个SCHED_NORMAL / SCHED_OTHER的位置。更硬核的实时场景还有另外两个调度类撑着呢。看了下/sys/kernel/debug/sched_features确认一下EEVDF在你系统上跑没跑cat/sys/kernel/debug/sched_features# 如果输出里有 EEVRUN 那就是 EEVDF 再跑# 如果在 6.6 内核上默认就是 EEVDF下次你的服务器负载高了但响应还很快说不定就是EEVDF在默默干活。