Linux内核调度器CFS完全公平调度算法深度解析

引言

完全公平调度器（Completely Fair Scheduler，CFS）是Linux内核中用于调度普通进程（SCHED_NORMAL）的核心调度类。自Linux 2.6.23版本引入以来，CFS彻底取代了之前O(1)调度器，成为了Linux桌面和服务器系统中的默认调度器。CFS的设计哲学是"尽可能公平地分配CPU时间给所有可运行进程"，其核心思想不是通过时间片轮转，而是通过红黑树追踪每个进程的虚拟运行时间（vruntime）来实现理想化的精确公平。

本文将深入解析CFS调度器的核心数据结构、算法原理、NUMA负载均衡策略以及与实时调度器的交互机制，帮助用户全面理解Linux内核进程调度的底层逻辑。

1. CFS的核心设计理念

1.1 从O(1)调度器到CFS的演进

在CFS之前，Linux内核使用的是O(1)调度器。O(1)调度器通过运行队列中的活跃/过期数组来实现常数时间的调度决策，但这种设计存在几个根本性问题：

• 时间片固定粒度：O(1)调度器为每个进程分配固定大小的时间片，导致交互式进程的响应时间不稳定。
• 优先级调整算法复杂：为提升交互式进程体验，O(1)调度器引入了"睡眠/运行"启发式计算来动态调整优先级，该算法复杂且不准。
• 公平性难以保证：随着进程数量增长，不同优先级进程间的时间片差异导致不公平性放大。

CFS的提出者是Ingo Molnar，他的核心思想借鉴了"虚拟时钟"概念，提出了"谁在CPU上运行的时间最少，谁就最该运行"的原则。

1.2 CFS的基本原理

CFS不再使用时间片的概念，而是为每个进程维护一个虚拟运行时间（vruntime）。vruntime表示进程在CPU上运行的加权时间。调度时，CFS选择vruntime最小的进程优先运行。

这种设计的美妙之处在于：当进程数量趋于无穷时，任何进程获得的CPU时间比率趋近于1/N，实现了理论上的完全公平。

2. 核心数据结构

2.1 调度实体 sched_entity

在内核中，每个可调度的实体都内嵌一个sched_entity结构体：

struct sched_entity {
    struct load_weight  load;        // 调度权重（由优先级决定）
    struct rb_node      run_node;    // 红黑树节点
    u64                 vruntime;    // 虚拟运行时间（核心字段）
    u64                 exec_start;  // 本次开始执行的时间
    u64                 sum_exec_runtime; // 总的实际运行时间
    u64                 prev_sum_exec_runtime; // 上一次切换时的总运行时间
    // ...
};

关键运算关系如下：

// 虚拟运行时间增量 = 实际运行时间 * (NICE_0_LOAD / 进程权重)
delta_vruntime = delta_exec * (NICE_0_LOAD / se->load.weight)

权重越大的进程（优先级越高），vruntime增长越慢，从而获得更多的实际CPU时间。

2.2 运行队列 cfs_rq

每个CPU的运行队列中都有一个CFS私有的cfs_rq：

struct cfs_rq {
    struct load_weight  load;        // 队列总权重
    unsigned long       nr_running;  // 可运行进程数
    u64                 min_vruntime; // 队列中最小的vruntime（关键）

    struct rb_root      tasks_timeline;  // 红黑树根节点
    struct rb_node      *rb_leftmost;    // 最左侧节点（最快调度的进程）

    struct sched_entity *curr;  // 当前正在运行的调度实体
    // ...
};

2.3 红黑树：CFS的核心数据结构

CFS使用红黑树（rbtree）来组织所有可运行的调度实体，以vruntime作为排序键值。这种设计的优势在于：

• 查找最快进程 O(1)：通过rb_leftmost指针直接获取vruntime最小的节点。
• 插入新进程 O(log N)：红黑树的自平衡特性保证了插入效率。
• 删除进程 O(log N)：进程阻塞或退出时的删除操作高效。

// 将调度实体加入红黑树
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    u64 vruntime = cfs_rq->min_vruntime;

    // 选择合适的位置插入
    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(&se->run_node, &cfs_rq->tasks_timeline);
}

3. 虚拟运行时间（vruntime）机制

3.1 vruntime的计算公式

vruntime的计算是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;  // 实际执行时间
    curr->sum_exec_runtime += delta_exec;
    
    // 关键：计算虚拟运行时间增量
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    update_min_vruntime(cfs_rq);
}

calc_delta_fair的计算逻辑：

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    // NICE_0_LOAD = 1024 (nice值0对应的权重)
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

