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

2007 年，Ingo Molnár 在一封看似普通的 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 三代调度器的内部机制，用数学公式和内核源码揭示每次演变背后的设计权衡。

一、调度器的根本矛盾

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

公平性（Fairness）：每个进程按其权重获得相应比例的 CPU 时间。不能因为进程”碰巧”晚到就被饿死。

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

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

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

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

每一代调度器都是在这个三角中寻找不同的平衡点。

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

设计背景

Linux 2.6 早期（2003-2007）使用 O(1) 调度器，由 Ingo Molnár 开发。名字中的 “O(1)” 指的是调度决策的时间复杂度——无论系统中有多少个进程，选择下一个运行的进程都是常数时间。

核心数据结构

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

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

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

struct runqueue {
    struct prio_array *active;   // 当前活跃数组
    struct prio_array *expired;  // 过期数组
};

调度逻辑：

从 active 的位图中找到最高优先级的非空队列：ffs(bitmap) — O(1)
取出该队列的第一个进程运行
进程用完时间片后，放入 expired 的对应优先级队列
当 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]);
}

启发式交互性检测的问题

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

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

O(1) 调度器用一个叫做 sleep_avg 的启发式指标来做这个区分：进程睡眠时 sleep_avg 增加，运行时减少。sleep_avg 高的进程被视为”交互式”，获得优先级加成。

问题是：启发式就是一堆 if-else。 每当有人发现一种工作负载被误判，就添加一条新的启发式规则。代码变得越来越复杂，边界情况越来越多，最终变成了一个没人能完全理解的状态机。

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

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

个人思考

O(1) 调度器的失败教给我们一个重要的系统设计教训：不要用启发式解决可以用数学解决的问题。 如果你发现自己在写越来越多的 if-else 来处理边界情况，说明你的抽象层次不对。CFS 的突破就在于它换了一个完全不同的抽象——不再区分 I/O 和 CPU 进程，而是用一个统一的公平性模型。

三、CFS：用红黑树实现公平

核心思想

CFS 的核心思想极其简洁：

给每个进程维护一个 虚拟运行时间（vruntime）。vruntime 增长最慢的进程获得 CPU。

“虚拟”的含义是：vruntime 的增长速度与进程的权重成反比。高权重进程的 vruntime 增长慢（“时间过得慢”），低权重进程的 vruntime 增长快（“时间过得快”）。

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

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

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

这意味着： - nice 0 的进程：vruntime 以实际时间速度增长 - nice -5 的进程（权重约 3121）：vruntime 增长约为实际时间的 \(1024/3121 \approx 0.33\) 倍 → 需要运行更长实际时间才能”赶上” - 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 倍？这让用户可以用 nice 值做”线性”的调优——每降低 1 个 nice 值，大约多得 10% 的 CPU。如果倍率太大（比如 2 倍），调优就太粗糙；太小（比如 1.05 倍），调优范围又不够。

红黑树

CFS 用红黑树存储所有就绪进程，以 vruntime 为 key。调度时取红黑树最左节点（最小 vruntime）——这是 O(log n) 操作，但内核缓存了最左节点，实际是 O(1)。

// 选择下一个进程（简化）
struct task_struct *pick_next_task_fair(struct rq *rq) {
    struct sched_entity *se = __pick_first_entity(rq->cfs_rq);
    // se 是 vruntime 最小的调度实体
    return task_of(se);
}

// __pick_first_entity 返回红黑树最左节点
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq) {
    return rb_entry(cfs_rq->rb_leftmost, struct sched_entity, run_node);
}

调度周期与最小粒度

CFS 有两个关键参数：

sched_latency_ns（默认 6ms）：一个”调度周期”——在这段时间内，所有就绪进程都应该至少运行一次。
sched_min_granularity_ns（默认 0.75ms）：单次运行的最小时间片。

每个进程的时间片 = sched_latency_ns × (进程权重 / 所有就绪进程权重总和)。

当就绪进程很多时，按比例分配的时间片可能小于 sched_min_granularity_ns。此时 CFS 放弃了严格公平——每个进程至少运行 0.75ms，代价是调度周期拉长。

组调度与 cgroup

CFS 支持层级调度。通过 cgroup，你可以限制一组进程的总 CPU 份额。

cgroup/
├── A/  (cpu.shares = 1024)
│   ├── process_1
│   └── process_2
└── B/  (cpu.shares = 2048)
    └── process_3

A 组获得 1/3 的 CPU，B 组获得 2/3。A 组内的两个进程各得 1/6。

