CFS调度原理

  上一章节中描述了Linux系统中支持多种调度，不同的调度有不同的优先级范围。对于普通进程使用的CFS调度（Completely Fair Scheduler，CFS）。完全公平调度主要核心思想就是保证在一段时间内，每个进程能够运行的时间趋于相等。
  为了尽可能的保证一段时间内，每个进程能够运行的时间相等，那么系统就需要计算出每个进程每次能够运行的时间runtime，计算出每个进程的runtime后，系统总是让之前累计运行时间最少的进程先运行，累计运行时间长的进程后运行，这样让进程运行公平。

理想公平调度模型

  假设单核CPU上有3个进程，这3个进程都处于就绪队列中，调度器每次调度运行会挑选一个runtime值最小的来运行。

  如上图，TASK1先运行了4ms（runtime=4ms）让出调度，调度器查询就绪队列中发现TASK2和TASK3的runtime=0（没运行过），那么此次调度按顺序选择TASK2进行调度运行，TASK2运行了2ms就结束了其runtime=2ms。调度器在就绪队列中继续选择，发现此时TASK3的runtime值最小=0，那么挑选TASK3运行，TASK3运行了5ms让出调度其runtime=5ms。调度器继续从就绪队列中选择进程，发现TASK2 runtime=2ms为最小，因此选择TASK2运行，TASK2运行了4ms，因此runtime累计为=6ms。因此在T1时间内TASK1、TASK2、TASK3分别运行了4ms，5ms，6ms，随着时间的推进，调度器总是选择运行时间最小的先运行，那么各进程获得的运行时间趋于相等。
  调度器选择运行时间最小的进程先运行，那是不是进程得到调度后想运行多久就运行多久？答案并不是的，而是有一定的限制。在CFS调度中，规定了一个调度周期period，每个进程能够运行的最长时间等于period/进程数量（当然还没有考虑优先级权重）。规定这样的一个调度周期用来限制每个进程最长的运行时间，避免某个进程一直运行，这样保证一段时间内，每个进程都能够得到至少运行一次。理想情况下如果period为20ms，那么有4个进程，那么平均每个进程的运行时间为5ms。在Linux系统中period并不是固定一个值，因为period固定后，当进程数量越来越多后，每个进程分配的时间就会变少，那么调度器的切换时间就会变得频繁，频繁的切换调度器也就意味着需要频繁的切换上下文，这样对于系统的开销是得不偿失的。因此Linux系统的做法是默认情况下保持一个默认值（默认值6ms），当系统就绪进程个数超过一定数量后，计算处理的运行时间小于6ms后，那么Linux系统会进行动态调整。

kernel/sched/fair.c
static u64 __sched_period(unsigned long nr_running)
{
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity;
    else
        return sysctl_sched_latency;
}

  nr_running是系统中就绪进程数量，当超过sched_nr_latency，就无法保证调度延迟，period就转为调度最小粒度。如果没有超过，调度周期就等于调度延迟sysctl_sched_latency（6ms）。
因此根据sched_period可知，总时间固定的情况下，每个进程要运行的理想时间也是确定的。

优先级与虚拟时间

优先级

CFS想要实现的是每个进程能够平均分配时间片，但是现实并非如此，因为任务总是有优先级的，有权重之分，一些任务比较重要，所以它理论上能够运行更多时间（就好比每个人的能力不一样，产生的绩效不一样，所以公司在分配年终奖的时候会倾向于产出更多绩效的优秀员工）。基于上述的场景，引入了权重的概念，权重代表这优先级，也就是不同进程的优先级对应不同的权重，CFS调度器使用nice值来表示优先级，取值范围[-20,19]数值越小，优先级越大，每个nice值都与权重值一一对应。

kernel/sched/core.c
const int sched_prio_to_weight[40] = {
 /* -20 */     88761,     71755,     56483,     46273,     36291,
 /* -15 */     29154,     23254,     18705,     14949,     11916,
 /* -10 */      9548,      7620,      6100,      4904,      3906,
 /*  -5 */      3121,      2501,      1991,      1586,      1277,
 /*   0 */      1024,       820,       655,       526,       423,
 /*   5 */       335,       272,       215,       172,       137,
 /*  10 */       110,        87,        70,        56,        45,
 /*  15 */        36,        29,        23,        18,        15,
};

  引入权重后，分给进程的运行时间就由一下公式计算得来：

进程运行时间=总的CPU时间*（进程权重/就绪队列所有进程权重之和）

  如上假设就绪队列中有A和B两个进程，A进程的nice值是0，B的nice值-1。那么A和B各自运行的时间占比为：A=1024/（1024+1277）=44.5

虚拟时间

  理想情况下，不区分优先级和权重，那么每个进程能够平分运行时间，但是引入权重后，本身在每个进程得到运行的时长就是不一样的，优先级高的进程会得到更长的运行时间。当每个进程本身的能够得到的运行时间就不一样的情况下，按照3.2.1公平调度原则，累计运行时间少的先运行看起来就太适用了。
  为了解决这个问题，引入了虚拟时间。虚拟时间用于在加入权重后，衡量每个进程在一段时间内运行是公平的，即各自能够运行的虚拟时间是相等的。
  假设A、B、C的进程权重分别是1，2，3。那么A运行Nms、B运行2Nms，C运行3Nms才是公平的。虚拟时间和实际的转化公式如下：

vruntime = delta_exec*（nice_0_weight/weight）

  delta_exec表示实际运行时间，nice_0_weight表示nice值为0的进程权重值，weight表示进程的权重值。为什么是nice_0_weight/weight了，是因为nice_0_weight对应的权重实际运行时间和虚拟运行时间相当。
当引入优先级权重中，就不用runtime值最小来判定优先运行，而是选择vruntime来判断，选择vruntime值最小的优先运行。虚拟时间等于实际运行时间乘以一定比重，这个比重根据优先级来判断。调度保证每个进程在一定时间内运行的虚拟时间相等。

  就绪队列中的每个进程对应的vruntime将会被挂到红黑树中，当前CPU进行调度时，将会从左往右开始优先选择，也就是选择vruntime最小的进程先运行。之所以选择红黑树是因为查找速度是O(1)。

min_runtime

  考虑这样的一个场景，就绪队列中有A,B,C进程已经各自运行了一段时间了，此时有一个新的进程加入到就绪队列，D加入的时候，runtime应该是多少？如果D从0开始计算，那么D将会一直运行指导追赶上A/B/C三个进程，因为调度的原则就是选择最小的vruntime来运行，如果A/B/C已经运行了几天了，那么当D加入的时候就要先运行几天追赶上A/B/C，这样显然是不合理的。
  针对以上的场景，引入了min_runtime。min_runtime记录调度队列中，虚拟时间最小的值。因此当新进程加入的时候，其虚拟时间需要+min_runtime值，这样就能够解决上述场景的问题。