解析 Linux ‘CFS’ (完全公平调度器)：红黑树是如何在 (log N)$ 时间内找到下一个运行进程的？ - 智猿学院-前后端，数据库，人工智能，云计算等领域前沿技术讲座

各位同仁，各位技术爱好者，大家好。

今天，我们齐聚一堂，将深入探讨Linux内核调度器中一个极其精妙且核心的组件：完全公平调度器（Completely Fair Scheduler, 简称CFS）。CFS自Linux 2.6.23版本引入以来，以其卓越的性能和优雅的设计，成为了现代Linux系统调度进程的基石。我们将聚焦于CFS的核心数据结构——红黑树，并解析它是如何在对数时间复杂度（O(log N)）内高效地找到下一个需要运行的进程。

引言：操作系统的调度艺术与CFS的哲学

在多任务操作系统中，CPU是核心资源。如何高效、公平地分配CPU时间，是调度器永恒的挑战。早期的调度器往往采用固定时间片、优先级队列等机制，但随着系统负载的增加和处理核心数量的增长，这些调度器暴露出一些问题：例如，难以在响应时间、吞吐量和公平性之间取得平衡；优先级反转问题；以及在大量进程存在时，调度决策的复杂度过高。

Linux在CFS之前，经历了O(1)调度器、RSDL等演进。CFS的诞生，标志着Linux调度器设计理念的一次重大革新。它的核心哲学是“完全公平”。CFS不追求为每个进程分配精确的时间片，而是致力于让每个进程都感觉自己独占了CPU，或者说，都获得了“公平”的CPU时间份额。这种公平性是通过引入一个关键概念来实现的：虚拟运行时（Virtual Runtime, vruntime）。

vruntime可以被理解为一个进程“已经运行了多少时间”的度量，但这个时间是经过权重调整的。一个进程的vruntime越小，意味着它“落后”的越多，就越需要被调度运行。CFS的目标是让所有可运行进程的vruntime都趋于一致。

CFS的核心：`sched_entity`与红黑树

要理解CFS如何工作，我们首先需要了解它的核心数据结构。

1. `struct sched_entity`：进程在CFS中的化身

在Linux内核中，每个可调度的任务（task_struct）都会包含一个struct sched_entity的实例。这个结构体封装了CFS调度器所需的所有信息，它代表了一个进程（或一个任务组）在CFS世界中的“实体”。

// 简化版的 sched_entity 结构体，仅包含与本文主题直接相关的字段
struct sched_entity {
    struct rb_node rb_node;       // 用于将此实体插入红黑树
    u64 vruntime;                 // 虚拟运行时，核心调度指标
    unsigned long load_weight;    // 进程的权重，由nice值转换而来，影响vruntime增长速度

    // 其他字段，如 exec_start, sum_exec_runtime 等，用于统计和计算
    // ...
};

rb_node: 这是sched_entity的关键字段，它将sched_entity实例嵌入到红黑树中。通过container_of宏，我们可以从一个rb_node指针逆向找到它所属的sched_entity。
vruntime: 这是CFS进行调度决策的核心依据。它记录了进程的虚拟运行时间。
load_weight: 这个字段反映了进程的“优先级”。nice值越小（优先级越高），load_weight越大。load_weight越大，进程的vruntime增长越慢，从而获得更多的CPU时间。

2. 红黑树：CFS的运行队列

CFS为每个CPU维护一个就绪队列，这个队列的核心就是一个红黑树。所有当前处于可运行状态（Runnable）的进程（确切地说是它们的sched_entity实例）都会被插入到这棵红黑树中。红黑树的节点以vruntime为键值进行排序。

为什么CFS选择红黑树而不是其他数据结构？

这是一个非常关键的问题。我们可以考虑其他一些常见的数据结构：

链表/数组: 查找最小vruntime的进程需要O(N)时间，插入/删除也可能需要O(N)。当N很大时，性能会急剧下降，无法满足实时性要求。
堆（优先级队列）: 查找最小元素是O(1)，插入/删除是O(log N)。看起来很适合。但是，堆通常只能高效地找到最小/最大元素，而CFS除了查找最小，还需要根据vruntime的动态变化进行节点的调整（本质上是删除旧节点，插入新节点），以及在某些情况下需要遍历或范围查询（虽然CFS主要用作最小元素查找）。
AVL树/B树: 它们也是自平衡二叉搜索树，能够提供O(log N)的查找、插入和删除性能。红黑树相比AVL树，在插入和删除时，通常需要更少的旋转操作来重新平衡，这使得它在实际应用中，尤其是写操作频繁的场景下，可能表现更好。同时，红黑树的实现相对AVL树也更为简洁。

