Linux内核进程调度器架构与核心调度类解析 - 第4节

4.1 CFS 的核心理念：从固定时间片到公平权重

完全公平调度器（Completely Fair Scheduler, CFS）是 Linux 内核 2.6.23 版本引入的默认调度类，其设计哲学彻底颠覆了传统的基于固定时间片（Timeslice）的调度模型。CFS 的核心目标不是给每个进程分配一个固定的时间片，而是确保每个进程在理想的多任务处理器上获得 公平的 CPU 时间比例。

传统 O(1) 调度器依赖静态优先级和固定时间片，导致交互式进程响应慢、后台进程抢占不公平。CFS 引入了一个关键概念：虚拟运行时间（vruntime），通过它来量化进程的“不公平程度”，并始终选择 vruntime 最小的进程来运行。

4.1.1 公平权重与优先级映射

CFS 不直接使用 nice 值作为时间片长度，而是将 nice 值映射为 权重（weight）。权重决定了进程在竞争 CPU 时的“相对速度”。权重越大的进程，其 vruntime 增长越慢，从而获得更多的 CPU 时间。

权重表定义在 kernel/sched/core.c 的 prio_to_weight 数组中。CFS 通过权重计算 vruntime 的增量：

// 简化后的 vruntime 更新逻辑
// delta_exec: 进程实际运行的物理时间
// weight: 当前进程的权重
// NICE_0_LOAD: nice=0 时的基准权重 (1024)
vruntime += delta_exec * NICE_0_LOAD / weight;

从公式可以看出：权重越大，vruntime 增加越慢，进程在红黑树中的位置越靠左（越小），越容易被调度器选中。

4.2 虚拟运行时间（vruntime）的精确计算

vruntime 是 CFS 调度器的核心数据，它记录了进程在“理想多任务 CPU”上应该运行的时间。每次时钟中断或进程切换时，CFS 都会更新当前进程的 vruntime。vruntime 的计算涉及多个因素：

• 物理运行时间（delta_exec）： 进程实际占用 CPU 的纳秒数。
• 进程权重（weight）： 由 nice 值映射得到，用于归一化 vruntime 增长速率。
• 调度周期（sched_latency）： CFS 保证每个可运行进程至少运行一次的时间窗口，默认 6ms 乘以进程数。
• 最小粒度（min_granularity）： 进程被抢占前的最小运行时间，默认 0.75ms，防止频繁切换。

4.2.1 vruntime 更新流程

在 CFS 的 update_curr() 函数中，vruntime 的更新遵循以下步骤：

// 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;

    // 1. 计算自上次更新以来的物理运行时间
    delta_exec = now - curr->exec_start;
    curr->exec_start = now;

    // 2. 根据当前进程权重更新 vruntime
    curr->vruntime += calc_delta_fair(delta_exec, &curr->load);

    // 3. 更新 cfs_rq 的 min_vruntime（红黑树最左节点值）
    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;
}

4.3 红黑树（rbtree）在 CFS 中的应用

CFS 使用 红黑树（Red-Black Tree） 来组织所有可运行进程的调度实体（sched_entity）。红黑树是一种自平衡二叉搜索树，其插入、删除和查找的时间复杂度均为 O(log N)，非常适合内核调度场景。

4.3.1 红黑树作为就绪队列

每个 CPU 都有一个 cfs_rq（CFS 运行队列），其中包含一棵红黑树。树的键值是进程的 vruntime。CFS 调度器每次选择任务时，直接取红黑树最左边的节点（即 vruntime 最小的进程）来运行。

• 键值： 进程的 vruntime，值越小越靠左。
• 最左节点： 当前 vruntime 最小的进程，即“最不公平”的进程，优先被调度。
• 平衡性： 红黑树保证树的高度不超过 2*log2(N+1)，确保调度延迟可控。
• 缓存友好： 红黑树节点在内存中连续分配，利用 CPU 缓存。

4.3.2 红黑树操作与调度流程

4.4 CFS 调度类的核心数据结构

CFS 调度类（fair_sched_class）是 Linux 内核中实现最复杂的调度类。其核心数据结构包括：

• struct sched_entity： 调度实体，包含 vruntime、权重、红黑树节点等。每个进程的 task_struct 中内嵌一个 sched_entity。
• struct cfs_rq： CFS 运行队列，包含红黑树根节点、min_vruntime、当前运行实体等。
• struct sched_class： 调度类接口，CFS 通过 fair_sched_class 注册 enqueue_task、dequeue_task、pick_next_task 等回调。

4.4.1 关键数据结构关系图

4.5 CFS 调度决策的完整流程

当调度器需要选择下一个运行进程时，CFS 调度类执行以下步骤：

1. 更新当前进程 vruntime： 调用 update_curr()，计算自上次调度以来的物理运行时间，并更新当前进程的 vruntime。
2. 检查是否需要抢占： 如果当前进程的 vruntime 超过了红黑树最左节点的 vruntime 加上调度粒度，则设置抢占标志。
3. 选择下一个进程： 调用 pick_next_task_fair()，从红黑树中取出最左节点（vruntime 最小的进程）。
4. 设置执行上下文： 更新新进程的 exec_start 时间戳，切换到新进程的地址空间。
5. 处理组调度（可选）： 如果启用了 CFS 组调度，还需要递归处理调度组内的红黑树。

4.6 CFS 设计哲学总结

CFS 的设计哲学可以概括为以下几点：