RISC-V Linux Schedule 分析

Author: Jack Y. eecsyty@outlook.com Date: 2022/05/22 Revisor: Falcon falcon@tinylab.org Project: RISC-V Linux 内核剖析

前言

上一篇文章 我们分析了 RISC-V 架构下 Linux 内核的上下文切换机制，这篇文章我们顺着这个思路继续讨论 Linux 的任务调度。

__schedule() 函数是 Linux 任务调度的入口，不严格地说，调用一次 __schedule() 函数就是完成了一次任务调度过程，在这个函数的最后，调用了「RISC-V Linux 上下文切换分析」一文中介绍的 context_swtich() 函数来完成上下文切换。

本文参考的内核版本为 5.17。

何时调用 __schedule()

何时调用 __schedule() 函数的问题也就是 Linux 何时进行任务调度的问题。 在 __schedule() 函数定义的上面，有一段很长的注释（见 kernel/sched/core.c:6143），描述了调用这个函数来驱动调度过程的几种情况：

1. 显式阻塞，比如无法获得锁、等待信号量、进程进入等待队列等，这基本上就是进程由于自身原因进入等待状态。
2. 为了在周期性调度器中实现进程抢占，系统会在 timer tick 中断服务函数 scheduler_tick() 中设置 TIF_NEED_RESCHED 标志；如果这个标志被设置，那么在中断或用户空间返回时，会执行 __schedule() 函数，进行一次任务调度。
3. 进程唤醒（比如其等待的资源可获得了，或者其设置的等待时间到达了）并不是直接调用 __schedule() 函数切换到该进程，而仅仅是把它放到运行队列中，待下一次 __schedule() 调用时按照调度器的规则进行调度，有机会调度到这个被唤醒的进程。

__schedule() 流程分析

函数入参

__schedule() 函数有一个入参，名为 sched_mode，类型为 unsigned int，顾名思义它代表着调度模式。这个调度模式是为了在开启 RT 的情况下，__schedule() 函数能够区分这次调用是进程被抢占了，还是进程由于等待资源而「主动」让出CPU。sched_mode 共有三个枚举，其中后两者都是在开启 RT 情况下有效。

// kernel/sched/core.c:6133
#define SM_NONE			0x0
#define SM_PREEMPT		0x1
#define SM_RTLOCK_WAIT		0x2

准备工作

在 __schedule() 函数的开始，首先进行了一些准备工作：

// kernel/sched/core.c:6191
cpu = smp_processor_id();
rq = cpu_rq(cpu);
prev = rq->curr;

schedule_debug(prev, !!sched_mode);

if (sched_feat(HRTICK) || sched_feat(HRTICK_DL))
    hrtick_clear(rq);

local_irq_disable();
rcu_note_context_switch(!!sched_mode);

rq_lock(rq, &rf);
smp_mb__after_spinlock();

首先 schedule_debug() 记录了一些调试用的统计信息，并检查了一些状态是否符合预期。

hrtick_clear() 函数关闭了 hrtimers，后者利用硬件提供了一个比较精确的定时器子系统。因为此时已经在调度函数中了，不需要再通过 hrtimers 来进入调度器（详见「参考文档 1」)。

之后关闭了 IRQ 中断，防止在调度过程中被中断打断。

然后通过 rcu_note_context_switch() 函数更新 RCU 状态，有关 RCU 的介绍可阅读参考文章 2。

尽管每个 CPU 有一个单独的 Running Queue，但 rq 还是有可能被其他 CPU 访问（比如负载均衡场景），因此上述代码中最后两行先加了 rq 的锁，然后又加了一个内存屏障。 这个内存屏障在 RISC-V 的实现如下：

// arch/riscv/include/asm/barrier.h:70
#define smp_mb__after_spinlock()	RISCV_FENCE(iorw,iorw)

