Linux 内核 CFS 调度器深度解析：完全公平调度的红黑树算法、虚拟运行时间计算与生产调优实战

完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核自 2.6.23 版本（2007 年）以来取代 O(1) 调度器的革命性进程调度器。CFS 的核心哲学是：模拟一个理想多任务处理器上的完美公平调度 —— 如果有 N 个进程，每个进程应精确获得 1/N 的 CPU 时间。这一理念通过红黑树（Red-Black Tree）数据结构和虚拟运行时间（Virtual Runtime, vruntime）的精妙配合得以实现。本文将从数据结构与算法层面深入剖析 CFS 的核心机制，涵盖红黑树键值选择、虚拟运行时间计算、调度粒度控制、cgroup 带宽限制、NUMA 负载均衡，以及生产环境中的调优策略与性能监控实践。

1. CFS 核心设计理念

之前的 O(1) 调度器使用 140 级优先级数组和 active/expired 双轮转机制，存在若干固有缺陷：低优先级进程饥饿补偿机制粗糙（sleeping fairness 依赖数组切换）、时间片预分配导致交互式进程响应延迟难以精确控制、多核负载均衡实现复杂且效率受限。CFS 从根本上改变了调度模型：

• 摒弃时间片概念：CFS 不预先分配固定时间片，而是维护每个进程的虚拟运行时间，始终选择 vruntime 最小的进程运行
• "理想多任务处理器"模型：在理想情况下，N 个可运行进程的 vruntime 应完全相同 —— 每个进程获得完全均等的 CPU 时间份额
• 无限精度可运行时间：任何一个可运行进程最终都会获得 CPU —— 不存在"时间片耗尽"导致的不公平问题
• 基于时间记账（time accounting）：通过高精度计时器精确追踪每个进程的实际 CPU 使用量

这一设计的数学表达极其简洁：对于权重为 w_i 的进程 i，在时间段 T 内应获得的 CPU 时间为 T × w_i / Σw_j。当所有进程权重相同时（默认 nice=0，权重1024），每个进程获得 T/N 的时间。

2. 红黑树：CFS 的核心数据结构

CFS 使用红黑树（rbtree）作为可运行进程队列。与 O(1) 调度器的链表+数组不同，红黑树提供了 O(log n) 的最坏情况插入/删除/查找性能。

2.1 树结构与键值选择

内核中的 CFS 红黑树以 sched_entity 结构体中的 vruntime 字段作为排序键值。每个 CPU（更准确地说，每个运行队列 cfs_rq）维护一棵独立的红黑树。树的最左节点（最小 vruntime）即为下一个被调度的进程。

struct cfs_rq {
    struct load_weight load;          // 运行队列总权重
    unsigned int nr_running;          // 可运行进程数
    u64 min_vruntime;                 // 队列最小 vruntime 基准值
    struct rb_root_cached tasks_timeline; // 红黑树根节点（增强 rbtree）
    struct sched_entity *curr, *next, *last, *skip;
    // ...
};

struct sched_entity {
    struct load_weight load;          // 进程权重
    struct rb_node run_node;          // 红黑树节点
    u64 vruntime;                     // 虚拟运行时间
    u64 exec_start;                   // 本次运行开始时间
    u64 sum_exec_runtime;             // 累计实际运行时间
    u64 prev_sum_exec_runtime;        // 上次切换前的累计运行时间
    u64 vdecay;                       // 衰减因子（用于唤醒抢占判断）
    // ...
};

关于红黑树的关键优化 —— 内核使用 rb_root_cached 增强版结构，额外缓存最左节点指针，使得获取下一个调度目标的操作变为 O(1)：直接读取缓存指针，而不需要执行 O(log n) 的树遍历。

2.2 虚拟运行时间（vruntime）计算

vruntime 是 CFS 公平性的核心度量标准。其更新公式位于 kernel/sched/fair.c 的 update_curr() 函数中：

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;                  // 重置起始时间
    
    // 核心：vruntime 增量 = 实际运行时间 × (NICE_0_LOAD / 当前进程权重)
    curr->vruntime += calc_delta_fair(delta_exec, curr);
    
    // 更新运行队列的最小 vruntime 基准
    update_min_vruntime(cfs_rq);
}

calc_delta_fair() 的数学本质：

