Linux CFS 调度器深度解析：完全公平调度的实现原理与工程实践

引言

进程调度是操作系统的核心组件之一，它决定了哪个进程在何时获得 CPU 时间。在 Linux 内核的发展历程中，调度器的设计经历了多次重大变革。2.6.23 内核引入的 CFS（Completely Fair Scheduler，完全公平调度器）标志着调度设计理念的一次飞跃——从追求复杂的启发式算法转向简洁的数学公平模型。

本文将从调度器设计哲学出发，深入剖析 CFS 的核心数据结构、调度算法、组调度机制、负载均衡策略，并介绍 6.6 内核引入的 EEVDF（Earliest Eligible Virtual Deadline First）调度器，帮助读者全面理解 Linux 进程调度的工程本质。

一、从 O(1) 调度器到 CFS 的设计演化

1.1 O(1) 调度器的局限

在 2.6.23 之前，Linux 使用 O(1) 调度器。虽然它能在常数时间内完成调度决策，但存在以下核心问题：

• 启发式规则复杂：通过 interactive/非交互式的启发式判断赋予进程不同的优先级和奖励，代码维护困难
• 公平性难以保证：优先级粒度粗，不同 nice 值之间的 CPU 分配比例非线性
• 扩展性差：活动/过期数组的设计在多核场景下难以优雅扩展

1.2 CFS 的设计哲学

CFS 由 Ingo Molnár 提出，核心思想极其简洁：

"CFS 模拟了一个完全公平的多任务 CPU 下的调度行为——每个任务在极短的时间片内都能获得等量的 CPU 时间。"

这一哲学的关键推论是：CFS 不维护传统的时间片概念，而是通过虚拟运行时间（vruntime）来追踪每个进程的"应得"CPU 量。

二、CFS 核心数据结构

2.1 红黑树（rbtree）

CFS 使用红黑树来组织所有可运行进程，以 vruntime 作为排序键。红黑树提供了 O(log n) 的插入、删除和查找操作效率：

struct cfs_rq {
    struct load_load load;        // CFS 运行队列的负载权重
    unsigned long runnable_weight;
    unsigned int nr_running;     // 可运行任务数量
    unsigned int h_nr_running;   // 包含组调度的总数
    
    u64 exec_clock;              // 执行时钟
    u64 min_vruntime;            // 最小虚拟运行时间（红黑树最左端）
    struct rb_root_cached tasks_timeline; // 红黑树根节点（带缓存最左端）
    struct rb_node *curr;        // 当前运行任务
    struct rb_node *next;        // 下一个要运行的任务（用于抢占提示）
    struct rb_node *last;        // 刚刚完成的任务
    struct rb_node *skip;        // 需要跳过的任务（如设置了 SKIP）
    // ... 其他字段
};

2.2 调度实体（sched_entity）

每个进程（或调度组）在 CFS 红黑树中由一个调度实体表示：

struct sched_entity {
    struct load_weight load;     // 负载权重（基于 nice 值）
    unsigned long runnable_weight;
    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;   // 上次切换时的 sum_exec_runtime
    
    u64 migratios;               // 迁移次数统计
    // ... 其他字段
};

2.3 虚拟运行时间的计算

vruntime 的计算公式是 CFS 公平性的数学基石：

delta_vruntime = (delta_exec * NICE_0_LOAD) / weight

其中：
- delta_exec: 实际执行时间（纳秒）
- NICE_0_LOAD: nice 0 的权重基准值（1024）
- weight: 进程的调度权重（基于 nice 值查表得到）

权重越高的进程，每次实际执行积累的 vruntime 越慢，从而更频繁地被调度。

2.4 nice 值与权重的映射

Linux 内核使用预定义的权重表将 -20 到 19 的 nice 值映射到具体权重：

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 值（优先级提高），权重增加约 25%，这意味着高优先级进程获得约 1.25 倍的 CPU 时间。

三、CFS 调度算法详解

3.1 调度入口：pick_next_task_fair