核心公式：vruntime增量 = 实际运行时间 × (1024 / 进程权重)

3.2 优先级与权重的映射

内核使用prio_to_weight数组将nice值（-20到19）映射为权重：

static const int 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,
};

可以看出，nice值每降低1级（优先级升高），CPU时间获取比率约增加10%。两个进程的CPU时间比率近似为 1.25^|nice差值|。

3.3 min_vruntime的妙用

每个cfs_rq维护一个min_vruntime字段，它记录了该运行队列中所有进程的最小vruntime。这个字段有两个关键作用：

• 新进程的vruntime校准：新创建的进程或唤醒的进程的vruntime不会从零开始，而是设为min_vruntime，防止"饥饿"新进程。
• 跨CPU迁移：进程在不同CPU间迁移时，通过min_vruntime保持公平性。

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
    struct sched_entity *curr = cfs_rq->curr;
    struct rb_node *leftmost = rb_first(&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);
}

4. 调度流程详解

4.1 主调度函数 schedule()

当系统需要重新调度时（显式调用schedule()或抢占点触发），内核会执行以下流程：

asmlinkage __visible void __sched schedule(void)
{
    struct task_struct *tsk = current;
    schedule_preempt_disabled();
    for (;;) {
        // 关闭中断，防止并发
        raw_spin_lock_irq(&rq->lock);
        
        // 从最高优先级调度类中选择下一个要运行的进程
        next = pick_next_task(rq);
        
        // 如果选出的进程与当前不同，执行上下文切换
        if (likely(prev != next)) {
            context_switch(rq, prev, next);
        }
        raw_spin_unlock_irq(&rq->lock);
    }
}

4.2 CFS的pick_next_task

pick_next_task_fair是CFS选择下一个运行进程的核心函数：

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;

    // 更新当前进程的vruntime
    update_curr(cfs_rq);

    // 如果当前进程仍在运行队列，则先将其放回红黑树
    if (cfs_rq->curr && cfs_rq->curr->on_rq)
        __enqueue_entity(cfs_rq, cfs_rq->curr);

    // 取出红黑树最左侧节点（vruntime最小 = 最该运行的进程）
    if (first = rb_first(...))
        se = rb_entry(first, struct sched_entity, run_node);
    
    // 设置下一个运行进程
    set_next_task_fair(rq, p);
    return p;
}

时间复杂度为 O(log N) 来自红黑树操作。若CPU支持，rb_leftmost缓存可提供 O(1) 的最左节点访问。

4.3 进程入队与出队

enqueue_task_fair — 进程变为可运行状态时调用：

static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &p->se;

    // 遍历rq层级结构的每个cfs_rq
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        // 更新vruntime统计
        update_curr(cfs_rq);
        // 将se加入红黑树
        __enqueue_entity(cfs_rq, se);
        // 更新cfs_rq统计
        update_load_avg(cfs_rq, se, UPDATE_TG);
        // 将se加入nr_running
        cfs_rq->nr_running++;
    }
    // 更新rq的总权重和h_nr_running
    add_nr_running(rq, 1);
    // 检查是否需要抢占当前进程
    if (flags & ENQUEUE_WAKEUP)
        check_preempt_curr(rq, p, flags);
}

dequeue_task_fair — 进程被阻塞时调用，操作的对称逆过程。

4.4 抢占机制 check_preempt_curr

当新唤醒的进程vruntime显著小于当前进程时，CFS触发抢占：

static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;
    struct cfs_rq *cfs_rq = task_cfs_rq(curr);

    // 如果新进程的vruntime - 当前进程的vruntime < 抢占粒度，则不抢占
    // 默认sched_wakeup_granularity_ns = 4ms，防止过于频繁的抢占

    // 否则，标记需要重新调度
    resched_curr(rq);
}

这种"懒惰抢占"策略在保证公平性的同时，避免了上下文切换开销过大。

5. NUMA感知与负载均衡

5.1 NUMA调度域层级结构

现代多核/多插槽系统中，CFS与SMP负载均衡深度结合：

struct sched_domain {
    struct sched_domain *parent;   // 上级域
    struct sched_domain *child;    // 下级域
    struct sched_group   *groups;  // 组的链表
    unsigned long min_interval;    // 最小均衡间隔
    unsigned long max_interval;    // 最大均衡间隔
    unsigned int  busy_factor;
    unsigned int  imbalance_pct;
    // ...
};

Linux内核构建了分层的调度域（sched_domain）：

