Linux进程调度CFS

1. 进程

1.1 什么是进程？

操作系统作为硬件的使用层，提供使用硬件资源的能力，而进程作为操作系统使用层，提供使用操作系统抽象出的资源层的能力。
进程是指计算机中已运行的程序。进程本身不是基本的运行单位，而是线程的容器。程序本身只是指令、数据及其组织形式的描述，进程才是程序（那些指令和数据）的真正运行实例。
Linux内核把进程叫做任务（task），进程的虚拟地址空间可分为用户虚拟地址空间和内核虚拟地址空间，所有进程共享内核虚拟地址空间，每个进程有独立的用户虚拟地址空间。

1.2 进程的生命周期

Linux操作系统属于多任务操作系统，系统中的每个进程能够分时复用CPU时间片，通过有效的进程调度策略实现多任务并行执行。
进程能被CPU调度，等待CPU资源分配以及等待外部事件时会属于不同的状态
- 创建状态：创建新进程；
- 就绪状态：进程获取可以运作所有资源及准备相关条件；
- 执行状态：进程正在CPU中执行操作；
- 阻塞状态：进程因等待某些资源而被跳出CPU；
- 终止状态：进程消亡。

1.3 进程的两种特殊形式

没有用户虚拟地址空间的进程叫内核线程，共享用户虚拟地址空间的进程叫用户线程；
共享同一个用户虚拟地址空间的所有用户线程叫线程组。

2. task_struct结构体分析

2.1 Linux内核提供API函数来设置进程状态

TASK_RUNING（可运行状态或者可就绪状态）；
TASK_INTERRUPTIBLE（可中断睡眠状态，又叫浅睡眠状态）；
TASK_UNINTERUPTIBLE（不可中断状态，又叫深度睡眠状态）；
TASK_STOPPED（终止状态）；
EXIT_ZOMBIE（僵尸状态）。

2.2 什么是task_struct？

进程是操作系统调度的一个实体，需要对进程资源做一个抽象化，此抽象化为进程控制块（PCB，Process Control BLock），在Linux内核里面采用task_struct结构体来描述进程控制块。Linux内核涉及进程和程序的所有算法都围绕名为task_struct的数据结构而建立操作。

2.3 进程优先级

int             prio;
int             static_prio;
int             normal_prio;
unsigned int    rt_priority;

prio调度优先级：数值越小，优先级越高。
- 大多数情况下，prio等于normal_prio
- 特殊情况，如果进程X占有实时互斥锁，进程Y正在等待锁，进程Y的优先级比进程X优先级高，那么把X的优先级临时提高到进程Y的优先级，即进程X的prio的值等于进程y的prio值。
static_prio静态优先级：针对于普通进程有意义，值为120+nice，数值越小，表示优先级越高。
normal_prio正常优先级：
- 对于限期进程为-1；
- 对于实时进程为99 - rt_priority
- 对于普通进程为static_prio
rt_priority实时优先级：针对实时进程，范围为1-99，数值越大优先级越高。

3. 调度类及进程调度CFS

3.1 调度

调度：就是按照某种调度的算法设计，从进程的就绪队列当中选取进程分配CPU，主要是协调对CPU等等相关的资源使用。
进程调度目的：最大限度利用CPU时间。
如果调度器支持就绪状态切换到执行状态，同时支持执行状态切换到就绪状态，称该调度器为抢占式调度器。

3.2 调度类 sched_class

在这里插入图片描述

调度器类可分为5种：
- extern const struct sched_class stop_sched_class; // 停机调度类
- extern const struct sched_class dl_sched_class; // 限期调度类
- extern const struct sched_class rt_sched_class; // 实时调度类
- extern const struct sched_class fair_sched_class; // 公平调度类
- extern const struct sched_class idle_sched_class; // 空闲调度类
这5种调度类的优先级从高到低依次为：停机调度类–>限期调度类–>实时调度类–>公平调度类–>空闲调度类
其中，停机调度类和空闲调度类是内核级调度，用户无法选择使用这两个调度器

