Linux内核CFS调度器深度实战：从红黑树记账到NUMA负载均衡

引言

完全公平调度器（Completely Fair Scheduler, CFS）是Linux内核最伟大的设计之一。自2.6.23版本（2007年）取代O(1)调度器以来，CFS用优雅的红黑树算法实现了"完全公平"的理想调度模型。本文将从CFS的核心概念出发，深入剖析其数据结构、算法实现、NUMA扩展、cgroup集成，并最终给出生产环境的调优清单。

1. CFS核心思想：虚拟运行时间（vruntime）

CFS的核心哲学是：让每个可调度实体获得与其权重成正比的CPU时间份额。为了衡量"公平性"，CFS引入了虚拟运行时间（virtual runtime, vruntime）的概念。

vruntime的计算公式为：

vruntime  = delta_exec * (NICE_0_LOAD / weight)

其中：

• delta_exec：实体实际占用的CPU时间（由调度器tick更新）
• NICE_0_LOAD：nice值为0的进程权重（常量1024）
• weight：进程的实际权重（由nice值映射表决定）

这意味着：优先级越高（nice值越小）的进程，其vruntime增长越慢，从而获得更多的实际CPU时间。一个nice=0的进程vruntime与实际时间等速增长，而nice=19的进程vruntime增速是nice=0的36.6倍，自然就被"挤"到了后面。

2. 红黑树：CFS的高效数据结构

CFS使用红黑树（Red-Black Tree）来组织所有可调度实体，键值为vruntime。红黑树是平衡二叉搜索树，保证以下操作均为O(log n)：

• 插入：新唤醒的进程或新创建的进程被插入树中
• 删除：进程睡眠或退出时从树中移除
• 最左查找：选择vruntime最小的进程运行（完全公平！）

内核中CFS红黑树的关键数据结构定义：

// kernel/sched/sched.h
struct cfs_rq {
    struct load_weight load;          // 队列总权重
    unsigned int nr_running;          // 可运行实体数
    u64 min_vruntime;                 // 队列最小vruntime缓存
    struct rb_root_cached tasks_timeline;  // 红黑树根节点 最左节点缓存
    struct sched_entity *curr;        // 当前运行的实体
    ...
};

struct sched_entity {
    struct load_weight load;          // 实体权重
    struct rb_node run_node;          // 红黑树节点（键值=vruntime）
    u64 vruntime;                     // 虚拟运行时间
    u64 exec_start;                   // 本次调度开始时间
    u64 sum_exec_runtime;             // 累计实际执行时间
    u64 prev_sum_exec_runtime;        // 上次切换前的累计执行时间
    ...
};

min_vruntime是CFS的一个精妙设计：它记录队列中所有实体的最小vruntime。当新进程被唤醒时，其vruntime会被设置为max(sched_vslice计算值, cfs_rq-