进程调度：从 CFS 到 EEVDF 的哲学演变

2007 年，Ingo Molnar 在一封看似普通的 LKML 邮件中提交了一个补丁：用一个叫 CFS（Completely Fair Scheduler）的新调度器替换 Linux 的 O(1) 调度器。这个改动的核心思想来自 Con Kolivas——一个澳大利亚的麻醉医师、业余内核开发者。他提出的 Rotating Staircase Deadline Scheduler 虽然没有被合并，但它的”公平调度”理念彻底改变了 Linux。

16 年后的 2023 年，Linux 6.6 又一次更换了默认调度器。这次叫 EEVDF（Earliest Eligible Virtual Deadline First），由 Peter Zijlstra 实现。原因？CFS 承诺的”完全公平”有一个隐藏的缺陷——它只保证长期公平，不保证短期公平。一个刚唤醒的任务可能需要等很久才能获得 CPU，即使它的”应得份额”已经积累了很多。

本文从调度器的根本矛盾讲起，逐一解剖 O(1)、CFS、EEVDF 三代调度器的内部机制，用数学公式和内核源码揭示每次演变背后的设计权衡。

一、调度器的使命：CPU 是不可存储的资源

CPU 时间和磁盘空间有本质区别——磁盘空间可以存储，CPU 时间不行。你没用掉的这 1ms，它就永远消失了。这意味着调度器面对的是一个流式分配问题：它必须在每个时刻立即做出决策，不能”攒着”以后分配。

这个约束使得 CPU 调度本质上是一个在线算法问题。调度器在做决策时不知道未来会发生什么：哪个进程会被唤醒、哪个进程会阻塞、用户会不会敲键盘。它只能基于当前信息做出最不坏的选择。

操作系统调度器试图同时满足三个相互矛盾的目标：

公平性（Fairness）：每个进程按其权重获得相应比例的 CPU 时间。不能因为进程”碰巧”晚到就被饿死。公平性的极端形式是理想处理器（Generalized Processor Sharing，GPS）——一个假想的 CPU 同时以无穷小的时间片轮转所有进程，使得每个进程在任意时间窗口内都精确获得其权重比例的 CPU。现实中不存在无穷小的时间片，所以所有调度器都是 GPS 的近似。

响应性（Responsiveness）：用户敲键盘、点鼠标后，系统应该在毫秒级响应。这意味着 I/O 密集型（交互式）进程应该被优先调度，即使 CPU 密集型进程”更需要” CPU。

吞吐量（Throughput）：上下文切换有开销（保存/恢复寄存器、TLB 刷新、缓存污染）。切换越少，总吞吐量越高。但公平性和响应性都要求频繁切换。

这三个目标形成了一个不可能三角：

• 追求极致公平 → 频繁抢占 → 上下文切换开销大 → 吞吐量下降
• 追求极致吞吐 → 减少切换、长时间片 → 交互响应慢
• 追求极致响应 → I/O 进程高优先级 → CPU 进程被饿死 → 不公平

每一代调度器都是在这个三角中寻找不同的平衡点。O(1) 偏向响应性（用启发式检测交互进程），CFS 偏向公平性（用统一的数学模型），EEVDF 试图在保持公平的同时收紧响应性的上界。

二、O(1) 调度器：启发式的巅峰与终结

设计背景

Linux 2.6 早期（2003-2007）使用 O(1) 调度器，由 Ingo Molnar 开发。它的前身是 Linux 2.4 的调度器——一个 O(n) 的简单实现，每次调度都要遍历整个就绪队列。当进程数达到数千时，调度本身成为瓶颈。O(1) 调度器的目标很明确：无论系统中有多少个进程，选择下一个运行的进程都是常数时间。

核心数据结构：bitmap + active/expired 双数组

O(1) 调度器为每个 CPU 维护两个优先级数组：active 和 expired。

// O(1) 调度器的核心结构（简化）
#define MAX_PRIO 140  // 0-99 实时优先级，100-139 普通优先级

struct prio_array {
    int nr_active;                                     // 此数组中的进程总数
    unsigned long bitmap[MAX_PRIO / BITS_PER_LONG];    // 位图：哪些优先级有就绪进程
    struct list_head queue[MAX_PRIO];                   // 每个优先级一个链表
};

struct runqueue {
    spinlock_t lock;
    unsigned long nr_running;    // 就绪进程总数
    struct prio_array *active;   // 当前活跃数组
    struct prio_array *expired;  // 过期数组
    struct prio_array arrays[2]; // 实际存储，active/expired 指向其中一个
};

调度逻辑分四步：

1. 从 active 的位图中找到最高优先级的非空队列：sched_find_first_bit(bitmap) — 利用硬件指令 bsf/__ffs，O(1)
2. 取出该队列的第一个进程运行
3. 进程用完时间片后，重新计算优先级，放入 expired 的对应优先级队列
4. 当 active 为空时，交换 active 和 expired 指针 — O(1)

// 选择下一个进程（概念代码）
struct task_struct *pick_next_task(struct runqueue *rq) {
    int idx = sched_find_first_bit(rq->active->bitmap);  // O(1)
    return list_first_entry(&rq->active->queue[idx]);
}

// 时间片耗尽时
void scheduler_tick(struct runqueue *rq, struct task_struct *p) {
    if (--p->time_slice <= 0) {
        dequeue_task(p, rq->active);
        p->prio = effective_prio(p);          // 重新计算动态优先级
        p->time_slice = task_timeslice(p);    // 重新分配时间片
        enqueue_task(p, rq->expired);         // 放入 expired 数组
    }
}

