Linux 内核 CFS 调度器深度实战：从 vruntime 到负载均衡的完整剖析

一、进程调度概述

进程调度是操作系统的核心职责之一——它决定了哪个进程在何时获得 CPU 时间片。Linux 内核作为一个通用操作系统内核，需要同时满足交互式应用的低延迟需求、批处理任务的高吞吐量需求，以及实时任务的确定性时间约束。为了应对这些截然不同的需求，Linux 内核设计了一套分层调度框架。

1.1 调度策略与调度类

Linux 内核通过 调度类（Scheduling Class） 机制实现了调度策略的分层管理。每个调度类负责一类进程的调度行为，优先级从高到低依次为：

SCHED_DEADLINE > SCHED_FIFO/SCHED_RR（实时类）> SCHED_NORMAL/SCHED_BATCH/SCHED_IDLE（CFS 类）> SCHED_IDLE（空闲类）

各调度策略的含义：

• SCHED_FIFO：先进先出实时策略，不使用时间片，进程一直运行直到主动放弃 CPU 或被更高优先级的实时进程抢占
• SCHED_RR：轮转实时策略，每个进程有时间片限制，时间片耗尽后排入同优先级队列末尾
• SCHED_DEADLINE：基于 Earliest Deadline First（EDF）的实时策略，适用于有明确截止时间要求的任务
• SCHED_NORMAL：普通分时策略，由 CFS 调度器管理，适用于大多数用户进程
• SCHED_BATCH：批处理策略，CFS 变体，倾向于让进程运行更长时间但抢占更不频繁
• SCHED_IDLE：空闲策略，仅当系统中没有任何其他可运行任务时才运行

1.2 实时优先级与 Nice 值

实时进程使用实时优先级（sched_priority），范围 1-99（数值越大优先级越高）。普通进程使用 Nice 值，范围 -20 到 19，Nice 值越小意味着更大的权重和更多的 CPU 时间。CFS 将 Nice 值映射为权重（weight），通过权重分配 CPU 时间比例。

1.3 task_struct 中的调度字段

Linux 内核中，每个进程的调度信息存储在 task_struct 结构体的子字段中：

struct task_struct {
    ...
    const struct sched_class *sched_class;  // 调度类
    struct sched_entity      se;            // CFS 调度实体（普通进程）
    struct sched_rt_entity   rt;            // RT 调度实体（实时进程）
    struct sched_dl_entity   dl;            // Deadline 调度实体
    unsigned int             policy;        // 调度策略
    int                      prio;          // 动态优先级
    int                      static_prio;   // 静态优先级（Nice 值衍生）
    int                      normal_prio;   // 基于 static_prio 和调度策略计算
    unsigned int             rt_priority;   // 实时优先级
    ...
};

值得注意的是，调度类通过函数指针表（sched_class）实现了策略模式：enqueue_task、dequeue_task、pick_next_task、task_tick 等操作都通过函数指针动态绑定，实现了调度策略的模块化扩展。

二、CFS 调度器的核心设计

2.1 vruntime：虚拟运行时间

CFS（Completely Fair Scheduler）的核心思想是公平——确保每个可运行进程获得与其权重成比例的 CPU 时间份额。为了实现这一点，CFS 引入了 vruntime（virtual runtime，虚拟运行时间） 概念：

vruntime += delta_exec * (NICE_0_LOAD / weight)

其中：

• delta_exec：进程实际运行的物理时间
• NICE_0_LOAD：Nice=0 对应的权重基准值（1024）
• weight：当前进程的权重（由 Nice 值换算）

关键点在于：权重越大的进程，每单位物理时间的 vruntime 增长越慢，因此被调度的频率更高。Nice=-20 的进程权重约为 88761，而 Nice=19 的进程权重仅为 15，这意味着前者获得的 CPU 时间约为后者的 5900 倍。

2.2 红黑树：可运行队列的实现