// arch/riscv/include/asm/barrier.h:17
#define RISCV_FENCE(p, s) \
	__asm__ __volatile__ ("fence " #p "," #s : : : "memory")

这里 RISC-V 的实现是使用 fence 指令加了 iorw 的全量屏障，这部分作者在注释中也说明了他其实也不认为有必要加全量屏障，但加上以后「更加安全」，详情内容读者可以阅读 arch/riscv/include/asm/barrier.h:45。

更新运行队列的 clock

__schedule() 函数接下来更新了 rq 的时钟：

// kernel/sched/core.c:6221
	/* Promote REQ to ACT */
	rq->clock_update_flags <<= 1;
	update_rq_clock(rq);

// kernel/sched/core.c:679
void update_rq_clock(struct rq *rq)
{
	s64 delta;

	lockdep_assert_rq_held(rq);

	if (rq->clock_update_flags & RQCF_ACT_SKIP)
		return;

	delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
	if (delta < 0)
		return;
	rq->clock += delta;
	update_rq_clock_task(rq, delta);
}

clock_update_flags 的移位我觉得算是一个比较取巧的操作，我认为可以理解为一个状态机的状态转换。如果某个地方给 clock_update_flags 设置成了 RQCF_REQ_SKIP，即请求跳过 clock_update，那么这里就左移一位变成 RQCF_ACT_SKIP，并在后面「执行」跳过的动作；如果 clock_update_flags 为 0，即没有请求跳过，那移位后还是 0。

然后 update_rq_clock() 函数中，如果 clock_update_flags 为 RQCF_REQ_SKIP，则直接返回，跳过更新 clock 的过程。 如果不跳过，这里主要是更新 rq 的两个成员 clock 和 clock_task，前者是当前运行队列总共运行的时间，后者是去除中断时间后，当前运行队列实际执行任务的时间。 代码中通过 sched_clock_cpu 先计算 delta 再加到 clock 上，这是避免时钟波动造成 clock 变小的情况。

有关当前任务的一些处理

接下来根据正在运行的任务状态，进行一些处理工作：

// kernel/sched/core.c:6225
switch_count = &prev->nivcsw;

prev_state = READ_ONCE(prev->__state);
if (!(sched_mode & SM_MASK_PREEMPT) && prev_state) {
    if (signal_pending_state(prev_state, prev)) {
        WRITE_ONCE(prev->__state, TASK_RUNNING);
    } else {
        prev->sched_contributes_to_load =
            (prev_state & TASK_UNINTERRUPTIBLE) &&
            !(prev_state & TASK_NOLOAD) &&
            !(prev->flags & PF_FROZEN);

        if (prev->sched_contributes_to_load)
            rq->nr_uninterruptible++;

        deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);

        if (prev->in_iowait) {
            atomic_inc(&rq->nr_iowait);
            delayacct_blkio_start();
        }
    }
    switch_count = &prev->nvcsw;
}

switch_count 是取了当前任务的切换计数的地址，如果当前任务是「非自愿」让出 CPU，那么则取 nivcsw；反之如果当前任务是「自愿」让出 CPU，那么取 nvcsw。这里面 “iv” 即 involuntary，而 “v” 即 voluntary。 后面如果真的发生了上下文切换，那么就会把 switch_count 这个地址的值加一。

判断当前任务是否「自愿」让出 CPU 的条件是 !(sched_mode & SM_MASK_PREEMPT) && prev_state，首先判断 __schedule() 函数的入参，即发生调度的场景是否是抢占，如果当前任务是被抢占的，肯定就不是「自愿」让出 CPU的；如果不是抢占场景，那么需要根据当前任务的 __state 来判断。

主要任务状态的定义如下（后面还有一些，这里就不一一列举了，有关任务状态的介绍读者可阅读「参考文章 3」）：

// include/linux/sched.h:83
#define TASK_RUNNING		0
#define TASK_INTERRUPTIBLE	1
#define TASK_UNINTERRUPTIBLE	2

只要当前任务状态不为 TASK_RUNNING，那就说明当前任务在调用到 __schedule() 函数之前，处于某些原因，已经「自愿」更改到其他状态了；也就是说如果当前任务的状态仍为 TASK_RUNNING 那就是当前任务原本处于正在运行的状态，而因为时间片到了等原因，被剥夺了 CPU 的使用权。

对于任务「自愿」退出的情况，需要做一些额外处理：

如果当前进程仍有未处理的信号，则把该任务重新挂上 TASK_RUNNING 的状态，注意此时该任务仍在运行队列中，下一次从运行队列中取任务时，大概率还会取到该任务，让其能处理完这些信号。

如果当前进程没有未处理的信号，那么既然该任务已经「自愿」放弃 CPU，那么目前其必然也没有再次被调度的必要，调用 deactivate_task() 函数将该任务从运行队列中移除。 同时如果其状态处于「不可中断」，则把该运行队列的 nr_uninterruptible 加一，这会在负载均衡时计算各个 CPU 的任务数量时用到；如果其正在等待 IO，那么给该运行队列的 nr_iowait 加一，这个 iowait 用于统计任务处于 IO 等待的时间，可在存储性能优化时提供参考（详见 kernel/sched/core.c:5059 处的注释）。

选取下一个任务

接下来会调用 pick_next_task() 函数，从运行队列中选取下一个任务用于调度，这里也是各种调度算法的核心。

pick_next_task() 函数的实现在 kernel/sched/core.c:5677，这个函数目前非常长，主要原因是在 Linux 5.14 版本中合并了「Core Scheduling」特性，该特性主要解决支持超线程 CPU 中的安全性问题，读者可详见「参考文章 4」。Linus 认为这个特性只对于少数云服务提供商有用处（详见「参考文章 5」)，因此目前 Linux 默认是关闭这个功能的。

