预计阅读时间： 5 分钟
本文简易而快速地介绍了Linux内核中完全公平类调度类CFS调度器的原理和实现。
原理
其实CFS（Completely Fair Scheduler）的核心原理很简单，就是使得每个进程都尽可能“公平”地获得运行时间。因此每次都选择过去运行得最少得进程运行。当然，作为一个调度器，它要满足的需求远不止于此。Linux的抢占式进程和在完全公平类fair_sched_class中支持优先级等一系列特性，使得CFS的设计变得比简单的选出运行时间最少要复杂得多。但是不要着急，我们一步一步来理解CFS的原理。
最小运行时间
为了避免过度频繁的抢占发生，Linux内核设置了每个Task（进程）的最小运行时间（或称运行时间粒度），在这个时间内，这个进程的CPU资源是不可被抢占的。除非进程主动让出CPU或者执行了阻塞的系统调用，一般而言进程都可以执行最少执行完这个时间。最小运行时间可以通过内核参数sched_min_granularity_ns来查看。
cat /proc/sys/kernel/sched_min_granularity_ns 3000000
时间片
CFS通过引入权重来保证高优先级的进程能够获得更多的CPU时间，进程间按照权重比例分配时间片。调度周期内分配给进程的运行时间按照这个公式计算：
运行时间tn=调度周期T * 进程权重w / 运行队列中全部进程的权重之和S
权重是一个和nice值有关的量，现在在Linux内核中的定义位于kernel/sched/core.c#L9516（文章发布时），数值如下：
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,
};
其中nice值为0的权重NICE_0_LOAD=1024，nice值每差1，权重大约差1.25倍。这里的1.25计算依据来源于nice值差1，运行时间相差10%这样的设计。
虚拟运行时间
解决完每次分配多少时间的问题后，还有一个问题需要解决，就是下一个运行的进程是谁？CFS实现的原则是“完全的公平”，那么高优先级的进程如何保证多一点的运行时间？这就要引入一个概念，叫“虚拟运行时间”了。假设我们希望有如下的情况出现：
高优先级进程运行15ms=低优先级运行5ms
那么我们就将这个相等的量设置为一个“虚拟运行时间”，这样就可以保证高优先级进程运行的时间几乎总是低优先级的3倍。在Linux中，这个虚拟运行时间与实际运行时间的关系就是刚刚提到的权重：
虚拟运行时间=真实运行时间 * NICE_0_LOAD / 进程的权重
Linux在调度元素中定义了vruntime变量（include/linux/sched.h#L453），用于记录进程的累计虚拟运行时间，代码如下：
struct sched_entity {
/* For load-balancing: */
struct load_weight load;
struct rb_node run_node;
struct list_head group_node;
unsigned int on_rq;
u64 exec_start;
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
u64 nr_migrations;
struct sched_statistics statistics;
...
}
进程每次运行完毕后就会更新vruntime变量，至于如何挑选出vruntime最少的进程，这将由红黑树完成。
红黑树
红黑树是一种自平衡的二叉树，最左的叶子节点永远是key最小的节点。红黑树通过插入（更新）和删除时的操作保证这些原子操作之间红黑树永远是平衡的。
具体的操作参见https://www.jianshu.com/p/e136ec79235c
内核将调度队列上的进程按照vruntime排列成红黑树，这样选取最小vruntime的进程就变为了简单地选出最左边的叶子节点了。
最小vruntime
内核除了红黑树以外还维护一个min_vruntime变量，以记录此时最小的虚拟运行时间。
为什么需要这个min_vruntime？我们设想以下几种状况：
- 新的进程加入了红黑树，那么它的vruntime应当是多少？
- 休眠了10万年的进程等待到了它要求的事件，现在被唤醒了，它还保持原有的vruntime吗？
- 进程被负载均衡迁移到另一个CPU上（另一个调度队列），那么它的vruntime如何改变？
由此可以看出，min_vruntime的作用就是帮助Linux内核解决这些情况。