// 当 active 为空
if (rq->active->nr_active == 0) {
    struct prio_array *tmp = rq->active;
    rq->active = rq->expired;
    rq->expired = tmp;    // O(1) 指针交换
}

这个设计非常聪明：所有进程都跑完一轮后，一次指针交换就开始下一轮。不需要遍历任何数据结构。

启发式交互性检测：为什么被淘汰

O(1) 调度器的致命缺陷在于它的交互性检测。它试图区分 “I/O 密集型” 和 “CPU 密集型” 进程：

• I/O 密集型进程经常睡眠等待 I/O，醒来后应该立即获得 CPU
• CPU 密集型进程长时间占用 CPU，应该被降低优先级

O(1) 调度器用一个叫做 sleep_avg 的启发式指标来做这个区分：进程睡眠时 sleep_avg 增加（最多到 MAX_SLEEP_AVG），运行时减少。sleep_avg 被映射到 -5 到 +5 的动态优先级加成。

// 伪代码：动态优先级计算
int bonus = (sleep_avg * MAX_BONUS / MAX_SLEEP_AVG) - MAX_BONUS / 2;
// bonus 范围 [-5, +5]
p->prio = max(100, min(139, p->static_prio - bonus));

问题是：启发式就是一堆 if-else。 每当有人发现一种工作负载被误判，就添加一条新的启发式规则。到 2007 年，kernel/sched.c 已经膨胀到超过 7000 行，其中大量是处理各种边界情况的补丁代码。

更具体的问题：

1. CPU 密集的编解码器被误判为交互式：视频编码器每帧处理之间有短暂的 I/O 等待（读取下一帧），sleep_avg 会累积，导致它获得不应有的优先级加成
2. “饥饿陷阱”：当系统中有大量交互式进程时，CPU 密集型进程可能长期停留在 expired 数组中得不到运行
3. 不可预测：同样的进程在不同工作负载下表现截然不同，因为 sleep_avg 的值取决于系统的全局状态

Con Kolivas 在 2004 年的一封著名邮件中抱怨：“调度器的交互性检测代码已经变成了一堆不可维护的魔法数字。”

更根本的问题是：试图用启发式区分 I/O 和 CPU 进程本身就是错误的抽象。 很多进程（如浏览器）在渲染页面时是 CPU 密集的，在等待网络时是 I/O 密集的——它在两种模式之间频繁切换，启发式永远慢半拍。

O(1) 调度器的失败教给我们一个重要的系统设计教训：不要用启发式解决可以用数学解决的问题。 如果你发现自己在写越来越多的 if-else 来处理边界情况，说明你的抽象层次不对。

三、CFS 核心：虚拟运行时间与红黑树

核心思想：vruntime

CFS 的核心思想极其简洁：

给每个进程维护一个 虚拟运行时间（vruntime）。每次调度时选择 vruntime 最小的进程运行。

“虚拟”的含义是：vruntime 的增长速度与进程的权重成反比。高权重进程的 vruntime 增长慢（“虚拟时间过得慢”），因此它更容易保持最小 vruntime，从而获得更多实际运行时间。低权重进程的 vruntime 增长快（“虚拟时间过得快”），很快就被别人追上并抢占。

数学上，如果进程 \(i\) 的权重为 \(w_i\)，物理运行时间为 \(\Delta t\)，则其 vruntime 增量为：

\[ \Delta\text{vruntime}_i = \Delta t \cdot \frac{w_0}{w_i} \]

其中 \(w_0 = 1024\) 是 nice 0（默认优先级）的权重。

这意味着：

• nice 0 的进程（权重 1024）：vruntime 以 1:1 速度增长
• nice -5 的进程（权重 3121）：vruntime 增长速率为 \(1024/3121 \approx 0.33\)，需要 3 倍实际时间才能追上 nice 0
• nice +5 的进程（权重 335）：vruntime 增长速率为 \(1024/335 \approx 3.06\)，很快就被抢占

Nice 值到权重的映射

CFS 的权重表是精心设计的。相邻 nice 值的权重比约为 1.25:1，即 nice 差 1 对应 CPU 份额差约 10%。

// 内核中的权重表 (kernel/sched/core.c)
const int sched_prio_to_weight[40] = {
 /* -20 */ 88761, 71755, 56483, 46273, 36291,
 /* -15 */ 29154, 23254, 18705, 14949, 11916,
 /* -10 */  9548,  7620,  6100,  4904,  3906,
 /*  -5 */  3121,  2501,  1991,  1586,  1277,
 /*   0 */  1024,   820,   655,   526,   423,
 /*   5 */   335,   272,   215,   172,   137,
 /*  10 */   110,    87,    70,    56,    45,
 /*  15 */    36,    29,    23,    18,    15,
};

为什么选择 1.25 倍？这让用户可以做”线性”调优——每降低 1 个 nice 值约多得 10% 的 CPU。如果倍率太大（比如 2 倍），调优粒度太粗；太小（比如 1.05 倍），nice -20 到 +19 的 40 级范围覆盖的总倍率就不够。1.25 倍使得 nice -20 和 nice +19 之间的权重比达到约 \(1.25^{39} \approx 5920\) 倍，足以覆盖从实时音频到低优先级后台任务的需求。

红黑树：O(log n) 插入，O(1) 取最小

CFS 用红黑树存储所有就绪进程，以 vruntime 为 key。调度时取红黑树最左节点（最小 vruntime）。虽然红黑树的查找是 O(log n)，但内核用 rb_leftmost 缓存了最左节点指针，取最小是 O(1)。插入和删除仍为 O(log n)。