实现上，每个 cgroup 是一个 sched_entity，和进程一样参与 vruntime 竞争。cgroup 内部又有自己的红黑树。这形成了一个层级调度树。

CFS 的隐藏缺陷

CFS 承诺”完全公平”，但它有一个微妙的问题：唤醒延迟不公平。

考虑两个进程 A 和 B，权重相同：

A 一直在运行，vruntime 不断增加
B 睡眠了很长时间（等待 I/O），vruntime 停止增长
B 被唤醒，此时 B 的 vruntime 远小于 A

CFS 会让 B 立即获得 CPU（vruntime 最小），并且 B 可以运行很长时间来”追赶” A 的 vruntime。如果 B 积累了 100ms 的”vruntime 欠债”，它可以连续运行 100ms 不被抢占。

这在长期看是公平的（B 最终会和 A 的 vruntime 对齐），但在短期是灾难性的——其他进程在 B “追赶”期间得不到 CPU。

CFS 通过在唤醒时调整 vruntime（设置为 max(进程vruntime, cfs_rq->min_vruntime - sched_latency_ns/2)）来缓解这个问题，但这是另一个启发式补丁。

四、EEVDF：短期公平的数学解

为什么需要 EEVDF

CFS 的核心问题可以这样概括：vruntime 只编码了”谁跑了多少”，没有编码”谁应该在什么时候跑”。一个进程可能”应该”在 10ms 前就获得 CPU，但 CFS 只知道它的 vruntime 小，不知道它已经等了多久。

EEVDF（Earliest Eligible Virtual Deadline First）通过引入虚拟截止时间（virtual deadline）解决了这个问题。

核心概念

EEVDF 为每个进程维护三个值：

虚拟合格时间（virtual eligible time, \(ve_i\)）：进程”有资格”获得 CPU 的最早虚拟时间
虚拟截止时间（virtual deadline, \(vd_i\)）：进程当前时间片的虚拟截止时间
lag：进程实际获得的 CPU 时间与”应得份额”之间的差距

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

其中 \(S_i(t)\) 是进程 \(i\) 到时刻 \(t\) 的”理想”服务量（按权重比例分配），\(s_i(t)\) 是实际获得的服务量。

\(\text{lag} > 0\)：进程被欠了 CPU 时间（应该优先）
\(\text{lag} < 0\)：进程多用了 CPU 时间（可以等等）
\(\text{lag} = 0\)：完全公平

当进程请求一个长度为 \(r_i\) 的时间片时：

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

调度决策：选择 \(ve_i \leq V(t)\)（合格）的进程中，\(vd_i\) 最小的。这里 \(V(t)\) 是当前的虚拟时间。

关键区别

EEVDF 和 CFS 的根本区别：

CFS：选 vruntime 最小的进程。vruntime 只反映”跑了多少”，不反映”截止时间”。
EEVDF：选截止时间最早的合格进程。截止时间编码了”这个时间片应该在什么时候完成”，合格条件保证了不会过早调度。

EEVDF 如何解决唤醒延迟问题

回到之前的场景：进程 B 睡眠后被唤醒。

在 CFS 下：B 的 vruntime 很小，会霸占 CPU 很久。

在 EEVDF 下：B 被唤醒时，它的 lag 确实为正（被欠了 CPU），但它的虚拟截止时间是 \(ve_B + r_B/w_B\)。即使 lag 很大，B 也只能获得一个时间片的优先权，而不是无限的”追赶”时间。下一个时间片需要重新竞争。

这保证了短期公平：任何进程在任何时刻的 lag 都有上界——不会无限积累。

在 Linux 6.6+ 中的实现

Peter Zijlstra 在 2023 年将 EEVDF 合并进 Linux 6.6。实现上，红黑树的 key 从 vruntime 变成了 virtual deadline。最左节点就是截止时间最早的进程。

// EEVDF 选择下一个进程（简化自内核源码）
struct sched_entity *pick_eevdf(struct cfs_rq *cfs_rq) {
    struct sched_entity *best = NULL;
    // 遍历红黑树，找 eligible 且 deadline 最小的
    // 实际实现用了 augmented rb-tree 优化
    struct rb_node *node = cfs_rq->tasks_timeline.rb_root.rb_node;
    while (node) {
        struct sched_entity *se = rb_entry(node, struct sched_entity, run_node);
        if (entity_eligible(cfs_rq, se)) {
            if (!best || deadline_lt(se, best))
                best = se;
            node = node->rb_left;   // 尝试更小的 deadline
        } else {
            node = node->rb_right;  // 不合格，往右找
        }
    }
    return best;
}

EEVDF 在 CFS 上的性能改进

