📚 课程目录第1章 CFS调度器概述

CFS完全公平调度参数调优：从默认值到生产环境 - 第1节

1.1 CFS设计哲学：从“时间片轮转”到“虚拟时间公平”

完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核 2.6.23 版本引入的默认调度器，其设计哲学彻底颠覆了传统基于固定时间片和优先级的调度模型。CFS 的核心目标不是“给每个进程分配一个时间片”，而是让每个进程在无限小的时间粒度上都能获得 CPU 的“公平份额”。

CFS 的公平性建立在 “虚拟运行时间”（vruntime） 概念之上。每个调度实体（进程或线程）都有一个 vruntime，它表示该进程在理想多处理器系统上已经运行的时间，并经过优先级加权。CFS 总是选择 vruntime 最小的进程来运行，从而确保所有进程的 vruntime 尽可能接近，实现“完全公平”。

  核心思想： 如果系统有 N 个可运行进程，CFS 的目标是让每个进程获得 1/N 的 CPU 时间。它不依赖固定的时间片，而是通过动态调整 vruntime 的增长速率来实现加权公平。

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

CFS 的实现依赖于两个关键数据结构：调度实体（sched_entity） 和 红黑树（rbtree）。红黑树是 CFS 的“就绪队列”，而调度实体是树中的节点。

1.2.1 调度实体（sched_entity）

每个可运行的进程（或线程组）在内核中对应一个 struct sched_entity 结构体。它记录了调度所需的核心字段：

字段	类型	说明
`load.weight`	unsigned long	进程权重，由 nice 值映射而来，决定 vruntime 增长速率
`vruntime`	u64	虚拟运行时间，CFS 调度的核心排序依据
`run_node`	struct rb_node	红黑树节点，用于将调度实体插入就绪树
`on_rq`	unsigned int	标记该实体是否在就绪队列上
`exec_start`	u64	当前调度周期开始的时间戳
`sum_exec_runtime`	u64	进程实际消耗的总 CPU 时间

1.2.2 红黑树（rbtree）

CFS 为每个 CPU 维护一棵红黑树，树中存储该 CPU 上所有可运行的调度实体。树的键值是 vruntime。红黑树是一种自平衡二叉搜索树，其特性保证了：

最左节点（vruntime 最小）就是下一个要运行的进程，查找时间复杂度为 O(1)。
插入和删除操作的时间复杂度为 O(log N)，其中 N 是就绪进程数。
树的高度始终保持在 O(log N)，不会退化为链表。

性能关键点： 当系统中有数千个进程时，红黑树的 O(log N) 插入/删除性能远优于 O(1) 调度器使用的链表遍历。这是 CFS 能够支撑高并发负载的基石。

1.3 CFS 与 O(1) 调度器的对比

O(1) 调度器是 Linux 2.6.0~2.6.22 版本的默认调度器，它使用多级反馈队列（140 个优先级队列）和位图来在 O(1) 时间内选择下一个进程。CFS 在多个维度上对其进行了革命性改进：

对比维度	O(1) 调度器	CFS 调度器
核心算法	固定时间片 + 优先级队列	虚拟运行时间 + 红黑树
时间复杂度	O(1) 选择进程，但交互性启发式复杂	O(log N) 插入/删除，O(1) 选择最左节点
公平性	基于时间片，高优先级进程可能“饿死”低优先级	基于 vruntime，所有进程按权重比例获得 CPU
交互性	依赖复杂的“交互性启发式”猜测进程类型	通过睡眠时间补偿自动处理交互进程
负载均衡	定期拉取/推送任务，开销较大	基于调度域（sched_domain）的层次化均衡
可调参数	大量 sysctl 参数，难以理解	参数精简（`sched_latency_ns`、`sched_min_granularity_ns` 等）
多核扩展性	全局运行队列锁竞争严重	每个 CPU 独立红黑树，锁粒度更细

生产环境启示： O(1) 调度器的“交互性启发式”在数据库、Web 服务器等混合负载下经常误判，导致 I/O 密集型进程响应延迟。CFS 通过 vruntime 机制天然解决了这个问题，这也是生产环境推荐使用 CFS 的根本原因。

1.4 关键代码路径：vruntime 更新与调度点

理解 CFS 的代码实现有助于后续参数调优。以下是最核心的 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 = now - curr->exec_start;

    // 更新实际运行时间
    curr->sum_exec_runtime += delta_exec;

    // 核心：根据权重计算 vruntime 增量
    // 权重越大（优先级越高），vruntime 增长越慢
    curr->vruntime += calc_delta_fair(delta_exec, curr);

    // 更新时间戳
    curr->exec_start = now;
}

// 调度点：选择下一个进程
static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq) {
    // 红黑树最左节点就是 vruntime 最小的实体
    struct rb_node *left = cfs_rq->rb_leftmost;
    struct sched_entity *se = rb_entry(left, struct sched_entity, run_node);

    // 检查是否需要跳过当前进程（组调度场景）
    if (cfs_rq->skip == se) {
        // 取次左节点
        se = __pick_next_entity(se);
    }
    return se;
}

调优切入点： calc_delta_fair() 函数中的权重映射直接受 nice 值影响。在生产环境中，通过调整 /proc/sys/kernel/sched_latency_ns 和 sched_min_granularity_ns 可以控制调度周期的长度，从而影响 vruntime 的累积速度。

1.5 本章小结

设计哲学： CFS 用“虚拟时间”替代“固定时间片”，通过让所有进程的 vruntime 趋于相等来实现加权公平。
数据结构： 红黑树以 vruntime 为键值组织就绪进程，提供 O(log N) 的插入/删除和 O(1) 的最左节点查找。
对比 O(1)： CFS 消除了复杂的交互性启发式，避免了优先级反转和饥饿问题，在多核环境下锁竞争更小。
调优基础： vruntime 的计算逻辑和调度周期参数是后续章节调优的核心对象。