📚 课程目录第4章调度实体与调度类

4. 调度实体与调度类：struct sched_entity、struct sched_class、调度类层次结构

Linux 内核的调度器并非一个单一的算法，而是由多个调度类（Scheduling Class）组成的层次化体系。每个调度类管理一组具有相同调度策略的进程，而调度实体（Scheduling Entity）则是调度器操作的基本单元。理解这两者的关系与结构，是掌握内核抢占与调度行为的关键。

4.1 调度实体：struct sched_entity

调度实体是内核调度器进行 CPU 时间分配的基本对象。在 CFS（完全公平调度器）中，每个进程（task_struct）内嵌了一个 struct sched_entity 实例，用于参与公平调度的红黑树管理。

  核心作用：调度实体抽象了“谁可以被调度”这一概念，使得调度器可以统一处理普通进程、组调度（task group）等不同粒度的调度对象。

以下是 struct sched_entity 的关键字段（位于 include/linux/sched.h）：

struct sched_entity {
    /* CFS 负载权重 */
    struct load_weight      load;
    /* 红黑树节点，用于在 CFS 就绪队列中排序 */
    struct rb_node          run_node;
    /* 当前虚拟运行时间，CFS 调度的核心指标 */
    u64                     vruntime;
    /* 上一次加入就绪队列的虚拟时间 */
    u64                     prev_sum_exec_runtime;
    /* 当前调度实体所属的 cfs_rq */
    struct cfs_rq           *cfs_rq;
    /* 指向父调度实体（用于组调度） */
    struct sched_entity     *parent;
    /* 当前调度实体所在的运行队列深度 */
    unsigned int            depth;
};

字段	说明	调度意义
`load.weight`	调度实体的权重，由进程优先级（nice 值）决定	权重越高，获得的 CPU 时间片越多
`vruntime`	虚拟运行时间，记录进程已消耗的 CPU 时间（经过权重归一化）	CFS 选择 vruntime 最小的实体运行
`run_node`	红黑树节点，将调度实体插入 CFS 就绪队列	实现 O(log n) 的进程查找与插入
`cfs_rq`	指向该实体所在的 CFS 运行队列	用于在组调度中定位上下文
`parent`	指向父调度实体，用于组调度层次	支持调度实体的树形嵌套

关键理解：vruntime 是 CFS 调度的“货币”。每次时钟 tick 或进程唤醒时，调度器会更新 vruntime，并检查是否需要抢占当前进程。vruntime 越小，表示进程“欠”的 CPU 时间越多，越应该被优先调度。

4.2 调度类：struct sched_class

调度类定义了调度器的一组操作接口。每个调度类实现一套完整的调度策略，包括如何选择下一个运行进程、如何将进程加入/移出运行队列、如何处理时钟中断等。内核通过调度类实现了策略与机制的分离。

struct sched_class {
    /* 调度类的名称，用于调试和 /proc 文件系统 */
    const char              *name;

    /* 将一个调度实体加入运行队列 */
    void (*enqueue_task)    (struct rq *rq, struct task_struct *p, int flags);
    /* 将一个调度实体移出运行队列 */
    void (*dequeue_task)    (struct rq *rq, struct task_struct *p, int flags);
    /* 检查当前进程是否可以被抢占 */
    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
    /* 选择下一个要运行的进程 */
    struct task_struct *(*pick_next_task)(struct rq *rq);
    /* 时钟 tick 处理函数，更新调度实体状态 */
    void (*task_tick)       (struct rq *rq, struct task_struct *p, int queued);
    /* 进程 yield 系统调用处理 */
    void (*yield_task)      (struct rq *rq);
    /* 设置进程调度参数 */
    void (*set_curr_task)   (struct rq *rq);
    /* 进程迁移到另一个 CPU */
    void (*migrate_task_rq) (struct task_struct *p, int new_cpu);
};

回调函数	触发时机	典型实现（CFS）
`enqueue_task`	进程变为可运行状态（如唤醒、fork）	将 sched_entity 插入红黑树，更新 vruntime
`dequeue_task`	进程进入睡眠、退出或被迁移	从红黑树移除，记录最后一次执行时间
`pick_next_task`	调度器需要选择下一个进程	选取红黑树最左节点（vruntime 最小）
`task_tick`	周期性时钟中断	更新当前进程的 vruntime，检查是否需要抢占
`check_preempt_curr`	新进程加入运行队列时	比较新进程与当前进程的 vruntime，决定是否抢占