// 选择下一个进程（简化）
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct sched_entity *se = __pick_first_entity(&rq->cfs);
    return task_of(se);
}

// __pick_first_entity 返回红黑树最左节点（已缓存）
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) {
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

// 进程入队时插入红黑树
void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    update_curr(cfs_rq);             // 更新当前进程的 vruntime
    __enqueue_entity(cfs_rq, se);    // 按 vruntime 插入红黑树
    cfs_rq->nr_running++;
}

调度周期与最小粒度

CFS 用两个参数控制时间片分配：

• sched_latency_ns（默认 6ms，后改为 24ms / 8 核）：一个”调度周期”——在此时间内所有就绪进程都应至少运行一次
• sched_min_granularity_ns（默认 0.75ms）：单次运行的最小时间片

每个进程的理想时间片为：

\[ \text{slice}_i = \text{sched\_latency} \times \frac{w_i}{\sum_j w_j} \]

当就绪进程数 \(n\) 使得 \(\text{sched\_latency} / n < \text{sched\_min\_granularity}\) 时，CFS 放弃严格公平——每个进程至少运行 0.75ms，调度周期自动拉长为 \(n \times \text{sched\_min\_granularity}\)。

四、CFS 的数学：理想处理器与加权公平排队

理想处理器模型（GPS）

CFS 的理论基础是广义处理器共享（Generalized Processor Sharing，GPS）模型。GPS 假设一个理想处理器能够同时以无穷小粒度服务所有活跃流。对于 \(n\) 个权重分别为 \(w_1, w_2, \ldots, w_n\) 的进程，在任意时间区间 \([t_1, t_2]\) 内，进程 \(i\) 获得的服务量为：

\[ S_i(t_1, t_2) = \frac{w_i}{\sum_{j \in A(t)} w_j} \cdot (t_2 - t_1) \]

其中 \(A(t)\) 是 \(t\) 时刻的活跃进程集合。GPS 是”完全公平”的理想模型，但现实中 CPU 一次只能跑一个进程，我们需要用离散时间片来近似它。

加权公平排队（WFQ）

加权公平排队（Weighted Fair Queuing，WFQ）是 GPS 在分组交换网络中的离散近似，最早由 Demers、Keshav 和 Shenker 在 1989 年提出。CFS 本质上是 WFQ 在 CPU 调度领域的应用。

WFQ 的核心思想：为每个数据包（在 CPU 调度中是每个时间片）计算一个”虚拟完成时间”（virtual finish time），然后按虚拟完成时间从小到大服务。CFS 简化了这一点——它不显式计算虚拟完成时间，而是持续追踪每个进程的虚拟运行时间 vruntime，选择 vruntime 最小的进程。

vruntime 公式推导

设进程 \(i\) 的权重为 \(w_i\)，在物理时间 \([0, t]\) 内的实际运行时间为 \(\text{runtime}_i(t)\)。定义全局虚拟时间为：

\[ V(t) = \int_0^t \frac{1}{\sum_{j \in A(\tau)} w_j} d\tau \]

在 GPS 模型下，进程 \(i\) 的理想服务量为 \(S_i(t) = w_i \cdot V(t)\)。进程 \(i\) 的虚拟运行时间定义为：

\[ \text{vruntime}_i(t) = \int_0^t \frac{w_0}{w_i} \cdot \mathbb{1}[\text{进程 } i \text{ 正在运行}] \, d\tau \]

其离散形式即为：

\[ \text{vruntime}_i \mathrel{+}= \Delta t \cdot \frac{w_0}{w_i} \]

在理想状态下（完全公平时），所有进程的 vruntime 应该相等。CFS 通过始终调度 vruntime 最小的进程来趋近这个目标。

内核中使用整数运算避免浮点数。vruntime 的单位是纳秒，权重的倒数通过预计算的 inv_weight 表用乘法+移位来代替除法：

