2.8.6 调度进程
调度进程的核心函数是__schedule()，函数原型如下：
kernel/sched/core.c
static void __sched notrace __schedule(bool preempt)
参数preempt表示是否抢占调度，值为true表示抢占调度，强制剥夺当前进程对处理器的使用权；值为false表示主动调度，当前进程主动让出处理器。
主动调度进程的函数是schedule()，它把主要工作委托给函数__schedule()。
函数__schedule的主要处理过程如下。
（1）调用pick_next_task以选择下一个进程。
（2）调用context_switch以切换进程。
1．选择下一个进程
函数pick_next_task负责选择下一个进程，其代码如下：
kernel/sched/core.c
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;
/*
* 优化：如果所有进程属于公平调度类，
* 我们可以直接调用公平调度类的pick_next_task方法
*/
if (likely((prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = fair_sched_class.pick_next_task(rq, prev, rf);
if (unlikely(p == RETRY_TASK))
goto again;
/* 假定公平调度类的下一个调度类是空闲调度类*/
if (unlikely(! p))
p = idle_sched_class.pick_next_task(rq, prev, rf);
return p;
}
again:
for_each_class(class) {
p = class->pick_next_task(rq, prev, rf);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
}
}
/* 空闲调度类应该总是有一个可运行的进程 */
BUG();
函数pick_next_task针对公平调度类做了优化：如果当前进程属于空闲调度类或公平调度类，并且所有可运行的进程属于公平调度类，那么直接调用公平调度类的pick_next_task方法来选择下一个进程。如果公平调度类没有选中下一个进程，那么从空闲调度类选择下一个进程。
一般情况是：从优先级最高的调度类开始，调用调度类的pick_next_task方法来选择下一个进程，如果选中了下一个进程，就调度这个进程，否则继续从优先级更低的调度类选择下一个进程。现在支持5种调度类，优先级从高到低依次是停机、限期、实时、公平和空闲。
（1）停机调度类选择下一个进程。停机调度类中用于选择下一个进程的函数是pick_next_task_stop，算法是：如果运行队列的成员stop指向某个进程，并且这个进程在运行队列中，那么返回成员stop指向的进程，否则返回空指针。
（2）限期调度类选择下一个进程。限期调度类中用于选择下一个进程的函数是pick_next_task_dl，算法是：从限期运行队列选择绝对截止期限最小的进程，就是红黑树中最左边的进程。限期调度类不支持任务组，所以不需要考虑调度实体是任务组的情况。
（3）实时调度类选择下一个进程。实时调度类中用于选择下一个进程的函数是pick_next_task_rt，算法如下。
1）如果实时运行队列没有加入运行队列（rt_rq.rt_queued等于0，如果在一个处理器上所有实时进程在一个周期内用完了运行时间，就会把实时运行队列从运行队列中删除），那么返回空指针。
2）从根任务组在当前处理器上的实时运行队列开始，选择优先级最高的调度实体。
3）如果选中的调度实体是任务组，那么继续从这个任务组在当前处理器上的实时运行队列中选择优先级最高的调度实体，重复这个步骤，直到选中的调度实体是进程为止。
（4）公平调度类选择下一个进程。公平调度类中用于选择下一个进程的函数是pick_next_task_fair，算法如下。
1）从根任务组在当前处理器上的公平运行队列中，选择虚拟运行时间最小的调度实体，就是红黑树中最左边的调度实体。
2）如果选中的调度实体是任务组，那么继续从这个任务组在当前处理器上的公平运行队列中选择虚拟运行时间最小的调度实体，重复这个步骤，直到选中的调度实体是进程为止。
（5）空闲调度类选择下一个进程。空闲调度类中用于选择下一个进程的函数是pick_next_task_idle，算法是：返回运行队列的成员idle指向的空闲线程。
2．切换进程
切换进程的函数是context_switch，执行的主要工作如下。
（1）switch_mm_irqs_off负责切换进程的用户虚拟地址空间。
（2）switch_to负责切换处理器的寄存器。
函数context_switch的代码如下：
kernel/sched/core.c
static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
struct task_struct *next, struct pin_cookie cookie)
{
struct mm_struct *mm, *oldmm;
prepare_task_switch(rq, prev, next);
prepare_task_switch执行进程切换的准备工作，调用每种处理器架构必须定义的函数prepare_arch_switch。ARM64架构没有定义函数prepare_arch_switch，使用默认定义，它是一个空的宏。
mm = next->mm;
oldmm = prev->active_mm;
arch_start_context_switch(prev);
函数arch_start_context_switch开始上下文切换，是每种处理器架构必须定义的函数。ARM64架构没有定义函数arch_start_context_switch，使用默认定义，它也是一个空的宏。
if (! mm) {
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next);
} else
switch_mm_irqs_off(oldmm, mm, next);
如果下一个进程是内核线程（成员mm是空指针），内核线程没有用户虚拟地址空间，那么需要借用上一个进程的用户虚拟地址空间，把借来的用户虚拟地址空间保存在成员active_mm中，内核线程在借用的用户虚拟地址空间的上面运行。
函数enter_lazy_tlb通知处理器架构不需要切换用户虚拟地址空间，这种加速进程切换的技术称为惰性TLB。ARM64架构定义的函数enter_lazy_tlb是一个空函数。
如果下一个进程是用户进程，那么调用函数switch_mm_irqs_off切换进程的用户虚拟地址空间。
if (! prev->mm) {
prev->active_mm = NULL;
rq->prev_mm = oldmm;
}
如果上一个进程是内核线程，那么把成员active_mm设置成空指针，断开它和借用的用户虚拟地址空间的联系，把它借用的用户虚拟地址空间保存在运行队列的成员prev_mm中。
/* 这里我们只切换寄存器状态和栈 */
switch_to(prev, next, prev);
barrier();
return finish_task_switch(prev);
}
函数switch_to是每种处理器架构必须定义的函数，负责切换处理器的寄存器。
barrier()是编译器优化屏障，防止编译器优化时调整switch_to和finish_task_switch的顺序。
函数finish_task_switch负责在进程切换后执行清理工作。
（1）切换用户虚拟地址空间。ARM64架构使用默认的switch_mm_irqs_off，其定义如下：
include/linux/mmu_context.h
#ifndef switch_mm_irqs_off
#define switch_mm_irqs_off switch_mm
#endif
函数switch_mm的代码如下：
arch/arm64/include/asm/mmu_context.h
1 static inline void
2 switch_mm(struct mm_struct *prev, struct mm_struct *next,
3 struct task_struct *tsk)
4 {
5 if (prev ! = next)
6 __switch_mm(next);
7
8 /*
9 * 更新调入进程保存的寄存器TTBR0_EL1值，
10 * 因为可能还没有初始化（调用者是函数activate_mm），
11 * 或者ASID自从上次运行以来已经改变（在同一个线程组的另一个线程切换上下文以后）
12 *
13 * 避免把保留的寄存器TTBR0_EL1值设置为swapper_pg_dir（init_mm；例如通过函数idle_task_exit）
14 */
15 if (next ! = &init_mm)
16 update_saved_ttbr0(tsk, next);
17 }
18
19 static inline void __switch_mm(struct mm_struct *next)
20 {
21 unsigned int cpu = smp_processor_id();
22
23 /*
24 * init_mm.pgd没有包含任何用户虚拟地址的映射，对于TTBR1的内核虚拟地址总是有效的。
25 * 只设置保留的TTBR0
26 */
27 if (next == &init_mm) {
28 cpu_set_reserved_ttbr0();
29 return;
30 }
31
32 check_and_switch_context(next, cpu);
33 }
第5行和第6行代码，如果prev不等于next，即上一个进程和下一个进程的用户虚拟地址空间不同，那么调用函数__switch_mm切换用户虚拟地址空间。
函数__switch_mm的执行过程如下。
1）第27～30行代码，如果切换到内核的内存描述符init_mm，那么把寄存器TTBR0_EL1设置为保留的地址空间标识符0和保留的零页empty_zero_page的物理地址。目前只有这种情况需要切换到内核的内存描述符init_mm：内核支持处理器热插拔，当处理器下线时，如果空闲线程借用用户进程的内存描述符，那么必须切换到内核的内存描述符init_mm。寄存器TTBR0_EL1（转换表基准寄存器0, Translation table base register 0）用来存放进程的地址空间标识符和页全局目录的物理地址，其中高16位是地址空间标识符，处理器的页表缓存使用地址空间标识符区分不同进程的虚拟地址。
2）第32行代码，这是函数__switch_mm的重点，调用函数check_and_switch_context为进程分配地址空间标识符，具体过程参考3.12.3节。
第15行和第16行代码，如果通过切换寄存器TTBR0_EL1仿真PAN特性，那么把进程的地址空间标识符和页全局目录的物理地址保存到进程描述符的成员thread_info.ttbr0，等进程退出内核模式时使用进程描述符的成员thread_info.ttbr0设置寄存器TTBR0_EL1。PAN（Privileged Access Never）特性用来禁止内核访问用户虚拟地址。如果处理器不支持PAN特性，那么内核通过切换寄存器TTBR0_EL1仿真PAN特性：进程进入内核模式时把寄存器TTBR0_EL1设置为保留的地址空间标识符0和内核的页全局目录（swapper_pg_dir）后面的保留区域的物理地址，退出内核模式时把寄存器TTBR0_EL1设置为进程的地址空间标识符和页全局目录的物理地址。使用保留的地址空间标识符0可以避免命中页表缓存的表项，防止内核访问用户虚拟地址。
（2）切换寄存器。宏switch_to把这项工作委托给函数__switch_to：
include/asm-generic/switch_to.h
#define switch_to(prev, next, last) \
do { \
((last) = __switch_to((prev), (next))); \
} while (0)
ARM64架构定义的函数__switch_to如下：
arch/arm64/kernel/process.c
1 __notrace_funcgraph struct task_struct *__switch_to(struct task_struct *prev,
2 struct task_struct *next)
3 {
4 struct task_struct *last;
5
6 fpsimd_thread_switch(next);
7 tls_thread_switch(next);
8 hw_breakpoint_thread_switch(next);
9 contextidr_thread_switch(next);
10 entry_task_switch(next);
11 uao_thread_switch(next);
12
13 /*
14 * 在这个处理器上执行完前面的所有页表缓存或者缓存维护操作，
15 * 以防线程迁移到其他处理器
16 */
17 dsb(ish);
18
19 /* 实际的线程切换 */
20 last = cpu_switch_to(prev, next);
21
22 return last;
23 }
第6行代码，调用函数fpsimd_thread_switch以切换浮点寄存器。
第7行代码，调用函数tls_thread_switch以切换线程本地存储相关的寄存器。
第8行代码，调用函数hw_breakpoint_thread_switch以切换调试寄存器。
第9行代码，调用函数contextidr_thread_switch把上下文标识符寄存器CONTEXTIDR_EL1设置为下一个进程的进程号。
第10行代码，调用函数entry_task_switch使用当前处理器的每处理器变量__entry_task记录下一个进程的进程描述符的地址，因为内核使用用户栈指针寄存器SP_EL0存放当前进程的进程描述符的第一个成员thread_info的地址，但是用户空间会改变用户栈指针寄存器SP_EL0，所以使用当前处理器的每处理器变量__entry_task记录下一个进程的进程描述符的地址，以便从用户空间进入内核空间时可以恢复用户栈指针寄存器SP_EL0。
第11行代码，调用函数uao_thread_switch根据下一个进程可访问的虚拟地址空间上限恢复用户访问覆盖（User Access Override, UAO）状态。开启UAO特性以后，get_user()/put_user()使用非特权的加载/存储指令访问用户地址空间，当使用函数set_fs(KERNEL_DS)把进程可访问的地址空间上限设置为内核地址空间上限时，设置覆盖位允许非特权的加载/存储指令访问内核地址空间。
第17行代码，dsb(ish)是数据同步屏障，确保屏障前面的缓存维护操作和页表缓存维护操作执行完。
第20行代码，调用函数cpu_switch_to以切换通用寄存器。
1）切换浮点寄存器。
函数fpsimd_thread_switch负责切换浮点（Floating-point, FP）寄存器。因为不同处理器架构的浮点寄存器不同，而且有的处理器架构不支持浮点运算，所以各种处理器架构需要自己实现函数fpsimd_thread_switch。ARM64处理器支持浮点运算，浮点运算和单指令多数据（Single Instruction Multiple Data, SIMD）功能共用32个128位寄存器，这些寄存器称为浮点寄存器，用于向量运算时称为向量寄存器，标记为V0～V31（V代表vector），用于标量（标量浮点数或者标量整数）运算时标记为Q0～Q31（Q代表Quadword，即4个字，一个字是4字节）。
因为不是所有处理器都支持浮点运算，所以内核不允许使用浮点数，只有用户空间可以使用浮点数。利用这个特性，处理器从进程切换到内核线程时不需要切换浮点寄存器。如果处理器从进程P切换到内核线程，然后从内核线程切换到进程P，那么两次进程切换都不需要切换浮点寄存器。
切换出去的进程把浮点寄存器的值保存在进程描述符的成员thread.fpsimd_state中。
ARM64架构实现的函数fpsimd_thread_switch如下：
arch/arm64/kernel/fpsimd.c
1 void fpsimd_thread_switch(struct task_struct *next)
2 {
3 if (! system_supports_fpsimd())
4 return;
5
6 if (current->mm && ! test_thread_flag(TIF_FOREIGN_FPSTATE))
7 fpsimd_save_state(¤t->thread.fpsimd_state);
8
9 if (next->mm) {
10 struct fpsimd_state *st = &next->thread.fpsimd_state;
11
12 if (__this_cpu_read(fpsimd_last_state) == st
13 && st->cpu == smp_processor_id())
14 clear_ti_thread_flag(task_thread_info(next),
15 TIF_FOREIGN_FPSTATE);
16 else
17 set_ti_thread_flag(task_thread_info(next),
18 TIF_FOREIGN_FPSTATE);
19 }
20 }
第3行和第4行代码，如果处理器不支持浮点和SIMD，那么直接返回。
第6行和第7行代码，如果当前进程是用户进程，并且处理器的浮点状态是当前进程的，那么把浮点寄存器保存到当前进程的进程描述符的成员thread.fpsimd_state中。
第9行代码，如果下一个进程是用户进程，执行以下操作。
❑ 第12～15行代码，如果当前处理器的浮点状态是下一个进程的浮点状态，那么清除下一个进程的标志位TIF_FOREIGN_FPSTATE，指示当前处理器的浮点状态是下一个进程的浮点状态。
❑ 第16～18行代码，否则，设置下一个进程的标志位TIF_FOREIGN_FPSTATE，指示当前处理器的浮点状态不是下一个进程的。当进程准备返回用户模式的时候，在函数do_notify_resume中，发现进程设置了标志位TIF_FOREIGN_FPSTATE，那么调用函数fpsimd_restore_current_state从进程描述符的成员thread.fpsimd_state恢复浮点寄存器，并清除标志位TIF_FOREIGN_FPSTATE。
函数fpsimd_save_state负责保存浮点寄存器的状态，其代码如下：
arch/arm64/kernel/entry-fpsimd.S
ENTRY(fpsimd_save_state)
fpsimd_save x0, 8
ret
ENDPROC(fpsimd_save_state)
头文件“arch/arm64/include/asm/fpsimdmacro.h”定义了宏fpsimd_save，把宏展开后，函数fpsimd_save_state的代码如下：
arch/arm64/kernel/entry-fpsimd.S
ENTRY(fpsimd_save_state)
Stp q0, q1, [x0, #16 * 0] /* 把寄存器q0和q1存储到地址(x0 + 16) */
stp q2, q3, [x0, #16 * 2]
stp q4, q5, [x0, #16 * 4]
stp q6, q7, [x0, #16 * 6]
stp q8, q9, [x0, #16 * 8]
stp q10, q11, [x0, #16 * 10]
stp q12, q13, [x0, #16 * 12]
stp q14, q15, [x0, #16 * 14]
stp q16, q17, [x0, #16 * 16]
stp q18, q19, [x0, #16 * 18]
stp q20, q21, [x0, #16 * 20]
stp q22, q23, [x0, #16 * 22]
stp q24, q25, [x0, #16 * 24]
stp q26, q27, [x0, #16 * 26]
stp q28, q29, [x0, #16 * 28]
stp q30, q31, [x0, #16 * 30]! /* 把寄存器q30和q31存储到地址(x0 + 16 * 30)，然后把寄存
器x0加上（16 * 30）*/
mrs x8, fpsr
str w8, [x0, #16 * 2]
mrs x8, fpcr
str w8, [x0, #16 * 2 + 4]
ret
ENDPROC(fpsimd_save_state)
寄存器x0存放当前进程的进程描述符的成员thread.fpsimd_state的地址。
该函数把浮点寄存器q0～q31、浮点状态寄存器（Floating-point Status Register, FPSR）和浮点控制寄存器（Floating-point Control Register, FPCR）保存到当前进程的进程描述符的成员thread.fpsimd_state中。
2）切换通用寄存器。函数cpu_switch_to切换下面这些通用寄存器。
❑ 由被调用函数负责保存的寄存器x19～x28。被调用函数必须保证这些寄存器在函数执行前后的值相同，如果被调用函数需要使用其中一个寄存器，必须先把寄存器的值保存在栈里面，在函数返回前恢复寄存器的值。
❑ 寄存器x29，即帧指针（Frame Pointer, FP）寄存器。
❑ 栈指针（Stack Pointer, SP）寄存器。
❑ 寄存器x30，即链接寄存器（Link Register, LR），它存放函数的返回地址。
❑ 用户栈指针寄存器SP_EL0，内核使用它存放当前进程的进程描述符的第一个成员thread_info的地址。
相关代码如下：
arch/arm64/kernel/entry.S
1 ENTRY(cpu_switch_to)
2 mov x10, #THREAD_CPU_CONTEXT
3 add x8, x0, x10
4 mov x9, sp
5
6 stp x19, x20, [x8], #16 //保存由被调用者负责保存的寄存器
7 stp x21, x22, [x8], #16
8 stp x23, x24, [x8], #16
9 stp x25, x26, [x8], #16
10 stp x27, x28, [x8], #16
11 stp x29, x9, [x8], #16
12 str lr, [x8]
13
14 add x8, x1, x10
15
16 ldp x19, x20, [x8], #16 //恢复由被调用者负责保存的寄存器
17 ldp x21, x22, [x8], #16
18 ldp x23, x24, [x8], #16
19 ldp x25, x26, [x8], #16
20 ldp x27, x28, [x8], #16
21 ldp x29, x9, [x8], #16
22 ldr lr, [x8]
23 mov sp, x9
24
25 msr sp_el0, x1
26
27 ret
28 ENDPROC(cpu_switch_to)
函数cpu_switch_to有两个参数：寄存器x0存放上一个进程的进程描述符的地址，寄存器x1存放下一个进程的进程描述符的地址。
第2行代码，寄存器x10存放进程描述符的成员thread.cpu_context的偏移。
第3行代码，寄存器x8存放上一个进程的进程描述符的成员thread.cpu_context的地址。
第4行代码，寄存器x9保存栈指针。
第6～12行代码，把上一个进程的寄存器x19～x28、x29、SP和LR保存到上一个进程的进程描述符的成员thread.cpu_context中。寄存器LR存放函数的返回地址，是函数context_switch中调用函数cpu_switch_to之后的一行代码。指令stp（store pair）表示存储一对。指令“stp x19, x20, [x8], #16”表示把寄存器x19和x20存储到寄存器x8里面的地址，然后把寄存器x8加上16。
第14行代码，寄存器x8存放下一个进程的进程描述符的成员thread.cpu_context的地址。
第16～23行代码，使用下一个进程的进程描述符的成员thread.cpu_context保存的值恢复下一个进程的寄存器x19～x28、x29、SP和LR。指令ldp（load pair）表示加载一对。指令“ldp x19, x20, [x8], #16”表示从寄存器x8里面的地址加载两个64位数据到寄存器x19和x20，然后把寄存器x8加上16。
第25行代码，把用户栈指针寄存器SP_EL0设置为下一个进程的进程描述符的第一个成员thread_info的地址。
第27行代码，函数返回，返回值是寄存器x0的值：上一个进程的进程描述符的地址。
图2.29描述了函数cpu_switch_to切换通用寄存器的过程，从进程prev切换到进程next。进程prev把通用寄存器的值保存在进程描述符的成员thread.cpu_context中，然后进程next从进程描述符的成员thread.cpu_context恢复通用寄存器的值，使用用户栈指针寄存器SP_EL0存放进程next的进程描述符的成员thread_info的地址。
图2.29 ARM64架构切换通用寄存器
链接寄存器存放函数的返回地址，函数cpu_switch_to把链接寄存器设置为进程描述符的成员thread.cpu_context.pc，进程被调度后从返回地址开始执行。进程的返回地址分为以下两种情况。
❑ 如果进程是刚刚创建的新进程，函数copy_thread把进程描述符的成员thread.cpu_context.pc设置为函数ret_from_fork的地址。
❑ 对于其他情况，返回地址是函数context_switch中调用函数cpu_switch_to之后的一行代码：“last = 函数cpu_switch_to的返回值”。当进程被切换出去的时候，把这个返回地址记录在进程描述符的成员thread.cpu_context.pc中。
（3）执行清理工作。函数finish_task_switch在从进程prev切换到进程next后为进程prev执行清理工作，其代码如下：
kernel/sched/core.c
1 static struct rq *finish_task_switch(struct task_struct *prev)
2 __releases(rq->lock)
3 {
4 struct rq *rq = this_rq();
5 struct mm_struct *mm = rq->prev_mm;
6 long prev_state;
7
8 …
9 rq->prev_mm = NULL;
10
11 prev_state = prev->state;
12 vtime_task_switch(prev);
13 …
14 finish_lock_switch(rq, prev);
15 finish_arch_post_lock_switch();
16
17 fire_sched_in_preempt_notifiers(current);
18 if (mm)
19 mmdrop(mm);
20 if (unlikely(prev_state == TASK_DEAD)) {
21 if (prev->sched_class->task_dead)
22 prev->sched_class->task_dead(prev);
23
24 …
25 /*释放进程的内核栈 */
26 put_task_stack(prev);
27
28 put_task_struct(prev);
29 }
30
31 tick_nohz_task_switch();
32 return rq;
33 }
第9行代码，rq是当前处理器的运行队列，如果进程prev是内核线程，那么rq->prev_mm存放它借用的内存描述符。这里把rq->prev_mm设置为空指针。
第12行代码，函数vtime_task_switch(prev)计算进程prev的时间统计。
第14行代码，函数finish_lock_switch(rq, prev)把prev->on_cpu设置为0，表示进程prev没有在处理器上运行；然后释放运行队列的锁，开启硬中断。
第15行代码，函数finish_arch_post_lock_switch()在执行完函数finish_lock_switch()以后，执行处理器架构特定的清理工作。ARM64架构没有定义，使用默认的空函数。
第18行和第19行代码，如果进程prev是内核线程，那么把它借用的内存描述符的引用计数减1，如果引用计数减到0，那么释放内存描述符。
第20行代码，如果进程prev的状态是TASK_DEAD，即进程主动退出或者被终止，那么执行以下清理操作。
1）第21行和第22行代码，调用进程prev所属调度类的task_dead方法。
2）第26行代码，调用函数put_task_stack：如果结构体thread_info放在进程描述符里面，而不是放在内核栈的顶部，那么释放进程的内核栈。
3）第28行代码，把进程描述符的引用计数减1，如果引用计数变为0，那么释放进程描述符。