Linux 内核 CFS 调度器深度实战：从完全公平到实时调度的全链路剖析

一、调度器架构全景

Linux 操作系统的核心职责之一是在多个进程之间高效、公平地分配 CPU 资源。作为内核最复杂的子系统之一，进程调度器直接决定了系统的吞吐量、响应时间和资源利用率。从早期的 O(n) 调度器到 2.6 引入的 O(1) 调度器，再到 2.6.23 革命性的 CFS（Completely Fair Scheduler），Linux 调度器的演进历程本身就是一部操作系统发展史。

CFS 由 Ingo Molnár 设计，其核心哲学极其优雅：模拟一个"完全公平"的理想多任务处理器。在一个理想的、拥有无数个 CPU 的完美机器上，每个进程都应该获得 1/N 的 CPU 时间——每个进程都能在尽可能短的时间内执行完毕。CFS 的目标就是在只有一个实际 CPU 的现实世界中，尽可能逼近这个理想状态。

与现代调度器架构相比，Linux 引入了一个分层的调度类（Scheduler Class）框架：

• stop_sched_class：最高优先级，用于 CPU 热插拔、migration 等关键操作
• dl_sched_class：Deadline 调度类，基于 EDF（Earliest Deadline First）算法，满足硬实时需求
• rt_sched_class：实时调度类，支持 SCHED_FIFO 和 SCHED_RR 策略
• fair_sched_class：CFS 调度类，普通进程的默认调度器（SCHED_NORMAL / SCHED_BATCH）
• idle_sched_class：空闲调度类，当没有可运行进程时执行 idle 任务

调度器类的优先级从高到低排列，每个调度类通过链表注册到全局调度器框架中。这种模块化设计使得添加新的调度策略变得简单——只需实现约 20 个回调函数即可。

二、CFS 的红黑树时间模型

CFS 摒弃了传统的时间片（time slice）概念，转而使用一个全新的数据结构来追踪进程的"公平性"——红黑树（rbtree）。每个可运行的进程都位于这棵红黑树上，键值是该进程的虚拟运行时间（vruntime）。

核心数据结构 struct cfs_rq 管理着 CFS 的就绪队列：

struct cfs_rq {
    struct load_weight load;        // 队列总权重
    unsigned long runnable_weight;  // 可运行进程总权重
    unsigned int nr_running;       // 可运行进程数
    u64 exec_clock;                // 执行时钟
    u64 min_vruntime;              // 最小 vruntime（红黑树最左值）
    struct rb_root_cached runnodes; // 红黑树根节点
    struct sched_entity *curr;     // 当前执行实体
    struct sched_entity *next;     // 下一个要执行的（跳过唤醒抢占）
    struct sched_entity *last;     // 上一个执行的（记录执行时间补偿）
};

每个调度实体（struct sched_entity）嵌入在进程描述符 task_struct 中，包含以下关键字段：

struct sched_entity {
    struct load_weight load;    // 进程权重（与 nice 值相关）
    struct rb_node run_node;    // 红黑树节点
    u64 exec_start;             // 本次开始执行的时间
    u64 sum_exec_runtime;       // 累计执行时间
    u64 vruntime;               // 虚拟运行时间
    u64 prev_sum_exec_runtime;  // 上次切换出的累计时间
    // ...
};

vruntime 的计算公式是 CFS 的核心数学表达：

vruntime += (delta_exec * NICE_0_LOAD) / weight

其中 delta_exec 是实际运行时间，weight 是基于 nice 值查表得到的权重。这意味着低 nice 值（高权重）进程的 vruntime 增长更慢——在红黑树上更靠左，因此获得更多 CPU 时间。

CFS 调度决策极其简单：选择 vruntime 最小的进程执行。由于红黑树是有序结构，这个操作的时间复杂度仅为 O(1)——最左节点始终缓存在 cfs_rq->rb_leftmost 中。

三、Nice 值与 CPU 份额分配

Linux 的 nice 范围是 -20（最高优先级）到 +19（最低优先级），对应权重从 88761 递减到 15。CFS 使用一个预计算数组 sched_prio_to_weight[40] 将 nice 值映射到权重。

权重与 nice 值的换算关系为每差 1 个 nice 级别，CPU 份额变化约 10%（精确倍数为 1.25）。例如：

