Linux 内核 CFS 调度器深度实战：完全公平调度算法全解析

一、从 O(1) 到 CFS——调度器的范式革命

Linux 内核的进程调度器经历了两次重大演变：O(1) 调度器（2.6.0 ~ 2.6.22）和 CFS 完全公平调度器（2.6.23 至今）。O(1) 调度器虽然以其常数时间复杂度著称，但它的时间片估算模型在交互式进程场景下表现不佳——经常导致桌面应用卡顿、响应延迟不稳定。

CFS（Completely Fair Scheduler）由 Ingo Molnár 设计，其核心哲学颠覆了传统思路：不分配时间片，而是分配 CPU 时间份额。CFS 的目标是让每个进程获得"完全公平"的 CPU 时间，没有进程会被"饿死"或"过度优待"。

CFS 的关键特性：

• 虚拟运行时（vruntime）：用红黑树追踪每个进程的"公平进度"，而非固定时间片
• O(log N) 调度复杂度：在运行队列中用红黑树高效选取最"亏欠"的进程
• NICE 值映射：通过权重因子将 nice 值转化为实际 CPU 份额，支持优先级调度
• 完美的 SMP 负载均衡：结合调度域实现 NUMA 感知的并行负载分配
• 组调度（Group Scheduling）：支持按用户/cgroup 分组实现层次化公平

二、核心数据结构

CFS 的实现非常精巧，主要涉及以下几个关键数据结构：

2.1 调度实体 struct sched_entity

// kernel/sched/sched.h
struct sched_entity {
    struct load_weight  load;       // 权重（由 nice 值决定）
    struct rb_node      run_node;   // 红黑树节点
    u64                 exec_start; // 本次开始执行的时间
    u64                 sum_exec_runtime; // 累计运行时间
    u64                 vruntime;          // 虚拟运行时
    u64                 prev_sum_exec_runtime; // 切换出去时的累计运行时间
    // ...
};

vruntime 是 CFS 的"心脏"——它衡量的是进程在虚拟时钟上的推进速度。高权重的进程（低 nice 值）vruntime 增长慢，因此在红黑树上更"靠左"，被更频繁地调度。

2.2 CFS 运行队列 struct cfs_rq

struct cfs_rq {
    struct load_weight load;       // 队列总权重
    unsigned int       nr_running; // 可运行进程数
    u64                exec_clock; // 该队列的虚拟执行时钟
    u64                min_vruntime; // 队列最小 vruntime（作为基准偏移量）
    struct rb_root     tasks_timeline; // 红黑树根节点
    struct rb_node     *rb_leftmost;   // 最左侧节点缓存（最快路径）
    // ...
};

2.3 task_struct 中的调度相关字段

struct task_struct {
    // ...
    int                     prio;           // 动态优先级 (0-139)
    int                     static_prio;    // 静态优先级 (nice 值转换)
    int                     normal_prio;    // 基于静态优先级和调度策略
    unsigned int            rt_priority;    // 实时优先级
    const struct sched_class *sched_class;  // 调度类
    struct sched_entity     se;             // 普通进程调度实体
    struct sched_rt_entity  rt;             // 实时进程调度实体
    // ...
};

三、vruntime——CFS 的数学基础

3.1 虚拟运行时的计算公式

vruntime 的计算是 CFS 能够"完全公平"的数学保证：

// 当进程运行时更新 vruntime
delta_exec = now - exec_start;                        // 真实运行时间
delta_exec_weighed = delta_exec * (NICE_0_LOAD / se->load.weight); // 加权
se->vruntime += delta_exec_weighed;                    // 累加

关键洞察：权重越大的进程（nice 值越低），NICE_0_LOAD / load 的比值越小，vruntime 增长越慢。这保证了：

• nice 0 的进程：vruntime 增长速率 = 1×（基准）
• nice -5 的进程：vruntime 增长速率约 0.31×（获得约 3 倍于基准的 CPU 时间）
• nice +5 的进程：vruntime 增长速率约 3.1×（获得约 1/3 的 CPU 时间）

3.2 权重表 sched_prio_to_weight

内核使用一个预计算的查找表将 nice [-20, +19] 映射到权重值：

static 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 倍（即 10% 的 CPU 时间差），这个设计确保了即使 nice 值差异很小，也能获得可辨识的调度优先级差异。

3.3 min_vruntime 偏移量

vruntime 的基准偏移量机制是 CFS 设计的另一个巧思：

• 每个 cfs_rq 维护一个 min_vruntime，记录该队列历史最小 vruntime
• 新创建进程的 vruntime 初始化为所在 cfs_rq 的 min_vruntime，而不是 0
li>这避免了新进程因为 vruntime 太小而"霸占" CPU
• 当进程从一个 CPU 迁移到另一个 CPU 时，会根据目标队列的 min_vruntime 做偏移校正，保证公平的连续性

