O(n)算法虽然历史有点悠久，但很有必要研究，是后续O(1)等算法理解的基础。由于O(n)不是本文重点，建议先去网上了解相关知识点。
O(1) 调度器中引入了per-CPU runqueue的概念。系统中所有的可运行状态的进程首先经过负载均衡模块挂入各个CPU的runqueue，每隔 200ms，处理器都会检查 CPU 的负载是否不均衡，如果不均衡，处理器就会在 CPU 之间进行一次任务均衡操作。然后由主调度器和tick调度器驱动该CPU上的调度行为。每一个优先级的进程被挂入不同链表中。
上图说明了 task 与负载均衡和 runqueue 以及对应调度器之间的关系。每个 runqueue 里又会分为active和expired队列，每个队列中挂载着140个优先级不同的 task 。关于调度器在 runqueue 里的算法实现我们看下面一张图：
可以看出2.6 kernel 里有 140 种优先级，所以我们就用长度为 140 的 array 去记录优先级。每个优先级下面用一个 FIFO queue 管理这个优先级下的 process。那么，我们怎么找到当前最高优先级下面的可执行的 process 呢？如果从 0 开始一直遍历下去，算法虽然不是 O(N)，但是是跟优先级多少相关的 O(M)，也不能算作 O(1)。在 2.6 scheduler 里，采用 bitarray。它为每种优先级分配一个 bit，如果这个优先级队列下面有 process，那么就对相应的 bit 染色，置为 1，否则置为 0。问题就简化成寻找一个 bitarray 里面最高位是 1 的 bit（left-most bit），这基本上是一条 CPU 指令的事（fls）
- 在 active bitarray 里，寻找 left-most bit 的位置 x。
- 在 active priority array（APA）中，找到对应队列 APA[x]。
- 从 APA[x] 中 dequeue 一个 process，dequeue 后，如果 APA[x] 的 queue 为空，那么将 active bitarray 里第 x bit置为 0。
- 对于当前执行完的 process，重新计算其 priority，然后 enqueue 到 expired priority array（EPA）相应的队里 EPA[priority]。
- 如果 priority 在 expired bitarray 里对应的 bit 为 0，将其置 1。
- 如果 active bitarray 全为零，将 active bitarray 和 expired bitarray 交换一下。
比如，调度周期是12ms，2个相同优先级的进程A和B，那么每个进程的运行时间各为6ms。倘若进程A,B的优先级nice分别为0和1，那么权重分别是1024和820。它们的关系如下：权重 = 1024 / 1.25nice(次方)
那么进程A获取的运行时间是12x1024/(1024+820)=6.66ms，进程B获取的运行时间是12x820/(1024+820)=5.34ms。进程A的cpu使用比例是6.66/10=66.6%，进程B的cpu使用比例是5.34/10=53.4%。这里我们看到2个进程的执行时间分别是6.66ms和5.34ms，是不一样的。但是CFS是想让每个进程完全公平调度，这里就引入一个概念——虚拟时间，CFS也是通过虚拟时间相等来保证调度公平的。虚拟时间vriture_runtime和实际时间wall time转换公式如下：虚拟时间 = 实际时间 * (1024/进程权重) = (调度周期 * 进程权重 / 所有进程总权重) * (1024 / 进程权重) = 调度周期 * 1024 / 所有进程总权重
可以看出虽然进程的权重不同，但是它们的 vruntime增长速度应该是一样的 ，与权重无关。（进程A的虚拟时间=6.66 *（1024/1024）= 6.66ms，进程B的虚拟时间=5.34 *（1024/820）= 6.66ms。这里我们看出虽然进程的优先级不同，但最终的虚拟时间一样。）总结：谁的vruntime值较小就说明它当前占用cpu的时间较短，受到了“不公平”对待，因此下一个运行进程就是它。这样既能公平选择进程，又能保证高优先级进程获得较多的运行时间。这就是CFS的主要思想了。
CFS维护了一个按照虚拟时间排序的红黑树：
任务存储在以时间为顺序的红黑树中（由 sched_entity 对象表示），对处理器需求最多的任务 （最低虚拟运行时）存储在树的左侧，处理器需求最少的任务（最高虚拟运行时）存储在树的右侧。为了公平，调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。任务通过将其运行时间添加到虚拟运行时， 说明其占用 CPU 的时间，然后如果可运行，再插回到树中。这样，树左侧的任务就被给予时间运行了，树的内容从右侧迁移到左侧以保持公平。因此，每个可运行的任务都会追赶其他任务以维持整个可运行任务集合的执行平衡。
添加良许个人微信即送3套程序员必读资料
→ 精选技术资料共享
→ 高手如云交流社群
本公众号全部博文已整理成一个目录，请在公众号里回复「m」获取！
推荐阅读：
就是要让你搞懂Nginx，这篇就够了！
好玩、有趣的 Linux 命令学习神器 kmdr！
为什么只有 Pornhub 这么红？
5T技术资源大放送！包括但不限于：C/C++，Linux，Python，Java，PHP，人工智能，单片机，树莓派，等等。在公众号内回复「1024」，即可免费获取！！