Phoronix 的基准测试（Linux 6.6 vs 6.5）显示：

场景	CFS (6.5)	EEVDF (6.6)	变化
桌面交互延迟 (P99)	12.3ms	8.1ms	-34%
hackbench（调度吞吐）	4.2s	3.8s	-10%
内核编译 (make -j16)	124s	122s	-2%
Redis QPS	285K	289K	+1%

交互延迟改善最显著（34%），吞吐量基本持平或略有改善。这正是 EEVDF 的设计目标——在不牺牲吞吐的前提下改善延迟公平性。

五、实时调度：SCHED_DEADLINE

硬实时 vs 软实时

前面讨论的都是普通进程的调度（SCHED_NORMAL/SCHED_OTHER）。Linux 还支持实时调度：

SCHED_FIFO：优先级抢占式 FIFO。同优先级内先到先服务，高优先级永远抢占低优先级。
SCHED_RR：带时间片的轮转。同优先级内轮转，高优先级仍然抢占低优先级。
SCHED_DEADLINE（Linux 3.14+）：基于 EDF（Earliest Deadline First）的实时调度。

SCHED_FIFO 和 SCHED_RR 有一个根本问题：它们不提供时间隔离。 一个高优先级的 SCHED_FIFO 进程如果陷入死循环，可以完全饿死所有低优先级进程（包括 init 进程和 sshd）。你连登录服务器杀掉它的机会都没有。

SCHED_DEADLINE 的设计

SCHED_DEADLINE 基于 CBS（Constant Bandwidth Server） 模型。每个实时任务声明三个参数：

runtime：每个周期内需要的最大 CPU 时间
deadline：每个周期的截止时间
period：周期长度

// 设置 SCHED_DEADLINE
struct sched_attr attr = {
    .sched_policy   = SCHED_DEADLINE,
    .sched_runtime  = 10 * 1000 * 1000,  // 10ms
    .sched_deadline = 30 * 1000 * 1000,  // 30ms
    .sched_period   = 30 * 1000 * 1000,  // 30ms
};
sched_setattr(pid, &attr, 0);

这意味着：进程每 30ms 需要 10ms 的 CPU 时间，必须在 30ms 内完成。系统保证在 deadline 前给予足够的 runtime——前提是系统的总利用率不超过 100%。

EDF 的最优性

Liu & Layland（1973）证明了 EDF 的最优性定理：

在单处理器上，如果一组周期性任务的总利用率 \(U = \sum_{i=1}^{n} \frac{C_i}{T_i} \leq 1\)，那么 EDF 可以调度它们使得所有截止时间都被满足。而且 EDF 是最优的——如果 EDF 无法调度，任何其他算法也不行。

这里 \(C_i\) 是任务 \(i\) 的最坏执行时间，\(T_i\) 是其周期。

CBS 在 EDF 基础上增加了带宽隔离：一个任务即使超出声明的 runtime，也不会影响其他任务的截止时间保证。超时的任务会被推迟到下一个周期。

六、CFS 与 EEVDF 模拟实现

// cfs_eevdf_sim.c — CFS 与 EEVDF 调度策略模拟
#include <stdio.h>
#include <stdlib.h>
#include <float.h>

#define MAX_TASKS 16

typedef struct {
    int id;
    double weight;       // 权重
    double vruntime;     // CFS: 虚拟运行时间
    double ve;           // EEVDF: virtual eligible time
    double vd;           // EEVDF: virtual deadline
    double lag;          // EEVDF: lag
    double total_run;    // 总物理运行时间
    int is_runnable;
} Task;

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

