目录
CFS简介
CFS，即Completely Fair Scheduler，由资深内核开发者 Ingo Molnar开发，在2.6.23版本的内核中并入主线，并沿用至今。按照内核文档介绍（参考linux-4.18 Documentation/scheduler/sched-design-CFS.txt），CFS的设计理念用一句话概括：在真实的硬件上实现理想的、精准、完全公平的多任务调度。
任务调度器发展
什么是调度器（scheduler）？调度器的作用是什么？调度器是一个操作系统的核心部分，可以比作是CPU时间的管理员。调度器主要负责选择某些就绪的任务来执行。不同的调度器根据不同的方法挑选出最适合运行的任务。那么依据什么挑选最适合运行的任务呢？这就是每一个调度器需要关注的问题。
不同的任务有不同的需求，因此我们需要对任务进行分类：一种是普通进程，另外一种是实时进程，对于实时进程，Linux内核的主要考虑因素是优先级，调度器总是选择优先级最高的那个进程执行。普通进程又分为交互式进程（IO密集型的，等待IO）和批处理进程（CPU密集型的，守护进程等），交互式进程需要和用户进行交互，因此对调度延迟比较敏感，而批处理进程属于那种在后台默默干活的，因此它更注重吞吐，对调度延迟要求不高。普通进程如何细分时间片则是调度器的核心思考点。过大的时间片会严重损伤系统的响应延迟，让用户明显能够感知到延迟，卡顿，从而影响用户体验。较小的时间片虽然有助于减少调度延迟，但是频繁的切换对系统的吞吐会造成严重的影响。
任务？进程？进程是资源管理的单位，线程才是调度的单位，但线程调度器这个说法很少见，所以我们可以说任务调度器。
Linux内核中使用一个非常大的结构体来同时表达进程和线程，即task_struct。但是调度类管理和调度的单位是调度实体，即sched_entity，并不是task_struct。我们这里只看下task_struct中与调度相关的字段：
struct task_struct {
/*
进程执行时，它会根据具体情况改变状态,Linux 中的进程主要有如下状态
TASK_RUNNING 可运行
TASK_INTERRUPTIBLE 可中断的等待状态
TASK_UNINTERRUPTIBLE 不可中断的等待状态
TASK_ZOMBIE 僵死
TASK_STOPPED 暂停
*/
volatile long state; /* -1 unrunnable, 0 runnable, >0 stopped */
int prio; /*动态优先级，根据静态优先级及其他条件计算而来*/
int static_prio; /*普通进程静态优先级，取值范围是100（优先级最高）～139（优先级最低），分别对应nice value的-20 ～ 19。*/
int normal_prio; /*调度器综合考虑各种因素，例如调度策略，nice value、scheduling priority等，把这些factor全部考虑进来，归一化成一个数轴上的number，以此来表示其优先级，这就是normalized priority。对于一个线程，其normalized priority的number越小，其优先级越大。*/
unsigned int rt_priority; /*实时进程优先级*/
unsigned int policy; /*调度策略*/
const struct sched_class *sched_class; /*调度类*/
struct sched_entity se; /*普通进程调度实体*/
struct sched_rt_entity rt; /*实时进程调度实体*/
struct sched_dl_entity dl;
};
不同的任务有不同的需求，因此一个系统中会共存多个调度器，目前Linux支持的调度器有RT scheduler、Deadline scheduler、CFS scheduler及Idle scheduler等。
针对以上调度类，系统中有明确的优先级概念。每一个调度类利用next成员构建单项链表。优先级从高到低示意图如下：
sched_class_highest----->stop_sched_class
.next---------->dl_sched_class
.next---------->rt_sched_class
.next--------->fair_sched_class
.next----------->idle_sched_class
.next = NULL
Linux的任务调度器是不断演进的，先后出现过三种里程碑式的调度器：
- O(n)调度器 内核版本 2.4-2.6
- O(1) 调度器 内核版本 2.6.0-2.6.22
- CFS调度器 内核版本 2.6.23-至今
O(n) 调度器
O(n)调度器采用一个全局队列runqueue作为核心数据结构，存在的问题非常多：
- 对runqueue队列的遍历的复杂度是O(n)；
- 多个cpu共享全局队列，随着CPU数目增多，加锁开销成为性能瓶颈；
- 实时进程和普通进程混合且无序存放
- CPU空转问题：当runqueue链表中的所有进程耗尽时间片，才会启动新一轮对系统中所有进程时间片重新计算的过程，只要有一个CPU上还在运行着进程，其他CPU都是idle，造成CPU资源的浪费
- task bouncing issue：一般而言，一个进程最好是一直保持在同一个CPU上运行。随着runqueue中的进程一个个的耗尽其时间片，cpu可选择的余地在不断的压缩，从而导致进程可能在一个和它亲和性不大的处理器上执行。
O(1)调度器
O（n）调度器中只有一个全局的runqueue，严重影响了扩展性，因此O（1）调度器中引入了per-CPU runqueue的概念。系统中所有的可运行状态的进程首先经过负载均衡模块挂入各个CPU的runqueue，然后由各自的调度器驱动CPU上的调度行为。
由于引入了per-CPU runqueue，O（1）调度器删除了全局runqueue的spin lock，同时把spin lock放入到per-CPU runqueue数据结构中，通过把一个大锁细分成小锁，可以大大降低调度延迟，提升系统响应时间。这种方法在内核中经常使用，是一个比较通用的性能优化方法。
在Linux 2.5版本的开发过程中，Ingo Molnar设计的O（1）调度器替换掉了原始的、简陋的O（n）调度器，从而解决了扩展性很差，性能不佳的问题。然而O（1）并非完美，在实际的使用过程中，还是有不少的桌面用户在抱怨交互性比较差。
在O（n）和O（1）调度器中，时间片是固定分配的，静态优先级高的进程获取更大的time slice。例如nice value等于20的进程获取的default timeslice是5ms，而nice value等于0的进程获取的是100ms。直观上，这样的策略没有毛病（高优先级的获取更多的执行时间），但是，这样的设定潜台词就是：高优先级的进程会获得更多的连续执行的机会，这是CPU-bound进程期望的，但是实际上，CPU-bound进程往往在后台执行，其优先级都是比较低的。
因此，假设我们调度策略就是根据进程静态优先级确定一个固定大小的时间片，这时候我们在如何分配时间片上会遇到两难的状况：想要给用户交互型进程设定高优先级，以便它能有更好的用户体验，但是分配一个大的时间片是毫无意义的，因为这种进程多半是处于阻塞态，等待用户的输入。而后台进程的优先级一般不高，但是根据其优先级分配一个较小的时间片往往会影响其性能，这种类型的进程最好是趁着cache hot的时候狂奔。
怎么办？或者传统调度器固定分配时间片这个设计概念就是错误的。
在反反复复修复用户卡顿issue的过程中，很多天才工程师试图通过修改用户交互指数算法来解决问题，试图去猜测进程对交互性的需求，这其实非常困难，就像收集了一个人性格特点，业余爱好，做事风格，逻辑思维水平，星座猜。。。也很难猜测一个人的心中所想。
在进程调度这件事情上为何不能根据实实在在确定的东西来调度呢？一个进程的静态优先级已经完说明了其调度需求了，这就足够了，不需要猜测进程对交互性的需求，只要维持公平就OK了，而所谓的公平就是进程获取和其静态优先级匹配的CPU执行时间。在这样的思想指导下，Con Kolivas提出了RSDL（Rotating Staircase Deadline）调度器。
RSDL调度器
RSDL（Rotating Staircase Deadline)）调度器仍然沿用了O（1）调度的数据结构和软件结构，当然删除了那些令人毛骨悚然的评估进程交互指数的代码。限于篇幅，这一小节只简单了解下RSDL算法，了解Rotating、Staircase和Deadline这三个基本概念。
首先看Staircase概念，它更详细表述应该是priority staircase，即在进程调度过程中，其优先级会象下楼梯那样一点点的降低。在传统的调度概念中，一个进程有一个和其静态优先级相匹配的时间片，在RSDL中，同样也存在这样的时间片，但是时间片是散布在很多优先级中。例如如果一个进程的优先级是120，那么整个时间片散布在120～139的优先级中，在一个调度周期，进程开始是挂入120的优先级队列，并在其上运行6ms（这是一个可调参数，我们假设每个优先级的时间配额是6ms），一旦在120级别的时间配额使用完毕之后，该进程会转入121的队列中（优先级降低一个level），发生一次Rotating，更准确的说是Priority minor rotating。之后，该进程沿阶而下，直到139的优先级，在这个优先级上如果耗尽了6ms的时间片，这时候，该进程所有的时间片就都耗尽了，就会被挂入到expired队列中去等待下一个调度周期。这次rotating被称为major rotating。当然，这时候该进程会挂入其静态优先级对应的expired队列，即一切又回到了调度的起点。
Deadline是指在RSDL算法中，任何一个进程可以准确的预估其调度延迟。一个简单的例子，假设runqueue中有两个task，静态优先级分别是130的A进程和139的B进程。对于A进程，只有在进程沿着优先级楼梯从130走到139的时候，B进程才有机会执行，其调度延迟是9 x 6ms ＝ 54ms。
多么简洁的算法，只需要维持公平，没有对进程睡眠/运行时间的统计，没有对用户交互指数的计算，没有那些奇奇怪怪的常数……调度，就是这么简单。
CFS调度器
CFS是Completely Fair Scheduler简称，即完全公平调度器。CFS调度器和以往的调度器的不同之处在于没有时间片的概念，而是分配cpu使用时间的比例。例如：2个相同优先级的进程在一个cpu上运行，每个进程都分配50%的cpu运行时间，这就是要实现的公平。
如果进程优先级相同，那么只要保证每个进程的实际运行时间相同即可（每个调度周期内），就能做到公平。调度时，调度器只需要记录每个进程的实际运行时间，每次调度时挑出已经运行时间最短的进程。
以上的例子是基于相同的优先级，但现实却并非如此，有些任务优先级比较高，有些任务优先级比较低，那么CFS调度器的如何比较和选择呢？
虚拟时间vruntime
CFS引入权重的概念，权重代表着进程的优先级。权重和nice值一一对应，nice值的取值范围是[-20, 19]，数值越小代表优先级越大，同时也意味着权重值越大。内核提供了一个表格转换nice值和权重。
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,};
数组的值可以看作是公式：
\[weight = 1024 / 1.25^{nice} \]计算得到。公式中的1.25取值依据是：进程每降低一个nice值，将多获得10% cpu的时间。公式中以1024权重为基准值计算得来，1024权重对应nice值为0，其权重被称为NICE_0_LOAD。默认情况下，大部分进程的权重基本都是NICE_0_LOAD。
虚拟时间virtual_runtime和实际时间（wall_time）转换公式如下：
\[vruntime = wall\_time * (\frac{NICE\_0\_LOAD}{weight}) \]举个例子：进程A和B，他们的权重分别是1024和820（nice值分别是0和1），进程A运行的时间，即wall_time是3.3ms，进程B运行的时间是2.7ms，进程A的虚拟时间3.3 * 1024 / 1024 = 3.3ms，我们可以看出nice值为0的进程的虚拟时间和实际时间是相等的。进程B的虚拟时间是2.7 * 1024 / 820 = 3.3ms。我们可以看出尽管A和B进程的权重不一样，但是计算得到的虚拟时间是一样的。直观上，我们可以理解为低优先级进程的时间走的快一些，高优先级进程的时间走的慢一些。CFS主要保证每一个进程获得执行的虚拟时间一致即可。在选择下一个即将运行的进程的时候，只需要找到虚拟时间最小的进程即可。
源码浅析
CFS有很多进程操作，这里我们仅浅析一下进程创建过程中有关调度器的一点内容。进程创建是通过do_fork()函数完成，我们一路尾随do_fork()函数，do_fork()---->_do_fork()---->copy_process()---->sched_fork()。针对sched_fork()函数，删减部分代码如下：
int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
/*
* We mark the process as NEW here. This guarantees that
* nobody will actually run it, and a signal or other external
* event cannot wake it up and insert it on the runqueue either.
*/
p->state = TASK_NEW;
/*
* Make sure we do not leak PI boosting priority to the child.
*/
p->prio = current->normal_prio;
if (dl_prio(p->prio)) {
put_cpu();
return -EAGAIN;
} else if (rt_prio(p->prio)) {
p->sched_class = &rt_sched_class;
} else {
p->sched_class = &fair_sched_class; /* 1 */
}
if (p->sched_class->task_fork)
p->sched_class->task_fork(p); /* 2 */
return 0;
}
- fair_sched_class是CFS调度类。
- 调用调度类中的task_fork函数。task_fork方法主要做fork相关的操作。传递的参数p就是创建的
task_struct。
CFS调度类fair_sched_class的初始化方法如下：
const struct sched_class fair_sched_class = {
.next = &idle_sched_class, //下一个调度器是idle调度器（链表按照优先级顺序排列）
.enqueue_task = enqueue_task_fair, //将一个task加入到cfs_rq
.dequeue_task = dequeue_task_fair, // 将一个task从cfs_rq删除
.yield_task = yield_task_fair,
.yield_to_task = yield_to_task_fair,
.check_preempt_curr = check_preempt_wakeup, // 检查指定task是否可以抢占当前task
.pick_next_task = pick_next_task_fair, // 切换task, 当前task加入到cfs_rq队列，取新的task设置成current
.put_prev_task = put_prev_task_fair,
#ifdef CONFIG_SMP
.select_task_rq = select_task_rq_fair,
.migrate_task_rq = migrate_task_rq_fair,
.rq_online = rq_online_fair,
.rq_offline = rq_offline_fair,
.task_dead = task_dead_fair,
.set_cpus_allowed = set_cpus_allowed_common,
#endif
.set_curr_task = set_curr_task_fair,
.task_tick = task_tick_fair,
.task_fork = task_fork_fair,
.prio_changed = prio_changed_fair,
.switched_from = switched_from_fair,
.switched_to = switched_to_fair,
.get_rr_interval = get_rr_interval_fair,
.update_curr = update_curr_fair,
#ifdef CONFIG_FAIR_GROUP_SCHED
.task_change_group = task_change_group_fair,
#endif
};
task_fork_fair实现如下：
static void task_fork_fair(struct task_struct *p)
{
struct cfs_rq *cfs_rq;
struct sched_entity *se = &p->se, *curr;
struct rq *rq = this_rq();
struct rq_flags rf;
rq_lock(rq, &rf);
update_rq_clock(rq);
cfs_rq = task_cfs_rq(current);
curr = cfs_rq->curr; /* 1 */
if (curr) {
update_curr(cfs_rq); /* 2 */
se->vruntime = curr->vruntime; /* 3 */
}
place_entity(cfs_rq, se, 1); /* 4 */
se->vruntime -= cfs_rq->min_vruntime; /* 5 */
rq_unlock(rq, &rf);
}
cfs_rq是CFS调度器就绪队列，curr指向当前正在cpu上运行的task的调度实体。
更新当前正在运行的调度实体(sched_entity )的运行时间和虚拟运行时间。
将父进程的虚拟运行时间赋给了新进程的虚拟运行时间。
place_entity()函数在进程创建以及唤醒的时候都会调用，创建进程的时候传递参数initial=1。设想一下子如果休眠进程的vruntime保持不变, 而其他运行进程的 vruntime一直在推进, 那么等到休眠进程终于唤醒的时候, 它的vruntime比别人小很多, 会使它获得长时间抢占CPU的优势, 其他进程就要饿死了. 这显然是另一种形式的不公平，因此CFS是这样做的：在休眠进程被唤醒时重新设置vruntime值，以cfs_rq->min_vruntime值为基础，给予一定的补偿，但不能补偿太多. 这个重新设置其虚拟运行时间的工作就是就是通过place_entity来完成的。新进程创建完成后, 也是通过place_entity完成其虚拟运行时间vruntime的设置的。
我们前面讲解place_entity的时候说到, 新创建的进程和睡眠后苏醒的进程为了保证他们的vruntime与系统中进程的vruntime差距不会太大, 会使用place_entity来设置其虚拟运行时间vruntime, 在place_entity中重新设置vruntime值，以cfs_rq->min_vruntime值为基础，给予一定的补偿，但不能补偿太多。这样由于休眠进程在唤醒时或者新进程创建完成后会获得vruntime的补偿，所以它在醒来和创建后有能力抢占CPU是大概率事件，这也是CFS调度算法的本意，即保证交互式进程的响应速度，因为交互式进程等待用户输入会频繁休眠。
但是这样子也会有一个问题, 我们是以某个cfs就绪队列的min_vruntime值为基础来设定的, 在多CPU的系统上，不同的CPU的负载不一样，有的CPU更忙一些，而每个CPU都有自己的运行队列，每个队列中的进程的vruntime也走得有快有慢，比如我们对比每个运行队列的min_vruntime值，都会有不同, 如果一个进程从min_vruntime更小的CPU (A) 上迁移到min_vruntime更大的CPU (B) 上，可能就会占便宜了，因为CPU (B) 的运行队列中进程的vruntime普遍比较大，迁移过来的进程就会获得更多的CPU时间片。这显然不太公平
同样的问题出现在刚创建的进程上, 还没有投入运行, 没有加入到某个就绪队列中, 它以某个就绪队列的min_vruntime为基准设置了虚拟运行时间, 但是进程不一定在当前CPU上运行, 即新创建的进程应该是可以被迁移的.
CFS是这样做的：
- 当进程从一个CPU的运行队列中出来 (dequeue_entity) 的时候，它的vruntime要减去队列的min_vruntime值
- 而当进程加入另一个CPU的运行队列 ( enqueue_entiry) 时，它的vruntime要加上该队列的min_vruntime值
- 当进程刚刚创建以某个cfs_rq的min_vruntime为基准设置其虚拟运行时间后，也要减去队列的min_vruntime值
这样，进程从一个CPU迁移到另一个CPU之后，vruntime保持相对公平。
下面继续对update_curr()一探究竟。
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr; /* 1 */
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
delta_exec = now - curr->exec_start; /* 2 */
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;
curr->sum_exec_runtime += delta_exec; /* 3 */
curr->vruntime += calc_delta_fair(delta_exec, curr); /* 4 */
update_min_vruntime(cfs_rq);
}
- 确定就绪队列的当前执行的调度实体。
- delta_exec计算本次更新虚拟时间距离上次更新虚拟时间的差值。
- 重新更新启动时间exec_start为now,以备下次计算时使用，最后将计算出的时间差加到先前的统计时间上。
- 开始计算虚拟时间。
其中NICE_0_LOAD的值为：1024，当进程的nice=0时，不需要进行加权处理，其虚拟时间就等于其实际运行时间。
就绪队列（runqueue）
系统中每个CPU都会有一个全局的就绪队列（cpu runqueue），使用struct rq结构体描述，它是per-cpu类型，即每个cpu上都会有一个struct rq结构体。每一个调度类也有属于自己管理的就绪队列。例如，struct cfs_rq是CFS调度类的就绪队列，管理就绪态的struct sched_entity调度实体，后续通过pick_next_task接口从就绪队列中选择最适合运行的调度实体（虚拟时间最小的调度实体）。struct rt_rq是实时调度器就绪队列。struct dl_rq是Deadline调度器就绪队列。
struct rq {
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
};
struct cfs_rq {
struct load_weight load;
unsigned int nr_running;
u64 min_vruntime;
struct rb_root_cached tasks_timeline;
};
struct rb_root_cached {
struct rb_root rb_root;
struct rb_node *rb_leftmost;
};
- load：就绪队列权重，就绪队列管理的所有调度实体权重之和。
- nr_running：就绪队列上调度实体的个数。
- min_vruntime：跟踪就绪队列上所有调度实体的最小虚拟时间。
- tasks_timeline：用于跟踪调度实体按虚拟时间大小排序的红黑树的信息（包含红黑树的根以及红黑树中最左边节点）。
CFS维护了一个按照虚拟时间排序的红黑树，所有可运行的调度实体按照p->se.vruntime排序插入红黑树。如下图所示。
CFS选择红黑树最左边的进程运行。随着系统时间的推移，原来左边运行过的进程慢慢的会移动到红黑树的右边，原来右边的进程也会最终跑到最左边。因此红黑树中的每个进程都有机会运行。
Linux中所有的进程使用task_struct描述。task_struct包含很多进程相关的信息（例如，优先级、进程状态以及调度实体等）。其中包括调度实体，调度实体存放与调度类相关的调度信息，并参与调度，CFS调度器对应的调度实体为struct sched_entity se，实时调度器对应的调度实体为struct sched_rt_entity rt，CFS调度器的调度实体sched_entity如下：
struct sched_entity
{
struct load_weight load; /* for load-balancing负荷权重，这个决定了进程在CPU上的运行时间和被调度次数 */
struct rb_node run_node;
unsigned int on_rq; /* 是否在就绪队列上 */
u64 exec_start; /* 上次启动的时间*/
u64 sum_exec_runtime;
u64 vruntime; /* 虚拟运行时间*/
u64 prev_sum_exec_runtime;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
...
};
CFS调度器使用cfs_rq跟踪就绪队列信息以及管理就绪态调度实体，并维护一棵按照虚拟时间排序的红黑树。tasks_timeline->rb_root是红黑树的根，tasks_timeline->rb_leftmost指向红黑树中最左边的调度实体，即虚拟时间最小的调度实体（为了更快的选择最适合运行的调度实体，因此rb_leftmost相当于一个缓存）。每个就绪态的调度实体sched_entity包含插入红黑树中使用的节点rb_node，同时vruntime成员记录已经运行的虚拟时间。我们将这几个数据结构简单梳理，如下图所示。
Reference:
蜗窝科技，强烈推荐内核源码分析好文
Linux系统如何标识进程？
NPTEL online course 讲解CFS简洁易懂
Linux进程调度器，也推荐【Linux内核之旅】公众号的其他文章
https://cs334.cs.vassar.edu/
为什么STL和linux都使用红黑树作为平衡树的实现?
Linux CFS调度器之唤醒抢占--Linux进程的管理与调度(三十）