当 CPU 需要选择下一个运行的进程时，CFS 调用 pick_next_task_fair()：

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    
    // 如果当前进程仍在运行队列且可运行，先将其放回
    if (prev_sched_entity)
        put_prev_task(rq, prev);
    
    // 选择红黑树最左端（vruntime 最小）的调度实体
    se = pick_next_entity(cfs_rq, NULL);
    set_next_entity(cfs_rq, se);
    
    return task_of(se);
}

3.2 选择下一个实体：pick_next_entity

CFS 默认选择 vruntime 最小的进程，但也会使用 "next" 指针进行优化：

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se;
    
    // 如果最左端就是当前进程，考虑使用 next/best 优化
    if (curr && (!left || entity_before(curr, left)))
        left = curr;
    
    se = left; // most left entity
    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;
    else if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;
    
    clear_buddies(cfs_rq, se);
    return se;
}

3.3 入队与出队操作

当进程状态变化时，需要在红黑树中进行插入或删除：

/* 将进程加入运行队列 */
static void enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
    bool curr = cfs_rq->curr == se;
    
    // 更新负载统计
    update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
    se_update_runnable(se);
    update_cfs_group(se);
    
    // 确保 vruntime 不小于 min_vruntime（防止新进程饥饿）
    if (!curr)
        __enqueue_entity(cfs_rq, se);
    se->on_rq = 1;
}

/* 将进程移出运行队列 */
static void dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
    update_curr(cfs_rq);
    update_load_avg(cfs_rq, se, 0);
    se_update_runnable(se);
    update_cfs_group(se);
    
    if (se != cfs_rq->curr)
        __dequeue_entity(cfs_rq, se);
    se->on_rq = 0;
    account_entity_dequeue(cfs_rq, se);
}

3.4 唤醒抢占策略

当一个进程被唤醒（如从 I/O 阻塞恢复）时，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;
    
    // 如果新唤醒的进程 vruntime 足够小，则允许抢占
    if (wakeup_preempt_entity(se, pse) == 1) {
        // 抢占当前进程
        resched_curr(rq);
    }
}

四、组调度（CGroup SCHED）机制

4.1 任务组层次结构

CFS 支持通过 CGroup 实现分层调度。每个 CPU 上维护一个 CFS 运行队列，运行队列中可以包含任务或任务组：

struct task_group {
    struct cgroup_subsys_state css;    // CGroup 子系统状态
    struct sched_entity **se;          // 每个 CPU 上的调度实体数组
    struct cfs_rq **cfs_rq;            // 每个 CPU 上的 CFS 运行队列数组
    unsigned long shares;              // 该任务组的 CPU 份额权重
    atomic_long_t load_avg;            // 负载平均值
    // ...
};

4.2 带宽控制（CFS Bandwidth Control）

Linux 通过 CFS bandwidth control 限制一个 CGroup 在指定周期内的 CPU 使用量：

struct cfs_bandwidth {
    ktime_t period;                    // 周期长度（默认 100ms）
    u64 quota;                         // 周期内可用的 CPU 时间
    u64 runtime;                       // 剩余可运行时间（可借入/借出）
    struct hlist_head throttled_cfs_rq; // 被限流的运行队列
    
    // 定时器，用于补充 runtime
    struct hrtimer period_timer;
    struct hrtimer slack_timer;
};

// 使用方法（Docker/K8s 等场景）：
// echo 100000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_period_us
// echo 50000 > /sys/fs/cgroup/cpu/mygroup/cpu.cfs_quota_us  // 限制为 0.5 核心

五、负载均衡策略

5.1 调度域（Sched Domain）

Linux 使用调度域的概念来描述 CPU 间的拓扑关系，从底层 SMT 线程到 NUMA 节点形成层次结构：

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;    // 不均衡阈值
    unsigned int cache_nice_tries; // 缓存友好尝试次数
    int flags;                     // SD_LOAD_BALANCE 等标志
    // ...
    unsigned long last_balance;    // 上次均衡时间
    unsigned int balance_interval; // 当前均衡间隔
    unsigned int nr_balance_failed;// 均衡失败次数
    // ...
};

5.2 负载均衡触发时机

负载均衡在以下时机被触发：