4.3 调度类层次结构

Linux 内核维护了一个调度类优先级链表。每个调度类有一个优先级值（class->prio），数值越小优先级越高。调度器在选择下一个进程时，会从最高优先级的调度类开始查询，直到找到一个有可运行进程的调度类。

  层次结构原则：高优先级调度类（如 Stop 类）的进程永远优先于低优先级调度类（如 Idle 类）的进程。同一调度类内部，由该调度类自己的算法决定进程顺序。

以下是内核中定义的调度类及其优先级顺序（从高到低）：

调度类	优先级	对应调度策略	典型用途
`stop_sched_class`	最高	—	停止 CPU 上的所有其他活动，用于 CPU hotplug、migration 等
`dl_sched_class`	高	`SCHED_DEADLINE`	实时截止时间调度，保证最坏情况下的响应时间
`rt_sched_class`	中	`SCHED_FIFO` / `SCHED_RR`	实时进程，优先级范围 0–99
`fair_sched_class`	低	`SCHED_NORMAL` / `SCHED_BATCH` / `SCHED_IDLE`	普通分时进程，CFS 调度
`idle_sched_class`	最低	—	每个 CPU 的空闲进程（swapper），无其他进程可运行时执行

抢占影响：调度类层次结构直接决定了内核抢占的触发条件。例如，当一个高优先级的 RT 调度类进程被唤醒时，即使当前运行的是 CFS 进程，调度器也会立即触发抢占（如果内核支持抢占）。这种跨调度类的抢占是内核抢占机制的核心场景之一。

4.4 调度类层次结构 SVG 图

下图展示了 Linux 内核中调度类的层次结构、优先级顺序以及进程选择流程：

4.5 调度实体与调度类的协作关系

调度实体和调度类通过以下方式协同工作：

进程创建时：内核根据进程的调度策略（如 SCHED_NORMAL）将进程关联到对应的调度类（如 fair_sched_class），并初始化内嵌的 struct sched_entity。
进程加入运行队列：调度类的 enqueue_task 回调被调用，将调度实体插入到该调度类管理的就绪队列数据结构中（如 CFS 的红黑树）。
调度决策时：pick_next_task 按调度类优先级遍历，找到第一个有可运行实体的调度类，然后由该调度类选择具体的调度实体。
时钟中断时：当前进程所属调度类的 task_tick 被调用，更新调度实体的 vruntime，并可能触发 check_preempt_curr 进行抢占检查。

组调度扩展：在启用组调度（CONFIG_FAIR_GROUP_SCHED）时，调度实体可以代表一个进程组（task group）。此时，调度实体形成树形结构，父调度实体管理子调度实体的 CPU 时间分配，实现了对一组进程的整体带宽控制。

4.6 调度类注册与链表维护

内核在初始化时，将各个调度类按照优先级顺序链接到一个全局链表中。调度器通过遍历该链表来实现进程选择。

// 内核中的调度类链表（简化示意）
extern const struct sched_class stop_sched_class;
extern const struct sched_class dl_sched_class;
extern const struct sched_class rt_sched_class;
extern const struct sched_class fair_sched_class;
extern const struct sched_class idle_sched_class;

// 调度类优先级链表头
static const struct sched_class * const sched_class_highest = &stop_sched_class;

// 链表顺序（通过 __begin/__end 段或显式指针维护）
#define sched_class_above(_a, _b)   ((_a)->prio < (_b)->prio)

// pick_next_task 的简化实现
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
    const struct sched_class *class;
    struct task_struct *p;

    // 从最高优先级调度类开始遍历
    for_each_class(class) {
        p = class->pick_next_task(rq);
        if (p)
            return p;
    }
    // 理论上不会到达这里，因为 idle 类总有进程
    BUG();
}

性能考量：在大多数情况下，pick_next_task 会快速命中 fair_sched_class，因为普通进程占绝大多数。内核通过快速路径优化（如直接检查当前运行队列是否只有 CFS 进程）来避免不必要的调度类遍历开销。

通过调度实体与调度类的双层抽象，Linux 内核实现了高度模块化的调度架构。开发者可以添加新的调度类而不影响现有调度策略，同时调度实体提供了统一的调度对象表示，为组调度、cgroup 等高级特性奠定了基础。