综合来看，红黑树的优势在于：

自平衡性: 保证了树的高度始终是O(log N)，从而所有基本操作（查找、插入、删除）的最坏时间复杂度都维持在O(log N)。这对于调度器至关重要，因为调度器需要在极短的时间内做出决策，且性能不应随进程数量的增加而显著恶化。
有序性: 红黑树是一种二叉搜索树，其节点按照键值（在这里是vruntime）有序排列。这意味着，树的最左侧节点总是存储着最小的vruntime，而最右侧节点则存储着最大的vruntime。CFS需要频繁地找到vruntime最小的进程来运行，红黑树能够以O(log N)的效率完成此任务。
动态性: 能够高效地处理进程的加入（变为可运行）和移除（阻塞或终止），而不会导致整个数据结构的重建。

3. 红黑树的五大性质

为了确保O(log N)的性能，红黑树必须满足以下五条性质：

节点颜色: 每个节点不是红色就是黑色。
根节点是黑色: 树的根节点必须是黑色的。
红色节点子节点是黑色: 如果一个节点是红色的，那么它的两个子节点必须是黑色的。这意味着不能有两个连续的红色节点。
路径黑色节点数相等: 从任一节点到其每个叶子（NIL节点）的所有路径都包含相同数量的黑色节点。
叶子节点是黑色: 所有叶子节点（NIL节点，即空节点）都是黑色的。

这些性质确保了从根到任意叶子节点的最长路径不会超过最短路径的两倍，从而保证了树的平衡性。

4. `cfs_rq`：CFS的运行队列结构体

每个CPU都有一个struct cfs_rq，它包含了该CPU上CFS调度器所需的所有信息，其中最重要的是指向红黑树根节点的rb_root。

// 简化版的 cfs_rq 结构体
struct cfs_rq {
    struct rb_root_cached tasks_timeline; // 红黑树的根节点，存储所有可运行的 sched_entity
    u64 min_vruntime;                    // 记录红黑树中最小的vruntime值，用于快速初始化新进程的vruntime

    // 其他统计信息和调度参数
    // ...
};

rb_root_cached是一个优化，它除了包含rb_root外，还额外缓存了树的最左侧节点，进一步加速了最小vruntime进程的查找。但这只是一个常数时间优化，其核心的O(log N)效率仍由红黑树的性质保证。

红黑树在CFS中的具体应用：如何找到下一个运行进程

现在，我们来深入探讨CFS如何利用红黑树，在O(log N)时间内找到下一个最“饥饿”的进程。

1. 插入进程 (`enqueue_entity`)

当一个进程从等待状态变为可运行状态时（例如，I/O完成，或sleep结束后），CFS需要将其对应的sched_entity插入到红黑树中。

插入过程如下：

计算初始vruntime: 新唤醒的进程的vruntime需要进行特殊处理。为了避免“插队”或“饥饿”，它的vruntime通常会被设置为当前cfs_rq的min_vruntime。这样可以确保新进程不会比当前所有正在运行或等待运行的进程更早地获得CPU，也不会因为vruntime过大而长时间得不到调度。
```
// 简化逻辑
u64 initial_vruntime = cfs_rq->min_vruntime;
// 可能还需要考虑wakeup_granularity进行微调
if (se->vruntime < initial_vruntime) {
    se->vruntime = initial_vruntime;
}
```
查找插入位置: 从红黑树的根节点开始，比较待插入sched_entity的vruntime与当前节点的vruntime。
- 如果待插入vruntime小于当前节点，则向左子树移动。
- 如果待插入vruntime大于等于当前节点，则向右子树移动。
- 这个过程持续进行，直到找到一个空位置（NIL节点）。
插入节点: 在找到的位置插入新的rb_node（附属于sched_entity），并将其颜色设置为红色。
自平衡: 根据红黑树的性质，新插入的红色节点可能会破坏红黑树的平衡（例如，出现两个连续的红色节点，或路径黑色节点数不一致）。此时，需要通过一系列的颜色翻转和旋转操作来恢复红黑树的平衡。这些操作确保了树的O(log N)高度特性。

伪代码示例：插入操作的核心逻辑（仅展示查找和插入，不包含平衡过程）

// 假设 se 是要插入的 sched_entity
void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    struct rb_node *parent = NULL;
    u64 vruntime = se->vruntime;

    // 1. 查找插入位置
    while (*link) {
        parent = *link;
        struct sched_entity *entry = rb_entry(parent, struct sched_entity, rb_node);

        if (vruntime < entry->vruntime) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
        }
    }

    // 2. 插入节点
    rb_link_node(&se->rb_node, parent, link); // 将se->rb_node链接到找到的位置
    rb_insert_color(&se->rb_node, &cfs_rq->tasks_timeline.rb_root); // 插入并进行红黑树平衡操作

    // 更新 cfs_rq->min_vruntime，如果插入的 vruntime 更小
    if (vruntime < cfs_rq->min_vruntime) {
        cfs_rq->min_vruntime = vruntime;
    }
}