CFS 使用 红黑树（Red-Black Tree） 作为其可运行队列的数据结构。红黑树以 vruntime 为键值排序，保证：

• 查找最小 vruntime 进程（最左叶子节点）：O(log n)
• 插入新进程或唤醒睡眠进程：O(log n)
• 删除进程（睡眠或退出）：O(log n)
• 树的大小可以动态增长，没有固定数量限制

相比 O(1) 调度器使用的 140 级优先级数组 + 位图方案，红黑树牺牲少量常数级性能，换来了精确的公平性和更高的可扩展性。

// 核心数据结构关系
struct cfs_rq {
    struct rb_root_cached  tasks_timeline;  // 红黑树根节点（带最左节点缓存）
    struct sched_entity   *curr;            // 当前运行进程
    struct sched_entity   *next;            // 下一个要调度的进程（用于抢占）
    struct sched_entity   *last;            // 上一次调度的进程（用于上下文切换优化）
    unsigned int           nr_running;      // 可运行进程数
    u64                    min_vruntime;    // 树中最小 vruntime（作为偏移量避免溢出）
    ...
};

struct sched_entity {
    struct rb_node   run_node;     // 红黑树节点
    u64              vruntime;     // 虚拟运行时间
    u64              exec_start;   // 本次调度的起始时间
    u64              sum_exec_runtime;   // 累计执行时间
    u64              vruntime_remainder; // 除法余数（保证精度）
    ...
};

CFS 还缓存了红黑树的最左节点（rb_leftmost），使得选取下一个要调度的进程可以在 O(1) 时间内完成，这是性能优化的关键。最左节点就是 vruntime 最小的进程，也就是「欠」CPU 时间最多的进程。

2.3 调度粒度与抢占

CFS 的重要设计参数是目标延迟（target latency）和最小粒度（minimum granularity）：

• target_latency（默认 6ms）：希望轮转一遍所有可运行进程的目标时间。每个进程的理想时间片 = target_latency / nr_running
• min_granularity（默认 0.75ms）：最小时间片下限，当进程数过多时避免切换开销过大

这意味着：系统中有 4 个可运行进程时，每个进程获得约 1.5ms 的时间片；当可运行进程数超过 8 个时，最小粒度生效，每个进程至少运行 0.75ms。

抢占（Preemption）在以下时机触发：

• 时钟中断（tick）：检查当前进程的时间片是否耗尽
• 新进程唤醒：唤醒的进程 vruntime 较小，可能抢占当前进程
• 进程就绪态转换：阻塞的进程 I/O 完成变为就绪态

新一代内核的 PREEMPT_RT 补丁进一步完善了抢占模型，允许在几乎所有的内核代码路径中抢占，极大降低了实时任务的调度延迟。

三、CFS 调度器的上下文切换与核心流程

3.1 context_switch：上下文切换的代价

进程上下文切换（context switch）是调度器最昂贵的操作，主要包括：

1. 保存/恢复寄存器：包括通用寄存器、浮点寄存器、向量寄存器（SSE/AVX/NEON等）
2. 切换页表：加载新进程的页全局目录（PGD），触发 TLB 刷新
3. 切换内核栈：每个进程拥有独立的内核栈，栈指针（SP）切换
4. 切换浮点状态：惰性 FP 状态保存——仅在首次 FP 访问时真正保存/恢复
5. 刷新 TLB/缓存：地址空间切换导致大量的缓存/TLB 失效

Linux 内核通过多种手段优化上下文切换开销：

• 惰性 FPU 切换：检测 TS_USEDFPU 标志，仅在进程实际使用时才保存浮点寄存器
• 地址空间隔离：同一地址空间（线程）之间切换时，无需切换页表
• Lazy TLB：跨 CPU 唤醒线程时，避免不必要的 TLB Shootdown IPI
• PCID（Process-Context Identifiers）：Intel 处理器特性，允许多个 TLB 条目共存，减少刷新开销

3.2 __schedule 函数：调度核心