// kernel/sched/fair.c — vruntime 更新
static void update_curr(struct cfs_rq *cfs_rq) {
    struct sched_entity *curr = cfs_rq->curr;
    u64 now = rq_clock_task(rq_of(cfs_rq));
    u64 delta_exec = now - curr->exec_start;

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    // delta_exec * weight_0 / weight_i（用乘法+移位代替除法）
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

static u64 calc_delta_fair(u64 delta, struct sched_entity *se) {
    if (se->load.weight != NICE_0_LOAD)
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

五、CFS 的问题：从 sleeper fairness 到延迟不可控

新进程的 vruntime 初始化

一个新 fork 的进程应该有多少 vruntime？如果初始化为 0，它会立即霸占 CPU 直到 vruntime 追上其他进程——这是”新进程饥饿攻击”。如果初始化得太大，新进程又会被饿死。

CFS 的做法是将新进程的 vruntime 设为当前运行队列的 min_vruntime：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) {
    u64 vruntime = cfs_rq->min_vruntime;
    if (initial) {
        // 新 fork 的进程：加一个惩罚，避免 fork bomb 抢占现有进程
        vruntime += sched_vslice(cfs_rq, se);
    }
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

sched_vslice 计算的是”该进程一个时间片对应的 vruntime 增量”。这意味着新进程的 vruntime 比当前最小值稍大，它需要等到下一个调度周期才有机会运行。

但这里有一个微妙的问题：min_vruntime 是单调递增的，而长期睡眠的进程的 vruntime 是冻结的。如果一个 cgroup 中的所有进程都睡眠了 10 秒，然后一个新进程 fork 进来，新进程的 vruntime 会被设成一个很大的值（因为 min_vruntime 在这 10 秒里被其他 cgroup 推高了），而旧进程醒来后 vruntime 很小——结果新进程被饿死。

sleeper fairness 争议

当进程从睡眠中唤醒时，它的 vruntime 可能远小于当前的 min_vruntime。CFS 对此有两种策略，由 sched_features 中的 GENTLE_FAIR_SLEEPERS 控制：

策略一（默认启用）：将唤醒进程的 vruntime 设为 max(vruntime, min_vruntime - sched_latency/2)。这给予睡眠者”半个调度周期”的补偿，但不超过半个周期。

策略二（GENTLE_FAIR_SLEEPERS 关闭）：不做任何调整。睡眠者保留其原始 vruntime，可以获得大量补偿。

两种策略各有问题：

• 策略一对短睡眠的交互式进程不利：一个每 1ms 醒来处理一次事件的进程，每次唤醒都只得到微小的 vruntime 优势，响应性不够好
• 策略二对长睡眠进程补偿过度：一个睡了 10 秒的后台任务醒来后可以霸占 CPU 很久

这个参数在内核邮件列表上引发了长期争议。不同发行版选择不同的默认值。Ubuntu 倾向于 GENTLE_FAIR_SLEEPERS=1（限制补偿），某些音频工作站发行版则关闭它以改善实时响应。

延迟不可控

CFS 最根本的问题是：它没有延迟上界的数学保证。

假设系统中有 \(n\) 个权重相同的进程。一个进程刚用完时间片，它的 vruntime 是所有进程中最大的。在最坏情况下，它需要等其他 \(n-1\) 个进程各运行一个时间片才能重新获得 CPU。等待时间为：

\[ \text{worst\_latency} = (n - 1) \times \text{min\_granularity} \]

当 \(n = 1000\) 时，最坏延迟为 \(999 \times 0.75\text{ms} = 749\text{ms}\)。对于交互式应用来说这完全不可接受。

CFS 的 sched_latency_ns 参数试图限制这个延迟，但它不是一个保证——当进程数超过 sched_latency / min_granularity（默认 8 个）时，延迟线性增长。而且 CFS 没有机制区分”需要低延迟”的进程和”不在乎延迟”的进程——所有同优先级进程被一视同仁。

EEVDF 正是为了解决这个问题而生。

六、EEVDF：Earliest Eligible Virtual Deadline First

理论起源

EEVDF 算法最早由 Ion Stoica 和 Hussein Abdel-Wahab 在 1995 年的论文《Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation》中提出。这篇论文的目标是设计一个比 WFQ 更灵活的比例份额调度算法，核心改进是引入了 eligible time 的概念——不是所有积累了”欠债”的进程都能立即获得服务。

核心概念

EEVDF 为每个进程维护以下值：

1. 虚拟合格时间（virtual eligible time, \(ve_i\)）：进程”有资格”获得 CPU 的最早虚拟时间。只有当全局虚拟时间 \(V(t) \geq ve_i\) 时，进程才 eligible
2. 虚拟截止时间（virtual deadline, \(vd_i\)）：进程当前请求（时间片）的虚拟截止时间
3. lag：进程实际获得的服务与”应得份额”之间的差距

lag 的定义

\[ \text{lag}_i(t) = S_i(t) - s_i(t) \]

其中：

• \(S_i(t) = w_i \cdot V(t)\) 是进程 \(i\) 到虚拟时刻 \(V(t)\) 的理想（GPS）服务量
• \(s_i(t)\) 是进程 \(i\) 到时刻 \(t\) 的实际服务量

lag 的含义：

• \(\text{lag} > 0\)：进程被欠了 CPU 时间，GPS 模型下它应该获得更多服务
• \(\text{lag} < 0\)：进程超额使用了 CPU 时间
• \(\text{lag} = 0\)：完全公平

virtual deadline 的计算

当进程请求一个长度为 \(r_i\) 的时间片时（\(r_i\) 是虚拟时间长度，等于物理时间片除以权重归一化后的值）：

\[ ve_i = V(t) \quad (\text{如果进程刚唤醒或刚用完上一个时间片}) \]

\[ vd_i = ve_i + \frac{r_i}{w_i} \]

更精确地说，如果进程有正的 lag（被欠了服务），eligible time 可以更早：

\[ ve_i = V(t) - \frac{\text{lag}_i(t)}{w_i} \]

调度决策：在所有 \(ve_i \leq V(t)\)（eligible）的进程中，选择 \(vd_i\) 最小的。

为什么 6.6 内核从 CFS 切换到 EEVDF

Peter Zijlstra 在提交 EEVDF 补丁时给出的核心理由是：EEVDF 消除了 CFS 中所有的 sleeper fairness 启发式补丁。

CFS 为了处理唤醒进程的 vruntime 补偿问题，积累了大量 ad-hoc 的调整逻辑（GENTLE_FAIR_SLEEPERS、START_DEBIT、唤醒抢占的各种条件判断）。这些补丁之间相互影响，导致行为难以预测。

EEVDF 用一个统一的数学框架取代了所有这些启发式：进程的 lag 自然编码了它被欠了多少服务，eligible time 防止了过度补偿，virtual deadline 保证了延迟上界。不需要任何特殊的唤醒补偿逻辑。

七、EEVDF 的数学：为什么保证 O(1) 延迟界

lag 的有界性定理

EEVDF 的关键数学性质是 lag 有界：

对于任意进程 \(i\)，在任意时刻 \(t\)：

\[ -r_{\max} < \text{lag}_i(t) < r_{\max} \]

其中 \(r_{\max}\) 是系统中最大的单次请求长度（时间片）。

证明的直觉：如果进程 \(i\) 的 lag 非常大（被欠了很多），它的 eligible time 会很早，deadline 也会很紧，因此它会被优先调度。一旦它运行了一个时间片，lag 就减小了。EEVDF 的 eligible 条件阻止了一个进程连续获得多个时间片来”追赶”——每个时间片结束后，进程需要重新竞争。

延迟上界

对于权重为 \(w_i\)、请求长度为 \(r_i\) 的进程，在 EEVDF 下，从它变为 eligible 到实际获得 CPU 的最坏等待时间为：

\[ \text{delay}_i \leq \frac{\sum_{j \neq i} r_j}{1} = O\left(\sum_{j} r_j\right) \]

但如果所有进程的请求长度 \(r_j\) 都有上界 \(r_{\max}\)，则：

\[ \text{delay}_i \leq (n - 1) \cdot r_{\max} \]

关键区别在于：在 CFS 中，一个刚唤醒的进程的等待时间取决于它的 vruntime 与 min_vruntime 的差距，这个差距可以任意大（取决于睡眠时长）。而在 EEVDF 中，等待时间只取决于当前活跃进程数和时间片大小，与睡眠历史无关。

更进一步，对于请求较小时间片的进程（比如交互式进程），它们的 deadline 更紧（\(vd = ve + r_i/w_i\)），因此在竞争中更有优势。这自然实现了”小请求优先”的策略，无需任何启发式。

在 Linux 6.6+ 中的实现

Peter Zijlstra 的实现使用了增强红黑树（augmented rb-tree）。红黑树以 virtual deadline 为 key 排序，每个节点额外记录子树中最小的 eligible time。这使得 pick_eevdf 可以在 O(log n) 时间内找到 eligible 且 deadline 最小的进程：

// EEVDF 选择下一个进程（简化自 kernel/sched/fair.c）
struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) {
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
    struct sched_entity *best = NULL;

    while (node) {
        struct sched_entity *se = rb_entry(node, struct sched_entity, run_node);

        // 如果左子树中有 eligible 的实体，先去左边（deadline 更小）
        if (node->rb_left && entity_eligible(cfs_rq,
                __node_2_se(node->rb_left))) {
            node = node->rb_left;
            continue;
        }

        // 检查当前节点
        if (entity_eligible(cfs_rq, se)) {
            best = se;
            break;  // 因为是按 deadline 排序的，第一个 eligible 就是最优
        }

        node = node->rb_right;
    }

    return best;
}

// eligible 检查：ve <= V(t)
static bool entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    return (s64)(se->vruntime - cfs_rq->min_vruntime) <= 0;
}

