Linux 内核 CFS 调度器深度实战：从 vruntime 到实时进程的全链路透视

引言：调度器 — 操作系统的"交通指挥官"

在 Linux 内核众多子系统中，调度器可能是最直接影响用户体验的组件之一。无论你是在运行一个高并发的 Web 服务器、一个低延迟的交易系统，还是在一个嵌入式控制板上读取传感器数据，调度器都在幕后做出千丝万缕的决策：哪个进程该获得 CPU？什么时候让出？如何保证公平？如何在满足实时性要求的同时最大化吞吐量？

Linux 的完全公平调度器（Completely Fair Scheduler，CFS）自 2.6.23（2007 年）引入以来，已经演变为一个高度精密的系统。本文将从数据结构、算法原理、性能优化、调试工具到硬件拓扑适应等多个维度，对 CFS 调度器进行一次全方位的深度剖析。

一、设计哲学：理想的、精确的多任务处理器

CFS 的设计基于一个简单而优雅的模型：假设存在一个"理想的多任务处理器"（ideal multitasking processor），它能同时将 CPU 时间公平地分配给所有 runnable 进程，每个进程获得 1/n 的 CPU 份额。现实中这样的硬件并不存在——CPU 核心数量是有限的，任何时刻一个核心上也只能运行一个任务。CFS 的目标就是无限逼近这个理想模型。

CFS 有几个核心设计原则：

• 公平性：每个 runnable 进程在一段时间窗口内获得的 CPU 时间应当与其权重成正比
• 低开销：调度决策本身必须是 O(log n) 甚至更快的操作
• 快速响应：交互式进程需要快速的唤醒和抢占能力
• 可扩展性：从单核嵌入式系统到数百核服务器都能高效运行

二、核心数据结构

2.1 task_struct 中的调度相关字段

每个进程在内核中由 task_struct 描述，其中与 CFS 调度器相关的关键字段包括：

struct task_struct {
    struct sched_entity    se;        // 每个调度实体的描述
    struct sched_rt_entity rt;         // 实时调度实体
    const struct sched_class *sched_class; // 调度类（fair/rt/deadline/idle）
    unsigned int           policy;     // 调度策略：SCHED_NORMAL/SCHED_FIFO/SCHED_RR/SCHED_DEADLINE
    int                    prio;       // 静态优先级 (0-139)
    int                    normal_prio;
    unsigned int           rt_priority; // 实时优先级 (0-99)
    int                    on_rq;      // 是否在运行队列上
    u64                     vruntime;   // 虚拟运行时间 ★核心字段
    u64                     exec_start; // 开始执行的时间戳
    u64                     sum_exec_runtime; // 累计实际运行时间
    u64                     prev_sum_exec_runtime; // 上次切换出去的累计运行时间
    // ...
};

2.2 sched_entity — 调度实体

sched_entity 是调度器管理的基本单位，可以属于一个 task、一个 task group 或一个 user（支持 group scheduling 时）：

struct sched_entity {
    struct load_weight  load;        // 调度实体的权重
    struct rb_node      run_node;    // 红黑树节点 ★
    struct list_head    group_node;  // 组调度链表节点
    unsigned int        on_rq;       // 是否在运行队列

    u64                 exec_start;
    u64                 sum_exec_runtime;
    u64                 vruntime;     // 虚拟运行时 ★
    u64                 prev_sum_exec_runtime;

    u64                 nr_migrations;

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity *parent;    // 上级调度实体
    /* rq on which this entity is to be queued: */
    struct cfs_rq       *cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq       *my_q;
#endif
};

load_weight 与进程的 nice 值对应。nice 值对应关系：nice 0 → weight 1024，每增加一个 nice 级权重变为原来的 0.8 倍，每减少一个 nice 级变为 1.25 倍。这意味着 nice -20 的进程获得的 CPU 时间约为 nice 0 的 11.3 倍（约 1024/90），而 nice 19 仅为 1/11.3。

2.3 cfs_rq — CFS 运行队列

每个 CPU 核心维护一个独立的 CFS 运行队列，通过 cfs_rq 结构管理：

struct cfs_rq {
    struct load_weight load;         // 运行队列总权重
    unsigned int nr_running;         // 可运行任务数
    unsigned int h_nr_running;       // 含子任务的总数

    u64 exec_clock;
    u64 min_vruntime;                // 队列中最小虚拟运行时 ★
    struct rb_root_cached tasks_timeline; // 按 vruntime 排序的红黑树 ★

    /*
     * 'curr' 指向当前运行任务的 sched_entity (NULL = 空闲)
     */
    struct sched_entity *curr, *next, *last, *skip;

    unsigned long runnable_weight;   // 可运行总权重

    struct rq *rq;                   // 所属的物理运行队列
    struct task_group *tg;           # 所属任务组（用于 cgroup）

    // ... load tracking 相关字段
    struct sched_avg avg;            // PELT 负载跟踪
};

2.4 红黑树 — CFS 调度器的基石

CFS 使用红黑树来维护所有 runnable 进程，以 vruntime 作为键值。红黑树的优点：

• 插入、删除、查找最小值操作均为 O(log n)
• 树的最左节点（rbtree_first_cached）始终是 vruntime 最小的进程，获得下一个时间片
• 无需额外维护"当前最小值"指针

关键操作：

// 选择下一个要运行的进程 → 取最左节点
static struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = cfs_rq->tasks_timeline.rb_leftmost;
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

// 进程入队 → 按 vruntime 插入红黑树
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link =