四、红黑树调度算法

CFS 使用红黑树作为可运行进程队列的数据结构。红黑树的关键性质使其非常适合这一场景：

• 自平衡：保证最坏情况 O(log N) 的插入/删除复杂度
• 中序遍历有序：vruntime 最小的进程始终在最左侧
• pick_next_task_cfs() 只需取出最左侧节点，常数时间完成

4.1 进程入队（enqueue）

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
    struct rb_node *parent = NULL;
    struct sched_entity *entry;
    u64 vruntime = cfs_rq->min_vruntime; // 使用 min_vruntime 作为比较基准

    // 红黑树搜索插入位置
    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);
        if (entity_before(se, entry)) { // se->vruntime < entry->vruntime
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
        }
    }

    // 链接节点并重新平衡红黑树
    rb_link_node(&se->run_node, parent, link);
    rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);

    // 缓存最左侧节点
    if (link == &cfs_rq->rb_leftmost)
        cfs_rq->rb_leftmost = &se->run_node;
}

4.2 进程出队（dequeue）

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    if (cfs_rq->rb_leftmost == &se->run_node)
        cfs_rq->rb_leftmost = rb_next(&se->run_node);
    rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
}

4.3 选择下一个进程

static struct sched_entity *__pick_next_entity(struct cfs_rq *cfs_rq)
{
    // 直接返回最左侧节点（vruntime 最小 = 最"亏欠"的进程）
    return rb_entry(cfs_rq->rb_leftmost, struct sched_entity, run_node);
}

五、调度时机与抢占逻辑

5.1 调度触发的时机

CFS 在以下时刻可能触发调度：

1. 时间片耗尽（实际上是基于 vruntime 的预算检查，见下文）
2. 进程主动放弃 CPU（I/O 等待、互斥量、sleep）
3. 周期性调度器时钟中断（scheduler_tick()）
4. 唤醒进程时可能抢占（check_preempt_curr()）
5. 进程创建/退出时

5.2 周期性调度检查 scheduler_tick()

// 每次 tick 中断调用
void scheduler_tick(void)
{
    int cpu = smp_processor_id();
    struct rq *rq = cpu_rq(cpu);
    struct task_struct *curr = rq->curr;

    curr->sched_class->task_tick(rq, curr, 0);
}

// CFS 的 task_tick 实现
static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
    struct cfs_rq *cfs_rq;
    struct sched_entity *se = &curr->se;

    // 遍历从当前进程到根 cfs_rq 的路径
    for_each_sched_entity(se) {
        cfs_rq = cfs_rq_of(se);
        entity_tick(cfs_rq, se, queued);
    }
}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *se, int queued)
{
    // 更新 vruntime
    update_curr(cfs_rq);

    // 如果队列中还有其他可能更"亏欠"的进程，则抢占
    if (cfs_rq->nr_running > 1)
        check_preempt_tick(cfs_rq, se);
}

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *cur)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    // ...
    delta = cur->vruntime - left->vruntime;

    // 如果当前进程的 vruntime 超过最亏欠进程一个阈值，则被抢占
    if (delta > ideal_runtime)
        resched_curr(rq_of(cfs_rq));
}

关键参数：ideal_runtime 是调度粒度决定的理想运行时间。默认配置下，当运行队列超过一定数量时，ideal_runtime 会按 min(latency, latency / nr_running) 计算，确保进程至少运行一段时间才会被切换。

5.3 唤醒抢占（Wake-up Preemption）

当一个睡眠进程被唤醒时，CFS 会检查它是否可以抢占当前进程：

// check_preempt_curr - check preemption on wakeup
static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
    struct task_struct *curr = rq->curr;
    struct sched_entity *se = &curr->se, *pse = &p->se;
    struct cfs_rq *cfs_rq = task_cfs_rq(curr);
    // ...

    // 当前进程的 vruntime 已经大于唤醒进程 vruntime 超过一个阈值
    // 唤醒进程可以抢占当前进程
    if (wakeup_preempt_entity(se, pse) == 1) {
        // 跳过相邻唤醒（频繁唤醒同级的乒乓效应）
        if (!same || !SCHED_WARN_ON(se == pse))
            goto preempt;
    }
    return;

preempt:
    resched_curr(rq);
}

六、组调度与层级公平

6.1 为什么需要组调度？

在桌面或服务器环境中，我们经常需要按用户或应用进行资源分配，而非单个进程：

• 两个用户的进程应该获得相等的 CPU 时间，不管每个用户开启了多少进程
• 容器（Docker/K8s）需要以组为单位进行资源限制
• web server 和编译任务应该分到不同的 CPU 份额

