还记得曾经写过一篇叫做《至今不敢写一篇cfs的文章》，那时我只是默默地欣赏cfs的和谐，可是一些转瞬即逝的感悟不写出来会是很大的遗憾，其实也谈不上什么感悟，只是理解罢了，有时你瞬间领悟的东西最好写下来，否则时间长了你会觉得很难理解。cfs调度器在2.6.23内核中被引入，起初的实现是多么的天真与纯朴，设计出来一个fair_key来代表队列的虚拟时钟，不管怎样总是实现了一个cfs的版本，到了2.6.25以后，cfs变得简单起来，没有了队列虚拟时钟的结构体，其概念直接融入了红黑树中的最左下角的调度实体的vruntime字段，其实就是让每个调度实体（没有组调度的情形下就是进程，以后就说进程了）的vruntime互相追赶，然后在某个地方会和归一，也就是达到同样的值。那么不同的优先级怎么体现呢？这就是cfs中最最精彩的地方，cfs不再说什么优先级，而统一改称权值，不同的权值的进程在相同真实时钟流逝中其虚拟时钟走的不同，也就是其vruntime的增量不同，具体来说，cfs用到了一个经验值，就是2.5%，就是说进程优先级数值每增加1，其权值降低原来的2.5%，这就有了一个一致的参照，更容易一些乘除运算，也使得cfs中的动态时间片和优先级之间成了简单的线性关系，计算每一个进程的虚拟时钟改前进多少的时候，用到了一个简单的公式，就是：
虚拟时钟的步伐(vruntime的增量)=(实际时间)*(nice为0的进程的权值/进程权值) [其中，nice为0的进程的权值为1024]
这个公式十分简单，这样就为cfs进行公平调度提供了数值依据，调度器总是挑选vruntime最小的进程然后运行它，运行多久呢？这又是cfs中最最精彩的一点，我指的是2.6.25内核版本以后的实现，从2.6.23中我看不出这点精彩，早期的cfs用的是更为复杂的计算，到底运行多久呢？又是一个公式：
进程运行时间=(系统调度周期)*(本进程的权值/本运行队列的总权值)
以上公式中的系统调度周期就是一个时间段，是一个真实的时间段，比如常规桌面系统中定义的20ms(5个进程以下)，这是什么意思呢？这就是说nr个进程公平分享这20ms，怎么个公平法呢？按照权值来，谁的权值越高谁分到的时间片越多，所有进程分到的时间总和就是这个系统调度周期，多于5个进程咋办呢？好办，按照比例增长这个调度周期就行，就按照(实际进程数量/5)这个比例增长就可以，这里这段话表明了一个含义，就是说每过一个系统调度周期也就是在一个系统调度周期内，可以保证系统中的每一个进程都可以运行，最终的结果就是每到了系统调度周期的末尾，所有进程的虚拟时钟vruntime得到归一，换句话说就是所有进程的vruntime将相同，然后开始下一个调度周期的时间片瓜分。这解决了一个大问题，就是进程饥饿问题，在以前的O(1)调度器中，进程会饥饿，为何会饥饿，第一受到系统进程数量的影响，因为时间片的分配是固定的，由优先级和HZ决定的，如果系统进程数量很多的话，就会导致进入过期队列的即使很高优先级的进程饥饿，毕竟低优先级的进程还要处理，否则就是低优先级的进程饥饿，这就使调度器进入了两难的境地，第二就是优先级调整以及交互进程判断，交互进程可以不进入过期队列，这样就会造成过期队列的进程饥饿，索性linux调度器引入了一个饥饿检测机制，从标而不是本上解决了这一个问题，不管怎样，这个解决方案显得勉强。其实还有一点，饥饿并不一定是交互进程重新排入运行队列的错，因为交互进程真正参与调度的时间很少，绝大多数时间是在等待键盘或者鼠标，即使你打字再快你也快不过cpu的主频的1/1000吧，因此如果交互进程恰恰在有饥饿进程存在的情况下重新排队才可以怪罪它，虽然交互进程在这个饥饿检测方面可以逃过责备，然而它那令人发毛的计算公式的意义，恐怕问及作者本人，他也难说明白，错在谁？错在O(1)调度器的设计，本质上O(1)调度器只是在选择进程上占优势，一旦进程多起来，一旦进程性质复杂起来，一切将失控，挑选进程，插入进程，以及进程出队等等都是一流的设计，时间复杂性都降到了O(1)的绝佳复杂度，然后要知道调度不仅仅是出队，入队，挑选，还有一点就是保证公平，而且任何事情都是一种权衡，虽然O(1)调度器在挑选，出队，入队方面做得绝佳，它必然要在公平方面补偿一下了，因此O(1)调度器的公平保障机制及其复杂又不和谐，cfs完美的解决了这一切，cfs利用了红黑树的统计性质，效果十分棒，另外它还兼顾了没有运行的进程，这些进程的虚拟时间随着运行进程的虚拟时间在前进总会落后，而调度器总是会选择最落后的进程运行，美妙的是，这一切发生在一个系统调度在周期的时间内，cfs是一种兼顾的解决方案，虽然它在入队，出队方面没有O(1)做得好，但是整体上十分和谐，十分高效。如果文字表达不清，那么就看看下面的图表：
| 真实时钟步伐 |
进程1(权值1)虚拟时钟步伐 |
进程2(权值2)虚拟时钟步伐 |
进程3(权值3)虚拟时钟步伐 |
| 1/6 |
2/6 |
0 |
0 |
| 2/6 |
2/6 |
1/6 |
0 |
| 3/6 |
2/6 |
1/6 |
1/9 |
| 4/6 |
2/6 |
1/6 |
2/9（vruntime依然最小，依然是进程3运行） |
| 5/6 |
2/6 |
2/6 |
2/9 |
| 6/6 |
2/6 |
2/6 |
3/9 |
| 7/6 |
4/6 |
2/6 |
3/9 |
| 8/6 |
4/6 |
3/6 |
3/9 |
| 9/6 |
4/6 |
3/6 |
4/9 |
| 10/6 |
4/6 |
3/6 |
5/9 |
| 11/6 |
4/6 |
4/6 |
5/9 |
| 12/6 |
4/6 |
4/6 |
6/9 |
| 13/6 |
6/6 |
4/6 |
6/9 |
| 14/6 |
6/6 |
5/6 |
6/9 |
| 15/6 |
6/6 |
5/6 |
7/9 |
| 16/6 |
6/6 |
5/6 |
8/9 |
| 17/6 |
6/6 |
6/6 |
8/9 |
| 18/6 |
6/6 |
6/6 |
9/9 |
图表1.cfs原理实例表（黑体为运行路径）
从上表可以看出，进程1，2，3的权值为1，2，3那么在一个使得虚拟时钟归一的真实时钟间隔内，进程的运行次数和其权值是成正比的，这里设进程2的虚拟时钟前进步伐和真实时钟一致，也就是以进程2为参照。
是的，cfs完美的解决了一切，那么cfs是怎样补偿睡眠进程的呢？注意，cfs已经不再区分这种睡眠是io睡眠还是交互睡眠，因为cfs中的调度周期可以保证进程总是在一个时间段内运行所有的进程，当初O(1)调度器下的交互进程之所以需要补偿就是害怕它们会饥饿，而饥饿意味着交互进程的响应变慢，现在不需要这一切了，但是睡眠进程需要补偿却是有意义的，因为可能它们有比较迫切的任务需要做，传统的UNIX调度器就是这么做的，更一般的原因就是，醒来后的精神一般比较好，多干点活是应该的，因此linux的cfs代码中存在对睡醒进程补偿：
if (sched_feat(NEW_FAIR_SLEEPERS)) {
unsigned long thresh = sysctl_sched_latency; //这就是这个调度周期
if (sched_feat(NORMALIZED_SLEEPER))
thresh = calc_delta_fair(thresh, se); //按比例增缩这个补偿的时间，保证公平
vruntime -= thresh; //进程补偿
}
vruntime = max_vruntime(se->vruntime, vruntime); //保证虚拟时钟不会倒流
上面的注释中的保证公平是何意呢？就是说保证不管其权值多少，保证其相同的补偿运行次数，也就是说都要保证刚睡醒的进程多运行n次，n表示权值为1024的nice 0进程在一个调度周期内运行的次数。为何要调整睡醒进程的vruntime，仅仅是为了补偿它吗？不！如果要补偿，最好的方式就是保留它睡前的vruntime，如果它睡得久的话，那么这个vruntime一定远远小于当前的其它运行队列进程的vruntime，如此一来这个刚睡醒的进程拼命追赶，最终的结果就是cfs为了公平，所有进程等着它，它将长时间占用cpu导致其它进程饥饿，做事不能太绝，既然睡眠了，补偿是有的，同时惩罚也应该，惩罚就是剥夺其原有的vruntime，直接将其带到前面，但是也不能全部剥夺，它还是需要多做一些事情的，就是相应地增加它的运行次数，别的进程至多忍受饥饿它执行3次的时间，这也是一种权衡，一种折中，饥饿和奖励的折中。
如果只看理论的话，那么很简单，应该都理解了，可是看代码的时候发现将进程插入红黑树的时候用到的key却不是进程的vruntime，而是se->vruntime - cfs_rq->min_vruntime，这怎么解释呢？我们看看vruntime的类型，是usigned long类型的，再看看key的类型，是signed long类型的，因为进程的虚拟时间是一个递增的正值，因此它不会是负数，但是它有它的上限，就是unsigned long所能表示的最大值，如果溢出了，那么它就会从0开始回滚，如果这样的话，结果会怎样？结果很严重啊，就是说会本末倒置的，比如以下例子，以unsigned char说明问题：
unsigned char a = 251，b = 254;
b += 5;
//到此判断a和b的大小
看看上面的例子，b回滚了，导致a远远大于b，其实真正的结果应该是b比a大8，怎么做到真正的结果呢？改为以下：
unsigned char a = 251，b = 254;
b += 5;
signed char c = a - 250,d = b - 250;
//到此判断c和d的大小
结果正确了，要的就是这个效果，可是进程的vruntime怎么用unsigned long类型而不处理溢出问题呢？因为这个vruntime的作用就是推进虚拟时钟，并没有别的用处，它可以不在乎，但是它却真的处理了溢出问题，然而在计算红黑树的key的时候就不能不在乎了，于是减去一个最小的vruntime将所有进程的key围绕在最小vruntime的周围，这样更加容易追踪。运行队列的min_vruntime的作用就是处理溢出问题的，它的追踪作用主要是随时可以找到红黑树最左下的进程。现在看看插入一个新进程发生地情况，简单的说，就是延缓整个cfs运行队列的进展，因为一个进程加入了，这个进程加入以后加到哪里呢？也就是说它在红黑树的key应该是多少呢？为了使得新进程更快的运行就应该将其加入不能在左下的位置，但是能是最左下角的位置吗？不能，那样相当于毫无依据的抢占了最值得运行的进程的位置，而当前最小的红黑树vruntime值也就是min_vruntime值已经给了下一个最值得运行的进程，活着还有一种可能，就是当前正在运行的进程的vruntime就是min_vruntime，那么解决问题的办法就是在min_vruntime的基础上加上一个值作为新进程的vruntime，什么值呢？很显然就是：
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
return calc_delta_fair(sched_slice(cfs_rq, se), se);
}
sched_slice计算了进程se每次应该推进的真实时钟，而calc_delta_fair是应该推进的虚拟时钟，对于上图的进程2，最终的结果就是1/6，对于进程3，结果就是1/9，这就是说，到此为止的虚拟时钟推进一笔勾销，从下一个开始，新进程参与竞争，什么叫下一个，下一个就是当前的运行进程的虚拟时钟完成这一次推进以后，新进程参与到竞争中来，就是这样。从此以后，一切安然。看看在__update_curr中的vruntime中怎么更新每个进程的vruntime的，就是用真实的时钟间隔调用calc_delta_fair的，这里却是用sched_slice(cfs_rq, se)调用的，也就是说cfs调度器认为新进程已经运行了sched_slice(cfs_rq, se)，而sched_slice(cfs_rq, se)是这个新进程每次运行的理想时间，所谓的承诺预先运行就是先让一个进程运行sched_slice以后再将其插入红黑树权衡，意义就是本来所有进程的虚拟时钟一致才算公平，只有当一个进程运行了sched_slice之后才会产生不公平，只有不公平确实发生了，cfs调度器才会去补偿最应得到补偿的，补偿这件事才算发生，其实正常运行的进程在运行了sched_slice之后，就会发生调度，然后在schedule中的pick_next_task之前会有一个put_prev_task的调度，后者是个当前进程入队的过程，其key值由其vruntime和cfs_rq的min_vruntime差来定义，这就是不公平之后的权衡，就是说在一个进程受到调度之前，也就是被权衡之前，其必须先入队，而入队只有承诺预先之后才入队，在新进程插入时，cfs调度器就认为已经承诺运行过该进程了，运行了多少呢？当前是运行了足以让cfs调度器权衡的时间段，就是sched_slice
看一下cfs的饥饿问题，如果直接用vruntime作为key值，cfs理论可以保证没有饥饿出现，可是key的计算却是两个同样递增的值的差，这怎么能保证一个key很大的进程一次又一次的被vruntime比较大，但是二值之差比较小的进程插队呢？很简单，就是这个及时min_vruntime更新和归一化过程阻止了这一切，记住，在插入进程的时候，用的是同一个min_vruntime，这样的话等于减去同一个值，其大小关系不变，最终不会导致饥饿，在以下代码段体现：
while (*link) {
parent = *link;
entry = rb_entry(parent, struct sched_entity, run_node);
if (key < entity_key(cfs_rq, entry)) {
...
}
cfs调度器的系统调度周期是可以配置的，对于桌面系统，最重要的是响应性而不是性能，因此非常小的调度周期就可以应付，也就是20ms，但是对于服务器来说，最大可将调度周期设置为1s。