__schedule() 是调度器的核心函数，在中断返回、系统调用返回、以及显式调用 schedule() 时触发。其执行流程如下：

disable_preempt();
prev = rq->curr;
update_rq_clock(rq);  // 更新运行队列时钟

// 1. 处理当前进程的状态
if (!prev->state || prev->state & TASK_RUNNING) {
    // 仍然是可运行状态，放回运行队列
    put_prev_task(rq, prev);
} else {
    // 非可运行状态（阻塞/退出），从运行队列移除
    dequeue_task(rq, prev, ...);
}
// 2. 选择下一个要运行的进程
next = pick_next_task(rq, prev);

// 3. 如果选中了不同的进程，执行上下文切换
if (prev != next) {
    rq->nr_switches++;
    rq->curr = next;
    context_switch(rq, prev, next);
    // 到这里时，当前代码已经在新进程的内核栈上
}

值得注意的是，__schedule() 执行时是不可抢占的（preempt disabled），这是为了保护运行队列数据结构的一致性。

3.3 pick_next_task：多调度类协作

Linux 内核的 pick_next_task() 是一个多阶段选择过程，按照调度类优先级依次尝试：

// kernel/sched/core.c
static struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
    // 按优先级从高到低遍历调度类
    // stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

    if (prev)
        prev->sched_class->put_prev_task(rq, prev);

    for_each_class(class) {
        p = class->pick_next_task(rq, prev);
        if (p)
            return p;
    }

    // 只有 idle 类时返回 idle 进程
    return idle_sched_class.pick_next_task(rq, prev);
}

这种设计使得 Deadline 进程 > RT 进程 > CFS 进程 > idle 进程的优先级层次得以自然实现。当一个更高优先级的进程从阻塞中唤醒时，check_preempt_curr() 会判断当前进程是否需要被抢占。

四、多核调度与负载均衡

4.1 SMP 调度域架构

在多核系统中，每个 CPU 拥有独立的运行队列，但需要通过负载均衡机制在迁移进程间保持负载均衡。Linux 内核使用 调度域（Sched Domain） 层次结构管理多核拓扑：

• MC 域（Multi-Core）：共享最后一级缓存（LLC）的 CPU 核心组
• DIE 域（Die）：同一物理封装内的核心组
• NUMA 域：跨 NUMA 节点的全局根域

这种层次化设计使得内核可以先在最轻量的 MC 级域内做负载均衡（缓存亲和性好），再在更大范围的 NUMA 级域内做全局均衡。

4.2 负载均衡策略

触发负载均衡的时机包括：

1. 周期性均衡（load_balance）：在时钟中断中检查是否需要均衡
2. 空闲均衡（idle_balance）：CPU 空闲时主动从繁忙 CPU 拉取进程
3. 唤醒均衡（wake_affine）：进程唤醒时选择最佳 CPU
4. NUMA 均衡（numa_balancing AutoNUMA）：迁移进程使其内存访问尽量本地化

负载均衡的核心挑战是缓存亲和性与负载均衡的矛盾：将进程迁移到空闲 CPU 可以减少等待时间，但代价是 L1/L2 缓存失效。CFS 通过计算 CPU 的 avg_load_avg 和进程的 load_avg 决定何时迁移，以及迁移多少负载。

4.3 cgroup CPU 控制组

Linux 内核通过 cgroup（control group）机制实现了对进程组的 CPU 资源隔离和限制。对于 CFS 类进程，主要使用的 cgroup CPU 子系统包括：

• cpu.shares：定义 cgroup 组的权重比例，类似于 Nice 值组级版本。权重越高，组内进程获得越多 CPU 时间
• cpu.cfs_quota_us / cpu.cfs_period_us：限制 cgroup 在 period 时间内的最大 CPU 使用量。例如 quota=50000, period=100000 表示最多使用 0.5 个 CPU 核心
• cpu.cfs_burst_us（v2）：允许 cgroup 在空闲时积累 CPU credit，用于应对突发负载

