Linux调度器演进：从O(1)到CFS再到EEVDF

Linux 进程调度演化史从 O(n) 到 CFS 再到 EEVDF30 年调度器的三次跃迁进程调度是操作系统的脉搏。这篇文章不堆概念带你从 Linux 0.01 走到内核 6.6看懂调度器为什么这样设计以及每次重构到底解决了什么问题。一、为什么调度器是 OS 的核心CPU 是整台计算机最宝贵的资源。一个操作系统可以没有图形界面、没有网络栈但不能没有进程调度——因为 CPU 只有一个或几个核而想用它的程序可能有几百个。调度器的终极命题在有限的 CPU 时间内让所有进程都觉得「公平」同时最大化系统吞吐量。这个命题里有两个天然矛盾公平 vs 吞吐量让每个进程平均分配 CPU公平意味着频繁切换进程上下文切换开销大降低吞吐量。延迟 vs 吞吐量交互进程比如你打字需要快速响应但计算密集型进程比如视频渲染需要长时间占用 CPU。一个好的调度器就是在这些矛盾之间找到平衡点。二、第一代Linux 0.01 的原始调度器1991Linus Torvalds 在 1991 年写的第一版 Linux 内核里调度器的核心逻辑非常简单// 简化版伪代码——遍历所有进程找 counter 最大的那个voidschedule(void){intc-1;structtask_struct*p,*next;for_each_task(p){if(p-stateTASK_RUNNINGp-counterc){cp-counter;nextp;}}if(!c){// 所有进程 counter 都用完了重新分配for_each_task(p)p-counter(p-counter1)p-priority;}switch_to(next);}这段代码只有几十行逻辑是每个进程有一个counter初始值等于优先级priority。调度时遍历所有进程找到counter最大的来执行。时钟中断每发生一次当前进程的counter减 1。当所有进程的counter都降到 0系统重新计算counter counter/2 priority。这个设计的巧妙之处你注意那个counter 1除以 2——它会「记住」之前用过 CPU 的进程。一个刚刚用光 counter 的进程下一轮从priority开始但一个之前没用过 CPU 的进程counter 保持初始值下一轮会得到counter priority远大于别人。这就是最简单的交互性优化I/O 密集型进程经常因为等 I/O 而主动让出 CPUcounter 没怎么消耗会在下一轮获得更多 CPU 时间。缺点时间复杂度 O(n)。2000 年左右的服务器可能有上百个进程每次调度都要遍历一遍。三、第二代O(1) 调度器2003Linux 2.6Ingo Molnar 在 2003 年提交了 O(1) 调度器核心思想是用两个位图 优先级数组替代遍历Active 数组正在运行 Expired 数组时间片用完 ┌─────────────────────┐ ┌─────────────────────┐ │ prio 0: [进程A, B] │ │ prio 0: [进程E] │ │ prio 1: [进程C] │ │ prio 1: [] │ │ prio 2: [] │ │ prio 2: [进程F, G] │ │ ... │ │ ... │ │ prio 139: [] │ │ prio 139: [] │ └─────────────────────┘ └─────────────────────┘ ↑ ↑ 当前从这取 Active 空了就交换140 个优先级0-99 实时100-139 普通进程每个优先级一个链表。用一个 140-bit 的位图bit[i]1 表示优先级 i 有可运行的进程。找最高优先级 找位图里第一个为 1 的位 → 一条 CPU 指令bsfl搞定。时间复杂度从 O(n) 变成了 O(1)在当时是个质的飞跃。但它的问题也逐渐暴露启发式规则太多为了判断一个进程是「交互式」还是「计算密集型」代码里塞了大量启发式判断平均睡眠时间、交互性评分……越来越难维护。公平性不够精细时间片的粒度太粗对桌面互动场景不够友好。维护困难到了 O(1) 调度器生命周期末期调度相关的代码已经膨胀到数千行布满 case-by-case 的特殊处理。四、第三代CFS 完全公平调度器2007Linux 2.6.234.1 CFS 的核心思想Ingo Molnar 再次出手彻底推翻了 O(1) 的设计引入了一个全新的范式。CFS 的核心理念可以用一句话概括——来自官方内核文档CFS 在一台真实的硬件上模拟一台「理想的、精确的多任务 CPU」。什么是「理想的多任务 CPU」假设有一台 CPU它有 100% 的算力同时跑 N 个进程每个进程精确地各得 1/N 的算力。如果有 2 个进程每个得 50%3 个进程每个得 33.3%——绝对公平。真实硬件不行——一次只能跑一个进程。所以 CFS 引入了**虚拟运行时间vruntime**的概念vruntime 实际运行时间 × (1024 / 进程权重)权重高的进程nice 值低vruntime 增长慢——能多跑。权重低的进程nice 值高vruntime 增长快——少跑。CFS 始终选择vruntime 最小的进程来执行。4.2 红黑树——O(log n) 的任务选择CFS 不用数组用红黑树rbtree按 vruntime 排序task D (vruntime50ms) / \ task B (30ms) task F (80ms) / \ \ task A (10ms) task C (40ms) task G (100ms)CFS 永远选树的最左节点vruntime 最小的进程。红黑树保证最左节点可以在 O(log n) 内找到。4.3 CFS 的几个关键参数参数含义默认值sched_min_granularity_ns一个进程最少连续运行多久才被抢占0.75mssched_latency_ns一个调度周期内所有可运行进程至少被调度一次6msnr_running 8时sched_wakeup_granularity_ns唤醒进程的 vruntime 比当前进程小多少才能抢占1ms这些参数的设计非常克制——CFS 的目标不是「切换越快越好」而是在公平的前提下尽量减少上下文切换因为 cache 会失效。4.4 CFS 的成就与局限CFS 从 2007 年运行到 2024 年活了 17 年是 Linux 历史上寿命最长的通用调度器。它足够好——公平、简洁、性能稳定。但它有一个结构性问题无法区分「需要更多 CPU 时间」和「需要更快响应」。nice 值只能调整 CPU 时间的分配比例不能表达「我运行时间不长但我需要马上响应」。2018 年开始社区尝试了latency-nice补丁来解决这个问题但直到 2023 年Peter Zijlstra 提出了一个更根本的方案。五、第四代EEVDF 调度器2024Linux 6.65.1 EEVDF 是什么EEVDF 的全称是Earliest Eligible Virtual Deadline First最早合格虚拟截止时间优先由 Ion Stoica 和 Hussein Abdel-Wahab 在 1995 年的论文中提出。Peter Zijlstra 在 2023 年提交了 Linux 版的 EEVDF 补丁[2]并在 Linux 6.62024 年中合并。5.2 它的工作原理EEVDF 给每个进程引入了三个新概念概念含义虚拟运行时间vruntime和 CFS 一样进程已获得的 CPU 时间滞后值lag进程实际获得的 CPU 时间 - 应该获得的 CPU 时间虚拟截止时间virtual deadline, VD进程下次必须被调度的时间点调度逻辑只考虑lag 0的进程即它还没有超过应得的 CPU 时间份额在这些「合格」进程中选择VD 最早的那个关键创新EEVDF 允许延迟敏感型进程设置更短的时间片time slice从而获得更早的 VD被更快调度——而不会占用超过它应得的 CPU 份额。这就是「响应快但不占便宜」。5.3 EEVDF 为什么比 CFS 好维度CFSEEVDF公平性好更好显式跟踪 lag延迟控制依赖启发式wakeup preemption精确VD 机制启发式规则不少大幅减少延迟敏感型任务需要猜测明确支持短 time slice → 早 VD睡眠进程处理vruntime 最小值修正lag 衰减机制——防止睡眠作弊一个具体场景音频处理应用需要每 5ms 获得一次 CPU。EEVDF 可以给它一个 5ms 的 request time slice保证它在 VD 之前被调度——不需要任何猜测或启发式规则。5.4 lag 的衰减机制防止「睡眠作弊」这是个很精妙的设计。假设一个进程跑了很多 CPU 时间后lag 变成负数它主动睡眠一小段时间。如果没有衰减机制它醒来后还是负数 lag就能继续抢占别人——相当于「偷了 CPU 时间后睡一觉就洗白了」。EEVDF 的做法睡眠期间 lag 不会立即清零而是按照虚拟运行时间VRT衰减。只有睡了足够长的时间lag 才会归零。这就是「deferred dequeue」机制——进程休眠时仍保留在运行队列中标记为待出队。六、调度器演化全景图1991 ─── Linux 0.01 原始调度器 (O(n)) │ 问题进程多时太慢 ▼ 2003 ─── O(1) 调度器 │ 问题启发式太多公平性不够细 ▼ 2007 ─── CFS 完全公平调度器 │ 问题不能区分「多要时间」和「快响应」 ▼ 2024 ─── EEVDF 调度器 │ 当前最新每次换代解决的核心问题O(n) → O(1)解决了性能时间复杂度O(1) → CFS解决了公平性和维护性CFS → EEVDF解决了延迟精度和启发式泛滥七、动手验证看看你的系统在用哪个# 查看内核版本6.6 才有 EEVDFuname-r# 查看 CPU 调度器当前策略cat/sys/kernel/debug/sched/features|head-20# 查看某个进程的调度策略chrt-p$(pgrep-fyour-app)# 输出示例pid xxxs current scheduling policy: SCHED_OTHER如果你在内核 6.6 的系统上EEVDF 已经是SCHED_OTHER普通进程的默认调度策略。你也可以通过内核引导参数sched_policyeevdf|cfs在两个调度器之间切换取决于你的内核编译配置。八、总结Linux 调度器的 30 年演化本质上是三条设计原则在互相博弈公平——每个进程都应得到它应得的 CPU 时间效率——不能为了公平把 CPU 浪费在调度本身响应——交互式任务不能因为公平而卡顿原始调度器的巧妙counter 衰减、O(1) 的工程智慧位图优先级数组、CFS 的理论优雅理想多任务 CPU 的模拟、EEVDF 的精确建模lag VD——每一代都在三条原则之间找到了一个新的平衡点。理解了这个演化脉络你就理解了操作系统调度器设计语言的完整语法。参考来源Linux Kernel Documentation: CFS SchedulerLinux Kernel Documentation: EEVDF SchedulerLWN.net: An EEVDF CPU scheduler for LinuxIon Stoica, Hussein Abdel-Wahab (1995): “Earliest Eligible Virtual Deadline First”