调度器

调度：就是按照某种调度的算法设计，从进程的就绪队列中选择进程分配CPU，主要是协调进程对CPU等相关资源的使用。

调度的目的：最大限度的使用CPU时间。

Linux内核中用来安排调度进程执行的模块称为调度器（Scheduler），它可以切换进程状态（执行、睡眠、退出等）。调度器相当于CPU的管理员，主要完成两件事：

1.选择某些就绪进程来执行

2.打断某些执行的进程让他们变为就绪态

操作系统还负责“上下文切换”，即保存切换前的寄存器内容等进程的状态，以便稍后恢复。

如果调度器支持就绪状态切换到执行状态，同时支持执行状态切换为就绪状态，就称该调度器为抢占式调度器。

kernel/sched/sched.h/：， struct sched_class ：调度类的结构体。

struct sched_class {
        const struct sched_class *next; // OS中有多个调度类,按照调度优先级排成一个链表
}

/* 将进程加入到执行队列中,即将调度实体存放到红黑树中，并将nr_running变量+1 */
 void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags); // struct rq 进程的调度实体
   
  /* 从执行队列删除进程,并将nr_running变量-1*/
 void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
   
  /* 放弃CPU的执行权限，实际上此函数执行先出队后入队，这种情况下它直接将调度实体存放在红黑树的最右端 */
 void (*yield_task) (struct rq *rq);
 bool (*yield_to_task)(struct rq *rq, struct task_struct *p, bool preempt);
   
  /* 专门用于检查当前进程是否可被新进程抢占 */
 void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
   
  /* 选择下一个要运行的进程 */
 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);

调度器可分为五种，对应不同的调度策略：

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; // 公平调度类/cfs
extern const struct sched_class idle_sched_class; // 空闲调度类

这五种调度类优先级从高到低依次为：停机调度类，限期调度类，实时调度类，公平调度类，空闲调度类

停机调度类stop_sched_class：

优先级最高的调度类，停机进程是优先级最高的进程，可以抢占所有其他进程，其他进程不可能抢占停机进程，停机的意思是使处理器停下来，做更紧急的事情。

限期调度类/dl_sched_class / SCHED_DEADLINE：

最早使用优先算法。使用红黑树把进程按照绝对截止限期从小到达排序，每次调度时选择绝对截止期限最小的进程。如果限期进程用完了它的运行时间，它将让出处理器，并且把它从运行队列中删除。在下一个周期开始，重新把它添加到运行队列中。

实时调度类 / rt_sched_class / SCHED_FIFO：

为每个调度优先级维护一个队列。SCHED_FIFO实现了一种简单的、先进先出的调度算法。它不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。一旦一个SCHED_FIFO级进程处于可运行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止。 它不基于时间片，可以一直执行下去。只有更高优先级的SCHED_FIFO或者SCHED_RR任务才能抢占SCHED_FIFO任务。如果有两个或者更多的同优先级的SCHED_FIFO级进程，它们会轮流执行，但是依然只有在它们愿意让出处理器时才会退出。只有有SCHED_FIFO级进程在执行，其他级别较低的进程就只能等待它变为不可运行后才有机会执行。

实时调度类 / rt_sched_class / SCHED_RR：

SCHED_RR与SCHED_FIFO大体相同，只是SCHED_RR级的进程在耗尽事先分配给它的时间后就不能再继续执行了。也就是说，SCHED_RR是带有时间片的SCHED_FIFO——这是一种实时轮流调度算法。

公平调度类fair_sched_class：

使用完全公平调度算法。完全公平调度算法引入虚拟运行时间的相关概念：虚拟运行时间 = 实际运行时间 * nice0对应的权重 / 进程的权重

空闲调度类 / idle_sched_class：

每个CPU上都有一个空闲线程，即0号线程，空闲调度类优先级别最低，当没有其他进程可以调度的时候，才会调度空闲线程。

优先级

task_struct结构体中采用三个成员表示进程的优先级：prio和normal_prio（动态优先级）、static_prio（静态优先级）

linux内核优先级如下：/include/linux/sched/prio,h