3.3 CFS 完全公平调度器

用于Linux系统中普通进程的调度

3.3.1 几个结构体

struct rq：每个CPU都有一个对应的运行队列（run queue）；
struct cfs_rq：CFS运行队列，该结构中包含了 struct rb_root_cached（红黑树），用于链接调度实体struct sched_entity。rq运行队列中对应了一个CFS运行队列，此外，在task_group结构中也会为每个CPU再维护一个CFS运行队列；
struct task_struct：任务的描述符，包含了进程的所有信息，该结构中的struct sched_entity，用于参与CFS的调度；
struct task_group：组调度，Linux支持将任务分组来对CPU资源进行分配管理，该结构中为系统中的每个CPU都分配了struct sched_entity调度实体和struct cfs_rq运行队列，其中struct sched_entity用于参与CFS的调度；
struct sched_entity：调度实体，这个也是CFS调度管理的对象。
CFS调度类需要实现的所有接口定义在 struct sched_class 里：
- enqueue_task：向就绪队列中添加一个任务，当某个任务进入可运行状态时，调用这个函数。
  - 典型的场景就是内核里的唤醒函数，将被唤醒的任务插入rq然后设置任务运行态为 TASK_RUNNING。
  - 对 CFS 调度器来说，则是将任务插入红黑树，给 nr_running 增加计数。
- dequeue_task：将一个任务从就绪队列中删除。
  - 典型的场景就是任务调度引起阻塞的内核函数，把任务运行态设置成 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE，然后调用 schedule 函数，最终触发dequeue_task的操作。
  - 对 CFS 调度器来说，则是将不在处于运行态的任务从红黑树中移除，给 nr_running 减少计数。
- yield_task：处于运行态的任务主动让出 CPU。
  - 典型的场景就是处于运行态的应用调用sched_yield系统调用，直接让出 CPU。此时系统要调用 sched_yield 会先调用 yield_task 申请让出 CPU，然后调用 schedule 去做上下文切换。
  - 对 CFS 调度器来说，如果 nr_running 是 1，则直接返回，最终 schedule 函数也不产生上下文切换。否则，任务被标记为skip 状态。调度器在红黑树上选择待运行任务时肯定会跳过该任务。之后，因为 schedule 函数被调用，pick_next_task 最终会被调用。其代码会从红黑树中最左侧选择一个任务，然后把要放弃运行的任务放回红黑树，然后调用上下文切换函数做任务上下文切换。
- yield_to_task：让处于运行态的任务主动放弃CPU，并执行指定的任务。
- check_preempt_curr：用于在待运行任务插入rq后，检查是否应该抢占正在CPU上运行的当前任务。
  - 对 CFS 调度器而言，主要是在是否能满足调度时延和是否能保证足够任务运行时间之间来取舍
- pick_next_task：选择下一个最适合调度运行的任务，将其从rq移除。并且如果前一个任务还保持在运行态，即没有从rq移除，则将当前的任务重新放回到rq。
  - 内核 schedule 函数利用它来完成调度时任务的选择。
  - 对CFS调度器而言，大多数情况下，下一个调度任务是从红黑树的最左侧节点选择并移除。如果前一个任务是其它调度类，则调用该调度类的 put_prev_task 方法将前一个任务做正确的安置处理。但如果前一个任务如果也属于CFS调度类的话，为了效率，跳过调度类标准方法 put_prev_task，但核心逻辑仍旧是 put_prev_task_fair 的主要部分。
- put_prev_task：将前一个正在CPU上运行的任务从CPU上拿下的处理。如果任务还在运行态则将任务放回rq，否则，根据调度类要求做简单处理。
  - 此函数通常是 pick_next_task 的密切关联操作，是 schedule 实现的关键部分。如果前一个任务属于CFS调度类，则使用CFS调度类的具体实现 put_prev_task_fair。此时，如果任务还是 TASK_RUNNING 状态，则被重新插入到红黑树的最右侧。如果这个任务不是 TASK_RUNNING 状态，则已经从红黑树移除过了，只需要修改CFS 当前任务指针 cfs_rq->curr 即可。
