Linux调度器

调度器介绍

一个好的调度算法应该考虑以下几个方面：

公平：保证每个进程得到合理的CPU时间
高效：使CPU保持忙碌状态，即总是有进程在CPU上执行
响应时间：使交互应用的响应时间尽可能短
周转时间：使批处理用户等待输出的时间尽可能短
吞吐量：使单位时间内处理的进程数量尽可能多
负载均衡：在多核多处理器系统中提供更高的性能

在整个调度系统中存在两种调度算法，分别是针对实时进程和普通进程，所以在整个Linux内核中，实时进程和普通进程是并存的，但他们使用的调度算法并不相同，普通进程使用的使CFS调度算法（红黑树调度）

进程

在Linux当中进程主要分两种，分别是实时进程和普通进程

实时进程：对系统的响应时间要求很高，他们需要很短的响应时间，并且这个时间的变化非常小典型的实时进程有音乐播放器，视频播放器等。
普通进程：包括交互进程和非交互进程，交互进程如文本编辑器，他会不断地休眠，又不断通过鼠标键盘进行唤醒，而非交互进程就如后台维护进程，他们对IO，响应时间没有很高的要求，比如编译器。

他们在Linux内核运行时是共存的，实时进程的优先级是0~~99，实时进程优先级不会在运行期间内改变（静态优先级），而普通进程的优先级为100~~139，普通进程的优先级会在内核运行期间进行相应的改变（动态优先级）

调度策略

SCHED_NORMAL:普通进程使用的调度策略，现在此调度策略使用的是CFS调度器
SCHED_FIFO:实时进程使用的调度策略，此调度策略的进程一旦使用CPU则一直运行，直到有比其更高优先级的实时进程进入队列，或者自动放弃CPU，适用于时间要求比较高，但每次运行时间比较短的进程。
SCHED_RR:试试进程使用的时间片轮转法策略，实时进程的时间片用完后，调度器将其放到队尾，这样每个实时进程都可以执行一段时间。适用于每次运行时间比较长的实时进程

调度

处于TASK_RUNNING状态的进程会进入调度器进行选择，其他状态的调度器不会进入调度器进行调度，调度的时机如下：

调用cond_resched()时
显示调用schedule()时
从系统调用或异常终端返回用户空间时
从中断上下文返回用户空间时

当内核抢占（默认开启）时，会多出几个调度时机：

在系统调用或异常中断上下文中调用preempt_enabled()时（多次调用preempt_enabled()时，系统只会在最后一次调用时调度）
在中断上下文中，从中断处理函数返回到可抢占的上下文时（这里是中断下半部，中断上半部实际上会关中断，而新的中断只会被登记，由于上半部处理很快，上半部处理完成后才会执行新的中断信号，这样就形成了中断可重入，但是即使是中断下半部，也是不能够被调度的）

在系统启动调度器初始化时会初始化一个调度定时器，调度定时器每隔一定时间执行一个中断，在中断会对当前运行进程进行更新，如果进程需要被调度，在调度定时器中断中会设置一个调度标志位，之后从定时器中断返回，因为上面中断上下文返回时是有调度时机的，如果定时器中断返回时正好是返回到用户态空间，且调度标志位又置位了，这时候就会做进程切换。在内核源码的汇编代码中所有的中断返回处理都必须去判断调度标志位是否设置，如设置则执行schedule()进行调度。每次调度时，会优先在实时进程运行队列中查看是否有可运行的实时进程，如果没有，再去普通进程运行队列找下一个可运行的普通进程，如果也没有，则调度器会使用idle进程进行运行。

在中断期间的时候（无论是上半部还是下半部），调度是被禁止的，中断之后才被重新允许调度。对于异常，系统并不会禁止调度，也就是在异常上下文中，系统是有可能发生调度的

数据结构

普通进程使用的调度算法为CFS调度算法，它是以红黑树为基础的调度算法，相比于实时进程的调度算法复杂很多，而实时进程在组织架构上与普通进程没有太大差别，也较为简单

组织形式

每个CPU包含一个运行队列结构（struct rq），每个运行队列又包含有其自己的实时进程运行队列（struct rt_rq）、普通进程运行队列（struct cfs_rq）。也就是说每个CPU都有它自己的实时进程运行队列和普通进程运行队列。

组调度（struct task_group）

