1. 首页
  2. 系统内核
  3. 系统编程

Linux 完全公平调度器（CFS）深度解析：从红黑树到虚拟运行时

2 阅读 0 评论

Linux 完全公平调度器（CFS）深度解析：从红黑树到虚拟运行时

引言

进程调度是操作系统内核最为核心的组件之一。自 Linux 2.6.23 内核版本起，完全公平调度器（Completely Fair Scheduler, CFS） 取代了传统的时间片轮转 O(1) 调度器，成为 Linux 默认的进程调度器。CFS 的设计哲学极为优雅：它不再追踪传统意义上的"时间片"，而是为每个进程维护一个虚拟运行时（Virtual Runtime, vruntime），并始终选择 vruntime 最小的进程来运行，从而实现数学意义上的"完全公平"。

本文将深入剖析 CFS 的核心数据结构、调度算法原理、组调度机制、负载均衡策略，并通过内核源码级分析揭示其工程实现细节，最后给出生产环境中的性能调优清单。

1. CFS 设计哲学："理想多任务处理器"模型

CFS 的构建基于一个理论模型：理想多任务处理器（Ideal Multitasking Processor）。在这种理想状态下，所有可运行进程都获得完全相等的 CPU 时间——若有 N 个进程，每个进程获得 1/N 的实际 CPU 时间。

现实中这种理想处理器并不存在，因此 CFS 让每个进程累积 vruntime，并总是调度 vruntime 最小的进程，以逼近理想状态：

进程的理想CPU时间 = 实际经过时间 × (进程权重 / 所有进程权重总和)

其中 权重（weight） 由进程的 nice 值决定，nice 值每降低 1，进程获得的 CPU 时间约增加 10%。

2. 核心数据结构：红黑树与调度实体

2.1 struct sched_entity

// include/linux/sched.h
struct sched_entity {
    struct load_weight  load;       // 权重，由 nice 值转换
    struct rb_node      run_node;   // 红黑树节点
    u64                 vruntime;   // 虚拟运行时（纳秒）
    u64                 exec_start; // 本次开始执行的时间
    u64                 sum_exec_runtime; // 总实际运行时间
    u64                 prev_sum_exec_runtime; // 上次切换时的总运行时间
    // ...
};

每个任务（task_struct）内嵌一个 sched_entity 成员，而非通过指针引用。这是 Linux 内核的一贯设计风格——用容器宏 container_of 从成员反推宿主结构体，省去一次指针间接寻址。

2.2 struct cfs_rq

// kernel/sched/sched.h
struct cfs_rq {
    struct load_weight load;        // 该队列总权重
    unsigned long runnable_weight;  // 可运行总权重
    unsigned int nr_running;        // 可运行进程数
    u64 min_vruntime;               // 队列中最小 vruntime（单调递增）
    struct rb_root_cached tasks_timeline; // 红黑树根节点
    struct sched_entity *curr;      // 当前正在运行的调度实体
    // ...
};

min_vruntime 是整个 CFS 中最精妙的设计之一。它是一个单调递增的值，代表该 CFS 就绪队列中曾运行过的最小 vruntime。新创建进程或被唤醒的进程会被赋予一个不小于 min_vruntime 的值，防止"新进程饥饿老进程"的问题。

2.3 红黑树：CFS 的核心索引

CFS 使用红黑树（Red-Black Tree） 来维护所有可运行进程，键值为 vruntime。红黑树保证了插入、删除和查找操作均为 O(log n) 时间复杂度。

最左侧节点（vruntime 最小）即为下一个应被调度的进程。内核通过 rb_first_cached 宏以 O(1) 时间直接取出最左节点：

// 取出 vruntime 最小的进程
struct sched_entity *se = __pick_first_entity(cfs_rq);
return se ? entity_task_of(se) : NULL;

3. 虚拟运行时的计算

3.1 核心公式

// 更新当前进程的 vruntime
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); // 转换为虚拟时间
    update_min_vruntime(cfs_rq);
}

calc_delta_fair 将实际运行时间转换为虚拟运行时间：

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    // 默认权重时，虚拟时间 = 实际时间
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    return delta;
}