#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO     MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2)

调度策略

Linux内核提供一些调度策略供用户应用程序来选择调度器。

#define SCHED_NORMAL 0
#define SCHED_FIFO 1
#define SCHED_RR 2
#define SCHED_BATCH 3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE 5
#define SCHED_DEADLINE 6

SCHED_NORMAL：普通进程的调度策略，使task选择CFS调度器来调度运行

SCHED_FIFO：实时进程的调度策略，先进先出调度，没有时间片，没有更高优先级的状态下，只有等待主动让出CPU（非抢占）

SCHED_RR：实时进程的调度策略，采用时间片轮转，进程使用完时间片之后会进入优先级对应运行队列的尾部，把CPU让给同等优先级的其他进程

SCHED_BATCH：普通进程的调度策略，批量处理，使task选择CFS调度器来调度运行

SCHED_IDLE：普通进程的调度策略，使我们task以最低优先级选择CFS调度器来调度运行

SCHED_DEADLINE：限期进程调度策略，使我们task选择Deadline调度器来调度运行

注：stop调度器和DLE-task调度器，仅使用于内核，用户没有办法进行选择

CFS调度器

完全公平调度算法体现在对待每个进程都是公平的，让每个进程都运行一段相同的时间片，这就是基于时间片轮询调度算法。CFS定义一种新调度模型，它给cfs_rq（cfs的run queue）中的每一个进程都设置一个虚拟时钟 - virtual runtime（vruntime），如果一个进程得以执行，随着执行时间的不断增长，其vruntime也不断增大，没有得到执行的进程vruntime将保持不变。

        const struct sched_class *sched_class; // 表示该进程所属的调度器类

CFS：完全公平调度器。实际当中，必然会有进程优先级高或进程优先级低，此时CFS调度器会引入权重，使用该权重代表进程的优先级。各个进程会按照权重的比例来分配CPU时间。假设有X和Y两个进程，X权重为1024，Y权重为2048，那么X所获得CPU时间的比例为 ：%33 = （1024 / （1024 + 2048））* 100%

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

虚拟运行时间 = 实际运行时间 * NICE_0_LOAD / 进程权重

在一个调度周期里面，所有进程的虚拟运行时间都是不变的，所以在进程调度时，只需要找到虚拟运行时间最小的进程调度运行即可。

Linux采用红黑树保存调度实体，按照虚拟时间从小到大存储在红黑树中。

调度器通过各个组件模块及一系列数据结构，来排序和管理系统中的进程。它们之间关系如下：

主调度器：通过调用schedule()函数来完成进程的选择和切换。

周期性调度器：根据频率自动调用scheduler_tick函数，根据进程运行时间触发调度

上下文切换：主要做两个事情（切换地址空间、切换寄存器和栈空间）

CFS调度器的Linux部分内核源码：

const struct sched_class fair_sched_class = {
    .next           = &idle_sched_class,    
    .enqueue_task       = enqueue_task_fair,    
    .dequeue_task       = dequeue_task_fair,

.next：CPU运行队列中的下一个调度类，优先级更低，为空闲调度类

enqueue_task_fair：当task进入可运行状态时，用此函数将调度实体存放到红黑树，完成入队。

dequeue_task_fair：当任务退出可运行状态时，用此函数将调度实体从红黑树中移除，完成出队。

CFS调度器就绪队列

CFS顶级调度就绪队列 struct cfs_rq:

struct cfs_rq {
        struct load_weight        load;
        unsigned long              runnable_weight;
        unsigned int                 nr_running;
        unsigned int                 h_nr_running;
        unsigned int                 idle_h_nr_running;

        u64            exec_clock;
        u64            min_vruntime;
#ifndef CONFIG_64BIT
        u64            min_vruntime_copy;
#endif;

        struct rb_root_cached        tasks_timeline;

cfs_rq ： 跟踪就绪队列信息以及管理就绪态调度实体，并且维护一棵按照虚拟时间排序的红黑树

tasks_timeline->rb_root（红黑树的根）

tasks_timeline->rb_leftmost（指向虚拟时间最小的结点）