如果有两个进程分别属于两个用户，而进程的优先级不同，会导致两个用户所占用的CPU时间不同，这样显然是不公平的（如果优先级差距很大，低优先级进程所属用户使用CPU的时间就很小），所以内核引入组调度。如果基于用户分组，即使进程优先级不同，这两个用户使用的CPU时间都为50%。如果task_group1中的运行时间还没有用完，会调度task_group1中下一个被调度进程；相反，如果task_group1的运行时间使用结束，则调用上一层的下一个被调度进程。需要注意的是，一个组调度中可能会有一部分是实时进程，一部分是普通进程，这也导致这种组要能够满足即能在实时调度中进行调度，又可以在CFS调度中进行调度。

分组方式：

用户ID：按照进程的UserID进行分组，在对应/sys/kernel/uid/目录下会生成一个cpu.share文件，可以通过配置文件来配置用户所占CPU时间的比例
cgroup(control group)：生成组用于限制其所有进程，比如我生成一个组（生成后此组为空，里面没有进程），设置其CPU使用率为10%，并把一个进程丢到这个组中，那么这个进程最多只能使用10%的CPU，如果将多个进程丢到这个组，这个组所有进程评分10%

这里的进程组概念和fork调用产生的父子进程组概念不一样，文章所使用的进程组概念全为组调度中进程组的概念。

调度实体(struct sched_entity)

load：权重，是通过优先级转换而成，是vruntime计算的关键
on_rq：表明是否处于红黑树运行队列当中，需要明确的一个观点是，CFS运行队列里面包含有一个红黑树，但这个红黑树并不是CFS运行队列的全部，因为红黑树仅仅是用于选出下一个调度程序的算法。很简单的一个例子，普通程序运行时，其并不在红黑树中，但是还是处于CFS运行队列中，其on_rq为真。只有准备退出，即将睡眠等待和转为实时进程的进程其CFS运行队列的on_rq为假
vruntime：虚拟运行时间，调度的关键，其计算公式：一次调度间隔的虚拟运行时间 = 实际运行时间 * （NICE_o_LOAD / 权重）。可以看出跟实时运行时间和权重有关，红黑树以此作为排序的标准优先级越高的进程在运行时其vruntime增长的越慢，其可运行时间相对就长，而且也越有可能处于红黑树的最左节点，调度器每次都选择最左边的节点为下一个调度进程。注意其值为单调递增，在每个调度器的时钟中断时当前进程的虚拟运行时间都会累加，单纯的说就是进程们都在比谁的vruntime最小，最小的将被调度。
cfs_rq：此调度实体所处的CFS运行队列
my_q：如果此调度实体代表的时一个进程组，那么此调度实体就包含有一个自己的CFS运行队列，其CFS运行队列中存放的是此进程组中的进程，这些进程就不会再其他CFS运行队列的红黑树选择，如果进程组B还有个子进程组C原理都一样，就是一个层次结构。

调度类，里面包含的是调度处理函数struct sched_class

在内核中不同的调度算法他们的操作不同，为了方便修改、替换调度算法，使用了调度类，每个调度算法只需要实现自己的调度类就可以了，CFS算法有他的调度类，SCHED_FIFO也有他自己的调度类，当一个进程创建时，用什么调度算法就将task_struct -> sched_class 指向其相应的调度类，调度器每次调度处理器时，就通过当前进程的调度类函数进行操作，大大提高了可移植性和易修改性。

CFS运行队列（struct cfs_rq）

我们现在知道，在系统中至少有一个CFS运行队列，其就是根CFS运行队列，而其他的进程组和进程都包含在此运行队列中，不同的是进程组又有它自己的CFS运行队列，其运行队列中包含的是此进程组中的所有进程。当调度器从根CFS运行队列中选择了一个进程组进行调度时，进程组就会从自己的CFS队列中选择一个调度实体进行调度（这个调度实体可能为进程，也可能为一个子进程组），就这样一直深入，只要确定其代表着一个CFS运行队列，并且包含一个红黑树进行选择调度进程即可。

load：其保存的是进程组中所有进程的权值总和，子进程计算vruntime时有时候需要用到它

CPU运行队列（struct rq）

每个CPU都有自己的rq结构，其用于描述在此CPU上所运行的所有进程，其包括一个实时进程队列和一个根CFS运行队列，在调度时，调度器首先会去实时进程队列找是否有实时进程需要运行，如果没有才会去CFS运行队列找是否有进程需要运行。