这就是 cgroup CPU 控制器 和 CFS 组调度 发挥作用的地方。

6.2 调度实体层次

CFS 支持调度实体的层次组合：

• 进程级：task_struct->se，直接参与 cfs_rq 的红黑树排序
• cgroup 级：cgroup->se，每个 cgroup 也有自己的调度实体，作为更高层 cfs_rq 中的"进程"存在

层次关系示例：cgroup/cpu/A/proc_1 的流程：

proc_1.se → cfs_rq(cgroup A) → cgroup_A.se → root_cfs_rq

6.3 CPU Shares 份额比例

// /sys/fs/cgroup/cpu/A/cpu.shares 示例：
// cgroup A: shares=1024（默认）
// cgroup B: shares=2048

// 则 B 获得 A 的两倍 CPU 时间
// 比例计算：A 份额 = 1024/(1024+2048) = 33.3%
//          B 份额 = 2048/(1024+2048) = 66.7%

七、NUMA 与 SMP 负载均衡

7.1 调度域（Sched Domain）

现代多核系统使用 NUMA（非统一内存访问）架构，不同 CPU 访问不同内存节点的延迟差异显著。内核通过调度域来建模 CPU 拓扑：

• MC（Multi-Core）层：同一物理核心内的超线程（Hyper-Threading），迁移代价最低
• CPU 层：同一物理插槽（Socket）内核心之间迁移
• NUMA 层：跨节点迁移，代价最高
• ALLNODES：覆盖所有 CPU

负载均衡按照从最低层到最高层逐层进行，优先在最廉价层完成负载均衡。

7.2 负载均衡原语

// 每个时钟 tick 可能触发的负载均衡路径：
scheduler_tick()
  → trigger_load_balance()
    → raise_softirq(SCHED_SOFTIRQ)
      → run_rebalance_domains()
        → rebalance_domains() // 按调度域层级迭代
          → load_balance()    // 寻找最忙碌的组
            → detach_tasks()  // 从 busiest 组抽取进程
            → attach_tasks()  // 添加到本地队列

// IDLE 时触发：
void idle_balance(struct rq *rq)
{
    // 当 CPU 即将空闲时，尝试从其他 CPU 拉取进程
    for_each_domain(cpu, sd) {
        if (sd->flags & SD_BALANCE_NEWIDLE) {
            if (load_balance(cpu, rq, sd, CPU_NEWIDLE))
                break;
        }
    }
}

7.3 NUMA 平衡（NUMA Balancing）

Linux 4.0+ 引入了 Auto NUMA Balancing：

• 内核定期扫描进程的内存页面，通过NUMA_HINT_FAULTS统计各 NUMA 节点的缺页异常
• 如果大量页面在远端节点，可以考虑迁移进程到近端节点
• 也可以直接迁移页面到本地节点（比迁移进程代价更低）

八、CFS 的核心参数与调优

8.1 调度粒度

调优思路：

• 桌面交互场景：降低 sched_wakeup_granularity_ns 提升交互响应（代价是更多上下文切换）
• HPC/批量计算：增大 sched_latency_ns 减少切换开销，提升吞吐
• 低延迟交易：使用 SCHED_FIFO/SCHED_RR+ CPU 隔离（isolcpus），而非 CFS

echo 50000 > /sys/fs/cgroup/cpu/docker/xxx/cpu.cfs_quota_us
echo 100000 > /sys/fs/cgroup/cpu/docker/xxx/cpu.cfs_period_us

// kernel/sched/sched.h
extern const struct sched_class stop_sched_class;       // 最高优先级：停机调度
extern const struct sched_class dl_sched_class;         // 截止时间调度（SCHED_DEADLINE）
extern const struct sched_class rt_sched_class;         // 实时调度（SCHED_FIFO/SCHED_RR）
extern const struct sched_class fair_sched_class;       // CFS（SCHED_NORMAL/SCHED_BATCH）
extern const struct sched_class idle_sched_class;       // 最低优先级：空闲

// 设置 DL 调度策略参数
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_setattr(pid, &attr, 0);

# 检查容器进程的真实优先级
cat /proc//sched | grep "prio\|policy"

# 查看进程的 vruntime 演化
trace-cmd record -e sched_switch -e sched_wakeup &
# 在终端执行业务，然后分析

# 检查调度延迟
perf sched record -- sleep 1
perf sched latency --sort max

// CFS 最核心的一行代码：选择最"亏欠"的进程
struct sched_entity *pick_next = rb_entry(leftmost, struct sched_entity, run_node);
// 这就是 CFS 哲学：永远让跑得最少的人先跑