这在容器化场景中至关重要——Docker/Kubernetes 通过 cgroup 实现对容器 CPU 资源的精确配额管理。

4.4 SCHED_DEADLINE：实时 EDF 调度

SCHED_DEADLINE 是 Linux 3.14 引入的调度策略，它基于 EDF（Earliest Deadline First）算法和 CBS（Constant Bandwidth Server）理论：

struct sched_attr {
    .sched_policy   = SCHED_DEADLINE,
    .sched_runtime  = 10 * 1000 * 1000,   // 10ms 运行时间
    .sched_deadline = 20 * 1000 * 1000,   // 20ms 截止时间
    .sched_period   = 20 * 1000 * 1000,   // 20ms 周期
};

SCHED_DEADLINE 的优势在于它通过 可调度性分析（schedulability analysis） 保证：只要系统总利用率不超过 100%（在单核上），每个 Deadline 进程都能在其截止时间前完成执行。这使其成为音视频处理、工业控制等场景的理想选择。

五、CFS 性能调优实战

5.1 调整进程优先级

通过 nice 和 renice 命令调整进程的 Nice 值：

# 以高优先级启动新进程
nice -n -20 ./high_priority_app

# 动态调整运行中进程的优先级
renice -n -5 -p $(pidof myprocess)

# chrt 调整实时调度策略
chrt -f 99 ./realtime_app    # SCHED_FIFO, 优先级99
chrt -r 50 ./realtime_app    # SCHED_RR, 优先级50
chrt -d --sched-runtime 10000000 --sched-deadline 20000000 --sched-period 20000000 0 ./deadline_app

5.2 调整调度器参数

关键的内核调度 sysctl 参数：

# 增大目标延迟（适合多进程场景，减少上下文切换开销）
sysctl -w kernel.sched_latency_ns=24000000

# 减小最小粒度（适合低延迟交互场景）
sysctl -w kernel.sched_min_granularity_ns=1000000

# 迁移成本阈值（NUMA 场景调大以减少跨节点迁移）
sysctl -w kernel.sched_migration_cost_ns=5000000

# AutoNUMA 平衡开关
sysctl -w kernel.numa_balancing=1

# 唤醒抢占粒度（调小以提高交互响应）
sysctl -w kernel.sched_wakeup_granularity_ns=4000000

5.3 CPU 绑核（CPU Affinity）

在某些高性能场景下，将进程绑定到特定 CPU 核心可以减少缓存失效和调度开销：

# 命令行绑核
taskset -c 0,1 ./my_app

# 代码中设置 CPU affinity
cpu_set_t cpuset;
CPU_ZERO(&cpuset);
CPU_SET(0, &cpuset);
CPU_SET(1, &cpuset);
sched_setaffinity(0, sizeof(cpuset), &cpuset);

# cgroup cpuset
mkdir /sys/fs/cgroup/cpuset/echo
echo "0-1" > /sys/fs/cgroup/cpuset/echo/cpuset.cpus
echo "0" > /sys/fs/cgroup/cpuset/echo/cpuset.mems
echo $(pidof myapp) > /sys/fs/cgroup/cpuset/echo/cgroup.procs

5.4 容器场景的 CPU 限制实践

Docker/Kubernetes 中常见的 CPU 限制配置：

# Docker 限制 2.5 核 CPU
docker run --cpus=2.5 --cpu-shares=512 my_image

# Kubernetes Pod 资源请求
resources:
  requests:
    cpu: "1000m"    # 1000 millicore = 1核
  limits:
    cpu: "2000m"

注意 cpu.shares（请求）和 cfs_quota（限制）的区别：shares 只是在竞争 CPU 时按比例分配，而 quota 是硬性上限。当容器使用量低于 limits 时，空闲的 CPU 时间可以被其他容器使用；但超过 quota 时，即使在 CPU 空闲时也会被节流（throttle）。