公式本质：vruntime_增量 = 实际运行时间 × (NICE_0_LOAD / 进程权重)

  • nice=0（权重 1024）: 虚拟时间 == 实际时间
  • nice=5（权重 ~100）: 虚拟时间 ≈ 实际时间 × 10.24（跑同样的时间，vruntime 增长更快）
  • nice=-5（权重 ~3360）: 虚拟时间 ≈ 实际时间 × 0.31（跑同样的时间，vruntime 增长更慢）

3.2 时钟源与精度

Linux 使用 TSC（Time Stamp Counter） 或 HPET 作为高精度时钟源，以纳秒为单位记录时间。update_curr 在以下时机被调用：

  • 每次时钟中断（tick）
  • 进程被唤醒或阻塞时
  • 上下文切换时

4. 上下文切换与调度流程

4.1 主调度路径

// kernel/sched/core.c
static void __sched notrace __schedule(bool scheduling)
{
    struct task_struct *prev, *next;
    struct rq *rq;
    unsigned long switch_count;
    
    prev = rq->curr;
    
    // 1. 更新当前任务的 vruntime
    update_rq_clock(rq);
    
    // 2. 从红黑树中选择 vruntime 最小的任务
    next = pick_next_task(rq, prev, rf);
    
    // 3. 如果选中的不是当前任务，执行上下文切换
    if (likely(prev != next)) {
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;
        
        // 实际的上下文切换
        context_switch(rq, prev, next);
    }
}

4.2 pick_next_task 多类调度器协作

Linux 支持多种调度类（SCHED_CFS、SCHED_FIFO、SCHED_RR、SCHED_DEADLINE），pick_next_task 按优先级依次检查：

pick_next_task()
├── pick_next_task_dl()    // SCHED_DEADLINE（最高优先级）
├── pick_next_task_rt()    // SCHED_FIFO / SCHED_RR
├── pick_next_task_idle()  // SCHED_IDLE（最低优先级）
└── pick_next_task_fair()  // SCHED_CFS（默认）

这意味着实时任务（RT 调度类）永远比 CFS 任务优先被调度。

4.3 context_switch 的实现

上下文切换分为两部分：

  1. 切换内存空间（switch_mm）：如果新旧进程的地址空间不同，则更新 CR3 寄存器，刷新 TLB。
  2. 切换寄存器状态（switch_to）：汇编实现的寄存器状态保存与恢复，涉及通用寄存器、栈指针、指令指针等。
// arch/x86/kernel/process_64.c
__visible __notrace_funcgraph struct task_struct *
__switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
    // 保存 FPU/SSE 状态
    // 保存调试寄存器 DR0-DR7
    // 保存/恢复 MSR寄存器 (GSBASE, FSBASE,_KERNEL_GSBASE)
    // 切换栈指针和指令指针
    return prev_p;
}

5. 组调度（Group Scheduling / cgroups）

5.1 为什么需要组调度？

在单用户多进程场景下，CFS 实现了进程间的公平。但在多用户或容器化场景中，我们需要组之间的公平——比如确保用户 A 的所有进程和用户 B 的所有进程各获得 50% 的 CPU，而不管每组的进程数量。

组调度通过 cpu cgroup 实现，在 CFS 内部形成层级结构：每个 cgroup 拥有自己的 cfs_rq，组内的进程先在组内按 vruntime 竞争，再在组间按组级 sched_entity 竞争。

5.2 层级调度模型

cfs_root_rq
├── userA_cfs_rq (1024 份额)
│   ├── process_a1 (vruntime: 1500)
│   └── process_a2 (vruntime: 800)
└── userB_cfs_rq (1024 份额)
    ├── process_b1 (vruntime: 300)
    └── process_b2 (vruntime: 1100)

5.3 CPU shares 机制

通过 cpu.shares 文件（对应 cgroup v1）或 cpu.weight（cgroup v2）设置组的CPU份额权重：

# cgroup v1: 设置 CPU 份额
echo 2048 > /sys/fs/cgroup/cpu/mygroup/cpu.shares  # 获得 2x 权重

# cgroup v2: 设置 CPU 权重
echo 100 > /sys/fs/cgroup/mygroup/cpu.weight  # nice=0 对应值 100

6. 负载均衡：SMP 系统中的挑战

6.1 调度域（Sched Domain）与调度组（Sched Group）

在多核/NUMA 系统中，CFS 负载均衡通过调度域实现层次化管理：

