3. 调度实体与调度类：struct sched_entity、struct sched_class 数据结构详解，调度类层次结构

调度实体（Scheduling Entity）和调度类（Scheduling Class）是 CFS（Completely Fair Scheduler）调度器的两大核心抽象。调度实体代表一个可调度的单元（进程或进程组），而调度类则定义了调度策略的具体实现。本章将深入剖析这两个关键数据结构的内部细节，并揭示调度类的层次化组织方式。

3.1 调度实体：struct sched_entity

struct sched_entity 是内核调度器对调度单元的抽象。它不直接等同于 task_struct，而是嵌入在 task_struct 中，用于记录调度所需的负载、时间片、运行队列等信息。对于组调度（Group Scheduling），一个调度实体可以代表一组进程。

核心作用： 调度实体是 PELT（Per-Entity Load Tracking）算法跟踪负载的基本单位。每个调度实体都维护着自己的负载贡献历史，这是实现精细化负载均衡的基础。

3.1.1 关键字段解析

字段名 类型 描述
load struct load_weight 调度实体的权重，用于计算虚拟时间（vruntime）和负载贡献。
run_node struct rb_node 红黑树节点，用于将调度实体插入到 CFS 运行队列的红黑树中。
on_rq unsigned int 标志位，指示该调度实体是否在运行队列上。
vruntime u64 虚拟运行时间，CFS 调度器根据此值选择下一个运行的进程。
exec_start u64 当前调度实体开始执行的时间戳（基于 rq 时钟）。
sum_exec_runtime u64 该调度实体累计消耗的 CPU 时间。
prev_sum_exec_runtime u64 上一次被切换出去时的累计运行时间。
nr_migrations u64 调度实体在 CPU 之间迁移的次数。
statistics struct sched_statistics 调度统计信息，如睡眠时间、等待时间等。
avg struct sched_avg PELT 核心数据结构，存储调度实体的平均负载、运行时间等。
cfs_rq struct cfs_rq * 指向该调度实体所属的 CFS 运行队列。
my_q struct cfs_rq * 如果该调度实体代表一个任务组，则指向其自己的 CFS 运行队列。
关键理解： avg 字段是 PELT 算法的核心。它包含了 load_avg（负载平均值）、util_avg（利用率平均值）和 runnable_avg（可运行平均值），这些值通过指数加权移动平均（EWMA）算法计算得出，是负载跟踪和调频（DVFS）决策的直接依据。

3.1.2 调度实体与 task_struct 的关系

每个进程的 task_struct 中都内嵌了一个 struct sched_entity 实例，通常命名为 se。对于组调度，一个 task_group 会拥有一个或多个调度实体（每个 CPU 一个），这些实体代表整个任务组参与调度。

// task_struct 中的调度实体
struct task_struct {
    // ... 其他字段 ...
    struct sched_entity se;      // 主调度实体
    struct sched_rt_entity rt;   // 实时调度实体（如果使用 RT 调度类）
    struct sched_dl_entity dl;   // Deadline 调度实体（如果使用 DL 调度类）
    // ... 其他字段 ...
};

3.2 调度类：struct sched_class

struct sched_class 是一个函数指针结构体，它定义了一组标准的调度操作接口。不同的调度策略（如 CFS、实时、Deadline）通过实现这些接口来提供各自的调度行为。这种设计体现了面向对象的多态思想，使得内核可以灵活地扩展和替换调度算法。

3.2.1 核心操作接口

