一、吞吐与响应
操作系统调度器设计追求的目标有两点：吞吐率大与响应快。
吞吐：全局视野，单位时间内追求工作效率最大化。
响应：单个任务视野，最小化某个任务的响应时间，哪怕以牺牲其他任务为代价。
但是，这两点很明显是相互矛盾的。
对Linux系统而言，它不是一个完全照顾吞吐的系统，也不是一个完全照顾响应的的系统。它作为一个软实时系统，实际上是想达到某种平衡，同时也提供给用户一定的配置能力。
- 对应服务器来说，倾向于吞吐。
- 对应低延迟桌面来说，倾向于响应。
二、进程类型
进程按类型主要分为IO消耗型与CPU消耗型。
IO消耗型（响应型）：CPU利用率低，进程的运行效率主要受限于I/O速度。对及时调度到敏感，对cpu性能不敏感。可能触发频率高，但单次不需要长的时间片，并且大部分时间在睡眠。
CPU消耗型（吞吐型）：CPU利用率高。对及时调度不敏感，对cpu性能敏感。可能触发频率不高，但是一旦执行就希望时间片越长越好。大部分时间在工作。
比如现在某个进程正在执行长时间编译工作（CPU消耗型），这时候你点击下鼠标（IO消耗型），这时候肯定是优先响应鼠标点击，在切回去编译。这样的用户体验才是人性化的。
注：操作系统时间片概念，它表明进程在被抢占前能持续运行的时间。
三、进程优先级
优先级号一共有0-139，其中0-99的是RT（实时）进程，100-139的是非实时进程。
数字越低优先级越高。
四、进程调度
在早期2.6内核时，调度器使用的是优先级数组和Bitmaps
1）实时调度
- 优先级：0-99，属于RT进程。
对应有两个调度策略：
SCHED_FIFO：不同优先级按照优先级高的先跑到睡眠，优先级低的再跑。同等优先级的先进先出，先ready的跑完到睡然后后ready的才接着跑。
SCHED_RR：不同优先级按照优先级高的先跑到睡眠，优先级低的再跑。同等优先级的进行时间片轮询。
举例：
| 进程 | 策略 | 优先级 |
|---|---|---|
| T1 | FIFO | 8 |
| T2、T3 | RR | 3 |
| T4 | FIFO | 1 |
那么他们在Linux上的跑法是：
T4 T4 T2 T3 T2 T3 T1 T1
当然，Linux中大多数的进程都不是RT的，而是非RT的普通进程。并且，就算有RT的进程一直存在，CPU也不会一直被RT进程霸占，必须给普通进程留有一定的时间片。在Linux对RT有个补丁限制：
在sched_rt_period_us时间内，RT进程最多跑sched_rt_runtime_us时间，剩下的时间必须留给非RT进程使用。
在Linux系统中上述两个时间在如下位置：
/proc/sys/kernel/sched_rt_period_us
/proc/sys/kernel/sched_rt_runtime_us
2）非实时调度
- 在不同的优先级进行时间片轮询
- -20 ~ 19的nice值，值越小优先级越高
普通进程调度，进程不会像RT进程那样一直占据CPU，而是所有的进程都轮询获得CPU，只是当优先级高的进程可获得更多的时间片，醒来后可以抢占优先级低的进程。但是，当进程的CPU占有率高，或者一开始的优先级高的，后面内核会动态降低它的优先级，这样可以让IO消耗型的进程能够竞争过CPU消耗型的进程，从而保障IO消耗型的进程能够及时获得CPU使用权。
这里使用的调度算法叫：CFS（完全公平调度算法），在Linux中对应SCHED_NOMAL策略。
SCHED_NOMAL：每次都调度vruntime（虚拟时间）最小的进程
计算公式：vruntime = pruntime * NICE_0_LOAD/ weight
注：
pruntime：进程的物理运行时间，即实际的运行时间
weight：权重
NICE_0_LOAD：参数，等于1024，也是nice值为0的权重
而weight与nice有关,如下位置定义了两者的对应关系：
kernel/sched/sched.h
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};
从这个数组关系看出，nice越小的weight越大。
完全公平调度策略，内部的实现使用的是红黑树。
左节点小于右节点
CFS调度策略：
前提：在没有RT进程运行的情况下，只有普通进程。
Linux最先调度vruntime最小的进程，也就是位于红黑树最左边的进程。假设最先调度的进程是p1，那么随着p1的运行，p1的pruntime就会变大，就会导致p1的vruntime就会变大，那么p1在红黑树中的位置就会往右移动。下一次，就会调度最新的vruntime最小的进程。
-
IO消耗型：pruntime小，weight大（nice值小），vruntime小，优先被调度。 -
CPU消耗型：pruntime大，weight小（nice值大），vruntime大，低优先级被调度。
另外，vruntime随着pruntime会动态变化，红黑树结构也会相应做调整。这样就很巧妙地同时照顾了普通进程的CPU/IO消耗型与优先级（nice值）的情况。
举例：
比如有4个普通进程，如下表，目前显然T1的vruntime最小(这是它喜欢睡的结果)，然后T1被调度到。
| process | pruntime | weight | vruntime |
|---|---|---|---|
| T1 | 8 | 1024（nice=0） | 8*1024/1024=8 |
| T2 | 10 | 526 （nice=3） | 10*1024/526=19 |
| T3 | 20 | 1024（nice=0） | 20*1024/1024=20 |
| T4 | 20 | 820 （nice=1） | 20*1024/820=24 |
然后，我们假设T1被调度再执行12个pruntime，它的vruntime将增大delta*1024/weight（这里delta是12，weight是1024），于是T1的vruntime成为20，那么这个时候vruntime最小的反而是T2（为19），此后，Linux将倾向于调度T2（尽管T2的nice值大于T1，优先级低于T1，但是它的vruntime现在只有19）。
最后总结一点：
普通进程调度之间遵循peace&love ,大家都非常nice，但是RT进程是特权阶级，普通进程在跑，如果突然有一个RT进程过来了，那么RT进程就是无敌的，它会被调度，直到它运行结束或者睡眠。
参考：
宋宝华Linux的进程、线程以及调度
《 Linux内核设计与实现》
网友评论