Linux CFS 调度器深度实战：从红黑树到 NUMA 感知调度

15 阅读 0 评论 0 点赞

引言

Linux 内核的 Completely Fair Scheduler (CFS) 是现代操作系统调度器设计的典范。自 2.6.23 内核版本引入以来，CFS 以其优雅的红黑树数据结构和虚拟运行时（vruntime）机制，彻底取代了传统的时间片轮转调度器，成为 Linux 默认的进程调度类。本文将深入剖析 CFS 的核心设计理念、数据结构实现、NUMA 扩展策略，以及如何通过 cgroup 和调度参数进行生产环境调优。

一、CFS 的设计哲学：完全公平调度

1.1 颠覆传统时间片

传统调度器（如 Linux 的 O(1) 调度器）基于固定时间片和优先级数组，存在"时间片耗尽"、"交互式进程识别滞后"等固有缺陷。CFS 的根本创新在于：不分配时间片，而是分配 CPU 使用比例。每个进程不再被分配"运行 X ms"，而是保证在调度周期内获得一定比例的 CPU 时间。

CFS 的核心公式可以简化为：

// 理想情况下每个进程应得的运行时间
ideal_runtime = sched_latency / nr_running

// 实际进程权重归一化
delta_vrun = (delta_exec * NICE_0_LOAD) / curr->se.load

其中 sched_latency 默认为 24ms，nr_running 为运行队列中的进程数。当进程数超过阈值时，调度周期会自动延长以提供最小时间片保障。

1.2 Nice 值与权重的映射

Linux 中 nice 值范围 -20 到 +19，对应权重从 88761 到 15。内核使用 sched_prio_to_weight[] 和 sched_prio_to_wmult[] 两个预计算表：

const int sched_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.25 倍，这意味着 nice +1 的进程比 nice 0 的进程少获得约 20% 的 CPU 时间。

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

2.1 为什么是红黑树？

CFS 选择红黑树作为运行队列的组织结构：

O(log n) 插入/删除：进程唤醒（enqueue_entity）和阻塞（dequeue_entity）都涉及树操作。

O(1) 最小值查询：最左侧节点就是 vruntime 最小的进程，通过 rb_leftmost 缓存实现。

高效的范围操作：pick_next_task_fallback 等场景可能需要遍历部分节点。

2.2 虚拟运行时（vruntime）的精确计算

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;

    if (unlikely(!curr)) return;

    delta_exec = now - curr->exec_start;
    if (unlikely(!delta_exec)) return;

    curr->exec_start = now;
    curr->sum_exec_runtime += delta_exec;

    // 关键：按权重折算虚拟运行时间
    curr->vruntime += calc_delta_fair(delta_exec, curr);

    // 更新整个 CFS 运行队列的最小 vruntime
    update_min_vruntime(cfs_rq);
}

其中 calc_delta_fair() 实现了按权重折算：vruntime = delta_exec * NICE_0_LOAD / se->load.weight。优先级高的进程权重更大，vruntime 增长更慢，因此能获得更多实际运行时间。

2.3 新进程的 vruntime 初始化策略

新创建的子进程若从 0 开始会过度抢占 CPU，因此：

初始 vruntime 对齐：place_entity() 中设置 INITIAL_VRUNTIME 为 cfs_rq->min_vruntime，确保新进程从队列中间位置开始排队。

fork 后惩罚：为防止 fork-bomb 攻击，子进程的 vruntime 会增加一个调度延迟。

三、调度触发与上下文切换

3.1 触发调度的时机

周期性调度 tick：每个 timer tick 调用 task_tick_fair()，检查当前进程的 vruntime 是否超过了已运行时长 + min_granularity。

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(DOUBLE_TICK))
        hrtick_start(rq, HZ/NSEC_PER_SEC);
}

唤醒抢占：当进程从阻塞状态唤醒（check_preempt_curr()），会比较被唤醒进程与当前运行进程的 vruntime。若被唤醒进程的 vruntime 小得多（超过 wakeup_granularity 阈值），则发生抢占。

3.2 上下文切换流程

当调度触发后，pick_next_task_fair() 执行：

1. 从 CFS 红黑树中取出最左侧节点（最小 vruntime）

2. 调用 __pick_next_entity() 从组调度中选出具体进程

3. 调用 context_switch() 切换内存地址空间和寄存器上下文