- select_task_rq：为给定的任务选择一个最优的CPU就绪队列rq，返回rq所属的CPU号。
- set_curr_task：当任务改变自己的调度类或者任务组时，该函数被调用。
  - 用户进程可以使用 sched_setscheduler系统调用，通过设置自己新的调度策略来修改自己的调度类。
  - 对CFS调度器而言，当任务把自己调度类从其它类型修改成CFS调度类，此时需要把该任务设置成正当前CPU正在运行的任务。例如把任务从红黑树上移除，设置 CFS 当前任务指针 cfs_rq->curr 和调度统计数据等。
- task_tick：每次周期性时钟到的时候，这个函数被调用，可能触发调度。
- task_dead：进程结束时调用。
- switched_from：用于切换调度类。
- switched_to：切换到下一个进程来运行。
- prio_changed：改变进程优先级。

3.3.2 CFS调度机制

它给cfs_rq（cfs的run queue）中的每一个进程设置一个虚拟时钟，vruntime。如果一个进程得以执行，随着时间的增长（一个个tick的到来），其vruntime将不断增大。没有得到执行的进程vruntime不变。调度器总是选择vruntime跑得最慢的那个进程来执行。这就是所谓的“完全公平”。为了区别不同优先级的进程，优先级高的进程vruntime增长得慢，以至于它可能得到更多的运行机会。
CFS不区分具体的cpu算力消耗型进程，还是io消耗型进程，统一采用红黑树算法来管理所有的调度实体sched_entity，算法效率为O(log n)。CFS跟踪调度实体sched_entity的虚拟运行时间vruntime，平等对待运行队列中的调度实体sched_entity，将执行时间少的调度实体sched_entity排列到红黑树的最左边。调度实体sched_entity通过enqueue_entity()和dequeue_entity()来进行红黑树的出队入队。

在这里插入图片描述

调度周期：为了保证每个任务都在合理的期限内运行, 把时间分成一块块调度周期。而在每个调度周期中, 让每个任务分到同样多的 vruntime。这样的话，至多经过一个调度周期，所有任务又能运行了，而且任务切换不会过于频繁。
调度延迟：从进程加入到运行队列，到被放到cpu上执行经历的时间，和调度周期有关，当运行个数小于等于8时，调度延迟等于调度周期。
在每个sched_latency内，根据各task的权重值，可以计算出运行时间 runtime = 调度周期 * 进程权重 / 所有进程权重之和。
虚拟时间vruntime的计算：vruntime = runtime * nice_0_weight / seight。
根据虚拟运行时间vruntime将各个调度实体用红黑树管理，最左边的节点对应着最小的vruntime。
在调度的时候选择最小vruntime对应的进程进行调度。

3.3.3 流程分析

runtime与vruntime的计算

CFS调度器没有时间的概念，而是根据虚拟运行时间对任务进行排序，选择虚拟运行时间最小的进程进行调度。
计算vruntime是调用sched_vslice实现的，计算的时候依赖调度周期。

CFS调度tick

主要的工作包括：
- 更新运行时的各类统计信息，比如vruntime，运行时间、负载值、权重值等；
- 检查是否需要抢占，主要是比较运行时间是否耗尽，以及vruntime的差值是否大于运行时间等；

任务出队入队

当任务进入可运行状态时，需要将调度实体放入到红黑树中，完成入队操作。
当任务退出可运行状态时，需要将调度实体从红黑树中移除，完成出队操作。
CFS调度器使用enqueue_task_fair函数将任务入队到CFS队列，使用dequeue_task_fair函数将任务从CFS队列中出队操作。
出队与入队的操作中，核心的逻辑可以分成两部分：
- 1）更新运行时的数据，比如负载、权重、组调度的占比等等；
- 2）将sched_entity插入红黑树，或者从红黑树移除；