void cfs_simulate(Task tasks[], int n, int ticks) {
    double slice = 1.0;  // 每 tick 的物理时间
    double w0 = 1024.0;  // 基准权重

    printf("=== CFS 模拟 ===\n");
    for (int t = 0; t < ticks; t++) {
        int next = cfs_pick_next(tasks, n);
        if (next < 0) break;
        // 运行一个 tick
        tasks[next].vruntime += slice * (w0 / tasks[next].weight);
        tasks[next].total_run += slice;
    }

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

// ===== EEVDF 模拟 =====
int eevdf_pick_next(Task tasks[], int n, double V) {
    int best = -1;
    double min_vd = DBL_MAX;
    for (int i = 0; i < n; i++) {
        if (tasks[i].is_runnable && tasks[i].ve <= V) {
            if (tasks[i].vd < min_vd) {
                min_vd = tasks[i].vd;
                best = i;
            }
        }
    }
    if (best < 0) {
        // 无合格进程，选 vd 最小的
        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 total_weight = 0;
    for (int i = 0; i < n; i++)
        if (tasks[i].is_runnable) total_weight += tasks[i].weight;

    double V = 0;  // 全局虚拟时间
    double request = 4.0;  // 每个时间片请求 4 ticks

    printf("\n=== EEVDF 模拟 ===\n");

    // 初始化 deadline
    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;

        tasks[next].total_run += slice;
        V += slice / total_weight;

        // 更新 lag
        for (int i = 0; i < n; i++) {
            if (tasks[i].is_runnable) {
                double ideal = tasks[i].weight / total_weight * (t + 1) * slice;
                tasks[i].lag = ideal - tasks[i].total_run;
            }
        }

        // 检查时间片是否用完（简化：每 request ticks 更新 deadline）
        if ((int)tasks[next].total_run % (int)request == 0) {
            tasks[next].ve = V;
            tasks[next].vd = V + request / tasks[next].weight;
        }
    }

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

int main(void) {
    // 场景：3 个进程，权重分别为 1024、2048、512（nice 0, -5, +5 近似）
    Task cfs_tasks[3] = {
        {.id = 0, .weight = 1024, .is_runnable = 1},
        {.id = 1, .weight = 2048, .is_runnable = 1},
        {.id = 2, .weight = 512,  .is_runnable = 1},
    };

    Task eevdf_tasks[3] = {
        {.id = 0, .weight = 1024, .is_runnable = 1},
        {.id = 1, .weight = 2048, .is_runnable = 1},
        {.id = 2, .weight = 512,  .is_runnable = 1},
    };

    int total_ticks = 100;
    cfs_simulate(cfs_tasks, 3, total_ticks);
    eevdf_simulate(eevdf_tasks, 3, total_ticks);

    // 理想分配：w1:w2:w3 = 1024:2048:512 = 2:4:1
    // 总 100 ticks → 进程 0: 28.6, 进程 1: 57.1, 进程 2: 14.3
    printf("\n理想分配: P0=%.1f, P1=%.1f, P2=%.1f\n",
           100 * 1024.0 / 3584, 100 * 2048.0 / 3584, 100 * 512.0 / 3584);

    return 0;
}

编译运行：

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

七、工程踩坑备忘

坑	现象	原因	解法
nice -20 但延迟更高	设了最高优先级但 P99 延迟反而高了	nice 只影响 CPU 份额，不影响 I/O 优先级。且极高权重会导致超长时间片	用 `ionice` 配合，或用 SCHED_DEADLINE
cgroup CPU 限制导致卡顿	`cpu.max = 50000 100000` 限了 50%，但 shell 卡	cgroup 内所有进程共享配额，一个 CPU-heavy 进程吃完了 shell 的份额	把交互进程放到独立 cgroup，或用 `cpu.weight` 代替硬限制
容器内 top 显示 CPU 使用率异常	容器限了 2 核，top 显示 200%	老版本 top 读 `/proc/stat` 看到的是宿主机 CPU 核数	用 `lxcfs` 或容器内装 cAdvisor
EEVDF 下批处理任务变慢	升级到 Linux 6.6 后编译速度降了 3%	EEVDF 的短期公平性导致更频繁的抢占	`sched_util_clamp_min` 或调整 `sched_min_granularity_ns`
NUMA 调度跨节点访问	多 NUMA 节点服务器性能不稳定	调度器把进程迁移到远端 NUMA 节点，内存访问延迟增加	`numactl --cpunodebind=0 --membind=0 ./program`

八、总结与个人思考

调度器的设计哲学谱系

固定优先级 (SCHED_FIFO/RR)
  ↓ 问题：饿死低优先级
时间片轮转 + 优先级老化 (O(1))
  ↓ 问题：启发式不可维护
虚拟运行时间公平 (CFS)
  ↓ 问题：短期不公平
虚拟截止时间公平 (EEVDF)
  ↓ 问题：多核调度的负载均衡仍是开放问题

为什么调度器这么难

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

评价标准不唯一：服务器要吞吐，桌面要交互，实时要确定性。一个调度器不可能在所有场景下都是最优的。
测量困难：调度器的 overhead 本身很难测量——你需要用精确的硬件计时器，但计时器的中断本身会影响调度。
非线性效应：调度决策影响缓存使用，缓存使用影响进程运行时间，运行时间又影响调度决策。这个反馈回路使得理论分析很难指导实践。

最后

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

如果有什么值得记住的，那就是：好的系统设计用数学代替直觉，用统一的模型代替 if-else。

上一篇: 页面置换算法：LRU 的谎言与 ARC 的真相
下一篇: I/O 调度：CFQ → mq-deadline → BFQ → kyber

目录