1. CFS的原理
CFS给每一个进程安排一个虚拟运行时钟vruntime，当一个进程得以执行，随着时间的推移，vruntime的值不断的增大。而没有运行的进程的vruntime的是不会改变的。而调度器总是选择进程队列中vrutime最小的进程执行，这就体现了“完全公平性”。那如何区分不同进程之间的优先级呢？就是说优先级高的进程vruntime增长的速度会比较慢，因此会得到更多的运行机会。
2. CFS的设计思路
CFS的思路比较简单，就是根据每个进程的权重分配运行时间，则进程的运行时间的计算公式如下：
分配给进程的时间 = 调度周期*进程权重/(所有进程权重之和) (1)
调度周期就相当于将所有处于TASK_RUNING的进程调度一次运行时间，也相当于在O(1)调度算法中运行队列和过期队列切换一次的时间。假如有两个线程A和B，它们的群众分别是1和2，调度周期是30ms。那么进程A的运行时间是 30*(1)/(1+2) = 10ms, 进程B的运行时间是30*(2)/(1+2) = 20ms。
请注意上述的例子中，运行时间是不一样的，那如何体现公平性？公平性是体现在vruntime中的，vruntime中记录的是进程的运行时间，但并不是直接去记录运行时间，而是根据的进程的权重进行相应的调整。我们给出实际运行时间到vruntime的计算公式：
vruntime = 进程的运行时间 * 1024 / 进程的权重 (2)
公式2中1024是nice为0的进程权重，代码中是NICE_0_LOAD。也就是说所有的进程都是以nice为0的进程权重1024来计算自己的vruntime的增长速度。现在我们将公式(2)中的进程的运行时间用公式(1)代替：
vruntime = 调度周期*进程权重/(所有进程权重之和) * 1024 / 进程的权重 = 调度周期*1024/(所有进程权重之和) (3)
可以看出所以的进程的权重虽然不同，但是他们的vrutime的增长速度是相同的，与权重无关。那么我们就可以根据vruntime来选择要运行的进程，谁的vruntime比较小，那说明他的CPU运行时间就比较小，下一个需要运行的进程就是它。这样既可以公平的选择进程，又可以保证更高优先级的进程可以获得更多的运行时间。就是CFS的主要思想。
CFS的思想就是让每个调度实体（没有组调度的情形下就是进程，以后就说进程了）的vruntime互相追赶，而每个调度实体的vruntime增加速度不同，权重越大的增加的越慢，这样就能获得更多的cpu执行时间。 再补充一下权重的来源，权重跟进程nice值之间有一一对应的关系，可以通过全局数组prio_to_weight来转换，nice值越大，权重越低。
3. CFS的数据结构
首先是调度实体sched_entity，sched_entity是一个调度单位，在组调度关闭的时候，它等同于一个进程。每一个task_struct中都包含一个sched_entity，权重以及vruntime都保存在里面。使用红黑树将所有的sched_entity组织在一起，sched_entity以vruntime为key值插入到红黑树中(实际上是以vruntime-min_vruntime为key，是为了防止溢出)，同时缓存最左侧结点同时也是vruntime的最小值结点，这样就可以选中vruntime最小的进程。其中只有等待CPU就绪状态的进程在这颗树上，睡眠进程以及正在运行的进程都不在这颗树上。
4. Vruntime溢出问题
作为红黑树的key不是vruntime而是vruntime-min_vruntime。min_vruntime是红黑树中最小的key。这是因为vruntime的值是unsigned long类型的，vruntime的值随着进程的运行不断变大，而他会有一个上限，当达到unsinged long表示的最大值的时候就会溢出了。如果vruntime溢出了就会回滚到0，这样会导致一些问题。可是进程的vruntime怎么用unsigned long类型而不处理溢出问题呢？因为这个vruntime的作用就是推进虚拟时钟，并没有别的用处，它可以不在乎，然而在计算红黑树的key的时候就不能不在乎了，于是减去一个最小的vruntime将所有进程的key围绕在最小vruntime的周围，这样更加容易追踪。运行队列的min_vruntime的作用就是处理溢出问题的。
6. CFS小结
CFS还有一个重要的特点，即调度粒度小。CFS之前的调度器中，除了进程调用某些函数主动参与调度之外，每个进程都在用完时间片或被抢占。CFS会在每个tick的时候都会检查，
