带你玩转Linux内核调度器源码分析！
引言
调度器作为操作系统的核心部件，具有非常重要的意义，其随着linux内核的更新也不断进行着更新。本系列文章通过linux-3.18.3源码进行调度器的学习和分析，一步一步将linux现有的调度器原原本本的展现出来。此篇文章作为开篇，主要介绍调度器的原理及重要数据结构。
调度器介绍
随着时代的发展，linux也从其初始版本稳步发展到今天，从2.4的非抢占内核发展到今天的可抢占内核，调度器无论从代码结构还是设计思想上也都发生了翻天覆地的变化，其普通进程的调度算法也从O(1)到现在的CFS，一个好的调度算法应当考虑以下几个方面：
公平：保证每个进程得到合理的CPU时间。
高效：使CPU保持忙碌状态，即总是有进程在CPU上运行。
响应时间：使交互用户的响应时间尽可能短。
周转时间：使批处理用户等待输出的时间尽可能短。
吞吐量：使单位时间内处理的进程数量尽可能多。
负载均衡：在多核多处理器系统中提供更高的性能
而整个调度系统至少包含两种调度算法，是分别针对实时进程和普通进程，所以在整个linux内核中，实时进程和普通进程是并存的，但它们使用的调度算法并不相同，普通进程使用的是CFS调度算法(红黑树调度)。之后会介绍调度器是怎么调度这两种进程。
进程
在linux中，进程主要分为两种，一种为实时进程，一种为普通进程
实时进程：对系统的响应时间要求很高，它们需要短的响应时间，并且这个时间的变化非常小，典型的实时进程有音乐播放器，视频播放器等。
普通进程：包括交互进程和非交互进程，交互进程如文本编辑器，它会不断的休眠，又不断地通过鼠标键盘进行唤醒，而非交互进程就如后台维护进程，他们对IO，响应时间没有很高的要求，比如编译器。
它们在linux内核运行时是共存的，实时进程的优先级为0~99，实时进程优先级不会在运行期间改变(静态优先级)，而普通进程的优先级为100~139，普通进程的优先级会在内核运行期间进行相应的改变(动态优先级)。
调度策略
在linux系统中，调度策略分为
SCHED_NORMAL：普通进程使用的调度策略，现在此调度策略使用的是CFS调度器。
SCHED_FIFO：实时进程使用的调度策略，此调度策略的进程一旦使用CPU则一直运行，直到有比其更高优先级的实时进程进入队列，或者其自动放弃CPU，适用于时间性要求比较高，但每次运行时间比较短的进程。
SCHED_RR：实时进程使用的时间片轮转法策略，实时进程的时间片用完后，调度器将其放到队列末尾，这样每个实时进程都可以执行一段时间。适用于每次运行时间比较长的实时进程。
【文章福利】小编推荐自己的Linux内核技术交流群:【891587639】整理了一些个人觉得比较好的学习书籍、视频资料共享在群文件里面，有需要的可以自行添加哦！！！（含视频教程、电子书、实战项目及代码)
首先，我们需要清楚，什么样的进程会进入调度器进行选择，就是处于TASK_RUNNING状态的进程，而其他状态下的进程都不会进入调度器进行调度。系统发生调度的时机如下
调用cond_resched()时
显式调用schedule()时
从系统调用或者异常中断返回用户空间时
从中断上下文返回用户空间时
当开启内核抢占(默认开启)时，会多出几个调度时机，如下
在系统调用或者异常中断上下文中调用preempt_enable()时(多次调用preempt_enable()时，系统只会在最后一次调用时会调度)
在中断上下文中，从中断处理函数返回到可抢占的上下文时(这里是中断下半部，中断上半部实际上会关中断，而新的中断只会被登记，由于上半部处理很快，上半部处理完成后才会执行新的中断信号，这样就形成了中断可重入, 但是即使是中断下半部, 也是不能够被调度的)
而在系统启动调度器初始化时会初始化一个调度定时器，调度定时器每隔一定时间执行一个中断，在中断会对当前运行进程运行时间进行更新，如果进程需要被调度，在调度定时器中断中会设置一个调度标志位，之后从定时器中断返回，因为上面已经提到从中断上下文返回时是可能有调度时机的，如果定时器中断返回时正好是返回到用户态空间, 而且调度标志位又置位了, 这时候就会做进程切换. 在内核源码的汇编代码中所有中断返回处理都必须去判断调度标志位是否设置，如设置则执行schedule()进行调度。而我们知道实时进程和普通进程是共存的，调度器是怎么协调它们之间的调度的呢，其实很简单，每次调度时，会先在实时进程运行队列中查看是否有可运行的实时进程，如果没有，再去普通进程运行队列找下一个可运行的普通进程，如果也没有，则调度器会使用idle进程进行运行。之后的章节会放上代码进行详细说明。
系统并不是每时每刻都允许调度的发生，当处于中断期间的时候(无论是上半部还是下半部)，调度是被系统禁止的，之后中断过后才重新允许调度。而对于异常，系统并不会禁止调度，也就是在异常上下文中，系统是有可能发生调度的。
数据结构
在这一节中，我们都是以普通进程作为讲解对象，因为普通进程使用的调度算法为CFS调度算法，它是以红黑树为基础的调度算法，其相比与实时进程的调度算法复杂很多，而实时进程在组织结构上与普通进程没有太大差别，算法也较为简单。
组成形式图1：
从图1 中可以看出来，每个CPU对应包含一个运行队列结构(struct rq)，而每个运行队列又包含有其自己的实时进程运行队列(struct rt_rq)、普通进程运行队列(struct cfs_rq)、和一个我自己也不太知道有什么用的dl队列(struct dl_rq)，也就是说每个CPU都有他们自己的实时进程运行队列及普通进程运行队列，为了方便，我们在图中只描述普通进程的组织结构(最复杂的也是普通进程的组织结构)，红色se则为当前CPU上正在执行的程序，蓝色为下个将要执行的程序，其实图中并不规范，实际上当进程运行时，会从红黑树中剥离出来，然后设定下一个调度进程，当进程运行时间结束时，再重新放入红黑树中。而为什么CPU0上有两个蓝色将被调度进程，将在组调度中解释。而为什么红黑树中又有一个子红黑树，我们将在调度实体中解释。
组调度(struct task_group)
我们知道，linux是一个多用户系统，如果有两个进程分别属于两个用户，而进程的优先级不同，会导致两个用户所占用的CPU时间不同，这样显然是不公平的(如果优先级差距很大，低优先级进程所属用户使用CPU的时间就很小)，所以内核引入组调度。如果基于用户分组，即使进程优先级不同，这两个用户使用的CPU时间都为50%。这就是为什么图1 中CPU0有两个蓝色将被调度的程序，如果task_group1中的运行时间还没有使用完，而当前进程运行时间使用完后，会调度task_group1中的下一个被调度进程；相反，如果task_group1的运行时间使用结束，则调用上一层的下一个被调度进程。需要注意的是，一个组调度中可能会有一部分是实时进程，一部分是普通进程，这也导致这种组要能够满足即能在实时调度中进行调度，又可以在CFS调度中进行调度。 linux可以以以下两种方式进行进程的分组：
用户ID：按照进程的USER ID进行分组，在对应的/sys/kernel/uid/目录下会生成一个cpu.share的文件，可以通过配置该文件来配置用户所占CPU时间比例。
cgourp(control group)：生成组用于限制其所有进程，比如我生成一个组(生成后此组为空，里面没有进程)，设置其CPU使用率为10%，并把一个进程丢进这个组中，那么这个进程最多只能使用CPU的10%，如果我们将多个进程丢进这个组，这个组的所有进程平分这个10%。
注意的是，这里的进程组概念和fork调用所产生的父子进程组概念不一样，文章所使用的进程组概念全为组调度中进程组的概念。为了管理组调度，内核引进了struct task_group结构，如下：
在struct task_group结构中，最重要的成员为 struct sched_entity ** se 和 struct cfs_rq ** cfs_rq。在图1 中，root_task_group与task_group1都只有一个，它们在初始化时会根据CPU个数为se和cfs_rq分配空间，即在task_group1和root_task_group中会为每个CPU分配一个se和cfs_rq，同理用于实时进程的 struct sched_rt_entity ** rt_se 和 struct rt_rq ** rt_rq也是一样。为什么这样呢，原因就是在多核多CPU的情况下，同一进程组的进程有可能在不同CPU上同时运行，所以每个进程组都必须对每个CPU分配它的调度实体(struct sched_entity 和 struct sched_rt_entity)和运行队列(struct cfs_rq 和 struct rt_rq)。
调度实体(struct sched_entity)
在组调度中，也涉及到调度实体这个概念，它的结构为struct sched_entity(简称se)，就是图1 红黑树中的se。其实际上就代表了一个调度对象，可以为一个进程，也可以为一个进程组。对于根的红黑树而言，一个进程组就相当于一个调度实体，一个进程也相当于一个调度实体。我们可以先看看其结构，如下：
实际上，红黑树是根据 struct rb_node 建立起关系的，不过 struct rb_node 与 struct sched_entity 是一一对应关系，也可以简单看为一个红黑树结点就是一个调度实体。可以看出，在 struct sched_entity 结构中，包含了一个进程(或进程组)调度的全部数据，其被包含在 struct task_struct 结构中的se中，如下：
在 struct sched_entity 结构中，值得我们注意的成员是：
load：权重，通过优先级转换而成，是vruntime计算的关键。
on_rq：表明是否处于CFS红黑树运行队列中，需要明确一个观点就是，CFS运行队列里面包含有一个红黑树，但这个红黑树并不是CFS运行队列的全部，因为红黑树仅仅是用于选择出下一个调度程序的算法。很简单的一个例子，普通程序运行时，其并不在红黑树中，但是还是处于CFS运行队列中，其on_rq为真。只有准备退出、即将睡眠等待和转为实时进程的进程其CFS运行队列的on_rq为假。
vruntime：虚拟运行时间，调度的关键，其计算公式：一次调度间隔的虚拟运行时间 = 实际运行时间 * (NICE_0_LOAD / 权重)。可以看出跟实际运行时间和权重有关，红黑树就是以此作为排序的标准，优先级越高的进程在运行时其vruntime增长的越慢，其可运行时间相对就长，而且也越有可能处于红黑树的最左结点，调度器每次都选择最左边的结点为下一个调度进程。注意其值为单调递增，在每个调度器的时钟中断时当前进程的虚拟运行时间都会累加。单纯的说就是进程们都在比谁的vruntime最小，最小的将被调度。
cfs_rq：此调度实体所处于的CFS运行队列。
my_q：如果此调度实体代表的是一个进程组，那么此调度实体就包含有一个自己的CFS运行队列，其CFS运行队列中存放的是此进程组中的进程，这些进程就不会在其他CFS运行队列的红黑树中被包含(包括顶层红黑树也不会包含他们，他们只属于这个进程组的红黑树)。
对于怎么理解一个进程组有它自己的CFS运行队列，其实很好理解，比如在根CFS运行队列的红黑树上有一个进程A一个进程组B，各占50%的CPU，对于根的红黑树而言，他们就是两个调度实体。调度器调度的不是进程A就是进程组B，而如果调度到进程组B，进程组B自己选择一个程序交给CPU运行就可以了，而进程组B怎么选择一个程序给CPU，就是通过自己的CFS运行队列的红黑树选择，如果进程组B还有个子进程组C，原理都一样，就是一个层次结构。 而在 struct task_struct 结构中，我们注意到有个调度类，里面包含的是调度处理函数，它具体如下：
这个调度类具体有什么用呢，实际上在内核中不同的调度算法它们的操作都不相同，为了方便修改、替换调度算法，使用了调度类，每个调度算法只需要实现自己的调度类就可以了，CFS算法有它的调度类，SCHED_FIFO也有它自己的调度类，当一个进程创建时，用什么调度算法就将其 task_struct->sched_class 指向其相应的调度类，调度器每次调度处理时，就通过当前进程的调度类函数进程操作，大大提高了可移植性和易修改性。
CFS运行队列(struct cfs_rq)
我们现在知道，在系统中至少有一个CFS运行队列，其就是根CFS运行队列，而其他的进程组和进程都包含在此运行队列中，不同的是进程组又有它自己的CFS运行队列，其运行队列中包含的是此进程组中的所有进程。当调度器从根CFS运行队列中选择了一个进程组进行调度时，进程组会从自己的CFS运行队列中选择一个调度实体进行调度(这个调度实体可能为进程，也可能又是一个子进程组)，就这样一直深入，直到最后选出一个进程进行运行为止。
对于 struct cfs_rq 结构没有什么好说明的，只要确定其代表着一个CFS运行队列，并且包含有一个红黑树进行选择调度进程即可。
load：其保存的是进程组中所有进程的权值总和，需要注意子进程计算vruntime时需要用到进程组的load。CPU运行队列(struct rq)
每个CPU都有自己的 struct rq 结构，其用于描述在此CPU上所运行的所有进程，其包括一个实时进程队列和一个根CFS运行队列，在调度时，调度器首先会先去实时进程队列找是否有实时进程需要运行，如果没有才会去CFS运行队列找是否有进行需要运行，这就是为什么常说的实时进程优先级比普通进程高，不仅仅体现在prio优先级上，还体现在调度器的设计上，至于dl运行队列，我暂时还不知道有什么用处，其优先级比实时进程还高，但是创建进程时如果创建的是dl进程创建会错误(具体见sys_fork)。
