Linux CFS
CFS（Completely Fair Scheduler）是Linux 2.6.23之后的内核默认的线程调度器，它提供了一种相对公平的线程调度策略。它提供了多种调度算法，大致分为两类。
- 普通调度策略
- 实时调度策略
普通调度
普通调度策略，即最小vruntime调度。包含SCHED_OTHER, SCHED_IDLE, SCHED_BATCH这几类。在普通调度策略下，优先级（sched_priority）字段总是为0，并没有参与到调度策略的决策中。
注意：这里说的sched_priority与ps或top命令中看到的pri字段，并不是同一个含义。
vruntime
vruntime是一个线程在cpu上运行的累计时间经过归一校正计算后的结果 ，调度器会优先调度vruntime较小的线程。
理想情况下，所有线程的vruntime大小应该一致，即各线程得到了公平的调度。
线程切换原则
原则很简单：总是选择vruntime最小的线程进行调度。
线程A在执行一段时间后，它的vruntime逐渐累积。一旦A的vruntime超过另一个B的vruntime，CFS则做出线程切换，调度线程B执行。
红黑树
所有处于runnable状态的线程，基于vruntime值，组织一棵红黑树（CFS red-black tree）。以此方便地插入新的线程，或取出vruntime最小的线程。
基于nice值的动态优先级
nice值通过对vruntime的校正，进而影响线程被分配到的时间片的多少。nice的取值范围是-20（高优先级）~19（低优先级）。nice会影响线程占用CPU的时间，nice值越小被分配到的时间片越多。nice值仅会影响SCHED_OTHER和SCHED_BATCH策略。
下面简要解释算法：
每一个nice值都对应一个权重系数。大约为： weight = 1024 * (1.25)^(-nice)。
可以简要地理解为，权重系数为(1.25)^(-nice)。
- 当nice为0，权重系数=1，
vruntime即是线程在cpu上运行的实际时间。 - 当nice>0，权重系数>1，
vruntime会比线程在cpu上运行的实际时间更长。 - 当nice<0，权重系数<1，
vruntime会比线程在cpu上运行的实际时间更短。
调度策略
SCHED_OTHER
SCHED_OTHER仅用于sched_priority为0的线程，在sched_priority为0的所有SCHED_OTHER线程中，使用CFS默认的调度策略（最小vruntime调度），上面已经描述了具体算法。
SCHED_BATCH
SCHED_BATCH与SCHED_OTHER类似，仅用于sched_priority为0的线程。其不同之处在于：SCHED_BATCH会假设所有线程都是对cpu都是贪婪的，它会在线程的每一次调度之后，对线程施加一点“小惩罚”。这种策略通常应用于占用cpu较多，但又没有用户交互的线程中。
SCHED_IDLE
SCHED_IDLE仅用于sched_priority为0的线程，nice值对它也不起作用。此调度策略被应用于极低优先级的线程，仅当系统空闲时线予调度。
实时调度
SCHED_FIFO和SCHED_RR都属于实时线程调度策略。
sched_priority在实时调度策略中被使用，它的取值范围是1~99。调度器针对每一个sched_priority级别，都维护一个待执行的线程的队列。调度器会从最高优先级的非空队列中，选择队头节点的线程来执行。
SCHED_FIFO
当一个SCHED_FIFO达到可执行状态，它总是会抢占SCHED_OTHER, SCHED_IDLE, SCHED_BATCH的线程。SCHED_FIFO并没有把cpu时间切分时间片，一旦开始执行，就会一直执行，除非以下状况：
- 线程主动挂起（I/O等）。
- 被更高的优先级线程抢占。
它遵循以下规则：
- 正在被执行的
SCHED_FIFOA线程，如果被更高优先级的B线程抢占，它会放在队列队头中。一旦B线程执行完成，A线程会马上被恢复调度。 SCHED_FIFO的线程从不可执行转为可执行状态，它会被加入到对应sched_priority的队尾。SCHED_FIFO线程的优先级被调整时，如果是提高优先级，会被放入新优先级队列的队尾；如果是降低优先级，会被放在新优先级队列的队头。
SCHED_RR
RR（Round-robin）调度是针对FIFO调度的增强。在以上FIFO调度的策略的基础上，添加了以下规则：可以配置线程单次执行的最大时间片长度。一旦时间片被使用完，线程停止执行并放置到对应优先级队列的队尾。