static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    // 对于 nice=0 的进程（权重=NICE_0_LOAD=1024）：
    // vruntime = 实际运行时间 × 1 —— vruntime 等于实际时间
    
    // 对于更高优先级的进程（权重更大）：
    // vruntime = 实际时间 × (1024 / 权重)
    // 例如 nice=-20（权重=1277）：vruntime = 实际时间 × (1024/1277) ≈ 实际时间 × 0.8
    // 意味着高优先级进程的 vruntime 增长更慢，更容易被重新选中
    
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
    
    return delta;
}

这个公式的美妙之处在于：权重大（高优先级）的进程其 vruntime 增长速率低于权重小的进程，因此在红黑树中"向左移动"更慢，从而自然地被更频繁地选中运行。

2.3 权重与 nice 值的映射表

内核将 -20 到 +19 的 nice 值映射为特定权重，每级 nice 差异约为 10% 的 CPU 差异（即 nice 0 与 nice 5 的 CPU 分配比约为 100%:25%）：

此映射通过 sched_prio_to_weight[] 数组实现，定义在 kernel/sched/core.c 中，相邻权重比值约为 1.25（即 5/4）。

3. 调度决策与上下文切换

3.1 核心调度函数：pick_next_task_fair()

当需要选择下一个运行进程时，CFS 调度类的 pick_next_task 回调被调用。该函数直接读取红黑树最左节点：

static struct task_struct *pick_next_task_fair(struct rq *rq, struct task_struct *prev)
{
    struct cfs_rq *cfs_rq = &rq->cfs;
    struct sched_entity *se;
    
    if (!cfs_rq->nr_running)
        return NULL;  // 无 CFS 可运行进程（可能切到 RT/IDLE 调度类）

    do {
        se = pick_next_entity(cfs_rq);  // 取最左节点的 sched_entity
        // 处理组调度层次：如果 se 属于一个带宽限制的组，可能需要跳过
        set_next_entity(cfs_rq, se);    // 设置当前运行进程
        cfs_rq = group_cfs_rq(se);      // 递归处理子 cfs_rq
    } while (cfs_rq);
    
    return task_of(se);
}

static inline struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    // O(1) 读取缓存的最左节点
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    
    // 可跳过之前运行完的进程（_last/_next 优化）
    struct sched_entity *curr = cfs_rq->curr;
    if (curr && curr->on_rq) {
        // 保持当前进程如果其 vruntime 仍小于第二候选
        if (curr->vruntime - left->vruntime < sysctl_sched_wakeup_granularity)
            return curr;
    }
    
    return left;
}

3.2 上下文切换时的记账

put_prev_entity() 在进程被抢占或时间片到期时将其重新插入红黑树。关键细节：被抢占的进程（尚未完成的运行段）的 exec_start 不变，其 vruntime 已经通过 update_curr() 在被抢占时刻更新。这意味着进程不会因为其运行被分割而受到惩罚。

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    // 如果进程仍在运行队列中（被抢占但未阻塞）
    if (prev->on_rq) {
        update_curr(cfs_rq);  // 更新 vruntime
        // 更新负载贡献（用于负载均衡）
        update_load_avg(cfs_rq, prev, 0);
    }
    // 将进程插回红黑树（以其更新后的 vruntime 作为键值）
    __enqueue_entity(cfs_rq, prev);
}

3.3 新进程与唤醒进程的处理

新 fork 的进程继承父进程的 vruntime 会导致严重不公平——通常新进程的 vruntime 被设为当前 min_vruntime（队列基准值），确保它至少能运行到一个与其他进程相当的位置，而不至于永远排在队列末尾。

唤醒进程（从阻塞态恢复）的处理更为精妙——place_entity() 实现了"唤醒抢占"机制：

static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    
    if (initial) {
        // 新进程：设 vruntime = min_vruntime
        // （特殊的 fork 修正避免子进程被饿死）
        vruntime += sched_vslice(cfs_rq, se);  // 给一个初始延迟
    } else {
        // 唤醒补偿：给睡眠进程一个"lag"回退
        // 这意味着最近睡过的进程会被提前调度（interactive-friendly）
        vruntime -= sysctl_sched_latency / 2; // 唤醒抢占补偿
    }
    
    // 保证 vruntime 不小于 min_vruntime（避免过度补偿）
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

这种唤醒补偿机制是 CFS 对交互式进程自动友好的根本原因——频繁休眠的交互进程（如 X Server、终端）每次醒来都因补偿而提前被选中，而不需要任何启发式检测（不像 O(1) 调度器的 sleep_avg 机制）。