┌──────────────────────────┐
│      DIE Domain          │  - 同一物理封装（socket）
│  ┌─────────────────────┐ │
│  │    MC Domain        │ │  - 同一NUMA节点（多核共享L3）
│  │  ┌─────────────────┐│ │
│  │  │ SMT Domain      ││ │  - 同一物理核的超线程
│  │  │ ┌─────────────┐ ││ │
│  │  │ │ Single CPU  │ ││ │  - 单个逻辑CPU
│  │  │ └─────────────┘ ││ │
│  │  └─────────────────┘│ │
│  └─────────────────────┘ │
└──────────────────────────┘

5.2 负载均衡流程

负载均衡以周期性方式运行：

 // 触发条件：
 // 1. 定时器中断（tick_load_balance）
 // 2. CPU空闲时（idle_balance）
 // 3. fork/exec时（newidle_balance）

load_balance(int this_cpu, struct rq *this_rq,
             struct sched_domain *sd, enum cpu_idle_type idle)
{
    // 1. 找出调度域中最忙的组
    // 2. 在组内找出最忙的CPU（源CPU）
    // 3. 如果源的负载 > 本地负载 + 阈值，则执行迁移
    // 4. 选择可迁移的进程（考虑缓存亲和性、NUMA亲和等）
    // 5. 调用move_tasks()实际迁移}

5.3 NUMA balancing（自动页迁移）

Linux 3.13引入的automatic NUMA balancing与CFS紧密配合：

• 页故障（page fault）采样，识别跨NUMA节点访问热点进程
• 将进程迁移到离其内存更近的CPU
• 同时迁移进程的物理页（migrate_on_fault）
• 通过numastat / proc/[pid]/numa_maps查看NUMA分布

6. 组调度（Group Scheduling）

6.1 cgroups与CPU控制器

Linux通过cgroups实现资源分组管理，CFS通过调度组（task_group/cgroup_sched_domain）来支持组级份额分配：

// 查看cgroup的CPU分配$ cat /sys/fs/cgroup/cpu/mygroup/cpu.shares1024  // 默认权重
$ cat /sys/fs/cgroup/cpu/mygroup/cpu.cfs_quota_us
50000  // 每周期最多使用50ms（50% CPU）
$ cat /sys/fs/cgroup/cpu/mygroup/cpu.cfs_period_us100000 // 周期100ms

6.2 两层调度：组间+组内

组调度的实现非常巧妙——在同一棵红黑树上同时维护两种实体：

• 任务级调度实体：普通task_struct内嵌的se
• 组级调度实体：task_group包含的se，它也拥有独立的cfs_rq和vruntime

这种统一的数据结构使得组间和组内的调度逻辑完全一致，代码复用度极高。

// 组调度的核心循环
do {
    // 1. 在当前层级中选择vruntime最小的实体
    se = pick_next_entity(cfs_rq);
        // 2. 如果选中的是组级实体，深入该组的子cfs_rq
    if (se->my_q) {
        cfs_rq = se->my_q;
        // 递归选择
        continue;
    }    // 3. 如果选中的是任务级实体，返回    break;} while (1);

6.3 CFS Bandwidth Control（带宽控制）

CFS Bandwidth Control实现了对每个cgroup的CPU使用硬限制：

• 周期（period）：通常为100ms，定义了一个时间窗口。
• 配额（quota）：在该周期内cgroup允许使用的最大CPU时间。
• 限制机制：当cgroup用尽配额，其中的进程被节流（throttle），直到下一个周期刷新。

// 节流实现
static int assign_cfs_rq_runtime(struct cfs_rq *cfs_rq)
{
    struct cfs_bandwidth *cfs_b = tg_cfs_bandwidth(cfs_rq->tg);
    // 尝试从全局带宽池分配时间
    if (cfs_rq->runtime_remaining <= 0) {
        // 向全局池申请        if (!__assign_cfs_rq_runtime(cfs_b, cfs_rq, ...))
            throttle_cfs_rq(cfs_rq);  // 节流
        return 0;
    }
    return 1;
}

这是Docker/Kubernetes CPU限制（--cpus=2）的底层实现。

7. 实时调度器与CFS的交互

7.1 调度类的优先级

Linux内核定义了多个调度类，CFS处理的SCHED_NORMAL（SCHED_OTHER）的优先级低于实时类：

 // kernel/sched/sched.h
extern const struct sched_class stop_sched_class;     // 优先级最高
extern const struct sched_class dl_sched_class;      // SCHED_DEADLINEextern const struct sched_class rt_sched_class;       // SCHED_FIFO/RRextern const struct sched_class fair_sched_class;     // SCHED_NORMAL（CFS）
extern const struct sched_class idle_sched_class;     // 优先级最低

这种链式结构使得pick_next_task按优先级遍历调度类：先检查stop，再dl，再rt，再fair（CFS），最后idle。实时进程总是优先于普通进程被选中。

7.2 SCHED_DEADLINE与CFS的共存

SCHED_DEADLINE（EDF算法）的引入改变了CPU时间分配的逻辑：

• DEADLINE任务执行期间不计入CFS配额
• 当DL任务预算耗尽时，降级为CFS调度
• CFS的min_vruntime计算会排除DEADLINE任务，保证它们的vruntime不会膨胀

8. CFS的调优与监控

8.1 关键sysctl参数

参数	默认值	说明
sched_latency_ns	24ms	调度周期，CFS尝试在周期内轮转所有进程
sched_min_granularity_ns	3ms	最小调度粒度，防止过度切换
sched_wakeup_granularity_ns	4ms	唤醒抢占粒度，大于此值才允许抢占
sched_migration_cost_ns	500μs	认为进程"热"的缓存阈值
sched_autogroup_enabled	1（桌面）	自动为会话创建调度组，提升交互式体验

8.2 /proc与调度器交互

# 查看进程的调度信息
$ cat /proc/[pid]/sched
cat (1234, #threads: 1)
-------------------------------------------------------------------
exec_start                                :       1234567890.123
sum_exec_runtime                          :             1234.567
vruntime                                  :          98765.432
nr_migrations                              :                  42
nr_voluntary_switches                      :                 567
nr_involuntary_switches                    :                  89
se.statistics.block_start                  :       1234567800.000
...# 查看运行队列状态
$ cat /proc/sched_debug | grep -A 5 "cfs_rq"
# 查看系统调度统计
$ cat /proc/schedstat
$ vmstat 1  # 关注cs（上下文切换）列

8.3 使用perf分析调度行为

# 记录调度事件
$ perf record -e sched:sched_switch -e sched:sched_wakeup -a sleep 10# 查看上下文切换数量
$ perf stat -e cs -a sleep 1# 生成调度时间线
$ perf script --trace=sched:sched_switch

9. CFS的演进与未来

9.1 EEVDF：CFS的继任者？

Linux 6.6引入了EEVDF（Earliest Eligible Virtual Deadline First）作为新的调度器框架选项。与CFS不同：

• 引入了明确的eligible time（合格时间）概念，更精确地建模"欠债"程度。
• 每个任务具有lag值 = vruntime - ideal_vruntime，更直接的公平度量。
• 理论上对高分辨率定时器更加友好。
• 目前是可选特性（CONFIG_SCHED_CLASS_EEVDF），CFS仍是默认。

9.2 持久化Intel P-state与schedutil

CFS通过PELT（Per-Entity Load Tracking）负载指标驱动CPU调频器schedutil：

• PELT使用指数移动平均计算每个调度实体的负载。
• schedutil以PELT负载作为CPU频率选择依据。
• Intel的HWP（Hardware P-states）可以直接使用PELT信息，实现硬件自主调频。

9.3 eBPF在调度器中的应用

Linux 5.13+引入了sched_ext（Scheduler Extensibility），允许通过eBPF实现自定义调度策略：

// eBPF程序可以:// 1. 拦截调度决策，覆盖默认行为
// 2. 收集调度统计信息
// 3. 实现特定负载的定制调度策略例如：scx_rustland、scx_lavd

这标志着Linux内核调度器进入了可定制化的时代。

10. 总结

CFS是Linux内核中最重要、最复杂的子系统之一。它的设计优雅地将公平性、效率性和可扩展性融为一体：

• 理论上的完全公平：通过vruntime的数学建模，极限情况下任何进程获得1/N的CPU。
• 工程上的实用性：红黑树O(log N)的复杂度，在数万进程下仍高效运行。
• 层次化的扩展性：通过cgroups、调度域、调度类，支持从嵌入式设备到大型服务器的全场景。
• 智能化的感知能力：NUMA感知、负载均衡、能耗感知，持续演进。

理解CFS不仅是理解Linux内核的一个关键窗口，更是理解现代操作系统调度设计的最佳案例。随着EEVDF、sched_ext等新机制的引入，Linux调度器将持续演进，以满足云原生、AI推理、实时计算等新兴场景的需求。

参考资料

• 《Understanding the Linux Kernel》，3rd Edition，Chapter 7
• Linux内核源码：kernel/sched/fair.c、kernel/sched/core.c
• Kernel Documentation: scheduler/ 目录下的文档
• Ingo Molnar, "Modular Scheduler Core and Completely Fair Scheduler"，2007