实际内核代码比这复杂——它需要处理增强树的 min_vruntime 传播、树旋转时的更新等。但核心逻辑就是上面的搜索过程。

八、实时调度：SCHED_FIFO、SCHED_RR 与 SCHED_DEADLINE

调度策略层级

Linux 的调度器是模块化的。schedule() 函数按优先级依次询问各调度类：

stop_sched_class        → 内核停机任务（最高优先级）
  ↓
dl_sched_class          → SCHED_DEADLINE 任务
  ↓
rt_sched_class          → SCHED_FIFO / SCHED_RR 任务
  ↓
fair_sched_class        → SCHED_NORMAL (CFS/EEVDF) 任务
  ↓
idle_sched_class        → idle 任务（最低优先级）

只要高优先级调度类有就绪任务，低优先级的就不会被调度。一个 SCHED_FIFO 进程永远抢占 SCHED_NORMAL 进程。

SCHED_FIFO：简单粗暴的优先级抢占

SCHED_FIFO 拥有 1-99 的实时优先级。调度规则：

1. 高优先级永远抢占低优先级
2. 同优先级内先到先服务（FIFO），运行中的进程不会被同优先级进程抢占
3. 没有时间片概念——进程运行到主动让出 CPU（sched_yield）或被更高优先级抢占

这是最简单也最危险的调度策略。一个优先级 99 的 SCHED_FIFO 进程陷入死循环会饿死整个系统。内核提供了 /proc/sys/kernel/sched_rt_runtime_us（默认 950000）和 /proc/sys/kernel/sched_rt_period_us（默认 1000000）来限制：实时任务最多占用每秒中的 950ms，留 50ms 给普通任务。

SCHED_RR：带时间片的实时轮转

SCHED_RR 在 SCHED_FIFO 的基础上增加了时间片。同优先级的进程按时间片轮转（默认 100ms），高优先级仍然无条件抢占低优先级。

// 查看 SCHED_RR 的默认时间片
int sched_rr_get_interval(pid_t pid, struct timespec *tp);
// 通常返回 100ms

SCHED_DEADLINE：CBS + EDF 的工程实现

SCHED_DEADLINE（Linux 3.14+）是 Linux 实时调度的皇冠。它基于两个理论：

EDF（Earliest Deadline First）：始终运行截止时间最近的任务。Liu & Layland（1973）证明了 EDF 在单处理器上的最优性：如果任务集的总利用率 \(U \leq 1\)，EDF 保证所有截止时间都被满足。

\[ U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1 \]

CBS（Constant Bandwidth Server）：在 EDF 基础上增加带宽隔离。每个任务声明三个参数——runtime \(Q_i\)、deadline \(D_i\)、period \(T_i\)，其带宽为 \(Q_i / T_i\)。CBS 保证一个任务即使超出声明的 runtime，也不会影响其他任务的截止时间。超时的任务会被推迟：

