2.2.2 核心概念 - 调度类

简要介绍Sched Class

系统中可能运行着各种类型的进程，用户对不同种类进程的期望值是不一样的，例如对于实时进程，我们希望进程具备超高的响应速度，进程一旦就绪就立马被调度到；而对于批处理进程，用户更多关注的是其吞吐量，只要他能够在后台默默运行完成就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,
};

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