四、组调度（Group Scheduling）与层级 CFS

4.1 task_group 层次结构

CFS 引入了 task_group 概念，每个进程属于一个调度组，调度组本身也可作为 CFS 的调度实体参与父子调度：

struct task_group {
    struct cgroup_subsys_state css;
#ifdef CONFIG_FAIR_GROUP_SCHED
    struct sched_entity **se;          // 每个 CPU 一个调度实体
    struct cfs_rq **cfs_rq;            // 每个 CPU 一个 CFS 运行队列
    unsigned long shares;              // 该组的 CPU 份额权重
#endif
    struct rcu_head rcu;
    struct list_head list;
    struct task_group *parent;
    struct list_head siblings;
    struct list_head children;
};

4.2 带宽控制：cpu.cfs_quota_us

cgroup v1 的 CPU 子系统通过 cfs_period_us(默认 100ms)和 cfs_quota_us实现硬限流：

// 超过配额后 throttle 该组，直到下一个 period 恢复
static int tg_set_cfs_bandwidth(struct task_group *tg, u64 period, u64 quota)
{
    // 将配额转换为 per-CPU 的 runtime
    // 在 account_cfs_rq_runtime() 中实时扣减
}

生产环境中，这是容器 CPU 隔离的技术基础——Docker/K8s 的 CPU limit 最终映射到 cgroup 的 cfs_quota。

五、NUMA 感知调度

5.1 NUMA 架构下的调度挑战

在 NUMA 系统中，进程访问本地内存节点的延迟远低于跨节点访问。AutoNUMA 平衡机制从内核 3.13 引入：

1. 扫描阶段：内核定期扫描进程地址空间，收集各页面的访问计数

2. 迁移决策：若发现页面被另一 NUMA 节点的 CPU 频繁访问，标记为"迁移候选"

3. 页迁移：使用 move_pages() 或内核自动迁移将页面移到最常访问的节点

5.2 NUMA 调度域与负载均衡

Linux 的 SD（Sched Domain）层级结构从 MC 到 DIE 再到 NUMA 逐级进行负载均衡：

struct sched_domain {
    struct sched_domain *parent;    // 上层共享缓存域
    struct sched_domain *child;     // 下层更细粒度域
    unsigned long min_interval;     // 最小均衡间隔
    unsigned long max_interval;     // 最大均衡间隔
    unsigned int imbalance_pct;     // 触发均衡的不平衡阈值
};

numactl 和 set_mempolicy() 允许应用程序显式指定内存分配策略，配合调度器的 NUMA 亲和性实现最佳性能。

5.3 AutoNUMA 改进（kernel 5.x+）

较新内核中 AutoNUMA 引入了"慢速扫描"和"快速扫描"双模式：

慢速扫描（默认 1s 间隔）：全盘扫描，收集统计信息

快速扫描（触发后 200ms 间隔）：针对热点区域密集扫描，加速决策

六、生产环境调优实战

6.1 关键 sysctl 参数

kernel.sched_latency_ns：调度周期长度（默认 24ms），调高可提升吞吐但降低响应性
kernel.sched_min_granularity_ns：最小调度粒度（默认 3ms），防止进程频繁切换
kernel.sched_wakeup_granularity_ns：唤醒抢占阈值（默认 4ms），调低可提升交互响应性
kernel.numa_balancing：AutoNUMA 开关（0/1），密集型 NUMA 应用建议开启
kernel.sched_migration_cost_ns：防止进程被抢占后立即迁移的冷却时间（默认 500us）

6.2 cgroup 调优示例

# 为关键业务容器分配 2 个 CPU 的配额
mkdir /sys/fs/cgroup/cpu/critical-service
echo 200000 > /sys/fs/cgroup/cpu/critical-service/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/critical-service/cpu.cfs_period_us

# 使用 SCHED_FIFO 处理实时任务（需 root）
chrt -f 99 ./real-time-worker

# cgroup v2 的 CPU 权重设置
echo "max 200000 100000" > /sys/fs/cgroup/app/cpu.max
echo 100 > /sys/fs/cgroup/app/cpu.weight

6.3 性能监控工具

# 查看进程的 vruntime 和权重
cat /proc/<PID>/sched

# 查看 CFS 运行队列统计
cat /proc/sched_debug | grep -A 5 "cfs_rq"

# perf 分析上下文切换热点
perf stat -e context-switches,cpu-migrations -p <PID>