// 设置 SCHED_DEADLINE 任务
struct sched_attr attr = {
    .size           = sizeof(attr),
    .sched_policy   = SCHED_DEADLINE,
    .sched_runtime  =  5 * 1000 * 1000,  //  5ms runtime
    .sched_deadline = 10 * 1000 * 1000,  // 10ms deadline
    .sched_period   = 10 * 1000 * 1000,  // 10ms period
};

if (sched_setattr(0, &attr, 0) < 0) {
    perror("sched_setattr");
    // 常见原因：总利用率超过限制
}

Admission Control

SCHED_DEADLINE 在设置参数时执行准入控制。内核检查：

\[ \sum_{i=1}^{n} \frac{Q_i}{\min(D_i, T_i)} \leq \frac{M \cdot (1 - \text{rt\_bw})}{1} \]

其中 \(M\) 是 CPU 核数，\(\text{rt\_bw}\) 是为 SCHED_RT 保留的带宽比例。如果新任务会导致总利用率超限，sched_setattr 返回 EBUSY。

这是 SCHED_DEADLINE 优于 SCHED_FIFO/RR 的关键优势：它在设置时就拒绝不可调度的配置，而不是在运行时出现不可预期的截止时间违反。

九、完整 C 实现：CFS 与 EEVDF 模拟器

以下是一个完整的调度模拟器，包含简化的红黑树（用数组模拟）、vruntime 计算、eligible 检查和 deadline 调度：

// cfs_eevdf_sim.c — CFS 与 EEVDF 调度策略模拟器
// 编译: gcc -O2 -o cfs_eevdf_sim cfs_eevdf_sim.c -lm
// 运行: ./cfs_eevdf_sim

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <float.h>
#include <math.h>

#define MAX_TASKS 16
#define W0 1024.0  // nice 0 基准权重

typedef struct {
    int    id;
    double weight;
    // CFS 字段
    double vruntime;
    // EEVDF 字段
    double ve;           // virtual eligible time
    double vd;           // virtual deadline
    double lag;
    // 统计
    double total_run;    // 累计物理运行时间
    double max_wait;     // 最大等待时间（衡量延迟公平性）
    double last_run_at;  // 上次运行的时刻
    int    is_runnable;
} Task;

// ==================== CFS 模拟 ====================

int cfs_pick_next(Task tasks[], int n) {
    int best = -1;
    double min_vrt = DBL_MAX;
    for (int i = 0; i < n; i++) {
        if (tasks[i].is_runnable && tasks[i].vruntime < min_vrt) {
            min_vrt = tasks[i].vruntime;
            best = i;
        }
    }
    return best;
}

void cfs_simulate(Task tasks[], int n, int ticks) {
    double slice = 1.0;

    printf("=== CFS 模拟 (%d ticks, %d tasks) ===\n", ticks, n);

    for (int t = 0; t < ticks; t++) {
        int next = cfs_pick_next(tasks, n);
        if (next < 0) break;

        // 更新等待统计
        for (int i = 0; i < n; i++) {
            if (i != next && tasks[i].is_runnable) {
                double wait = (t * slice) - tasks[i].last_run_at;
                if (wait > tasks[i].max_wait)
                    tasks[i].max_wait = wait;
            }
        }

        // 运行选中进程
        tasks[next].vruntime += slice * (W0 / tasks[next].weight);
        tasks[next].total_run += slice;
        tasks[next].last_run_at = t * slice;
    }

    printf("%-4s %-10s %-10s %-12s %-10s\n",
           "ID", "Weight", "Runtime", "vruntime", "MaxWait");
    for (int i = 0; i < n; i++) {
        printf("%-4d %-10.0f %-10.1f %-12.2f %-10.1f\n",
               tasks[i].id, tasks[i].weight,
               tasks[i].total_run, tasks[i].vruntime, tasks[i].max_wait);
    }
}

// ==================== EEVDF 模拟 ====================

int eevdf_pick_next(Task tasks[], int n, double V) {
    int best = -1;
    double min_vd = DBL_MAX;

    // 第一轮：在 eligible 进程中选 deadline 最小的
    for (int i = 0; i < n; i++) {
        if (!tasks[i].is_runnable) continue;
        if (tasks[i].ve <= V && tasks[i].vd < min_vd) {
            min_vd = tasks[i].vd;
            best = i;
        }
    }

    // 第二轮：若无 eligible 进程，退化为选 deadline 最小的
    if (best < 0) {
        min_vd = DBL_MAX;
        for (int i = 0; i < n; i++) {
            if (tasks[i].is_runnable && tasks[i].vd < min_vd) {
                min_vd = tasks[i].vd;
                best = i;
            }
        }
    }
    return best;
}

