Linux 内核 CFS 与 EEVDF 调度器实战：从 vruntime 到延迟保证的完整工程解析

Linux 内核调度器是操作系统的核心组件之一，负责决定哪个进程在哪个 CPU 核心上运行。从早期的 O(n) 调度器到 O(1) 调度器，再到现在广泛使用的 CFS（完全公平调度器）以及 Linux 6.6 引入的 EEVDF（最早合格虚拟延迟优先），内核调度器经历了数次重大演进。这些演进不仅体现了性能优化的需求，更反映了从"尽力而为"到"延迟可保证"的设计哲学变迁。

本文将从 CFS 的核心数据结构入手，深入 vruntime 的运行红黑树实现、调度实体层级组织、带宽控制机制，然后过渡到 NUMA 感知调度的工程挑战，最终聚焦于 EEVDF 这一新一代调度器的设计动机、核心算法和迁移路径。文章包含大量 C/BPF 代码示例和内核 tracepoint 实战分析方法。

一、CFS 核心设计：从目标模型到数据结构

1.1 虚拟运行时间（vruntime）的本质

CFS 的设计目标是"完全公平"——在理想的多任务调度器中，每个可运行任务应在任何时间段内获得相等的 CPU 时间份额。由于物理 CPU 只能串行执行指令，CFS 引入虚拟运行时间的概念实现这一理想模型：

// kernel/sched/fair.c - 核心公式
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;

    delta_exec = now - curr->exec_start;
    if (unlikely((s64)delta_exec <= 0))
        return;

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

    // 关键公式：vruntime 按权重反比增长
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

calc_delta_fair 实现了负载权重补偿。假设任务 A 的权重为 1024（nice 0），任务 B 的权重为 820（nice 5），当两者各运行 20ms 物理时间时：

• 任务 A vruntime 增量 = 20ms × 1024/1024 = 20ms
• 任务 B vruntime 增量 = 20ms × 1024/820 = 25ms

权重越低（nice 值越高），vruntime 增长越快，从而更快被抢占，实现低优先级任务获得较少 CPU 时间的目标。

1.2 红黑树的调度决策

CFS 使用红黑树（按 vruntime 排序键）管理可运行任务。调度时选择 vruntime 最小的节点——也就是获得 CPU 时间最少的任务：

// kernel/sched/fair.c
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    bool leftmost = true;

    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;
        }
    }

    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);
    // leftmost=true 时放入 rb_leftmost 缓存，O(1) 获取最左侧节点
}

内核维护 cfs_rq->rb_leftmost 缓存最左侧节点（最小 vruntime），使 pick_next_task 达到 O(1)。入队和删除操作仍为 O(log n)。

1.3 min_vruntime 与时钟漂移补偿

不同 CPU 核心上的 CFS 队列需要保持 vruntime 可比性。min_vruntime 记录队列中已调度任务的最小 vruntime，新唤醒任务的 vruntime 被设置为不小于 min_vruntime，避免高 vruntime 的迁移任务长期霸占 CPU：

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);

    u64_vruntime = cfs_rq->min_vruntime;

    if (curr) {
        if (curr->on_rq)
            vruntime = curr->vruntime;
        else
            curr = NULL;
    }

    if (leftmost) {
        struct sched_entity *se = rb_entry(leftmost, ...);
        if (!curr)
            vruntime = se->vruntime;
        else
            vruntime = min(vruntime, se->vruntime);
    }

    cfs_rq->min_vruntime = max(vruntime, cfs_rq->min_vruntime);
}

二、调度实体层级与组调度

2.1 Sched Entity 的多层嵌套

Linux 的调度实体（struct sched_entity）以树状结构组织，支持组调度（CONFIG_FAIR_GROUP_SCHED）：

                    CPU rq
                   /   |   \
            cfs_rq_0  cfs_rq_1  cfs_rq_2     ← 每 CPU 运行队列
            /    \      |       /    \
          se_A1  se_A2 se_B1  se_C1  se_C2    ← 任务/任务组实体
                         /
                      sub_se_1                    ← 子任务组

