# 2.2.2 核心概念 - 调度类

系统中可能运行着各种类型的进程，用户对不同种类进程的期望值是不一样的，例如对于实时进程，我们希望进程具备超高的响应速度，进程一旦就绪就立马被调度到；而对于批处理进程，用户更多关注的是其吞吐量，只要他能够在后台默默运行完成就OK, 因此对于调度器而言，不同的进程类型意味着不同的调度逻辑。

Linux 在 2.6 版本中引入了“调度类（Sched Class）”的概念，意在将调度逻辑模块化，内核通过 `struct sched_class` 抽象出了调度类的通用行为：

```
/* file: kernel/sched/sched.h */
struct sched_class {
#ifdef CONFIG_UCLAMP_TASK
    int uclamp_enabled;
#endif

    void (*enqueue_task)(struct rq *rq, struct task_struct *p, int flags);
    void (*dequeue_task)(struct rq *rq, struct task_struct *p, int flags);
    /* 任务主动让出 CPU,  但是其状态依然是 runnable */
    void (*yield_task)(struct rq *rq);
    bool (*yield_to_task)(struct rq *rq, struct task_struct *p);

    /* 检查 p 是否会抢占 rq 中当前正在运行的 task. 通常情况下是在 p 进入 runnable
     * 状态时，检查 p 是否会抢占当前正在运行的 task */
    void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);

    /* 从 rq 中选择下一个任务来运行 */
    struct task_struct *(*pick_next_task)(struct rq *rq);

    void (*put_prev_task)(struct rq *rq, struct task_struct *p);
    void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);

#ifdef CONFIG_SMP
    /* 检查选中的 cpu 在其 sched_domain
       中是否负载是平衡的，如果不平衡则需要对任务进行迁移。
       * 并不是所有的 scheduling class 都会实现该方法
       * */
    int (*balance)(struct rq *rq, struct task_struct *prev, struct rq_flags *rf);

    /* 当系统调用 fork, exec 创建一个新的 task 时，在 SMP 系统中需要选择一个合理的
     * runqueue 来将该 task 入队。Scheduler 此时需要考虑负载均衡问题 */
    int (*select_task_rq)(struct task_struct *p, int task_cpu, int flags);

    /* 将任务迁移到目标 CPU 上 */
    void (*migrate_task_rq)(struct task_struct *p, int new_cpu);

    /* 当任务被唤醒（wake up）之后调用 */
    void (*task_woken)(struct rq *this_rq, struct task_struct *task);

    /* 修改任务的 CPU 偏好，即其可以被调度到哪些 CPU 上运行 */
    void (*set_cpus_allowed)(struct task_struct *p, const struct cpumask *newmask,
                             u32 flags);

    void (*rq_online)(struct rq *rq);
    void (*rq_offline)(struct rq *rq);

    struct rq *(*find_lock_rq)(struct task_struct *p, struct rq *rq);
#endif

    void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
    void (*task_fork)(struct task_struct *p);
    void (*task_dead)(struct task_struct *p);

    /*
     * The switched_from() call is allowed to drop rq->lock, therefore we
     * cannot assume the switched_from/switched_to pair is serliazed by
     * rq->lock. They are however serialized by p->pi_lock.
     */
    void (*switched_from)(struct rq *this_rq, struct task_struct *task);
    void (*switched_to)(struct rq *this_rq, struct task_struct *task);
    void (*prio_changed)(struct rq *this_rq, struct task_struct *task,
                         int oldprio);

    unsigned int (*get_rr_interval)(struct rq *rq, struct task_struct *task);

    void (*update_curr)(struct rq *rq);

#define TASK_SET_GROUP 0
#define TASK_MOVE_GROUP 1

#ifdef CONFIG_FAIR_GROUP_SCHED
    void (*task_change_group)(struct task_struct *p, int type);
#endif
};
```

结构体的字段几乎都是函数申明，这对于有 OO 编程经验的同学而言是很熟悉的： `struct sched_class` 实际上定义了一个接口（Interface），而各个调度类来负责具体的实现。

在讨论调度类的具体实现之前，我们先来看一下调度器是如何通过各个调度类来选择下一个任务的。该逻辑定义在主方法 `struct task_struct * 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;
    }

    /* The idle class should always have a runnable task: */
    BUG();
}
```

调度器按照顺序对具体的调度类进行遍历，依次调用每个调度类的 `pick_next_task` 方法从指定 rq 中寻找下一个可执行任务，如果返回非空，则将该任务返回。

这里引出了两个问题：

1. 遍历调度类的顺序为何？
2. 内核有哪些调度类实现？

顺序遍历实际上意味着调度类之间存在优先级关系，Linux 总共实现了5种调度类，按照优先级有高到底排序依次为：

1. `stop_sched_class` \
   Stop 是特殊的调度类，内核使用该调度类来停止 CPU. 该调度类用来强行停止CPU 上的其他任务，由于该调度类的优先级最高，因此一旦生效就将抢占任何当前正在运行的任务，并且在运行过程中自己不会被抢占。

   该调度类只有在SMP架构的系统中存在，内核使用该调度类来完成负载均衡与CPU热插拔等工作。