• nice 0 到 nice 1：后者获得前者的约 87.5%（100/112.5 约 0.889）
• nice -5 到 nice 0：后者的 CPU 份额是前者的约 3.125 倍（1.25 的 5 次方）

在多进程场景下，每个进程的 CPU 时间比例由以下公式决定：

time_i = (weight_i / sum(weight_all)) * sched_latency

其中 sched_latency 是目标调度延迟（默认 6ms），min_granularity 是最小颗粒度（默认 0.75ms）。当进程数量超过 sched_latency / min_granularity 时，CFS 会动态延长调度周期。

weight_from_nice() 函数实现了 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,
};

static inline int weight_from_nice(int nice) {
    return sched_prio_to_weight[nice + 20];
}

四、组调度与层级调度（cgroups）

CFS 通过"层级调度"机制支持 cgroup 级别的 CPU 资源控制。在 cgroup v1 中，cpu.shares 决定了该 cgroup 组相对于同层级其他组的 CPU 份额。

层级结构如下：

/sys/fs/cgroup/cpu/
├── user.slice/        (shares: 1024)
│   ├── user-1000.slice/
│   │   └── session-1.scope/
│   │       └── app-a.service/
├── system.slice/      (shares: 1024)
│   ├── systemd-journald.service/
│   └── cron.service/
└── machine.slice/     (shares: 1024)
    └── podmanUID.scope/

每个层级内的 CPU 份额按权重分配。system.slice 拥有 1024 shares，那么 systemd-journald 如果拥有 100 shares，它大约能分到该层级的 100/(100+50+...) 的 CPU 时间。

cgroup v2 使用 cpu.weight（默认 100，范围 1-10000）替代了 shares，计算更直观：

echo "80" > /sys/fs/cgroup/myapp/cpu.weight
echo "2000 1000000" > /sys/fs/cgroup/myapp/cpu.max

CFS 同时支持带宽控制（bandwidth control）：cpu.cfs_quota_us 和 cpu.cfs_period_us 可以在 cgroup 级别实现硬性的 CPU 时间限制。

调度实体可以"向上委托"——组调度通过 sched_entity 的 my_q 字段指向自己所属的 cfs_rq。当一个 SE 的 my_q 不为空时，说明它是一个代表一个调度组而非单个进程的"组 SE"。

五、调度器 tick 与抢占机制

CFS 在每个 tick 中断（通常为 250Hz 或 1000Hz）时调用 task_tick_fair()。核心逻辑极其简洁：

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

    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);
    }
    
    if (sched_feat(NONTASK_CAPACITY))
        update_load_avg(cfs_rq, se, UPDATE_TG);
}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *se, int queued) {
    // 1. 更新 vruntime 和负载统计
    update_curr(cfs_rq);
    
    // 2. 更新 cpu_load 用于负载均衡
    update_load_avg(cfs_rq, se, 0);
    
    // 3. 检查是否需要抢占
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, se);
}

check_preempt_tick() 是抢占决策的核心：

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr) {
    unsigned long ideal_runtime, delta_exec;
    struct sched_entity *se;
    s64 delta;

    // 计算当前进程应该运行的理想时间
    ideal_runtime = sched_slice(cfs_rq, curr);
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    
    // 如果已经运行超过理想时间片，标记需要抢占
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        return;
    }
    
    // 如果小于最小颗粒度，绝不抢占
    if (delta_exec < sysctl_sched_min_granularity)
        return;
        
    // 检查是否比最左邻居落后太多
    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;
    if (delta > ideal_runtime)
        resched_curr(rq_of(cfs_rq));
}

抢占的本质是：当一个进程连续运行时间超过其"公平份额"，或者其 vruntime 已经落后于最左邻居太多时，就会设置 TIF_NEED_RESCHED 标志，在下一次从内核态返回用户态时触发真正的上下文切换。

六、唤醒抢占与空闲调度

当一个睡眠进程被唤醒时（例如在 wake_up_process() 或 try_to_wake_up() 中），CFS 面临关键问题：是否应该抢占当前正在运行的进程？

check_preempt_curr() 函数处理这个决策：