每个实体可能包含子实体（当它是任务组时），on_rq 标识是否在红黑树上。my_q 指向下属 CFS 队列——如果是叶子任务则指向自己所在的 per-CPU 队列。

// 调度实体结构（简化）
struct sched_entity {
    struct load_weight  load;        // 权重
    struct rb_node      run_node;    // 红黑树节点
    u64                 exec_start;   // 开始执行时间戳
    u64                 sum_exec_runtime;  // 总运行时间
    u64                 vruntime;     // 虚拟运行时间
    u64                 prev_sum_exec_runtime; // 换出时的累计值
    struct cfs_rq      *cfs_rq;      // 所在 CFS 队列
    struct cfs_rq      *my_q;        // 子队列（任务组用）
};

2.2 带宽控制：CFS Bandwidth

CFS Bandwidth 通过 RT 调度类的带宽预留机制限制任务组的 CPU 使用量。每个任务组（cgroup cpu 子系统的 hierarchy）设置 cpu.cfs_quota_us 和 cpu.cfs_period_us：

// kernel/sched/fair.c - 带宽节流检查
static int do_sched_cfs_period_timer(struct cfs_bandwidth *cfs_b)
{
    // 周期内配额用完后，节流该组所有任务
    if (cfs_b->runtime_expires && cfs_b->runtime <= 0)
        throttle_cfs_rq(cfs_rq);
    else
        unthrottle_cfs_rq(cfs_rq);
}

工程实践中，容器平台如 Kubernetes 通过如下 cgroup 配置限制 Pod 资源：

# CPU limit: 2 cores
echo 200000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/myapp/cpu.cfs_period_us

# 或通过 cgroup v2
echo "200000 100000" > /sys/fs/cgroup/myapp/cpu.max

注意：CFS Bandwidth 的纳秒级精度和中断延迟敏感性使其不适合硬实时场景。对于严格实时需求，仍应使用 SCHED_FIFO 或 SCHED_RR 配合 sched_rt_runtime_us 保护。

三、NUMA 感知调度

3.1 自动 NUMA 均衡

在多 NUMA 节点系统中，跨节点访问内存的延迟可能是本地节点的 2-3 倍。Linux 的自动 NUMA 均衡（AutoNUMA）通过周期扫描页表的 Access 位，计算每个页面的"节点亲和性"，并在合适时机将页面迁移到访问者所在的节点：

// mm/mempolicy.c / kernel/sched/fair.c 配合
// 核心流程（简化）
void task_numa_work(struct work_struct *work)
{
    // 1. 扫描进程的 VMA 区域
    // 2. 通过清除 _PAGE_ACCESSED 位标记页面
    // 3. 下一轮扫描时检查未被访问的页面
    // 4. 对 "主访问节点" 与当前节点不同的页面执行迁移
    migrate_misplaced_pages_mm(mm, ...);
}

内核提供关键可调参数：

# 启用/禁用自动 NUMA 均衡
sysctl kernel.numa_balancing=1

# 扫描延迟（毫秒）— 新进程多久开始扫描
sysctl kernel.numa_balancing_scan_delay_ms=1000

# 扫描周期（毫秒）
sysctl kernel.numa_balancing_scan_period_min_ms=100
sysctl kernel.numa_balancing_scan_period_max_ms=60000

3.2 NUMA 调度实践中的模式

对于数据库和内存密集型应用，错误的 NUMA 配置可导致 30% 以上的吞吐量下降。常见的工程模式：

1. 手动绑定：numactl --cpunodebind=0 --membind=0 ./db_server 将进程绑定到 NUMA 0
2. Interleave 策略：numactl --interleave=all ./application 均匀分配跨节点内存
3. taskset 限定：taskset -c 0-7 ./worker 限定 CPU 范围，间接影响 NUMA 选择