2. 删除进程 (`dequeue_entity`)

当一个进程停止运行（例如，完成任务、进入睡眠、被终止）时，CFS需要将其对应的sched_entity从红黑树中移除。

删除过程如下：

查找节点: 根据sched_entity的地址，可以直接找到其对应的rb_node。
移除节点: 从红黑树中删除该rb_node。
自平衡: 类似插入，删除操作也可能破坏红黑树的平衡。同样需要通过颜色翻转和旋转操作来恢复树的平衡。

伪代码示例：删除操作的核心逻辑（仅展示移除，不包含平衡过程）

// 假设 se 是要删除的 sched_entity
void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se) {
    rb_erase(&se->rb_node, &cfs_rq->tasks_timeline.rb_root); // 从红黑树中移除节点并进行平衡

    // 如果删除的是最小 vruntime 的进程，需要更新 cfs_rq->min_vruntime
    // 实际内核中，min_vruntime会在pick_next_task_fair时更新，或者通过遍历最左侧节点来获取
}

3. 核心：在O(log N)时间内找到下一个运行进程

这是本文的核心。CFS需要找到vruntime最小的进程来运行，因为这个进程被认为是“最饥饿”的。在红黑树中，vruntime最小的节点就是红黑树的最左侧节点。

查找过程 (pick_next_task_fair -> __pick_first_entity):

从根节点开始: 获取红黑树的根节点。
向左遍历: 只要当前节点存在左子节点，就沿着左子节点向下移动。
找到最左节点: 当当前节点没有左子节点时，这个节点就是树中vruntime最小的节点。
返回sched_entity: 通过container_of宏，从找到的rb_node获取其对应的sched_entity。

为什么是O(log N)？

因为红黑树是自平衡的，其高度始终是O(log N)。从根节点到最左侧节点的遍历路径，其长度不会超过树的高度。因此，查找最左侧节点的操作只需要O(log N)的时间复杂度。

伪代码示例：查找最左侧节点（rb_first的简化版）

// 查找红黑树中 vruntime 最小的 sched_entity
struct sched_entity* __pick_first_entity(struct cfs_rq *cfs_rq) {
    struct rb_node *leftmost = cfs_rq->tasks_timeline.rb_root.rb_node;

    if (!leftmost) {
        return NULL; // 红黑树为空
    }

    // 缓存优化：如果 rb_root_cached 维护了最左节点，可以直接返回
    // struct rb_node *leftmost = cfs_rq->tasks_timeline.rb_leftmost;

    // 沿左子树向下遍历，直到找到最左侧的叶子节点
    while (leftmost->rb_left) {
        leftmost = leftmost->rb_left;
    }

    // 从 rb_node 恢复 sched_entity
    return rb_entry(leftmost, struct sched_entity, rb_node);
}

在实际的Linux内核中，struct rb_root_cached结构体就是为了加速这个操作而设计的。它直接缓存了红黑树的最左侧节点 (rb_leftmost)。这样，在大多数情况下，__pick_first_entity只需要O(1)时间就能获取到最左侧节点，只有在rb_leftmost失效时（例如，最左侧节点被删除），才需要重新遍历树来更新它。但从理论复杂度上讲，红黑树保证了即使没有这个缓存，查找操作也是O(log N)。

`vruntime`的精确管理与更新

vruntime是CFS的灵魂，它的精确计算和更新是实现公平性的关键。

1. `vruntime`的增长

一个进程的vruntime在其被调度运行时会持续增长。增长的速度取决于两个因素：

实际运行时间 (delta_exec): 进程实际占用CPU的时间。
权重 (load_weight): 进程的nice值决定了其load_weight。nice值越小（优先级越高），load_weight越大，vruntime增长得越慢。

vruntime的更新公式可以概括为：

se->vruntime += delta_exec * (NICE_0_LOAD / se->load_weight)

其中 NICE_0_LOAD 是nice值为0的进程的默认权重。这个公式的含义是，nice值越高的进程（load_weight越大），其vruntime增长得越慢，从而在调度决策中显得更“饥饿”，更容易被选中运行。反之，nice值低的进程（load_weight越小），其vruntime增长得越快，会更快地“满足”，从而让出CPU。

2. `update_curr`：实时更新`vruntime`

Linux内核通过update_curr函数来更新当前运行进程的vruntime。这个函数通常在时钟中断或进程被抢占时被调用。