• IDLE 负载均衡：当 CPU 即将空闲时（schedule() 中进入 idle 前）
• 周期性负载均衡：通过 SCHED_SOFTIRQ 软中断定期检查
• 唤醒负载均衡：新进程唤醒时选择最合适的 CPU
• NUMA 负载均衡：在 NUMA 架构下将进程迁移到内存所在节点

5.3 迁移决策

load_balance() 函数决定是否需要迁移以及迁移哪些任务：

static int load_balance(int this_cpu, struct rq *this_rq,
                       struct sched_domain *sd, enum cpu_idle_type idle,
                       int *continue_balancing)
{
    // 1. 找到最忙的调度组
    // 2. 从该组中选择合适的 CPU
    // 3. 从最忙的 CPU 上选择可迁移的任务
    // 4. 检查迁移后是否改善不均衡
    
    struct lb_env env = {
        .dst_cpu   = this_cpu,
        .dst_rq    = this_rq,
        .sd        = sd,
        .idle      = idle,
        .tasks     = LIST_HEAD_INIT(env.tasks),
    };
    
    // 计算当前 CPU 的负载
    env.src_cpu = group_balance_cpu(&sds);
    
    // 如果负载差异小于阈值，无需迁移
    if (!idle && continue_balancing && !should_balance(...))
        return 0;
    
    // 选择要迁移的任务并执行迁移
    detach_tasks(&env);
    attach_tasks(&env);
    
    return env.nr_moved;
}

六、EEVDF 调度器：CFS 的继任者

6.1 EEVDF 的诞生背景

虽然 CFS 在大多数场景下表现良好，但在以下场景存在性能瓶颈：

• 大量任务竞争 CPU 时，vruntime 的全局一致性导致频繁缓存失效
• 延迟敏感型任务的唤醒抢占延迟不够精确
• 云计算场景中，"延迟承诺"（需要保证最小执行时间间隔）难以表达

2023 年，Linux 社区提出 EEVDF（Earliest Eligible Virtual Deadline First）作为 CFS 的替代方案，最终在 6.6 主线内核中合并。

6.2 EEVDF 核心概念

EEVDF 引入了三个关键概念来替代 vruntime：

1. 虚拟时间（Virtual Time, VT）: 进程开始服务时的基准时间
2. 虚拟截止时间（Virtual Deadline, VD）: VT + 每单位权重对应的延迟
3. 合格时间（Eligible Time, ET）: 进程至少等到此时间后才能被调度

6.3 ELIGIBLE 条件与延迟承诺

EEVDF 的核心创新是引入延迟概念。每个进程声明一个最小请求运行时间（q），计算得到：

VT_ELIGIBLE = (当前最小请求时间)  // 基准
VD = VT + (q / weight)           // 截止时间 = VT + 请求量/权重

条件：当且仅当 VT >= 当前全局虚拟时间 时，进程才是"有资格的"（eligible）

这样可以避免一个进程在获得一小段时间后又被另一个进程抢占，从而保证延迟平滑性。

6.4 EEVDF 的数据结构

EEVDF 同样使用红黑树，但排序键是虚拟截止时间而非 vruntime：

struct sched_entity {
    // ... 继承自 CFS 的字段
    
    // EEVDF 新增/变更字段
    u64 deadline;           // 虚拟截止时间（红黑树排序键）
    u64 vruntime;           // 仍用于负载计算
    u64 min_vruntime;       // 用于保持时间单调性
    
    // 延迟相关
    u64 slice;              // 时间片长度
    u64 min_slice;          // 最小时间片
    u64 vlag;               // 虚拟延迟累积
};

struct rb_root_cached runqueue; // 按 deadline 排序的红黑树

6.5 EEVDF vs CFS 实测对比

根据社区和业界的基准测试数据：

场景	CFS	EEVDF	改善
尾部延迟（P99）	较高	显著降低	-40% ~ -60%
高负载公平性	良好	更精确	≈15%
上下文切换开销	中等	优化红黑树	≈-20%
吞吐量（轻载）	高	持平	≈0%
RFC 延迟承诺	不支持	原生支持	新增