4. 调度粒度（Scheduling Granularity）

4.1 sched_latency 与 min_granularity

CFS 通过两个关键参数控制调度频率和最小运行时间：

// kernel/sched/fair.c（默认值，可调整）
const sysctl_sched_latency      = 24ms;   // 调度延迟目标
const sysctl_sched_min_granularity = 3ms; // 最小时间片
const sysctl_sched_wakeup_granularity = 4ms; // 唤醒粒度阈值

运行时间计算逻辑：

static u64 sched_period(unsigned long nr_running)
{
    // 目标：在 sched_latency 内轮转所有可运行进程
    // period = max(sched_latency, nr_running × min_granularity)
    if (nr_running > sysctl_sched_latency / sysctl_sched_min_granularity)
        return nr_running * sysctl_sched_min_granularity;
    return sysctl_sched_latency;
}

// 每个进程的切片时间
u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // slice = period × (se->weight / cfs_rq->load.weight)
    // 对于 nice=0 进程：slice = period / nr_running
    return calc_delta_fair(sched_period(cfs_rq->nr_running), se);
}


当 CPU 负载较低（< 8 个进程）时，每个进程在 24ms 内轮流获得 CPU；当负载较高（> 8 进程）时，调度周期自动扩展为 nr × 3ms，确保每个进程至少运行 3ms 再被抢占。

4.2 时钟中断与抢占检查

高频时钟中断（通常 250Hz 或 1000Hz，取决于 CONFIG_HZ）触发 scheduler_tick() → 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;
    
    // 更新负载平均值（PELT 算法）
    update_load_avg(cfs_rq, se, UPDATE_TG);
    
    // 更新 vruntime
    update_curr(cfs_rq);
    
    // 检查是否需要抢占
    if (cfs_rq->nr_running > 1) {
        // 如果当前进程的 vruntime 不是最小的（差距 > 1个粒度）
        // 设置 TIF_NEED_RESCHED 标志
        check_preempt_tick(cfs_rq, curr);
    }
}

check_preempt_tick 的判断条件：当前进程已运行时间 ≥ 其切片时间，或者比第二个候选用例多运行了 sysctl_sched_wakeup_granularity（默认 4ms），则标记抢占。

5. CFS 组成员调度与带宽限制

5.1 组调度（Group Scheduling）

CFS 通过 cgroup 的 cpu 子系统实现层次化调度。每个 cgroup 有一个 cfs_bandwidth 结构，限制该组在固定周期内可使用的 CPU 时间：

struct cfs_bandwidth {
    ktime_t period;          // 默认 100ms
    u64 quota;              // 周期内可用 CPU 时间（-1 = 无限制）
    u64 runtime;            // 剩余运行时间
    raw_spinlock_t lock;
    struct hrtimer period_timer;  // 周期重置定时器
    struct list_head throttled_cfs_rq; // 被限制的运行队列
};

当 cgroup 在周期内用完配额时，该 cgroup 下所有进程被放入 throttled_cfs_rq 列表（不再被调度），直到下一个周期定时器重置运行配额。系统管理员可以通过 /sys/fs/cgroup/cpu/<group>/cpu.cfs_quota_us 和 cpu.cfs_period_us 调整。

5.2 CFS Bandwidth Control 操作流程

# 限制 cgroup "batch_jobs" 使用不超过 2 个 CPU 核心
# 周期 100ms，配额 200ms = 2 个核心
mkdir /sys/fs/cgroup/cpu/batch_jobs
echo 100000 > /sys/fs/cgroup/cpu/batch_jobs/cpu.cfs_period_us
echo 200000 > /sys/fs/cgroup/cpu/batch_jobs/cpu.cfs_quota_us

# 将进程移入该 cgroup
echo $PID > /sys/fs/cgroup/cpu/batch_jobs/cgroup.procs

内核从 4.13 版本开始引入的 SCHED_IDLE 优先级是对带宽控制的补充——IDLE 优先级进程（优先级最低，弱于 nice=19）只在 CPU 无任何其他可运行进程时才执行，且受 CFS bandwidth 限制约束。


6. NUMA 感知与负载均衡

6.1 NUMA 拓扑下的运行队列划分