在未开启「Core Scheduling」时，直接调用内部函数 __pick_next_task() 来使用「经典模式」选取下一个任务。

Linux 目前同时支持 5 种调度器，每种调度器根据其特点和用途采用不同的调度算法。对于非实时任务而言，Linux 默认采用完全公平调度器（Completely Fair Scheduler，简称 CFS），而对于实时任务则有专门的实时调度器。各个调度器之间有严格的优先级关系，高优先级调度器中的任务肯定比低优先级调度器中的任务先得到调度，即只有高优先级调度器中无任务时，低优先级调度器中的任务才有机会执行。

这 5 个调度器优先级的定义如下，从高到低分别为 stop_sched_class，dl_sched_class，rt_sched_class，fair_sched_class，idle_sched_class：

// include/asm-generic/vmlinux.lds.h:122
/*
 * The order of the sched class addresses are important, as they are
 * used to determine the order of the priority of each sched class in
 * relation to each other.
 */
#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 = .;

其中 stop_sched_class 只在多核场景下启用，用于热插拔等场景下停止 CPU；dl_sched_class 则为采用 Earliest Deadline First (EDF) 算法的 DeadLine 调度器；rt_sched_class 则为上文中提到的为实时任务准备的实时调度器；fair_sched_class 为 CFS 调度器；idle_sched_class 为空闲调度器，每个 CPU 核都有一个空闲线程，当没有其他线程可供调用时，则调度 idle_sched_class 中的空闲线程，此时该 CPU 处于「空闲」状态。

按照这样具有优先级顺序的调度器设计，__pick_next_task() 理应按照优先级从高到低顺序遍历各个调度器，如果某个调度器成功取出了任务，则选择该任务进行调度，后面低优先级的调度器则无需再访问：

// kernel/sched/core.c:5633
for_each_class(class) {
    p = class->pick_next_task(rq);
    if (p)
        return p;
}

但由于绝大多数任务都在 CFS 调度器上，因此这里也做了一个优化，先判断当前任务所属的调度器优先级是否等于或低于 CFS 调度器，再判断当前运行队列中的任务数量等于当前 CFS 运行队列的任务数量（即当前运行队列中的任务全都是 CFS 任务），同时满足这两个条件的话，则直接从 CFS 调度器中取任务即可：

// kernel/sched/core.c:5614
if (likely(prev->sched_class <= &fair_sched_class &&
        rq->nr_running == rq->cfs.h_nr_running)) {

    p = pick_next_task_fair(rq, prev, rf);
    if (unlikely(p == RETRY_TASK))
        goto restart;

    /* Assume the next prioritized class is idle_sched_class */
    if (!p) {
        put_prev_task(rq, prev);
        p = pick_next_task_idle(rq);
    }

    return p;
}

每个调度器都实现了自己的 pick_next_task() 函数，通过调度器结构体中的 pick_next_task 函数指针访问。

本文对于调度器具体的调度算法暂时按下不表，下篇文章将介绍 CFS 调度器的调度算法。

执行上下文切换

选取了新任务后，如果新任务和当前任务不同，则调用 context_switch() 函数进行上下文切换，在上一篇介绍上下文切换的文章中介绍过，context_switch() 最后会释放掉运行队列的锁。如果选取的新任务和当前任务相同，则无需上下文切换，直接释放掉运行队列的锁即可结束。

// kernel/sched/core.c:6275
if (likely(prev != next)) {
    rq->nr_switches++;
    RCU_INIT_POINTER(rq->curr, next);

    ++*switch_count;

    migrate_disable_switch(rq, prev);
    psi_sched_switch(prev, next, !task_on_rq_queued(prev));

    trace_sched_switch(sched_mode & SM_MASK_PREEMPT, prev, next);

    rq = context_switch(rq, prev, next, &rf);
} else {
    rq->clock_update_flags &= ~(RQCF_ACT_SKIP|RQCF_REQ_SKIP);

    rq_unpin_lock(rq, &rf);
    __balance_callbacks(rq);
    raw_spin_rq_unlock_irq(rq);
}

本文小结

本文介绍了 Linux 任务调度的入口 __schedule() 函数，其主要作用是在需要进行调度的时候，更新运行队列的一些基本信息，并按照优先级从调度器中选取一个任务，触发上下文切换。 下一篇文章将延续本文的思路，继续介绍当前 Linux 中最重要的 CFS 调度器。

参考文章

1. what is hrtick_clear(rq); in linux scheduler?
2. RCU synchronize原理分析
3. linux 中进程的状态
4. Core scheduling lands in 5.14
5. Re: [GIT PULL] scheduler changes for v5.14