CFS调度算法

CFS能在真实硬件上模拟出一种“公平的、精确的任务多处理CPU”。

1. 公平，即对于n个正在运行的任务，当这些任务同时不断地运行时，CPU会尽可能分配给他们1/n的处理时间。CFS是一种基于加权公平排队思想的调度算法。

2. 精确，指的是它采用红黑树作为调度的任务队列的数据结构。

简单介绍下红黑树特性：

1. 每个结点要么是红的要么是黑的。
2. 根结点是黑的。
3. 每个叶结点都是黑的。
4. 如果一个结点是红的，那么它的两个儿子都是黑的。
5. 对于任意结点而言，其到叶结点的每条路径都包含相同数目的黑结点。

• 接下来进入正餐，介绍下CFS：

1. CFS使用红黑树结构，来存储要调度的任务队列。

2. 每个节点代表了一个要调度的任务，节点的key即为虚拟时间（vruntime），虚拟时间由这个人物的运行时间计算而来。

3. key越小，也就是vruntime越小的话，红黑树对应的节点就越靠左。

4. CFS scheduler每次都挑选最左边的节点作为下一个要运行的任务，这个节点是“缓存的”——由一个特殊的指针指向；不需要进行O（logn）遍历来查找。也因此，CFS搜索的时间是O(1)。

现在问题还剩下一个，vruntime具体应该怎样计算呢？

1. vruntime = 实际运行时间 * （NICE_0_LOAD / 权重)

其中，NICE_0_LOAD是nice为0时的权重，它的值是1024。这个公式的意思是，如果进程的权重等于NICE_0_LOAD，那么它的虚拟运行时间和实际运行时间相同。如果进程的权重大于NICE_0_LOAD，那么它的虚拟运行时间就小于实际运行时间，表示它被优先调度。如果进程的权重小于NICE_0_LOAD，那么它的虚拟运行时间就大于实际运行时间，表示它被延后调度。

实际运行时间很好计算，就是该程序已经运行了多久，那么进程权重应该怎样计算呢？

答案是根据任务的nice值进行索引。nice值可以理解为是我们事先为任务分配的优先级。 这里的任务权重nice范围从-20到19。对应德权重值如下所示：

/*权重只和进程的nice值有关*/
const int sched_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值和load weight of this process的对应关系，一一对应

可能还是有点迷糊，这里举个例子就清楚了，现在我们有一个刚来的task，它的nice值是0，那么它的priority是多少呢？

答案是1024.

所以此时，该任务的vruntime += 0*1024/1024 = 0，那么该任务的key也就是0，它会被放在红黑树上相应的位置。

vruntime并不是无限小的，有一个最小值来限定。假如新进程的vruntime初值为0的话，比老进程的值小很多，那么它在相当长的时间内都会保持抢占CPU的优势，老进程就要饿死了，这显然是不公平的。

CFS是这样做的：每个CPU的运行队列cfs_rq都维护一个min_vruntime字段，记录该运行队列中所有进程的vruntime最小值，新进程的初始vruntime值就以它所在运行队列的min_vruntime为基础来设置，与老进程保持在合理的差距范围内。

对于新任务来说，vruntime = 0

这也是显而易见的，新来的任务运行时间是0嘛

这个特性也是CFS算法唤醒抢占特性的由来：

CFS的唤醒抢占特性：

休眠进程在唤醒时会获得vruntime的补偿，它在醒来的时候有能力抢占CPU是大概率事件，这也是CFS调度算法的本意，即保证交互式进程的响应速度，因为交互式进程等待用户输入会频繁休眠。

想象一下当你执行每一个敲击键盘、移动鼠标等交互操作的时候，对于系统来说，这就是来了个新任务->运行时间为0->vruntime为0->被放到调度任务队列红黑树的最左节点->最左节点通过一个特殊的指针指向，且该指针已被缓存。

这就是CFS能很快对交互式进程做出反应的全过程。

CFS流程

• 随着任务的执行，它的运行时间增加，因此vruntime也会变大，它会在红黑树中向右移动（想象一下这个画面）；
• 计算密集型作业将运行很长时间，因此它将移到最右侧；
• I/O密集型作业会运行很短的时间，因此它只会稍微向右移动；
• 对于更重要的任务，也就是nice值较小的（一般是小于0），他们的移动速度相对慢很多。（相对于nice = 0的任务，nice每小一级，CPU usage就会多10%，"10% effect"）虚拟时钟的滴答声更慢.

CFS的缺点：

也和唤醒抢占特性有关。CFS不能区分交互式进程和主动休眠的进程，主动休眠的进程并不要求快速响应，但也会在唤醒时获得补偿，例如通过调用sleep()、nanosleep()的方式，定时醒来完成特定任务，这有可能会导致其它更重要的应用进程被抢占，有损整体性能。