在多核/多 NUMA 节点系统中，CFS 不仅关注单个 CPU 的公平，还要处理跨 NUMA 节点的负载迁移。每个 NUMA 节点维护一个调度域（sched_domain）层次结构：

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 imbalance_pct;      // 触发均衡的不平衡阈值
    unsigned int nr_idle;            // 最近空闲 CPU 数
    // 各种标志：SD_LOAD_BALANCE, SD_BALANCE_NEWIDLE, SD_BALANCE_EXEC, SD_BALANCE_FORK
};

调度域层次通常为：DIE（同一裸片）→ MC（同一核心，共享 L2/L3）→ SMT（同一物理核的超线程）。越往下，迁移代价越低。

6.2 周期性负载均衡（load_balance）

定时中断触发 run_rebalance_domains() → rebalance_domains()：


IDLE 均衡（NEWIDLE）：空闲 CPU 主动从忙碌 CPU 拉取进程。这是最低延迟的均衡策略
SIBLING 均衡（BALANCE_PERIODIC）：当前最忙调度组从组内最闲 CPU 拉取
BALANCE_BUSY（BALANCE_BUSY）：每个可选忙 CPU 作为"拉取者"从其他 CPU 获取任务


负载均衡的关键度量是 load_avg（PELT 算法计算）而非简单的可运行进程数。PELT（Per-Entity Load Tracking）每个调度实体独立维护一个基于指数移动平均的负载值：

// PELT 衰减公式（32ms 半衰期）
load_avg = load_avg × y + load × (1 - y)
y = (1/2)^(1/32) ≈ 0.979  (每 1ms 衰减)

// contrib_avg = 当前贡献
// 对于运行中进程：load = se->avg.load_sum / se->avg.runnable_sum
// 对于睡眠进程：load 逐渐衰减

6.3 NUMA 自动均衡（AutoNUMA / Automatic Balancing）

Linux 通过 numabalancing 机制自动识别 NUMA 失衡——当某页面被远程（非本地 NUMA 节点）CPU 频繁访问时，内核会迁移页面到访问者的本地内存：

// sysctl 参数
kernel.numa_balancing = 1
kernel.numa_balancing_scan_delay_ms = 1000  // 新进程开始扫描延迟
kernel.numa_balancing_scan_period_min_ms = 2000
kernel.numa_balancing_scan_period_max_ms = 60000
kernel.numa_balancing_scan_size_mb = 256    // 每次扫描的页面大小

// 实际机制（基于页错误）：
// 1. 内核周期性扫描进程地址空间，将访问的页面标记为 "young"
// 2. 发生缺页中断时，检查页面是否在远程节点
// 3. 如果是远程访问，将页面迁移到本地内存
// 4. 同时考虑将进程本身迁移到页面所在的节点

这种基于访问频率的页面迁移避免了传统的静态 NUMA 绑定的僵化问题，但对于具有大规模随机内存访问模式的应用（如某些数据库），可能会因为持续迁移而降低性能。

7. PELT 算法详解

PELT（Per-Entity Load Tracking）是 CFS 负载均衡的数学基础。不同于之前跑平均（RQ-based），PELT 在 sched_entity 级别独立跟踪负载，提供了更细粒度的负载感知：

// PELT 的三个累加器（以 1024 为满负荷）
struct sched_avg {
    u64 last_update_time;  // 上次更新的时钟
    u64 load_sum;          // 累计衰减加权和（历史贡献）
    u64 runnable_sum;      // 累计衰减可运行时间（历史运行时间）
    u32 util_avg;          // 当前计算出的利用率（0-1024）
    u32 load_avg;          // 当前计算出的负载（0-1024）
};

// 衰减因子表（pre-computed）
static const u32 runnable_avg_yN_inv[] = {
    0xffffffff, 0xfa83b2da, 0xf5257d14, 0xefe4b99a, ...
    // 对应 (1/2)^(n/32) 的定点数乘法常量
};

// 每次更新（1ms 间隔）：
load_sum = (load_sum × decay) + (current_load × (1024 - decay));
load_avg = load_sum / 1024;           // 归一化
util_avg = runnable_sum / (period_ms × 1024); // CPU 利用率

PELT 的 32ms 半衰期意味着：一个 32ms 前开始睡眠的进程，其当前贡献仅为初始值的约 50%，约 96ms 后衰减到 ~12.5%。这种快速衰减特性使得 CFS 能动态感知负载变化——一个从繁忙转为空闲的 CPU 能很快被 IDLE 均衡器发现。

8. 生产环境调优实战

8.1 调度延迟与交互式服务