2. `dl_sched_class` \
   有些任务必须在指定时间窗口内完成。例如视频的编码与解码，CPU 必须以特定频率完成对应的数据处理；这类任务是优先级最高的用户任务，CPU 应该首先满足。

   Deadline 调度类用来调度这类任务，dl 便是单词 Deadline 的缩写，因此该调度类的优先级仅仅低于 Stop 调度类。
3. `rt_sched_class` \
   在本节开头我们提到，实时任务（Real-time Task）对响应时间要求更高，例如编辑器软件，它可能由于等待用户输入长期处于睡眠之中，但一旦用户有输入动作，我们就期望编辑器能够立马响应，而不是等系统完成其它任务之后才开始反应，这一点对用户体验十分重要。

   RT 调度类用来调度这类任务，该调度类的优先级低于 DL.
4. `fair_sched_class` \
   Fair 调度类用来调度绝大多数用户任务，CFS 实现的就是这种调度类，其核心逻辑是根据任务的优先级公平地分配 CPU 时间。我们会在后续章节中详细讨论 CFS 的实现细节。
5. `idle_sched_class` \
   与 Stop 类似，Idle 调度类也是仅供内核使用的特殊调度类，其优先级最低，只有在没有任何用户任务时才会用到。内核会为每个 CPU 绑定一个内核线程（kthread）来完成该任务，该线程会在队列无事可做的情况下启动该任务，并将 CPU 的功耗降到最低。

对调度类的遍历通过宏 `for_each_class` 完成，相关代码定义如下：

```
/* Defined in include/asm-generic/vmlinux.lds.h */
extern struct sched_class __begin_sched_classes[];
extern struct sched_class __end_sched_classes[];

#define sched_class_highest (__end_sched_classes - 1)
#define sched_class_lowest (__begin_sched_classes - 1)

#define for_class_range(class, _from, _to)          \
    for (class = (_from); class != (_to); class --)

#define for_each_class(class)                                       \
    for_class_range(class, sched_class_highest, sched_class_lowest)
```

代码从变量 `__end_sched_classes` 开始，反向遍历至变量 `__begin_sched_classes`, 这两个变量定义在文件 `include/asm-generic/vmlinux.lds.h` 中，顺序如下：

```
#define SCHED_DATA                              \
    STRUCT_ALIGN();                             \
    __begin_sched_classes = .;                  \
    *(__idle_sched_class)                       \
        *(__fair_sched_class)                   \
        *(__rt_sched_class)                     \
        *(__dl_sched_class)                     \
        *(__stop_sched_class)                   \
        __end_sched_classes = .;
```

该顺序便是各个调度类的优先级顺序。

接下来我们简单看一下各个调度类的实现及初始化。

每种调度类的实现都在单独的文件中：

* idle: `kernel/sched/idle.c`
* fair: `kernel/sched/fair.c`
* rt: `kernel/sched/rt.c`
* dl: `kernel/sched/deadline.c`
* stop: `kernel/sched/stop_task.c`

每个调度类都实现了 `sched_class` 中申明的所有方法，以 idle 调度器为例， `pick_next_task` 方法的实现如下：

```
struct task_struct *pick_next_task_idle(struct rq *rq)
{
    struct task_struct *next = rq->idle;

    set_next_task_idle(rq, next, true);

    return next;
}
```

调度类的每个方法实现，都以该调度类的名称为后缀，内核在初始化时将其与 `struct sched_class` 中定义的方法关联起来。调度类的初始化工作通过宏 `DEFINE_SCHED_CLASS` 实现：

```
#define DEFINE_SCHED_CLASS(name)                                        \
    const struct sched_class name##_sched_class __aligned(__alignof__(  \
                                                              struct sched_class)) __section("__" #name "_sched_class")
```

可以发现各调度类变量的命名格式： `__<class name>_sched_class`, 这与前文中看到的调度类变量名一致。以 idle 为例，初始化代码如下：

```
DEFINE_SCHED_CLASS(idle) = {

/* no enqueue/yield_task for idle tasks */

/* dequeue is not valid, we print a debug message there: */
.dequeue_task       = dequeue_task_idle,

.check_preempt_curr = check_preempt_curr_idle,

.pick_next_task     = pick_next_task_idle,
.put_prev_task      = put_prev_task_idle,
.set_next_task          = set_next_task_idle,

#ifdef CONFIG_SMP
.balance        = balance_idle,
.select_task_rq     = select_task_rq_idle,
.set_cpus_allowed   = set_cpus_allowed_common,
#endif

.task_tick      = task_tick_idle,

.prio_changed       = prio_changed_idle,
.switched_to        = switched_to_idle,
.update_curr        = update_curr_idle,
};
```

其中可以清楚地看到各个方法的绑定逻辑。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://s3.shizhz.me/linux-sched/concepts/sched-class.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.