# bpftrace 追踪调度延迟
bpftrace -e 'tracepoint:sched:sched_switch { @ktime = nsecs; }
  tracepoint:sched:sched_wakeup /pid==TARGET/ {
    @wakeup_latency_us = (nsecs - @ktime) / 1000;
  }'

七、eBPF 与 CFS 的未来演进：sched_ext

Linux 6.x 内核中引入了 sched_ext（Scheduler Extensibility），允许通过 eBPF 程序自定义调度策略。这意味着开发者可以用 C 编写调度器逻辑，编译为 eBPF 字节码加载到内核，实现对 CFS 的扩展或替换。典型场景包括：

MLFQ eBPF：实现多级反馈队列的微型调度器
Cache-aware 调度：根据 LLC 缓存命中率做迁移决策
能耗感知调度：在异构大小核架构中优化能效比
定制化 QoS：为特定 workload 实现专用调度策略

八、总结

CFS 的红黑树 + vruntime 设计是操作系统调度理论的经典实践。理解 CFS 不仅有助于我们掌握 Linux 内核的工作机制，更是云原生时代容器调度优化的基础。在生产环境中，结合 cgroup 带宽控制、NUMA 亲和性策略和 eBPF 监控工具，能够构建出高性能、可预测延迟的调度体系。

对于需要深入了解的读者，建议阅读 Linux 内核源码中的 kernel/sched/fair.c（约 12000 行），这是理解调度器内部实现的权威资料。同时可参考 Documentation/scheduler/sched-design-CFS.rst 获取官方设计文档。

点赞(0) 打赏

本文分类：内存管理
本文标签：Linux内核 CFS 进程调度 NUMA 数据结构
浏览次数：15 次浏览
发布日期：2026-10-07 20:44:50
本文链接：https://www.ybb.press/kernel-mm/15721.html

Linux CFS 调度器深度实战：从红黑树到 NUMA 感知调度

引言

一、CFS 的设计哲学：完全公平调度

1.1 颠覆传统时间片

1.2 Nice 值与权重的映射

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

2.1 为什么是红黑树？

2.2 虚拟运行时（vruntime）的精确计算

2.3 新进程的 vruntime 初始化策略

三、调度触发与上下文切换

3.1 触发调度的时机

3.2 上下文切换流程

四、组调度（Group Scheduling）与层级 CFS

4.1 task_group 层次结构

4.2 带宽控制：cpu.cfs_quota_us

五、NUMA 感知调度

5.1 NUMA 架构下的调度挑战

5.2 NUMA 调度域与负载均衡

5.3 AutoNUMA 改进（kernel 5.x+）

六、生产环境调优实战

6.1 关键 sysctl 参数

6.2 cgroup 调优示例

6.3 性能监控工具

七、eBPF 与 CFS 的未来演进：sched_ext

八、总结

评论列表共有 0 条评论

发表评论取消回复

Linux CFS 调度器深度实战：从红黑树到 NUMA 感知调度

引言

一、CFS 的设计哲学：完全公平调度

1.1 颠覆传统时间片

1.2 Nice 值与权重的映射

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

2.1 为什么是红黑树？

2.2 虚拟运行时（vruntime）的精确计算

2.3 新进程的 vruntime 初始化策略

三、调度触发与上下文切换

3.1 触发调度的时机

3.2 上下文切换流程

四、组调度（Group Scheduling）与层级 CFS

4.1 task_group 层次结构

4.2 带宽控制：cpu.cfs_quota_us

五、NUMA 感知调度

5.1 NUMA 架构下的调度挑战

5.2 NUMA 调度域与负载均衡

5.3 AutoNUMA 改进（kernel 5.x+）

六、生产环境调优实战

6.1 关键 sysctl 参数

6.2 cgroup 调优示例

6.3 性能监控工具

七、eBPF 与 CFS 的未来演进：sched_ext

八、总结

eBPF 革命：从内核可编程到生产级可观测性实战

io_uring 异步 I/O 革命：从 epoll 终结者到生产级引擎进化之路

eBPF 内核可编程革命：从字节码引擎到生产级可观测性实践

Linux 内核内存管理机制深度解析：从伙伴系统到 Slab 分配器

评论列表 共有 0 条评论

发表评论 取消回复

评论列表共有 0 条评论

发表评论取消回复