Linux内核CFS调度器已经在越来越多的场景中表现出不适合，比如采用SSD服务数据库时，许多人会告诉你改用NOOP/Deadline乃至BFQ，而背后的原因却往往一知半解。Linux内核调度器的适用场景是个复杂的问题，本文试图初步做一些研究和说明，以后相关话题还会随着认识的深入而继续更新。
CFS调度器全称为Complete Fair Scheduler，其主要设计思路是维持CPU时间分配的公平。为此，CFS给每个被调度任务引入了虚拟运行时间的概念，虚拟运行时间越小，意味着该任务获得CPU的时间越少，就越需要被调度来获取CPU。所有未运行的任务按照虚拟运行时间排序，存放在一棵红黑树中(见题图)。随着任务的运行其对应的虚拟运行时间会增加。当调度发生时(通常为时钟中断，IO中断，进程间唤醒通知等)，调度器比较当前运行任务跟最早没有运行任务的虚拟运行时间，或者跟唤醒的任务的虚拟运行时间相比较。如果后者的虚拟运行时间数值较小，调度器就在两个任务之间进行一次上下文切换。总体上，CFS算法试图保证正在运行的任务拥有最低虚拟运行时间。CFS也会采用一些启发式算法避免过度调度(Over Scheduling)，例如通过设置sched_min_granularity参数。用户也可以给任务指定"share"值，任务的虚拟运行时间跟它的share值相比于其他任务的比例成反比。
CFS设计的一个重要细节在于任务被唤醒进入运行状态后虚拟运行时间如何分配。通常这会平衡两个属性：1) 允许被唤醒任务快速运行，确保唤醒它的事件能够及时处理；2) 不要分配不公平的CPU时间份额。CFS通过如下策略来平衡这两点：vruntime(T) = max(vruntime(T), min(vruntime(∗)) − L)，后者代表所有未睡眠任务的最小虚拟运行时间减去一个位移L，通常等于调度延迟的一半大小。
很不幸，CFS的唤醒算法会让不定期的任务给一些延迟敏感的任务带来过长的等待时间，根本原因在于CFS所使用的位移值比延迟敏感任务的响应延迟deadline还要大。例如下图中，如果memcached A正在响应请求，此时另一个任务B被唤醒，如果B的虚拟运行时间小，那么就会发生抢占，并且B放在A的后边L长的时间，当B运行就会导致A的等待至少L长的时间才能继续处理请求。只有在A的虚拟运行时间不会超过B时，才会保证A不会受到上面调度延迟的干扰。因此，在系统负载低的情况下，memcached的响应延迟通常很好，这种情况下它通常因为虚拟运行时间不够长而不会被抢占。
可以通过给延迟敏感任务分配很大的share值来缓解调度延迟，可以通过nice命令设置，或者通过cgroup直接设置，这样该任务的虚拟运行时间增长总是很慢，发生抢占或者因抢占而导致的等待延迟都不高，但是这样会引起其他任务挨饿。还有种做法是采用Posix实时调度器，比如SCHED_FIFO以及SCHED_RR，前者是除非任务自己放弃执行，或者更高优先权的任务可以运行，否则调度的任务会一直执行下去，而后者则根据时间片(比如100ms)来周期性根据优先权选择执行的任务。这些调度器都是基于优先权的，且高优先权任务肯定无法被低优先权抢占执行，因此延迟敏感任务在内核采用这种调度器时表现会很好，如果有多个延迟敏感任务混排运行时，如果按照延迟越低优先权越高的原则分配优先权，可以整体上达到70%的负载。这也是许多性能调优文章里建议在采用SSD时更换调度策略为NOOP的原因所在。当然，跟分配share值的问题类似，采用实时调度器也会导致低优先权任务挨饿。
不论是CFS，还是SCHED_FIFO/RR，都可以给任务指定CPU配额，这样可以避免挨饿的发生，但也会带来副作用：当CPU时间超过配额时，任务就无法运行，这对于负载高的情况下会很不利。相比之下，BVT调度器(Borrowed Virtual Time)提供了为延迟敏感任务跟其他任务的混排提供了一个更加良好的合作机制，它的思想是给基于虚拟运行时间的调度增加一个"warp"参数，用来表示在调度决策时任务虚拟运行时间的静态偏移，调整后的虚拟运行时间称为有效虚拟运行时间。如下图所示，任务B初始正在睡眠，唤醒后，任务A调整后的w值比固定位移L还要小，因此A并不会被B抢占。这种调整对短时抢占有利，但同时对于长期运行的吞吐量公平影响最小，是个基于CFS调度策略的修正方案。
Linux内核调度，延迟和吞吐量两者本就是冲突的指标。默认的CFS调度器保证了公平，也就是为吞吐量优化，那么延迟就必然会出问题，如果只考虑延迟，那么除非这台物理机只跑某些低延迟的高优先权任务，否则其余的低优先权任务就会迟迟得不到处理，公平无法保证。
上面的所有讨论，如果引入IO因素，就会更加复杂起来，例如淘宝在CFS上修改而来的tpps调度器。我们以后针对这个方面再深入讨论。BVT提供了一种长期公平下的策略调整，但它只考虑了CPU时间，没有考虑IO，因此，在低延迟高IO型的任务下表现如何，以及warp参数如何调整都是新的课题。
所以，尽管在很多时候CFS都会存在问题，但我们需要根据任务类型，任务优先级设定，任务混排，IO设定等等因素来综合考虑调度器选择，而不能仅仅通过只言片语的参数设定就人云亦云。