函数指针 描述 典型实现（CFS）
enqueue_task 将调度实体加入运行队列。 enqueue_task_fair
dequeue_task 将调度实体从运行队列移除。 dequeue_task_fair
yield_task 进程主动让出 CPU。 yield_task_fair
check_preempt_curr 检查新唤醒的进程是否可以抢占当前进程。 check_preempt_wakeup
pick_next_task 选择下一个要运行的调度实体。 pick_next_task_fair
put_prev_task 将当前运行的调度实体放回运行队列。 put_prev_task_fair
set_curr_task 设置当前运行的调度实体。 set_curr_task_fair
task_tick 周期性时钟 tick 处理，用于更新 vruntime 和检查是否需要抢占。 task_tick_fair
update_curr 更新当前调度实体的运行时间统计。 update_curr_fair
select_task_rq 为进程选择合适的 CPU 运行队列（负载均衡的关键）。 select_task_rq_fair
migrate_task_rq 进程迁移到另一个 CPU 时的回调。 migrate_task_rq_fair
task_woken 进程被唤醒后的回调。 task_woken_fair

3.2.2 调度类的层次结构

内核中的调度类按照优先级从高到低组织成一个链表。调度器在选择下一个任务时，会从最高优先级的调度类开始查询，直到找到一个有可运行任务的调度类。

优先级顺序： 停止调度类（Stop） > Deadline 调度类（DL） > 实时调度类（RT） > 公平调度类（CFS） > 空闲调度类（Idle）。这种层次结构确保了实时任务和 Deadline 任务能够优先于普通进程获得 CPU 时间。

下图展示了调度类的层次结构以及它们与运行队列的关系：

调度类层次结构与运行队列关系图 调度类层次结构与运行队列关系 Stop 调度类 Deadline 调度类 RT 调度类 CFS 每个 CPU 的运行队列 (struct rq) cfs_rq (CFS 运行队列) rt_rq (RT 运行队列) dl_rq (DL 运行队列) 调度类选择逻辑 1. 调度器遍历调度类链表，从 Stop 开始。 2. 对每个调度类调用 pick_next_task()，直到找到有任务的调度类。 3. 高优先级调度类（如 RT）有任务时，低优先级类（如 CFS）不会被执行。

3.3 调度类的注册与使用

调度类通过 sched_class_highest 指针链接在一起。内核在初始化时，会按照优先级顺序将各个调度类实例注册到这个链表中。调度器核心函数 pick_next_task 会遍历这个链表，选择优先级最高的可运行任务。

// 调度类链表定义（简化）
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;

// 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, prev, rf);
        if (p)
            return p;
    }
    // 如果没有找到任何任务，返回 idle 任务
    return rq->idle;
}

3.4 调度实体与调度类的协同工作

调度实体和调度类共同构成了内核调度器的核心运行机制。调度类定义了“如何调度”的算法和策略，而调度实体则代表了“谁被调度”的具体对象。当调度器需要做出决策时，它会通过调度类的接口操作调度实体，例如将调度实体插入红黑树、更新其 vruntime 或选择下一个要运行的调度实体。

协同流程示例：
  1. 时钟中断触发： scheduler_tick() 调用当前任务所在调度类的 task_tick() 方法。
  2. 更新统计： CFS 调度类的 task_tick_fair() 调用 update_curr_fair()，更新当前调度实体 se 的 vruntime 和 sum_exec_runtime。
  3. 检查抢占： 如果当前任务的 vruntime 超过了红黑树中最左节点的 vruntime，则设置 TIF_NEED_RESCHED 标志。
  4. 进程切换： 在返回用户空间或中断返回时，检查 TIF_NEED_RESCHED 标志，调用 schedule() 函数。
  5. 选择下一个任务： schedule() 调用 pick_next_task()，遍历调度类链表，最终由 CFS 调度类的 pick_next_task_fair() 从红黑树中选择 vruntime 最小的调度实体。

通过这种清晰的分层和抽象，Linux 内核调度器实现了高度的模块化和可扩展性。开发者可以轻松地添加新的调度类（如 sched_ext 调度类），而无需修改调度器的核心框架。调度实体作为负载跟踪的基本单元，为 PELT 算法提供了精确的负载数据，使得调度器能够做出更加智能的决策。

← 上一章 📖 返回目录 下一章 →