// BPF 程序追踪 NUMA 迁移事件
// numa_migrate tracepoint
SEC("tracepoint/mm_numa_migrate")
int trace_numa_migrate(struct trace_event_raw_numa_migrate *ctx)
{
    u32 pid = bpf_get_current_pid_tgid() >> 32;
    bpf_printk("PID %d page migrate: from node %d to node %d\n",
               pid, ctx->from_node, ctx->to_node);
    return 0;
}

四、CFS 的局限与实时性挑战

尽管 CFS 在桌面和大多数服务器场景中表现优异，它在延迟敏感场景下面临三个核心挑战：

1. 无显式截止时间保证：CFS 不感知任务周期或 deadline，无法保证最坏情况延迟边界。交互式应用偶尔出现的"jank"（帧卡顿）源于此。
2. 唤醒抢占不公平：新唤醒的任务因 vruntime 被设为 min_vruntime（或更低的睡眠补偿），可能长时间霸占 CPU，导致已有任务饿死。
3. cgroup 层级权重传递损耗：多层 cgroup 嵌套时，带宽控制的时钟漂移导致约束不精确。

这些问题催生了 SCHED_DEADLINE 调度类（基于 EDF 算法）以及后来的 EEVDF 调度器。

五、EEVDF：下一代调度器设计

5.1 问题动机与核心算法

EEVDF（Earliest Eligible Virtual Delay First）在 Linux 6.6 被引入，作为 CFS 的补充调度类。它的核心创新在于将截止期（deadline）显式纳入任务属性，同时保留权重公平分配：

// 简化模型：每个任务维护三个时间量
struct eevdf_entity {
    u64 deadline;   // 计算得到的绝对截止期
    u64 vruntime;   // 虚拟运行时间（来自 CFS 权重）
    u64 vslice;     // 分配的 CPU 时间片
    u64 eligible;   // 何时变为就绪（eligible_time）
};

// 任务分配的 vslice
vslice = (delta_exec × weight) / cfs_rq->weight
// 截止时间
deadline = vruntime + vslice

// 调度规则：eligible_time != vruntime 时，可调度
//           否则按 eligible_time 排序选择

这与经典 EDF 调度器的区别在于：EEVDF 使用时间合格线（eligible time）替代物理就绪时间。当任务的 vruntime 被"追赶"（即任务等待时间超过 vslice），它的 eligible 时间早于当前时间，获得立即调度的机会。

5.2 内核实现要点

EEVDF 的内核实现复用 CFS 的数据结构框架，增加了时间合格线检查：

// 伪代码：EEVDF 任务选择
struct sched_entity *pick_next_eevdf(struct cfs_rq *cfs_rq)
{
    struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);
    struct sched_entity *se = rb_entry(leftmost, ...);

    // 检查最左侧任务是否已"合格"
    if (se->eligible <= rq_clock) {
        return se;  // 立即调度
    }
    
    // 从合格候选中取 eligible 最小的
    for_each_candidate_from_left() {
        if (candidate->eligible <= current_time)
            return candidate;
    }
    
    // 无合格候选，推进 min_vruntime
    advance_min_vruntime();
    return pick_earliest_eligible();
}

EEVDF 使用单一红黑树，以 eligible 为键排序，同时通过 vruntime 保证长期公平性。避免了 EDF 需要单独红黑树的额外开销。

5.3 实际收益与场景

从 Linux 6.6+ 内核的实测数据来看，EEVDF 在以下场景展现优势：

• 桌面交互延迟：4K 视频播放 + 编译任务场景下，帧延迟从 CFS 的 ~25ms 降至 ~12ms
• 虚拟化宿主机：混合负载中 vCPU 的调度延迟标准差降低约 40%
• 游戏：CPU 受限时，Low Framerate Compensation（LFC）更平滑

启用条件：需要内核 ≥ 6.6，且任务显式设置 SCHED_DEADLINE 或系统自动触发（部分发行版为桌面环境启用）。

# 手动检查当前调度策略
chrt -p $$  # 查看 SCHED_OTHER (CFS)