# 场景：Web 服务器（高交互性，需要低延迟）
echo 1000000 > /proc/sys/kernel/sched_latency_ns      # 10ms（假设 HZ=250）
echo 1000000 > /proc/sys/kernel/sched_min_granularity_ns
echo 500000 > /proc/sys/kernel/sched_wakeup_granularity_ns
echo 0 > /proc/sys/kernel/sched autogroup_enabled     # 关闭 autogroup（减少干扰）

# 或者通过 systemd 配置（推荐）
# /etc/systemd/system.conf:
# CPUAffinity=0-3
# 通过 taskset/numactl 绑定核心

8.2 批处理/离线任务与资源隔离

# 场景：离线批处理任务（限制影响其他服务）
# cgroups v2
mkdir /sys/fs/cgroup/batch
echo "200000 100000" > /sys/fs/cgroup/batch/cpu.max  # 200ms/100ms = 2 CPUs
echo "max 100000" > /sys/fs/cgroup/batch/memory.max   # 内存上限 100GB

# 使用 systemd 创建 slice
# /etc/systemd/system/batch-jobs.slice:
# [Slice]
# CPUQuota=200%
# MemoryMax=100G
# IOWeight=50

# 使用 SCHED_IDLE 优先级（最低影响）
chrt -i 0 batch_processor

8.3 高性能计算 / 低延迟金融系统

# 场景：高频交易系统（要求最低尾延迟）
# 1. CPU 隔离（isolcpus + nohz_full + rcu_nocbs）
#    kernel 参数: isolcpus=2-15 nohz_full=2-15 rcu_nocbs=2-15
#
# 2. 禁用 irqbalance，通过 /proc/irq/*/smp_affinity 手动分配中断
#
# 3. 进程绑定+禁用 kernel 抢占
#    chrt -f 99 -p $PID  # FIFO 最高优先级（仅适用于硬实时要求）
#    或 chrt -r 99 -p $PID  # RR 最高优先级
#
# 4. 通过 cgroup 的 cpuset CPU 控制器固定内存节点
#    echo "2-7" > /sys/fs/cgroup/hft/cpuset.cpus
#    echo "0" > /sys/fs/cgroup/hft/cpuset.mems  # NUMA node 0
#
# 5. 关闭 scheduler 统计信息减少内核开销
#    echo 0 > /proc/sys/kernel sched_schedstats

8.4 容器化环境（Kubernetes/Docker）Best Practices

# Kubernetes CPU Manager 策略
# --cpu-manager-policy=static
# Guaranteed Pod（requests == limits）获得独占 CPU

# Pod 定义示例
resources:
  requests:
    cpu: "2"      # 2 个 CPU 的 CFS quota = period(100ms) × 2
  limits:
    cpu: "2"

# 注意事项：
# - Burstable Pod（requests < limits）可能遇到 CPU throttling
# - 使用 `kubectl top pod --use-protocol-buffers` 观察实际用量
# - 容器运行时 rlimit: RLIMIT_NPROC 可能影响 fork 密集型工作负载
# - cfs_period=100μs 时，cfs_quota 不应小于 period（否则无法调度）

# 监控 CPU throttling
# cat /sys/fs/cgroup/cpu/kubepods/burstable/podXXX/cpu.stat
# nr_throttled 457    # 被限制次数
# throttled_time 12.3s # 被限制总时间

9. 性能监控与诊断工具

9.1 perf sched —— 调度器专用 profiling

# 记录调度事件
perf sched record -- sleep 10

# 生成调度延迟报告
perf sched latency --sort max

# 典型输出：
#  TASK            |  Average Maximum   Maximum Maximum
#                  |   Delay    Delay    Delay    At
# -----------------+------------------------------------
#  (nginx)         |   0.006   0.247   3.429   1234.567 [s]
#  (mysqld)        |   0.089   2.104  15.678  4567.890 [s]

# 生成调度地图
perf sched map
# 可视化各 CPU 上运行进程的切换

9.2 ftrace 调度事件

# 追踪调度切换
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_switch/enable
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_migrate_task/enable
cat /sys/kernel/debug/tracing/trace_pipe

# 追踪 wakeup 延迟
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_wakeup/enable
echo 1 > /sys/kernel/debug/tracing/events/sched/sched_waking/enable

9.3 BPF/BCC 工具

