Linux CFS的工作原理是什么？

在CFS算法引入之前，Linux使用过几种不同的调度算法，一开始的调度器是复杂度为O(n)的始调度算法(实际上每次会遍历所有任务，所以复杂度为O(n)), 这个算法的缺点是当内核中有很多任务时，调度器本身就会耗费不少时间，所以，从linux2.5开始引入赫赫有名的O(1)调度器，然而，linux是集全球很多程序员的聪明才智而发展起来的超级内核，没有最好，只有更好，在O(1)调度器风光了没几天就又被另一个更优秀的调度器取代了，它就是CFS调度器Completely Fair Scheduler. 这个也是在2.6内核中引入的，具体为2.6.23，即从此版本开始，内核使用CFS作为它的默认调度器，O(1)调度器被抛弃了。：

    O(n)调度：内核调度算法理解起来简单：在每次进程切换时，内核依次扫描就绪队列上的每一个进程，计算每个进程的优先级，再选择出优先级最高的进程来运行；尽管这个算法理解简单，但是它花费在选择优先级最高进程上的时间却不容忽视。系统中可运行的进程越多，花费的时间就越大，时间复杂度为O(n)
    O(1)调度：其基本思想是根据进程的优先级进行调度。进程有两个优先级,一个是静态优先级,一个是动态优先级.静态优先级是用来计算进程运行的时间片长度的,动态优先级是在调度器进行调度时用到的,调度器每次都选取动态优先级最高的进程运行.由于其数据结构设计上采用了一个优先级数组，这样在选择最优进程时时间复杂度为O(1)，所以被称为O(1)调度。

这两种调度算法，其基本思路都是通过一系列运行指标确定进程的优先级，然后根据进程的优先级确定调度哪个进程，而CFS则转换了一种思路，它不计算优先级，而是通过计算进程消耗的CPU时间（标准化以后的虚拟CPU时间）来确定谁来调度。从而到达所谓的公平性。

来源：简书 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Completely Fair Scheduler：完全公平调度器，linux 2.6.23后引入作为默认调度器

vruntime：virtual runtime

公式：vruntime = 实际运行时间 * 1024 / 进程权重，权重由nice确定，nice越大，权重越小

思想：各进程的vruntime增加速度不同，权重越大增加越慢，CFS会分配更多的CPU执行时间给vruntime更小的进程

实现：CPU的每个核都会实现一个红黑树，记录进程的vruntime，O(logn)