void eevdf_simulate(Task tasks[], int n, int ticks) {
    double slice = 1.0;
    double request = 4.0;  // 每个时间片请求量（物理时间单位）
    double total_weight = 0;

    for (int i = 0; i < n; i++)
        if (tasks[i].is_runnable) total_weight += tasks[i].weight;

    double V = 0;  // 全局虚拟时间
    int slices_run[MAX_TASKS] = {0};  // 每个任务当前时间片内已运行 tick 数

    printf("\n=== EEVDF 模拟 (%d ticks, %d tasks) ===\n", ticks, n);

    // 初始化 ve 和 vd
    for (int i = 0; i < n; i++) {
        tasks[i].ve = 0;
        tasks[i].vd = request / tasks[i].weight;
        tasks[i].lag = 0;
    }

    for (int t = 0; t < ticks; t++) {
        int next = eevdf_pick_next(tasks, n, V);
        if (next < 0) break;

        // 更新等待统计
        for (int i = 0; i < n; i++) {
            if (i != next && tasks[i].is_runnable) {
                double wait = (t * slice) - tasks[i].last_run_at;
                if (wait > tasks[i].max_wait)
                    tasks[i].max_wait = wait;
            }
        }

        // 运行选中进程
        tasks[next].total_run += slice;
        tasks[next].last_run_at = t * slice;
        slices_run[next]++;

        // 推进全局虚拟时间
        V += slice / total_weight;

        // 更新所有进程的 lag
        for (int i = 0; i < n; i++) {
            if (tasks[i].is_runnable) {
                double ideal = tasks[i].weight * V;
                // s_i(t) 是归一化后的实际服务量
                double actual = tasks[i].total_run * (tasks[i].weight / total_weight);
                tasks[i].lag = ideal - actual;
            }
        }

        // 时间片用完后重新计算 ve 和 vd
        if (slices_run[next] >= (int)request) {
            slices_run[next] = 0;
            tasks[next].ve = V;
            tasks[next].vd = V + request / tasks[next].weight;
        }
    }

    printf("%-4s %-10s %-10s %-10s %-10s %-8s\n",
           "ID", "Weight", "Runtime", "Deadline", "MaxWait", "Lag");
    for (int i = 0; i < n; i++) {
        printf("%-4d %-10.0f %-10.1f %-10.3f %-10.1f %-8.2f\n",
               tasks[i].id, tasks[i].weight,
               tasks[i].total_run, tasks[i].vd,
               tasks[i].max_wait, tasks[i].lag);
    }
}

// ==================== 主函数 ====================

int main(void) {
    // 场景：4 个进程，模拟 nice 0 / -5 / +5 / +10
    Task cfs_tasks[] = {
        {.id = 0, .weight = 1024, .is_runnable = 1},  // nice 0
        {.id = 1, .weight = 3121, .is_runnable = 1},  // nice -5
        {.id = 2, .weight = 335,  .is_runnable = 1},  // nice +5
        {.id = 3, .weight = 110,  .is_runnable = 1},  // nice +10
    };
    int n = sizeof(cfs_tasks) / sizeof(cfs_tasks[0]);

    Task eevdf_tasks[MAX_TASKS];
    memcpy(eevdf_tasks, cfs_tasks, sizeof(cfs_tasks));

    int total_ticks = 200;

    cfs_simulate(cfs_tasks, n, total_ticks);
    eevdf_simulate(eevdf_tasks, n, total_ticks);

    // 理想分配比例
    double total_w = 1024 + 3121 + 335 + 110;
    printf("\n理想分配 (%d ticks):\n", total_ticks);
    double weights[] = {1024, 3121, 335, 110};
    for (int i = 0; i < n; i++) {
        printf("  P%d (w=%.0f): %.1f ticks (%.1f%%)\n",
               i, weights[i],
               total_ticks * weights[i] / total_w,
               100.0 * weights[i] / total_w);
    }

    return 0;
}

编译运行：

gcc -O2 -Wall -o cfs_eevdf_sim cfs_eevdf_sim.c -lm
./cfs_eevdf_sim

观察重点：两个调度器的 total_run 应该接近理想分配，但 MaxWait（最大等待时间）的差异揭示了 EEVDF 在短期公平性上的优势。

十、cgroup 与 CPU 带宽控制

cpu.shares（cgroup v1）与 cpu.weight（cgroup v2）

CFS 的层级调度通过 cgroup 暴露给用户空间。每个 cgroup 拥有一个 sched_entity，和进程一样参与 vruntime 竞争。

cgroup v1 使用 cpu.shares（默认 1024），cgroup v2 使用 cpu.weight（默认 100，范围 1-10000）。它们都是比例权重——只在 CPU 竞争时起作用：

# cgroup v2 设置 CPU 权重
echo 200 > /sys/fs/cgroup/myapp/cpu.weight  # 2 倍于默认权重

如果系统只有一个 cgroup 在运行 CPU 密集任务，它可以用满所有 CPU，无论 weight 设多低。weight 只在多个 cgroup 竞争同一个 CPU 时才起作用。

cpu.cfs_quota_us 与 cpu.cfs_period_us：硬限制

CFS 带宽控制（CFS Bandwidth Control）允许设置硬限制：

# cgroup v1
echo 50000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us     # 50ms
echo 100000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us    # 100ms 周期
# → 该 cgroup 最多使用 50% CPU

# cgroup v2 等价写法
echo "50000 100000" > /sys/fs/cgroup/myapp/cpu.max

实现机制：内核为每个 cgroup 维护一个令牌桶。每个 period（默认 100ms）开始时，桶被填充 quota 微秒的令牌。cgroup 中的进程每运行 1us 消耗 1 个令牌。令牌耗尽时，该 cgroup 的所有进程被 throttle（移出运行队列），直到下一个 period 开始。

Throttling 问题

CFS 带宽控制的 throttling 机制有一个臭名昭著的问题：突发性 throttle。

考虑一个多线程应用（比如 Java 服务），配置了 quota=200000, period=100000（200ms/100ms = 2 核）。如果这个应用有 8 个线程同时醒来处理一批请求，它们可能在 period 开始后的 25ms 内就用完了全部 200ms 的配额（8 线程 × 25ms = 200ms）。然后在剩余的 75ms 内，所有线程都被 throttle。

从应用的角度看，它突然从”正常运行”变成”完全停止”长达 75ms——这对 P99 延迟是灾难性的。

