1. CFS 算法概述：完全公平调度器设计哲学、红黑树数据结构基础、虚拟运行时间概念

1.1 完全公平调度器（CFS）的设计哲学

CFS（Completely Fair Scheduler）是 Linux 内核 2.6.23 版本引入的默认进程调度器，由 Ingo Molnár 设计。其核心设计哲学可概括为：“模拟理想多任务处理器上的完美公平调度”。

在理想多任务处理器中，假设有 N 个可运行进程，每个进程应获得 1/N 的 CPU 时间。CFS 不采用传统的时间片轮转（Round-Robin）或优先级队列，而是通过虚拟运行时间（vruntime）来度量每个进程已获得的 CPU 时间，并始终选择 vruntime 最小的进程来运行。

1.2 红黑树数据结构基础

CFS 使用红黑树（Red-Black Tree）作为核心数据结构来组织可运行进程。红黑树是一种自平衡二叉查找树，具有以下关键特性：

• 平衡性：任何路径上的黑色节点数相同，确保树的高度不超过 2*log₂(n+1)。
• 查找效率：查找、插入、删除操作的时间复杂度均为 O(log n)。
• 有序性：中序遍历可得到按 vruntime 排序的进程序列。

在 CFS 中，红黑树的键值是进程的 vruntime。树的最左节点（vruntime 最小）即为下一个要运行的进程。

1.3 虚拟运行时间（vruntime）概念

虚拟运行时间（vruntime）是 CFS 实现公平调度的核心度量。它表示进程在理想多任务处理器上应获得的 CPU 时间，而非实际物理时间。

vruntime 的计算公式如下：

vruntime += delta_exec * (NICE_0_LOAD / se->load.weight)

其中：

• delta_exec：进程实际运行的物理时间。
• NICE_0_LOAD：nice 值为 0 时的默认权重（1024）。
• se->load.weight：当前进程的调度实体权重，由 nice 值决定。

1.4 CFS 调度流程与 vruntime 更新

CFS 的调度循环可概括为以下步骤：

1. 选择下一个进程：从红黑树中取出最左节点（vruntime 最小）。
2. 执行进程：将 CPU 分配给该进程运行。
3. 更新 vruntime：在进程运行期间（通过 tick 中断）或进程主动让出 CPU 时，更新其 vruntime。
4. 重新插入红黑树：如果进程未退出，将其重新插入红黑树（或更新其键值）。
5. 重复步骤 1。

1.5 关键数据结构与内核代码片段

在 Linux 内核中，CFS 的核心数据结构定义在 kernel/sched/fair.c 和 include/linux/sched.h 中。以下为关键结构：

// 调度实体（sched_entity），每个进程对应一个
struct sched_entity {
    struct load_weight      load;           // 进程权重
    struct rb_node          run_node;       // 红黑树节点
    struct list_head        group_node;     // 组调度链表节点
    unsigned int            on_rq;          // 是否在就绪队列中
    u64                     vruntime;       // 虚拟运行时间
    u64                     prev_sum_exec_runtime; // 上次调度时的总执行时间
    // ... 其他字段
};

// CFS 就绪队列（cfs_rq）
struct cfs_rq {
    struct load_weight      load;           // 就绪队列总权重
    unsigned int            nr_running;     // 可运行进程数
    u64                     min_vruntime;   // 最小虚拟运行时间
    struct rb_root_cached   tasks_timeline; // 红黑树根节点（含缓存）
    struct sched_entity     *curr;          // 当前正在运行的进程
    struct sched_entity     *next;          // 下一个要运行的进程
    // ... 其他字段
};

CFS 选择下一个进程的核心函数是 pick_next_entity()，其逻辑可简化为：

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
    struct rb_node *left = rb_first_cached(&cfs_rq->tasks_timeline);
    if (!left)
        return NULL;
    return rb_entry(left, struct sched_entity, run_node);
}

该函数通过 rb_first_cached() 直接获取红黑树最左节点（缓存了 leftmost 指针），时间复杂度为 O(1)。

1.6 本章小结