七、工程实践与性能调优

7.1 调度策略选择指南

策略	适用场景	标志
SCHED_NORMAL/OTHER	通用分时进程	CFS 默认
SCHED_FIFO	硬实时任务	FIFO 执行直到主动让出
SCHED_RR	软实时任务	带时间片的轮转
SCHED_BATCH	非交互后台批处理	CFS 但不唤醒抢占
SCHED_IDLE	极低优先级任务	仅空闲时运行
SCHED_DEADLINE	实时期限调度	EDF 算法

7.2 关键 sysctl 参数

# CFS 调度粒度控制
kernel.sched_min_granularity_ns = 1000000    # 最小调度粒度 1ms
kernel.sched_latency_ns = 8000000            # 调度延迟 8ms
kernel.sched_wakeup_granularity_ns = 1000000 # 唤醒粒度

# 负载均衡
kernel.sched_migration_cost_ns = 500000     # 迁移成本阈值
kernel.sched_nr_migrate = 32               # 单次迁移最大任务数

# NUMA 调度
kernel.numa_balancing = 1                   # 启用 NUMA 自动平衡
kernel.numa_balancing_scan_delay_ms = 1000  # 首次扫描延迟

7.3 实时场景配置实例

以音频处理系统为例，演示如何配置 SCHED_DEADLINE 实现精确调度：

#include <linux/sched.h>

struct sched_attr attr = {
    .size = sizeof(attr),
    .sched_policy = SCHED_DEADLINE,
    .sched_runtime = 50 * 1000 * 1000,   // 50ms 运行时间
    .sched_deadline = 100 * 1000 * 1000, // 100ms 截止时间
    .sched_period = 100 * 1000 * 1000,   // 100ms 周期
};

// sched_setattr() 设置属性

7.4 BPF 与调度器交互

现代 BPF 提供了与调度器深度集成的钩子：

// BPF 程序示例：在进程被切换走时记录
SEC("tp_btf/sched_switch")
int BPF_PROG(trace_sched_switch, bool preempt,
             struct task_struct *prev, struct task_struct *next)
{
    u32 prev_pid = prev->pid;
    u32 next_pid = next->pid;
    u64 ts = bpf_ktime_get_ns();
    
    // 将上下文切换事件发送到用户态
    struct event e = { .prev = prev_pid, .next = next_pid, .ts = ts };
    bpf_perf_event_output(ctx, &events, BPF_F_CURRENT_CPU, &e, sizeof(e));
    
    return 0;
}

7.5 性能监控与调试

排查调度相关性能问题的工具链：

# 查看进程的 vruntime 和调度统计
cat /proc/[pid]/sched

# 使用 perf 分析调度延迟
perf sched record -- sleep 1
perf sched latency

# 使用 ftrace 跟踪调度器决策
echo sched_switch > /sys/kernel/debug/tracing/set_tracer

# 使用 eBPF 工具 bcc 的 runqlat
/usr/share/bcc/tools/runqlat 1 10

# 查看调度组状态
cat /proc/sched_debug | grep "cfs_rq\|group"

八、总结与展望

Linux 调度器从 O(1) 到 CFS 再到 EEVDF 的演化，反映了一个持续追求的目标：在规模、公平性、实时性和能效之间取得最优平衡。

核心要点回顾：

• CFS：通过 vruntime 和红黑树实现了数学上的完全公平，是目前最广泛使用的通用调度器
• 组调度：通过层次化 CFS 运行队列支持容器化场景的 CPU 资源隔离
• 负载均衡：基于调度域的多层拓扑感知策略，优化了多核和 NUMA 系统的任务分布
• EEVDF：通过 deadline 排序和 eligible 条件，提供了更精确的延迟控制和延迟承诺能力

随着云计算和异构计算的发展，Linux 调度器仍在持续演进。未来的发展方向包括：异构 CPU 感知调度（大小核/TPU）、热插拔感知、能效优化、虚拟机场景的 host/guest 调度协同等。理解这些底层机制，将帮助开发者和系统管理员更好地驾驭 Linux 系统的性能表现。