Linux 5.4 引入了 cpu.cfs_burst_us 来缓解这个问题：允许 cgroup 在短时间内超出 quota，只要长期平均不超标。

# 允许突发使用最多额外 50ms
echo 50000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_burst_us

Kubernetes 的 CPU limit 坑

Kubernetes 的 resources.limits.cpu 直接映射到 CFS 带宽控制：

resources:
  requests:
    cpu: "500m"    # → cpu.shares / cpu.weight
  limits:
    cpu: "1000m"   # → cpu.cfs_quota_us = 100000, cpu.cfs_period_us = 100000

常见问题：

1. 设 limit = request：很多团队按照”最佳实践”设 limit == request。但这意味着应用不能利用空闲 CPU 做突发处理。一个 cpu.limit=1000m 的 Pod 即使节点上有 7 个空闲核心，也最多只能用 1 个核

2. 不设 limit：如果不设 limit（只设 request），cgroup 的 quota 是 -1（无限制）。应用可以使用节点上所有空闲 CPU。这在 CPU 不紧张时很好，但在节点负载高时，Pod 之间通过 cpu.weight 竞争，高权重 Pod 可能把低权重 Pod 饿到只剩一点点 CPU

3. GC 暂停被放大：Java/Go 的 GC 在 stop-the-world 阶段需要大量 CPU。如果 CPU limit 太低，GC 暂停时间会被成倍放大。一个正常 10ms 的 GC 暂停在 500m limit 下可能变成 20ms 甚至更长

4. runtime 检测错误：Go 1.19 之前的 runtime.NumCPU() 返回的是宿主机核数而非 cgroup 限制。设了 2 核 limit 的容器以为自己有 64 核，创建 64 个 P，导致过度调度。Go 1.19+ 的 GOMAXPROCS 会自动读取 cgroup 限制

十一、工程陷阱表

十二、个人观点

调度器的设计哲学谱系

固定优先级 (SCHED_FIFO/RR)
  ↓ 问题：饿死低优先级，无时间隔离
时间片轮转 + 优先级老化 + 启发式交互检测 (O(1))
  ↓ 问题：启发式不可维护，魔法数字泛滥
虚拟运行时间公平 (CFS)
  ↓ 问题：短期不公平，sleeper fairness 需要启发式补丁
虚拟截止时间公平 (EEVDF)
  ↓ 问题：多核负载均衡仍是开放问题

每一代演变的规律是相同的：用更强的数学模型替代上一代的启发式补丁。 O(1) 的 sleep_avg 启发式被 CFS 的 vruntime 统一模型替代。CFS 的 GENTLE_FAIR_SLEEPERS 启发式被 EEVDF 的 eligible + deadline 数学框架替代。

为什么调度器这么难

调度器是操作系统中最难正确实现的组件之一，因为：

1. 评价标准不唯一：服务器要吞吐量，桌面要交互性，实时要确定性，HPC 要减少迁移。一个调度器不可能在所有场景下都是最优的
2. 观测改变被观测者：测量调度延迟需要精确的硬件计时器，但计时器中断本身会触发调度决策。这是一个海森堡式的困境
3. 非线性反馈回路：调度决策影响缓存使用，缓存使用影响进程运行时间，运行时间又影响调度决策。这使得理论分析很难直接指导实践
4. 多核使一切更难：单核调度有良好的理论基础（WFQ、GPS 近似、EDF 最优性）。但在多核系统上，负载均衡的最优解是 NP-hard 的。Linux 的负载均衡器（load_balance()）本身就有几千行代码，充满了启发式——恰好是调度器本体试图消除的东西

对工程实践的启示

我在使用和调优调度器的过程中总结了几个原则：

1. 不要调优你不理解的参数。sched_min_granularity_ns、sched_latency_ns、sched_wakeup_granularity_ns 这些参数之间有复杂的交互关系。盲目调优往往适得其反

2. CPU limit 是一个谎言。Kubernetes 的 cpu.limit 给人的感觉是”我最多用这么多 CPU”，但实际行为是”每 100ms 我可以用 X ms，然后被完全停止”。这个时间粒度对微服务来说太粗了。如果你的服务对尾延迟敏感，认真考虑只设 request 不设 limit

3. SCHED_DEADLINE 被严重低估。大多数生产环境中的实时需求（音频处理、视频渲染、工业控制）使用 SCHED_FIFO 是因为”大家都这么用”。但 SCHED_DEADLINE 提供了更强的保证和更好的隔离，它的准入控制机制可以在部署时就发现资源不足的问题

4. 调度器不是银弹。如果你的应用延迟高，90% 的原因不在调度器，而在锁竞争、内存分配、I/O 阻塞或 GC 暂停。在碰调度器参数之前，先用 perf sched latency 和 perf sched timehist 确认调度确实是瓶颈

从 O(1) 到 CFS 到 EEVDF，Linux 调度器的演进历史是一部从启发式到数学模型的转变史。O(1) 用一堆魔法数字区分”交互进程”和”批处理进程”；CFS 用虚拟运行时间统一了所有进程；EEVDF 用虚拟截止时间进一步消除了短期不公平。

如果有什么值得记住的，那就是：好的系统设计用数学代替直觉，用统一的模型代替 if-else。 这个原则不止适用于调度器——它适用于所有你正在写的那些越来越多的 special case 处理。

系列导航： - 上一篇：页面置换算法：LRU 的谎言与 ARC 的真相 - 下一篇：I/O 调度

相关阅读： - 红黑树 vs AVL - epoll 的数据结构