之前讨论的调度器的设计两大思想，启发式算法和调度类。现在我们深入到linux官方调度器CFS上查看cfs调度器的设计思想

什么是CFS

CFS也就是Completely Fair Scheduler，完全公平调度器，顾名思义。
那怎么做到完全公平呢？我举个例子，假设有3个任务，每个任务的处理时间都是33.33%，那么它们公平了吗。答案是是的，这种调度器是公平调度器，但却不是完全公平调度器，为什么呢。

这种公平调度器在传统操作系统上其实叫做步幅调度，怎么理解

每个任务按照严格的比例划分
提供一个share概念，是每个进程按照比例分到的蛋糕
提供一个stride概念，每次运行之后就像前进一样，加上stride
提供一个pass概念，作为任务默认的初始值，每次运行后加上步子

那么步幅调度简单理解就是所有的进程在多个跑道上跑步，他们的起始点是pass值，我们通过进程的比例来决定份额share，如果share高，那么他同一时刻是优先跑。那么等价share可以换算成stride，也就是每个人的步子，同一时刻下份额高，那么步子低，也就是说stride低的先跑。每次时刻跑完了记录pass上自加stride

换句话说，现实生活中，每个人的步幅高，他就跑的快，步幅高是单位时间内某人步子更大，他天生就会比普通人快，但是我们要追求公平，所以我们让哪些跑的慢的同学，也就是单位时间步子小的同学占更大的份额，这样可以保证即使每个同学最终都是平均的到达终点

在实际情况下，跑得快的同学可以考虑情绪价值等一下跑的慢的同学，这是主观行为
在调度的设计中，机制让跑得快的同学一定要等跑得慢的同学，这是机制

一个跑步的图片，摘自网络

步幅调度的图片，摘自论文

理解了步幅调度，那么我们理解CFS就更轻松了，因为一个是公平调度，一个是完全公平调度。一方面他们的维持公平的原理是一致的，另一方面，它考虑了公平调度的缺点，去适当按照启发式的算法尝试做到完全公平

公平的概念

CFS和步幅调度很相似，在步幅调度中，stride越小，那么进程越容易被调度，而在cfs中，步幅不再存在，我们按照vruntime越小决定进程越容易被调度

那哪些地方需要做启发式的算法呢，我们可以先看看步幅调度的缺点

问题1. 新的任务进来时，pass肯定比旧的任务小，那么步幅调度一定优先调用新进程。这会导致眼下对其他任务并不公平。
问题2. 假设系统存在很高份额的任务，那么步幅调度肯定优先调用高份额低步幅的任务，如果低步幅的任务数量多，运行时间短，那么会导致眼下对其他任务并不公平。

可以看到，启发式算法要做到完全的公平，而不是绝对的公平。

完全的公平指的是既要整体上按照公平调度，也要在局部或眼下维持一定的公平。

权重

对于步幅调度，其时间为pass+stride不断累积，上图可以看到pass一直增加。它是决定公平
而对于CFS调度，需要维护局部的公平，所以增加了权重的概念。那么它计算公式需要乘以权重，如下


vruntime += delta * nice0 / weight

这里delta和nice0是很好理解，weight存在的意义就是局部最优的实施。


/*
 * Nice levels are multiplicative, with a gentle 10% change for every
 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 * that remained on nice 0.
 *
 * The "10% effect" is relative and cumulative: from _any_ nice level,
 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 * If a task goes up by ~10% and another task goes down by ~10% then
 * the relative distance between them is ~25%.)
 */
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,
};

根据注释可以理解，这里给定了sched_prio_to_weight，其值其实是一个近似计算的经验值，也就是每1个nice下，按照cpu下降10%的实测数据估算，这个比例~25%。
这里10%也可以估算。如下
假设A为n，B为n+1，那么


weight_a = 1024 / 1.25 ^ n   
weight_b = 1024 / 1.25 ^ (n + 1)
percentage_a = weight_a / (weight_a + weight_b)
percentage_b = weight_b / (weight_a + weight_b)

我拿最简单的权重计算


36 + 29 = 65
a = 36 / 65 = 55.38%
b = 29 / 65 = 44.61%
55.38% - 44.61% = 10.77% ~= 10%
29 * 1.25 = 36.25 ~= 36

实际上，为了代码实施的高性能，内核讨巧的提供了另一个预运算的查表sched_prio_to_wmult


/*
 * Inverse (2^32/x) values of the sched_prio_to_weight[] array, precalculated.
 *
 * In cases where the weight does not change often, we can use the
 * precalculated inverse to speed up arithmetics by turning divisions
 * into multiplications:
 */
const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

根据注释可以知道，他们的公式刚刚差2^32，也就是


sched_prio_to_wmult[prio] ≈ (2³²) / sched_prio_to_weight[prio]

在代码里面计算如下


                lw.weight = scale_load(sched_prio_to_weight[prio]);
                lw.inv_weight = sched_prio_to_wmult[prio];

nice的归一化

在内核中，nice默认归一化为1024，我们可以看到如下定义


#ifdef CONFIG_64BIT
# define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
# define scale_load(w)          ((w) << SCHED_FIXEDPOINT_SHIFT)
# define scale_load_down(w) \
({ \
        unsigned long __w = (w); \
        if (__w) \
                __w = max(2UL, __w >> SCHED_FIXEDPOINT_SHIFT); \
        __w; \
})
#else
# define NICE_0_LOAD_SHIFT      (SCHED_FIXEDPOINT_SHIFT)
# define scale_load(w)          (w)
# define scale_load_down(w)     (w)
#endif

这里sched fixed point shift为


# define SCHED_FIXEDPOINT_SHIFT               10

所以我们可以得到两个概念

nice的归一化为1024
nice的shift按照bit64/32决定，分别是20/10

那么这个shift在bit64上扩大为20也就意味着NICE_0_LOAD 的值从1024变大为1048576。换算到公式vruntime += delta * nice0 / weight相当于扩大了vruntime的计算精度，因为本身bit64可以算的值更大，这样调度的颗粒度能更加精确。但无论如何，我们统一理解nice的归一化是1024是没有任何问题的

总结

本文介绍了cfs调度的概念，并且提到了cfs的一个重要概念，权重，通过权重可以进行调度的启发式计算。

参考

https://web.eecs.umich.edu/~mosharaf/Readings/Stride.pdf

目录

什么是CFS

公平的概念

权重

nice的归一化

总结

参考