2001年，Linus Torvalds在Linux内核邮件列表中写下了这样一句话：“你要意识到，很少有东西能像调度器那样经受住时间的考验。这恰好证明了调度是简单的。”
五年后，O(1)调度器被废弃。十六年后，统治了Linux世界的CFS也被EEVDF取代。
调度从来都不是一个"已解决"的问题。
从20行代码到O(n)的困境
Linux v0.01的调度器只有20行代码。它维护一个固定大小的任务数组（最多64个进程），采用简单的轮转方式：遍历数组，找到时间片最大的可运行进程，执行它。时间片耗尽后，重新计算所有进程的时间片。
这种设计的复杂度是O(n)——每次调度决策都需要遍历整个任务列表。在单核、进程数有限的早期Linux时代，这完全够用。但当Linux开始进入服务器领域，进程数从几十增长到成百上千时，O(n)的问题暴露无遗。
更糟糕的是，这个调度器对"交互式"进程的处理几乎不存在。一个编译任务可以轻易地让终端响应变得迟钝，因为调度器根本不知道哪些进程需要快速响应，哪些可以慢慢执行。
O(1)的承诺与代价
2002年1月4日，Ingo Molnar向Linux内核邮件列表提交了一个名为"ultra-scalable O(1) SMP and UP scheduler"的补丁。它的核心设计目标很明确：无论系统中有多少进程，调度决策的时间必须是常数。
O(1)调度器通过两个关键数据结构实现了这一目标：运行队列（runqueue）和优先级数组（priority array）。每个CPU维护自己的运行队列，队列中包含两个优先级数组——活跃数组和过期数组。每个数组有140个优先级槽位，对应140个不同的优先级级别。
调度时，O(1)调度器只需找到活跃数组中最高优先级的非空槽位，然后从该槽位的链表中取出第一个进程。这确实是O(1)——不依赖进程数量。
但O(1)调度器有一个致命的软肋：交互性检测。
为了给交互式进程（如终端、GUI应用）更好的响应，O(1)调度器需要识别哪些进程是"交互式"的。它采用了一种启发式方法：分析进程的平均睡眠时间。睡眠时间长的进程被认为在等待用户输入，因此被判定为交互式进程，获得优先级奖励。
这套启发式规则极其复杂，且容易出错。一个进行大量磁盘I/O的进程也会频繁睡眠，但它并非交互式进程。更糟糕的是，一个恶意进程可以通过精心设计的I/O模式"欺骗"调度器，获得比公平份额更多的CPU时间。
Con Kolivas，一位澳大利亚的麻醉医生兼内核开发者，在2007年指出了O(1)调度器的根本问题：它的启发式规则是一场"无法获胜的游戏"。他提出了一个名为"Rotating Staircase Deadline"的调度器，用一种完全不同的方式处理交互性——不是猜测进程的行为，而是让进程自己展示它的需求。
虽然Kolivas的调度器没有被主线内核采用，但他的思想影响了后来的CFS设计。
CFS：放弃O(1)，换取数学上的公平
2007年10月，Linux 2.6.23发布，O(1)调度器被完全公平调度器（Completely Fair Scheduler，CFS）取代。CFS的核心设计可以用一句话概括：CFS试图在真实硬件上模拟一个"理想的多任务CPU"。
什么是理想的多任务CPU？假设有两个进程运行在一个理想CPU上，该CPU会以50%的速度并行执行每个进程。在真实硬件上，我们一次只能运行一个进程，但我们可以通过频繁切换来逼近这种理想状态。
CFS引入了一个关键概念：虚拟运行时间（vruntime）。每个进程都有vruntime，记录它获得了多少"加权"CPU时间。权重由进程的nice值决定：nice值越低（优先级越高），权重越大，vruntime增长越慢。这意味着高优先级进程在相同实际运行时间下积累更少的vruntime，从而获得更多CPU时间。
CFS的核心调度逻辑简单得出奇：总是选择vruntime最小的进程运行。
为了高效找到vruntime最小的进程，CFS使用了红黑树。所有可运行进程按vruntime排序存储在红黑树中，最左边的节点就是vruntime最小的进程。红黑树的自平衡特性保证了查找、插入、删除操作都是O(log n)——比O(1)慢，但换来的是数学上可证明的公平性。
为什么是红黑树而不是堆或AVL树？红黑树提供了最坏情况下的O(log n)保证，且在插入和删除时需要的旋转操作比AVL树少。对于调度器这种热点路径，减少写操作的开销至关重要。此外，红黑树的有序性使得按vruntime遍历所有进程变得高效——这对于调试和统计非常有用。
CFS没有传统意义上的"时间片"概念。进程运行时，它的vruntime不断增加。当vruntime增长到不再是树中最小时，调度器会切换到下一个进程。这种设计被称为"无时间片调度"——进程运行的时间取决于它应该获得的公平份额和当前系统负载，而不是一个固定的量子。
公平的代价：延迟与吞吐量的永恒矛盾
CFS解决了O(1)调度器的交互性检测问题，但它引入了新的困境。
公平不等于响应快。假设系统中有10个进程，每个进程应该获得10%的CPU时间。如果这10个进程都是CPU密集型的，CFS会轮流执行它们，每个进程运行一小段时间后切换。公平吗？是的。但对于需要低延迟的交互式进程来说，这可能意味着响应变慢。
CFS通过几个参数来调节这种权衡：
- sched_latency_ns（默认6ms）：调度周期，理想情况下每个可运行进程在这个周期内至少运行一次。
- sched_min_granularity_ns（默认0.75ms）：最小调度粒度，防止进程数量过多时时间片过小导致频繁切换。
- sched_wakeup_granularity_ns（默认1ms）：唤醒抢占粒度，决定一个新唤醒的进程是否应该抢占当前进程。
这些参数构成了CFS的调优空间，但也意味着没有"万能"的配置。桌面系统需要更低的延迟，服务器系统需要更高的吞吐量。CFS默认偏向桌面，但服务器管理员可以通过调整这些参数来改变行为。
2016年，一篇发表在EuroSys的论文《The Linux Scheduler: a Decade of Wasted Cores》揭示了CFS在多核系统上的严重问题。研究者发现，在某些工作负载下，Linux调度器会让CPU核心空闲数秒，而其他核心上却有大量进程在排队等待。这些性能缺陷导致同步密集型科学应用的性能下降数倍，数据库TPC-H吞吐量下降14-23%。
问题的根源在于多核环境下的负载均衡逻辑。为了减少锁竞争，CFS为每个CPU核心维护独立的运行队列。但这带来了新的问题：如何保持队列之间的平衡？负载均衡算法变得极其复杂，引入了调度域、调度组等概念。复杂性导致了缺陷。
论文作者总结道：“调度器曾是一个小而紧凑、基本与内核其他部分隔离的模块。现在它已经长成了一个复杂的怪物，触手伸向了系统的其他部分，如电源管理和内存管理。”
EEVDF：用虚拟截止时间解决延迟困境
2023年3月，Peter Zijlstra向Linux内核提交了EEVDF（Earliest Eligible Virtual Deadline First）调度器的补丁。2023年10月，Linux 6.6发布，EEVDF正式取代CFS，成为新的默认调度器。
EEVDF并非新发明。它由Ion Stoica和Hussein Abdel-Wahab在1995年的论文中提出，比CFS早了12年。但直到Linux面临越来越复杂的延迟需求，这个算法才被重新发现。
EEVDF的核心创新是引入了两个概念：滞后量（lag）和虚拟截止时间（virtual deadline）。
滞后量衡量一个进程"欠"了多少CPU时间。如果进程A应该获得20%的CPU但实际只获得了15%，它的滞后量为正，意味着它"被欠"了CPU时间。如果进程B获得了25%，它的滞后量为负，意味着它"透支"了。
只有滞后量非负的进程才被认为是"合格的"（eligible），可以被调度。这防止了一个进程通过长时间睡眠后突然醒来抢占大量CPU时间。
虚拟截止时间的计算方式是：虚拟截止时间 = 合格时间 + 时间片。时间片可以根据进程的延迟需求调整——需要低延迟的进程获得更短的时间片，从而拥有更近的虚拟截止时间，被优先调度。
这种设计的妙处在于：延迟需求和时间份额分离了。在CFS中，要让一个进程获得更快的响应，只能提高它的优先级，这同时也会给它更多CPU时间。而在EEVDF中，一个进程可以请求更短的调度延迟，而不需要更多CPU份额。
对于现代工作负载——尤其是音视频处理、游戏、实时通信等——这种分离至关重要。这些应用需要低延迟，但不需要大量CPU时间。EEVDF让它们可以"插队"到队列前面，快速执行一小段时间后让出CPU，而不会"偷走"其他进程的公平份额。
Zijlstra在提交补丁时写道：“EEVDF是一个定义更清晰的调度策略，因此它需要更少的启发式规则和可调参数。没有令人信服的理由保留CFS。”
调度的本质：权衡的艺术
回顾Linux调度器三十年的演进，我们可以看到一条清晰的主线：没有完美的调度算法，只有在特定场景下更合适的权衡。
O(1)调度器追求极致的调度效率，但在交互性检测上栽了跟头。它的启发式规则复杂、脆弱、容易被欺骗。当进程行为变得越来越不可预测时，猜测进程的意图变成了一个无解的问题。
CFS放弃了O(1)的时间复杂度，用O(log n)换取了数学上的公平性。它不再猜测进程的类型，而是让每个进程的vruntime说话。但公平不等于响应快，多核环境下的负载均衡问题让CFS变得复杂且容易出问题。
EEVDF回到1995年的学术论文，用虚拟截止时间将延迟需求和CPU份额分离。它简化了调度逻辑，减少了启发式规则，但仍然需要处理滞后量衰减、时间片选择等复杂问题。
更根本的是，调度器面临的是一个多维优化问题：公平性、吞吐量、延迟、能耗、缓存亲和性、NUMA局部性……这些目标往往相互冲突。提高缓存亲和性可能牺牲负载均衡；降低延迟可能增加上下文切换开销；节约能耗可能让CPU核心闲置。
2016年EuroSys论文的作者在结论中写道：“我们需要重新思考调度器的架构，因为它不能再是一个小而紧凑、基本与内核其他部分隔离的模块了。我们设想调度器是一个模块集合：核心模块和优化模块。核心模块实现最基本的调度功能，优化模块建议特定的增强。核心模块应该能够接收优化模块的建议并在可行时采纳，同时始终保持基本不变量——不让核心闲置而可运行线程在等待。”
这个愿景至今仍未完全实现。调度器仍然是内核中最复杂的子系统之一，充满了特殊情况和启发式规则。但EEVDF的引入是一个信号：Linux社区正在尝试简化，用更清晰的数学模型替代复杂的猜测。
尾声
Linus Torvalds在2001年说"调度是简单的"时，他可能没有预料到多核时代带来的复杂性。但有一点他是对的：调度的核心逻辑确实简单——选择下一个要运行的进程。
问题在于，“选择"这个动作背后隐藏了无数权衡。公平与效率，延迟与吞吐，简单与完整。每一次调度决策都是这些力量的交汇点。
从O(1)到CFS再到EEVDF，Linux调度器的演进不是技术的简单替代，而是对"公平"这一概念的不断重新理解。O(1)试图用启发式规则实现"感知上的公平”，CFS用vruntime实现了"数学上的公平"，EEVDF通过虚拟截止时间实现了"延迟可调的公平"。
每一个版本都更接近某种理想，但每一个版本也都暴露了新的问题。这不是失败，这是系统设计的本质——在约束条件下寻找最优解，而约束条件本身在不断变化。
调度从未被"解决"。它只是在不断演进。
参考资料
- Molnar, I. (2002). [announce] [patch] ultra-scalable O(1) SMP and UP scheduler. Linux Kernel Mailing List.
- Lozi, J.P., et al. (2016). The Linux Scheduler: a Decade of Wasted Cores. EuroSys ‘16.
- Stoica, I., & Abdel-Wahab, H. (1995). Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation. Technical Report.
- Linux Kernel Documentation. CFS Scheduler. https://docs.kernel.org/scheduler/sched-design-CFS.html
- Zijlstra, P. (2023). An EEVDF CPU scheduler for Linux. LWN.net.
- Corbató, F.J., et al. (1962). An Experimental Time-Sharing System. IFIPS.
- Arpaci-Dusseau, R.H., & Arpaci-Dusseau, A.C. (2018). Operating Systems: Three Easy Pieces. Chapter: Scheduling: The Multi-Level Feedback Queue.