NUMA Node / Socket
├── Sched Domain: LLC (Last Level Cache) domain
│   ├── Sched Group: CPU 0-3 (共享 L3 Cache)
│   └── Sched Group: CPU 4-7 (共享 L3 Cache)
├── Sched Domain: MC (Multi-Core) domain
│   ├── Sched Group: CPU 0-1
│   └── Sched Group: CPU 2-3
└── Sched Domain: SMT (Hyper-Threading) domain
    ├── Sched Group: CPU 0 (物理核)
    └── Sched Group: CPU 1 (超线程)

负载均衡从底层向上逐层检查，优先在最紧耦合的域内均衡，这样可以最大程度利用缓存局部性。

6.2 负载指标：PELT（Per-Entity Load Tracking）

Linux 3.8 引入的 PELT 算法为每个调度实体维护运行时间贡献的指数加权移动平均：

// 衰减因子以 32ms 为半周期，时间常数约 32ms
// 每次时钟中断更新
load_avg += load * (1 - y^n) + (衰减累计)

其中 y ≈ 0.978572（对应半衰期 32ms），表示越久远的运行贡献衰减越厉害。PELT 使负载均衡器能准确判断哪些 CPU 空闲、哪些过载。

6.3 负载均衡触发条件

  • 周期性均衡（load_balance）：每次时钟中断或调度器 tick 时触发
  • 空闲均衡（idle_balance）：某 CPU 进入 idle 时，从最繁忙的任务偷取任务
  • 唤醒均衡（wakeup balance）：新进程被唤醒时选择最合适的 CPU
  • NUMA 均衡（numa balancing）：扫描进程地址空间，将页面迁移到访问者所在 NUMA 节点

7. 调度延迟与抢占粒度

7.1 sched_latency / sched_min_granularity

CFS 定义了每个进程在一次调度周期内至少运行的时间：

sched_latency_ns    = 24ms (默认，当 CPU 上的进程数 >= 1 时)
sched_min_granularity = 3ms (默认最小运行时间)

每个进程的时间片 = sched_latency / nr_running
但最低不低于 sched_min_granularity

当进程数过多时（超过 sched_latency/sched_min_granularity = 8），每个进程只获得 sched_min_granularity，整个调度周期被拉长。

7.2 内核抢占与 PREEMPT

Linux 支持以下抢占级别：

  • PREEMPT_NONE：服务器模式，仅在内核返回用户态时抢占
  • PREEMPT_VOLUNTARY：自愿抢占点，减少延迟
  • PREEMPT：桌面模式，内核代码中大多数位置可抢占
  • PREEMPT_RT：实时模式，中断线程化、spinlock 替换为互斥锁

7.3 Wakeup Preemption（唤醒抢占）

当新进程被唤醒（如 I/O 完成）时，CFS 会检查抢占条件：

// check_preempt_wakeup
// 如果被唤醒进程的 vruntime 比当前进程小足够多，则抢占
gran = sysctl_sched_wakeup_granularity; // 默认 4ms
if (entity_before(se, pse) || (gran && wakeup_preempt_entity(se, pse) < 1))
    resched_curr(rq);

wakeup_granularity 的存在是为了防止过于频繁的切换——即使新进程的 vruntime 更小，如果当前进程运行的时间还不够一个"粒度"，则不抢占，以减少切换开销。

8. 生产环境调优清单

8.1 核心参数速查

参数默认值作用
kernel.sched_latency_ns24000000 (24ms)目标调度延迟（进程数少时）
kernel.sched_min_granularity_ns3000000 (3ms)最小运行时间
kernel.sched_wakeup_granularity_ns4000000 (4ms)唤醒抢占粒度
kernel.sched_migration_cost_ns500000 (0.5ms)任务迁移成本阈值
kernel.sched_autogroup_enabled1自动线程分组（桌面友好）
kernel.sched_cfs_bandwidth_slice_us5000 (5ms)CFS 带宽控制时间片
kernel.sched_rt_runtime_us950000 (95% for RT)RT进程最大占用比

8.2 高性能计算场景

# 减少调度延迟
sysctl -w kernel.sched_min_granularity_ns=1000000  # 1ms
sysctl -w kernel.sched_wakeup_granularity_ns=500000 # 0.5ms

