调度器
调度：就是按照某种调度的算法设计，从进程的就绪队列中选择进程分配CPU，主要是协调进程对CPU等相关资源的使用。
调度的目的：最大限度的使用CPU时间。
Linux内核中用来安排调度进程执行的模块称为调度器（Scheduler），它可以切换进程状态（执行、睡眠、退出等）。调度器相当于CPU的管理员，主要完成两件事：
1.选择某些就绪进程来执行
2.打断某些执行的进程让他们变为就绪态
操作系统还负责“上下文切换”，即保存切换前的寄存器内容等进程的状态，以便稍后恢复。
如果调度器支持就绪状态切换到执行状态，同时支持执行状态切换为就绪状态，就称该调度器为抢占式调度器。
kernel/sched/sched.h/：， struct sched_class ：调度类的结构体。
代码语言：javascript复制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);调度器可分为五种，对应不同的调度策略：
代码语言：javascript复制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
代码语言：javascript复制#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内核提供一些调度策略供用户应用程序来选择调度器。
代码语言：javascript复制#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 6SCHED_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将保持不变。
代码语言：javascript复制 const struct sched_class *sched_class; // 表示该进程所属的调度器类CFS：完全公平调度器。实际当中，必然会有进程优先级高或进程优先级低，此时CFS调度器会引入权重，使用该权重代表进程的优先级。各个进程会按照权重的比例来分配CPU时间。假设有X和Y两个进程，X权重为1024，Y权重为2048，那么X所获得CPU时间的比例为 ：3 = （1024 / （1024 2048））* 100%
实际运行时间 = 调度周期 * 进程权重 / 所有进程权重之和
虚拟运行时间 = 实际运行时间 * NICE_0_LOAD / 进程权重
在一个调度周期里面，所有进程的虚拟运行时间都是不变的，所以在进程调度时，只需要找到虚拟运行时间最小的进程调度运行即可。
Linux采用红黑树保存调度实体，按照虚拟时间从小到大存储在红黑树中。
调度器通过各个组件模块及一系列数据结构，来排序和管理系统中的进程。它们之间关系如下：
主调度器：通过调用schedule()函数来完成进程的选择和切换。
周期性调度器：根据频率自动调用scheduler_tick函数，根据进程运行时间触发调度
上下文切换：主要做两个事情（切换地址空间、切换寄存器和栈空间）
CFS调度器的Linux部分内核源码：
代码语言：javascript复制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:
代码语言：javascript复制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（指向虚拟时间最小的结点）