# 为特定任务设置调度策略
schedtool -F -p 90 -e ./realtime_task
chrt -r 90 ./realtime_task   # SCHED_RR

六、调度器性能观测与调优

6.1 Tracepoint 与 BPF 工具

现代 Linux 提供了丰富的调度器观测接口：

# 1. 查看系统事件记录
perf record -e sched:sched_switch -a sleep 10
perf script

# 2. BPF 工具集合（BCC/BPFtrace）
funclatency 'finish_task_switch'  # 记录上下文切换延迟
runqlat -mT 1                     # 每CPU运行队列延迟直方图（按毫秒）
runqlen -C                        # CPU 运行队列长度统计

# 3. sched_debug 查看调度域信息
cat /proc/sched_debug | grep -A 5 'cfs_rq'

# 4. kernelshark 查看调度热度图
trace-cmd record -e sched_switch -e sched_wakeup kernelshark

通过 sched_debug 可直接查看任务的调度器内部状态：

# cfs_rq 信息
cat /proc/sched_debug | grep -E "cfs_rq|exec_clock|min_vruntime"

# 单个任务信息
cat /proc/$(pidof myapp)/sched

6.2 关键内核参数调优

# CFS 调度粒度（减少上下文切换开销 → 吞吐优先）
sysctl kernel.sched_min_granularity_ns=10000000    # 10ms
sysctl kernel.sched_wakeup_granularity_ns=15000000  # 15ms

# 迁移成本（控制任务在 CPU 间迁移的倾向）
sysctl kernel.sched_migration_cost_ns=5000000       # 5ms

# NUMA 平衡
sysctl kernel.numa_balancing=1
sysctl kernel.numa_balancing_scan_delay_ms=500

# 能耗偏好（Intel P/E 核心调度）
sysctl kernel.sched_energy_aware=1

6.3 容器场景最佳实践

在 Kubernetes 或 Docker 环境中，调度器调优直接影响服务质量：

# CPU Manager: 静态策略，为独占 CPU 请求的 Pod 分配专用 CPU
apiVersion: machineconfiguration.openshift.io/v1
kind: KubeletConfig
spec:
  cpuManagerPolicy: "static"
  cpuManagerReconcilePeriod: "5s"
  topologyManagerPolicy: "single-numa-node"

# Pod 的 CPU request/limit 内核映射
# request → cpu.weight (cfs bandwidth + shares)
# limit   → cpu.max (cgroup v2 bandwidth)
cat /sys/fs/cgroup/kubepods/pod<uid>/cpu.weight
cat /sys/fs/cgroup/kubepods/pod<uid>/cpu.max

七、总结与展望

从 CFS 到 EEVDF，Linux 内核调度器经历了从纯按比例公平模型到融合显式时间保证的演进。CFS 通过 vruntime 和红黑树实现了高效的加权公平调度，NUMA 感知均衡进一步在多 socket 场景中释放了内存带宽潜力。EEVDF 的引入弥补了 CFS 在延迟保障方面的空白，为实时性要求严苛的场景提供了内核级支持。

展望未来，调度器的发展方向包括：

1. 异构核心调度：Intel 的 Thread Director + AMD 的 CPPC 权重集成
2. 机器学习的调度决策：利用强化学习动态调参
3. EEVDF 与 CFS 更深度的融合：在保持吞吐优势的同时提供可预测延迟
4. 能效优化的硬件反馈：基于 RAPL 的功耗感知调度

对于系统工程师而言，理解这些调度器的内部机制是诊断性能瓶颈和优化服务质量的根本前提。掌握 tracepoint 观测和 cgroup 调优技术，将理论转化为可量化的生产成果。

---

延伸参考：

• Linux 内核源码：kernel/sched/fair.c、kernel/sched/core.c
• Documentation/scheduler/ 内核文档
• Brendan Gregg 的《Systems Performance》第 6 章
• sched(7)、cgroups(7) 手册页