# 禁用 autogroup（HPC/实时场景不需要桌面友好的自动分组）
sysctl -w kernel.sched_autogroup_enabled=0

# 隔离 CPU 核心（结合 isolcpus 内核启动参数）
taskset -c 2-7 ./hpc_workload

8.3 低延迟服务场景

# 减少整体调度周期（减少每进程最小时间）
sysctl -w kernel.sched_latency_ns=6000000  # 6ms
sysctl -w kernel.sched_min_granularity_ns=1000000  # 1ms

# 关键服务绑定 CPU + 实时优先级
chrt -f 50 ./critical_service  # SCHED_FIFO 优先级50
taskset -c 2 ./critical_service

8.4 容器化场景

# 查看容器的 CFS 带宽限制
cat /sys/fs/cgroup/cpu/docker/<container_id>/cpu.cfs_period_us   # 通常 100000
cat /sys/fs/cgroup/cpu/docker/<container_id>/cpu.cfs_quota_us    # 例如 200000 = 2核上限

# 设置 CPU 限制（cgroup v2）
echo "200000 100000" > /sys/fs/cgroup/mygroup/cpu.max  # 2核上限
echo "max 100000" > /sys/fs/cgroup/mygroup/cpu.max    # 1核上限

9. 监控与可观测性

9.1 常用观测工具

# perf sched 调度事件分析
perf sched record -- sleep 10
perf sched latency    # 查看每个任务的调度延迟分布
perf sched map        # 可视化 CPU 占用热力图
perf sched script     # 原始事件日志

# sched_debug
cat /proc/sched_debug | head -100  # 详细的调度器状态

# ftrace 调度跟踪
echo 1 > /sys/kernel/debug/tracing/events/sched/enable
cat /sys/kernel/debug/tracing/trace_pipe

# BPF 跟踪
bpftrace -e 'tracepoint:sched:sched_switch { printf("%s -> %s\n", args->prev_comm, args->next_comm); }'

9.2 关键统计指标

/proc/<pid>/sched 中包含：
- se.vruntime          : 虚拟运行时
- nr_switches          : 上下文切换总数
- nr_voluntary_switches: 自愿切换次数（等待I/O等）
- nr_involuntary_switches: 非自愿切换次数（时间片耗尽）

如果 nr_involuntary_switches 远大于 nr_voluntary_switches，说明进程可能计算密集且 CPU 资源不足，应考虑增加分配。

10. 总结与展望

CFS 自 2007 年发布以来，已经成为 Linux 生态中经过最充分验证的核心组件之一。其核心贡献在于：

  • 用虚拟运行时抽象替代了传统时间片，实现了数学层面的公平性保证
  • 用红黑树保证了 O(log n) 的选择效率
  • 通过组调度扩展支持了从单进程公平到容器/用户公平的多层级需求
  • PELT 算法为 SMP 负载均衡提供了精确的负载度量

近年来，CFS 在以下方向持续演进：

  • NUMA 感知调度：减少跨节点迁移，提高内存本地性
  • 调度器热补丁：通过 Livepatch 在不重启内核的情况下修复调度器 bug
  • EEVDF 调度器(Linux 6.6+)：逐步用 Earliest Eligible Virtual Deadline First 替代 CFS 的核心算法
  • BPF 可扩展调度器：允许用户态通过 BPF 实现自定义调度策略（scx）

调度器的演进不会停止——在异构计算（大小核、GPU/CPU 协同）、实时边缘、云原生负载多变等场景驱动下，Linux 调度器仍在不断突破性能与公平性的边界。

点赞(0) 打赏
Linux eBPF 深度工程实战：从内核探针到可观测性革命
Linux eBPF 深度工程实战：从内核探针到可观测性革命
Linux io_uring 深度工程实战：从系统调用瓶颈到零拷贝异步 I/O 革命
Linux io_uring 深度工程实战：从系统调用瓶颈到零拷贝异步 I/O 革命
Linux 内核 Livepatch 深度工程实战：从 ftrace 到零停机热补丁
Linux 内核 Livepatch 深度工程实战：从 ftrace 到零停机热补丁
Linux 完全公平调度器（CFS）深度解析：从红黑树到虚拟运行时
Linux 完全公平调度器（CFS）深度解析：从红黑树到虚拟运行时

评论列表 共有 0 条评论

暂无评论