CFS, Completely Fair Scheduler 完全公平调度器
CFS（Completely Fair Scheduler，完全公平调度器）是 Linux 普通进程（SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE）曾经使用的调度算法，自 2007 年发布的 Linux 2.6.23 版本起取代了此前的 O(1) 调度器，用红黑树替代了原来的按优先级分桶的数组结构（调度器体系的整体介绍见 Linux 进程调度）。 需要先说明的是：CFS 已经不是当前内核的默认实现。从 2023 年 10 月发布的 Linux 6.6 起，普通进程的默认调度算法换成了 EEVDF，CFS 退居历史。本文仍以 CFS 为主，因为它的 vruntime 和红黑树是理解现在这套调度器的基础。 EEVDF：6.6 之后的默认调度器 EEVDF（Earliest Eligible Virtual Deadline First，最早合格虚拟截止时间优先）由 Peter Zijlstra 实现并在 Linux 6.6 合入，取代 CFS 成为 SCHED_NORMAL 等普通调度策略的默认算法。算法本身并不新，出自 Ion Stoica 和 Hussein Abdel-Wahab 1995 年的一篇论文。 它要解决的是 CFS 的一个短板：CFS 只保证长期的 CPU 时间份额公平，但对"什么时候该轮到我"没有约束，交互式任务的调度延迟不好控制。CFS 时期只能靠 sched_latency_ns 之类的旋钮和一些启发式补偿去调，效果有限。 EEVDF 引入两个概念： lag：进程"应得的 CPU 时间"与"实际获得的 CPU 时间"之差。lag 大于等于 0 说明它还欠着账，才有资格（eligible）被调度；lag 为负说明它已经超额使用，暂时靠边。 virtual deadline：在合格的进程中，按各自请求的时间片长度算出一个虚拟截止时间，调度器每次挑选虚拟截止时间最早的那个。 这样一来，份额公平由 lag 保证，响应延迟由 deadline 保证，需要低延迟的任务可以通过请求更短的时间片来更频繁地被调度，而不必牺牲它的总 CPU 份额。 ...