吐血整理

前面我们重点分析了如何通过 fork, vfork, pthread_create 去创建一个进程或者线程，以及后面说了它们共同调用 do_fork 的实现。现在已经知道一个进程是如何创建的，但是进程何时被执行，需要调度器来选择。所以这一节我们介绍下进程调度和进程切换的详情。

在 CPU 的角度看进程行为的话，可以分为两类：

CPU 消耗型进程需要高的吞吐率，IO 消耗型进程需要强的响应性，这两点都是调度器需要考虑的。

为了更快响应 IO 消耗型进程，内核提供了一个抢占(preempt)机制，使优先级更高的进程，去抢占优先级低的进程运行。内核用以下宏来选择内核是否打开抢占机制：

先来看几个相关的数据结构：

我们先把 task_struct 中和调度相关的结构拎出来：

分配给 CPU 的 task，作为调度实体加入到运行队列中。

runqueue 运行队列是本 CPU 上所有可运行进程的队列集合。每个 CPU 都有一个运行队列，每个运行队列中有三个调度队列，task 作为调度实体加入到各自的调度队列中。

三个调度队列：

这些数据结构的关系如下图所示：

调度的本质就是选择下一个进程，然后切换。在执行调度之前需要设置调度标记 TIF_NEED_RESCHED，然后在调度的时候会判断当前进程有没有被设置 TIF_NEED_RESCHED，如果设置则调用函数 schedule 来进行调度。

为 CPU 上正在运行的进程 thread_info 结构体里的 flags 成员设置 TIF_NEED_RESCHED。

那么，什么时候设置TIF_NEED_RESCHED呢 ？

2. wake_up_process 唤醒进程的时候

3. do_fork 创建新进程的时候

4. set_user_nice 修改进程nice值的时候

5. smp_send_reschedule 负载均衡的时候

Kernel 判断当前进程标记是否为 TIF_NEED_RESCHED，是的话调用 schedule 函数，执行调度，切换上下文，这也是上面抢占(preempt)机制的本质。那么在哪些情况下会执行 schedule 呢？

ret_to_user 是异常触发，系统调用，中断处理完成后都会调用的函数。

2. 内核态抢占

可以看出无论是用户态抢占，还是内核态抢占，最终都会调用 schedule 函数来执行真正的调度：

还记得调度的本质吗？调度的本质就是选择下一个进程，然后切换。如上图所示，用函数 pick_next_task 选择下一个进程，其本质就是调度算法的实现；用函数 context_switch 完成进程的切换，即进程上下文的切换。下面我们分别看下这两个核心功能。

字段

版本

O(n) 调度器

linux0.11 - 2.4

O(1) 调度器

linux2.6

CFS调度器

linux2.6至今

O(n) 调度器是在内核2.4以及更早期版本采用的算法，O(n) 代表的是寻找一个合适的任务的时间复杂度。调度器定义了一个 runqueue 的运行队列，将进程的状态变为 Running 的都会添加到此运行队列中，但是不管是实时进程，还是普通进程都会添加到这个运行队列中。当需要从运行队列中选择一个合适的任务时，就需要从队列的头遍历到尾部，这个时间复杂度是O(n)，运行队列中的任务数目越大，调度器的效率就越低。

所以 O(n) 调度器有如下缺陷：

内核2.6采用了O(1) 调度器，让每个 CPU 维护一个自己的 runqueue，从而减少了锁的竞争。每一个runqueue 运行队列维护两个链表，一个是 active 链表，表示运行的进程都挂载 active 链表中；一个是 expired 链表，表示所有时间片用完的进程都挂载 expired 链表中。当 acitve 中无进程可运行时，说明系统中所有进程的时间片都已经耗光，这时候则只需要调整 active 和 expired 的指针即可。每个优先级数组包含140个优先级队列，也就是每个优先级对应一个队列，其中前100个对应实时进程，后40个对应普通进程。如下图所示：

总的来说 O(1) 调度器的出现是为了解决 O(n) 调度器不能解决的问题，但 O(1) 调度器有个问题，一个高优先级多线程的应用会比低优先级单线程的应用获得更多的资源，这就会导致一个调度周期内，低优先级的应用可能一直无法响应，直到高优先级应用结束。CFS调度器就是站在一视同仁的角度解决了这个问题，保证在一个调度周期内每个任务都有执行的机会，执行时间的长短，取决于任务的权重。下面详细看下CFS调度器是如何动态调整任务的运行时间，达到公平调度的。

CFS是 Completely Fair Scheduler 简称，即完全公平调度器。CFS 调度器和以往的调度器不同之处在于没有固定时间片的概念，而是公平分配 CPU 使用的时间。比如：2个优先级相同的任务在一个 CPU 上运行，那么每个任务都将会分配一半的 CPU 运行时间，这就是要实现的公平。