static void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags) {
    const struct sched_class *class;
    
    if (p == rq->curr)
        return;
        
    // 遍历所有调度类，从最高优先级开始检查
    for_each_class(class) {
        if (class == &fair_sched_class)
            break;
    }
    
    if (p->sched_class < rq->curr->sched_class) {
        resched_curr(rq);
        return;
    }
    
    if (p->sched_class == rq->curr->sched_class) {
        if (p->sched_class->check_preempt_curr)
            p->sched_class->check_preempt_curr(rq, p, flags);
    }
}

place_entity() 对睡眠进程的 vruntime 做了关键处理：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial) {
    u64 vruntime = cfs_rq->min_vruntime;
    
    if (initial)  // 新创建进程
        vruntime += sched_vslice(cfs_rq, se);
    else          // 被唤醒的进程（补偿策略）
        vruntime -= sysctl_sched_latency;
    
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

这个设计非常精妙：被唤醒的进程会有一定的 vruntime"优惠"，使其有机会被快速调度。但这个优惠被限制在 min_vruntime - sched_latency 范围内，防止长时间睡眠的进程恶意抢占刚启动的高 vruntime 进程。

七、多核负载均衡与 NUMA 感知

在 SMP 和 NUMA 架构下，CFS 需要通过负载均衡确保各 CPU 核心上的负载均匀分布。负载均衡主要发生在三个场景：

1. tick 负载均衡：定期检查其他 CPU 的负载
2. 空闲负载均衡：CPU 即将空闲时主动拉取任务
3. NUMA 平衡：将进程迁移到靠近其内存访问的核心

负载均衡的核心数据结构是调度域（sched_domain）树：

DIE 域 包含 CPU0, CPU1, CPU2, CPU3

MC 域 包含 CPU0, CPU1 (在同一个 NUMA 节点)

NUMA 域 包含 Node0, Node1 (跨 NUMA 节点的负载均衡)

负载均衡的执行入口是 run_rebalance_domains()，通过 softirq 触发：

static void run_rebalance_domains(struct softirq_action *h) {
    struct rq *rq = this_rq();
    enum cpu_idle_type idle = rq->idle_balance ? CPU_IDLE : CPU_NOT_IDLE;
    
    for_each_domain(cpu, sd) {
        if (time_after_eq(jiffies, sd->last_balance + sd->balance_interval)) {
            if (load_balance(cpu, rq, sd, idle)) {
                break;
            }
            sd->last_balance = jiffies;
        }
    }
}

load_balance() 的执行逻辑：

1. 查找调度域中最繁忙的 CPU 组
2. 选择适合迁移的任务
3. 考虑缓存热度和 NUMA 亲和性
4. 执行 move_task_to() 完成迁移

Linux 6.x 引入了NUMA 失衡控制（NUMA Balancing）的改进版本：通过进程的 numa_faults 统计每个页面在不同 NUMA 节点被访问的频率，自动将页面迁移到访问频率最高的节点。

八、实时调度策略与 SCHED_DEADLINE

Linux 通过 sched_setattr() 系统调用支持三种实时调度策略：

策略	优先级	调度算法	适用场景
SCHED_FIFO	1-99（静态）	先进先出	确定性任务、简单实时
SCHED_RR	1-99（静态）	时间片轮转	需要公平性的实时任务
SCHED_DEADLINE	动态	EDF + CBS	多媒体、工业控制

SCHED_DEADLINE 是 Linux 3.14 引入的最先进的实时调度策略。它基于 EDF（Earliest Deadline First）算法，为每个进程定义三个参数：

• runtime (Q)：每次执行周期内允许的最大 CPU 时间
• deadline (D)：完成一次执行的截止时间
• period (P)：两次激活之间的最小间隔

SCHED_DEADLINE 内部使用 CBS（Constant Bandwidth Server） 算法进行准入控制：一个进程只有在我们能保证在其 deadline 前完成其 runtime 任务时，才会被接纳。

实时调度与 CFS 有严格的优先级关系：任何实时进程都可以无条件抢占 CFS 进程。

九、调度器性能调优与监控

生产环境中常见的 CFS 调优参数：

# 目标调度延迟（默认 6ms）
sysctl kernel.sched_latency_ns = 12000000

# 最小调度粒度（默认 0.75ms）
sysctl kernel.sched_min_granularity = 1000000

# 唤醒抢占粒度（默认 1ms）
sysctl kernel.sched_wakeup_granularity_ns = 2000000

# 迁移成本（影响负载均衡激进程度）
sysctl kernel.sched_migration_cost_ns = 500000

# NUMA 平衡（开启/关闭）
sysctl kernel.numa_balancing = 1

# 自动 NUMA 平衡扫描周期
sysctl kernel.numa_balancing_scan_delay_ms = 1000

诊断工具链：

• perf sched：可视化调度延迟和上下文切换
• /proc/schedstat：每 CPU 的调度统计信息
• /proc/<pid>/sched：单个进程的调度信息（vruntime、平均延迟等）
• bpftrace：使用 eBPF 脚本追踪调度器内部事件

案例一：高并发延迟敏感型应用：

sudo chrt -f 50 ./game-server

案例二：容器 CPU 隔离：

docker run --cpus="1.0" myapp
echo "max 100000 100000" > /sys/fs/cgroup/myapp/cpu.max

案例三：NUMA 绑核优化数据库性能：

numactl --cpunodebind=0 --membind=0 mysqld
taskset -c 0-15 mysqld

十、内核 6.x 调度器新特性

Linux 6.x 系列为调度器带来了多项重大改进：

Core Scheduling 改进：6.8 版本中，core_sched 改进了对 Intel 混合架构（P-core / E-core）的感知能力，通过 cpu.uclamp_min 和 cpu.uclamp_max 支持用户空间显式约束 CPU 频率。

P/E-core 感知调度：Intel Thread Director 支持使得 CFS 可以将计算密集型任务优先分配到 P-core，后台/中断密集型任务分配到 E-core。6.9 版本进一步增强了对 AMD 异构 CPU 的支持。

Latency Nice：io_latency_nice 补丁集被合入，允许进程声明自己的延迟需求（类似于 nice 值但独立于优先级），让调度器在 NUMA 平衡和负载均衡时参考。

sched_ext 进入稳定：从 6.12 开始，sched_ext 进入稳定阶段，Docker 和 systemd 开始支持通过 eBPF 替换默认调度器。

NUMA Balancing 优化：6.10 引入了 numa_balancing 的惰性模式，减少因 NUMA 迁移带来的性能波动。

十一、eBPF 对调度器的增强

Linux 5.x+ 中，eBPF 技术开始深度介入调度器，允许在运行时安全地影响调度决策。

sched_ext（Scheduler Extension）是 6.12 引入的革命性特性，允许用户空间自定义调度器：

SEC("ext_ops/select_cpu")
int select_cpu(struct task_struct *p, s32 prev_cpu, u64 wake_flags) {
    s32 cpu;
    cpu = bpf_get_idle_smp_processor_id();
    if (cpu >= 0)
        return cpu;
    return prev_cpu;
}

SEC("ext_ops/enqueue")
void enqueue(struct task_struct *p, u64 enq_flags) {
    struct task_ctx *ctx = bpf_task_storage_get(&task_ctx_map, p, 0, 0);
    if (ctx) {
        bpf_rq_set_latency_nice(p, ctx->latency_nice);
    }
}

sched_core（Core Scheduling）解决了多租户环境下的侧信道攻击问题。

eBPF 还提供了 BPF_PROG_TYPE_SCHED_CLS 和 BPF_PROG_TYPE_STRUCT_OPS 两类程序。

十二、总结与最佳实践

Linux CFS 调度器的设计哲学可以用三个关键词概括：

1. 公平（Fairness）：通过 vruntime 红黑树精确模拟理想多任务处理器
2. 效率（Efficiency）：O(log N) 入队，O(1) 出队，适合高并发
3. 灵活性（Flexibility）：模块化调度类架构，支持实时、截止期限、空闲等多种策略

从 2007 年合入主线至今，CFS 已经演进为支持数百个 CPU 核心、数千并发进程的企业级调度器。随着 eBPF、Core Scheduling 以及异构 CPU 支持的加入，Linux 调度器正从"内核硬编码策略"向"可编程调度框架"转变。理解 CFS 的核心机制，不仅是编写高性能应用的基础，更是深入 Linux 内核的必读篇章。

--EOF--