// 简化版的 update_curr 逻辑
void update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr) {
    u64 now = get_current_time_ns(); // 获取当前时间
    u64 delta_exec = now - curr->exec_start; // 计算本次运行了多长时间

    // 更新当前进程的 vruntime
    curr->vruntime += calc_delta_fair(delta_exec, curr); // calc_delta_fair 会根据权重调整 delta_exec

    // 更新 cfs_rq 的 min_vruntime
    // min_vruntime 通常是红黑树中最左侧节点的 vruntime
    // 确保 min_vruntime 不会落后太多
    cfs_rq->min_vruntime = max(cfs_rq->min_vruntime, curr->vruntime); // 简单示例，实际更复杂

    curr->exec_start = now; // 重置运行开始时间
}

calc_delta_fair函数会根据进程的load_weight调整delta_exec，以反映不同优先级的进程vruntime增长的差异。

3. 调度周期与最小粒度

CFS引入了两个重要的概念来控制调度行为：

sched_latency_ns: 调度延迟。这是一个目标值，表示在理想情况下，所有可运行进程都应该在这个时间段内至少运行一次。CFS会根据可运行进程的数量动态调整每个进程的“时间片”，以尽量满足这个目标。
sched_min_granularity_ns: 最小调度粒度。为了避免频繁的上下文切换开销，CFS规定一个进程在被抢占前，至少要运行min_granularity_ns这么长的时间。

当进程数量较少时，每个进程获得的时间片会比min_granularity_ns大；当进程数量很多时，为了确保所有进程能在sched_latency_ns内运行一次，每个进程的时间片可能会被压缩，但不会低于min_granularity_ns。

CFS调度流程概览

一个典型的CFS调度流程大致如下：

时钟中断或系统调用: 操作系统会周期性地收到时钟中断，或者进程发起系统调用（例如I/O操作、sleep）。这可能会触发调度器。
scheduler_tick: 在时钟中断中，scheduler_tick函数会被调用。它会检查当前运行进程是否已经用完了它的时间片（尽管CFS没有传统意义上的固定时间片），或者是否被更高优先级的进程抢占。
update_curr: 更新当前运行进程的vruntime。
check_preempt_tick: 检查是否需要抢占当前进程。如果当前进程的vruntime已经比红黑树中最左侧进程的vruntime大很多（超过wakeup_granularity），则可能触发抢占。
schedule(): 如果需要调度，schedule()函数会被调用。
- 它会调用pick_next_task()，对于CFS，这会进一步调用pick_next_task_fair()。
- pick_next_task_fair()的核心就是调用__pick_first_entity()，在红黑树中找到vruntime最小的sched_entity。
- 找到最合适的进程后，schedule()执行上下文切换(context_switch)，将CPU控制权从当前进程转移给新选定的进程。
进程切换: 新选定的进程开始运行。它的exec_start会被更新，vruntime开始增长。

CFS性能与可调参数

CFS的设计确保了其在多核和大规模并发环境下的优异性能。O(log N)的调度复杂度是其可伸缩性的关键。

Linux内核允许通过sysctl接口调整CFS的一些参数，以适应不同的工作负载需求。以下是一些常见的CFS sysctl参数：

通过调整这些参数，系统管理员可以微调CFS的行为，以优化系统的吞吐量、响应时间或公平性。

CFS：优雅与效率的结合

Linux的完全公平调度器CFS，通过引入虚拟运行时（vruntime）和巧妙地运用红黑树，实现了对CPU资源的公平且高效的分配。红黑树作为核心数据结构，以其自平衡的特性，保证了在进程数量N不断变化的情况下，查找、插入和删除操作都能在稳定的O(log N)时间内完成。特别是查找vruntime最小的进程这一核心操作，得益于红黑树的有序性，能够通过简单的左侧遍历路径快速定位。

这种设计不仅解决了传统调度器在可伸缩性上的挑战，也为现代多核、高并发的Linux系统提供了强大的调度能力。CFS的设计哲学简洁而强大，它将公平性抽象为vruntime的趋同，并通过高效的数据结构将这一理念付诸实践，使其成为Linux内核中最具代表性的创新之一。理解CFS如何利用红黑树，是理解现代操作系统调度器高效运行的关键。

引言：操作系统的调度艺术与CFS的哲学

CFS的核心：sched_entity与红黑树

1. struct sched_entity：进程在CFS中的化身

2. 红黑树：CFS的运行队列

3. 红黑树的五大性质

4. cfs_rq：CFS的运行队列结构体

红黑树在CFS中的具体应用：如何找到下一个运行进程

1. 插入进程 (enqueue_entity)

2. 删除进程 (dequeue_entity)