但现实中，必然是有的任务优先级高，有的任务优先级低。CFS 调度器引入权重 weight 的概念，用 weight 代表任务的优先级，各个任务按照 weight 的比例分配 CPU 的时间。比如：2个任务A和B，A的权重是1024，B的权重是2048，则A占 1024/(1024+2048) = 33.3% 的 CPU 时间，B占 2048/(1024+2048)=66.7% 的 CPU 时间。

在引入权重之后，分配给进程的时间计算公式如下：

实际运行时间 = 调度周期 * 进程权重 / 所有进程权重之和

CFS 调度器用nice值表示优先级，取值范围是[-20, 19]，nice和权重是一一对应的关系。数值越小代表优先级越大，同时也意味着权重值越大，nice值和权重之间的转换关系：

数组值计算公式是：weight = 1024 / 1.25nice。

如果一个 CPU 上有 N 个优先级相同的进程，那么每个进程会得到 1/N 的执行机会，每个进程执行一段时间后，就被调出，换下一个进程执行。如果这个 N 的数量太大，导致每个进程执行的时间很短，就要调度出去，那么系统的资源就消耗在进程上下文切换上去了。

所以对于此问题在 CFS 中则引入了调度周期，使进程至少保证执行0.75ms。调度周期的计算通过如下代码：

当进程数目小于8时，则调度周期等于6ms。当进程数目大于8时，则调度周期等于进程的数目乘以0.75ms。

根据上面进程实际运行时间的公式，可以看出，权重不同的2个进程的实际执行时间是不相等的，但是 CFS 想保证每个进程运行时间相等，因此 CFS 引入了虚拟时间的概念。虚拟时间(vriture_runtime)和实际时间(wall_time)转换公式如下：

vriture_runtime = (wall_time * NICE0_TO_weight) / weight

其中，NICE0_TO_weight 代表的是 nice 值等于0对应的权重，即1024，weight 是该任务对应的权重。

权重越大的进程获得的虚拟运行时间越小，那么它将被调度器所调度的机会就越大，所以，CFS 每次调度原则是：总是选择 vriture_runtime 最小的任务来调度。

为了能够快速找到虚拟运行时间最小的进程，Linux 内核使用红黑树来保存可运行的进程。CFS跟踪调度实体sched_entity的虚拟运行时间vruntime，将sched_entity通过enqueue_entity()和dequeue_entity()来进行红黑树的出队入队，vruntime少的调度实体sched_entity排列到红黑树的左边。

如上图所示，红黑树的左节点比父节点小，而右节点比父节点大。所以查找最小节点时，只需要获取红黑树的最左节点即可。

相关步骤如下：

pick_next_task_fair 会判断上一个 task 的调度器是否是 CFS，这里我们默认都是 CFS 调度：

update_curr 函数用来更新当前进程的运行时间信息:

pick_next_entity 函数会从就绪队列中选择最适合运行的调度实体（虚拟时间最小的调度实体），即从 CFS 红黑树最左边节点获取一个调度实体。

put_prev_entity 会调用 __enqueue_entity 将prev进程(即current进程)加入到 CFS 队列 rq 上的红黑树，然后将 cfs_rq->curr 设置为空。

set_next_entity 会调用 __dequeue_entity 将下一个选择的进程从 CFS 队列的红黑树中删除，然后将 CFS 队列的 curr 指向进程的调度实体。

理解了下一个进程的选择后，就需要做当前进程和所选进程的上下文切换。

Linux 内核用函数 context_switch 进行进程的上下文切换，进程上下文切换主要涉及到两部分：进程地址空间切换和处理器状态切换：

将下一个进程的 pgd 虚拟地址转化为物理地址存放在 ttbr0_el1 中(这是用户空间的页表基址寄存器)，当访问用户空间地址的时候 mmu 会通过这个寄存器来做遍历页表获得物理地址。完成了这一步，也就完成了进程的地址空间切换，确切的说是进程的虚拟地址空间切换。

其中 x19-x28 是 arm64 架构规定需要调用保存的寄存器，可以看到处理器状态切换的时候将前一个进程（prev）的 x19-x28，fp,sp,pc 保存到了进程描述符的 cpu_contex 中，然后将即将执行的进程 (next) 描述符的 cpu_contex 的 x19-x28，fp,sp,pc 恢复到相应寄存器中，而且将 next 进程的进程描述符 task_struct 地址存放在 sp_el0 中，用于通过 current 找到当前进程，这样就完成了处理器的状态切换。