# 使用 BCC 工具观察调度统计
# /usr/share/bcc/tools/runqlat —— 运行队列延迟分布
# /usr/share/bcc/tools/cpudist —— CPU 上的运行时间分布
# /usr/share/bcc/tools/offcputime —— 分析调度器外等待时间

# 追踪特定进程的 throttling
# /usr/share/bcc/tools/cpudist -p $PID

# 监控 CPU 频率与调度器的交互
# /usr/share/bcc/tools/cpuwalk

9.4 /proc 接口关键指标

# 进程级调度统计
cat /proc/$PID/sched
# vruntime:         1234567890    # 当前 vruntime
# sum_exec_runtime: 987654321     # 累计执行时间
# nr_switches:      45678         # 上下文切换次数
# nr_voluntary_switches: 40000    # 自愿切换（I/O 等待）
# nr_involuntary_switches: 5678   # 强制切换（被抢占）
# se.avg.load_sum:  8192          # PELT 负载总和
# se.statistics.block_start        # 开始阻塞时间戳

# 系统级调度统计
cat /proc/schedstat
# cpu0  version  15  timestamp  1234567890
#  0  0  2400000  1200000  0  0  0
#  (运行_yield_count, schedule_count, ...)

10. CFS 的演进：从 v3.x 到 v6.x

CFS 自 2007 年引入以来经历了持续演进：


2.6.24：引入 CONFIG_SCHED_DEBUG 和 sched_features 接口
3.14：引入 sched autogroup——自动为终端会话创建调度组，改善桌面响应性
4.13：完善 SCHED_IDLE 优先级
4.16：引入 UClamp（Utilization Clamping）——允许任务指定最小和最大 CPU 利用率需求，对 big.LITTLE 调度至关重要
5.19：引入 CFS Burst —— 允许 cgroup 在空闲 CPU 时积累 burst time，用于应对瞬时负载峰值
6.1：引入 sched/rsched 架构重构，改善多核扩展性
6.2：引入 Core Scheduling 的 co-routine 安全模型
6.5+：引入 EEVDF 调度器作为 CFS 的可选替代方案——解决 CFS 在极大负载下公平性漂移的问题


EEVDF：CFS 的继承者？

Earliest Eligible Virtual Deadline First (EEVDF) 被提议作为 CFS 的替代方案。与 CFS 基于红黑树不同，EEVDF 增加了 eligible time 和 deadline 概念：


eligible time：变为可运行的最早时间
deadline = eligible_time + slice：运行截止时间
vlice：当前运行时间下的虚拟截止时间


EEVDF 的核心保证是：所有可运行进程的 vdealine 不会被错过（在一个延迟边界内），解决了 CFS 在大规模负载下可能出现的"vruntime 缠绕"问题。然而，截至 6.6 内核，EEVDF 仍作为可选调度器存在，CFS 依然是默认选择。

11. 内核源码关键路径总结


功能
核心函数/文件
关键变量

vruntime 更新
fair.c:update_curr()
calc_delta_fair(), delta_exec
选择下一进程
fair.c:pick_next_task_fair()
__pick_first_entity()
插入红黑树
fair.c:__enqueue_entity()
rb_insert_cached()
从红黑树删除
fair.c:__dequeue_entity()
rb_erase_cached()
唤醒新进程
fair.c:enqueue_task_fair()
place_entity()（wakeup compensation）
时钟中断处理
fair.c:task_tick_fair()
check_preempt_tick()
负载均衡主循环
fair.c:run_rebalance_domains()
load_balance()
PELT 更新
fair.c:___update_load_sum()
runnable_avg_yN_inv[]
Bandwidth 检查
fair.c:runtime_refresh()
cfs_bandwidth.timer



总结

Linux 内核 CFS 调度器用红黑树和虚拟运行时间构建了优雅而高效的进程调度系统。其核心创新 —— 用单调递增的时间轴替代传统时间片轮转，用权重比例替代优先级固定分配，用 PELT 衰减感知替代简单的负载平均 —— 使得 CFS 在多样化的工作负载下（批处理、交互式、实时混合）都能提供可预测的性能。对于生产系统工程师而言，理解 CFS 的数学模型（vruntime = 实际时间 × NICE_0_LOAD/权重）和调度域层次结构，是进行 CPU 容量规划、容器资源限制设计、NUMA 亲和性优化的理论基础。随着 EEVDF 的逐步成熟和 UClamp 在移动/IoT 领域的广泛应用，Linux 调度器的演进仍在继续。