《面向应用开发者的系统指南》CPU篇之进程调度

2020-05-03

26分钟阅读时长

Linux系统

面向应用开发者的系统指南

本文是《面向应用开发者的系统指南》文档其中的一篇，完整的目录见《面向应用开发者的系统指南》导论。

概述

一种资源，如果本身数量有限，需要多个资源需求方来使用的情况下，就涉及到资源调度的问题。在内核中，CPU就是一种有限的资源，同时在系统中处于运行状态的进程数量有很多，此时就需要设计出一种方法，尽可能的保证这种资源被公平的分配到进程中间。

Linux内核中的进程调度，涉及到以下几个重要概念：

核心调度器：核心调度器可以认为是内核中进程调度模块，对外提供了周期性调度（定时触发）以及主调度器两个接口。
就绪队列：所有当前运行的进程都在这个队列中维护，需要选择出下一个执行的进程也从这个队列中选举。
调度优先级：给予不同的进程不同的优先级，这样分配到的时间就不一样。
调度算法：不同类型的进程使用不同的调度算法来选择执行进程。

以下来简单阐述这几个组件如何一起作用完成进程调度的工作。

每个CPU维护自己的就绪队列，就绪队列由结构体rq来表示，队列中的每个元素都是前面提到的描述进程信息的结构体task_struct。这里需要注意的是，虽然称之为“队列”，内部的实现中，根据不同的调度算法，使用了不同的数据结构来保存进程，比如CFS调度器使用了红黑树来保存进程，这一点在后面展开阐述，目前为止，暂且认为就绪队列是一个维护CPU所有当前就绪进程的容器。

runqueue

不同的调度器算法，无论内部如何实现，其最终都是从就绪队列中选择下一个可执行的进程来运行。在这个版本的内核中一共实现了如下几种调度器算法，它们统一由结构体sched_class来表示：

sched_class

调度器	描述	对应调度策略
dl_sched_class	deadline调度器	SCHED_DEADLINE
rt_sched_class	实时调度器	SCHED_FIFO、SCHED_RR
fair_sched_class	完全公平调度器	SCHED_NORMAL、SCHED_BATCH
idle_sched_class	idle调度器	SCHED_IDLE

以上列举了进程的几种调度器及对应的调度策略，其优先级依次递减。在下面的内容中，将详细介绍完全公平调度器（Completely Fair Scheduler，简称CFS），因为这是最普遍的进程调度器。

从以上的介绍可以看到，内核的调度器负责维护就绪队列，即提供了调度进程所需的数据来源；而不同的调度器算法则根据自己的实现来从就绪队列中选择进程来执行，那么选择的依据又是什么？答案是进程的优先级。

schedule

以上简单阐述了Linux进程调度中涉及到的四个最重要的要素，下面将展开讨论。

首先将介绍进程的优先级，通过这个值如何计算得到进程的权重，进一步得到CFS调度器算法中所需的虚拟运行时间。

紧接着介绍与进程调度相关的数据结构，以及内核中进程调度的核心调度器的实现。

最后就是详细展开CFS调度器内部的实现。

优先级、权重和虚拟运行时间

优先级

Linux通过nice命令设置进程的静态优先级，进程的nice值在[-20,19]之间，值越小优先级越高。而内核本身，选择范围[0,139]在内部表示优先级，同样是数值越低优先级越高：

nice

对于普通的进程，可以认为优先级不会发生变化，而实时进程则不然：

// kernel/sched/core.c
static int effective_prio(struct task_struct *p)
{
	p->normal_prio = normal_prio(p);
	// 如果不是实时进程，返回前面normal_prio的计算结果
	if (!rt_prio(p->prio))
		return p->normal_prio;
	return p->prio;
}

由于在这里不讨论实时进程，仅讨论普通进程，因此可以认为进程优先级就是静态不变的。

CPU时间权重

CFS调度器的设计理念，就是能够实现理想、精确的多任务CPU进程调度。与以往的调度器不同的是，CFS调度器没有时间片的概念，使用的是分配CPU时间的比例。通过进程的优先级，就可以计算出来一个进程在就绪队列中所占时间的权重了。

nice值与权重之间是一对一的关系，为了实现普通进程的nice值到CPU时间权重的快速计算，内核预计算好了一个映射数组：

// 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,
};

该数组的可以认为是这样根据nice值预先计算出来的：

weight = 1024 / (1.25 ^ nice)

公式中的1.25取值依据是：进程每降低一个nice值，将多获得10%的cpu时间。公式中以1024权重为基准值计算得来，1024权重对应nice值为0，其权重被称为NICE_0_LOAD。默认情况下，大部分进程的权重基本都是NICE_0_LOAD。

根据进程的权重值，可以得到分配给进程的CPU时间计算公式如下：

分配给进程的时间 = 总的cpu时间 * 进程的权重/就绪队列中所有进程权重之和

虚拟运行时间

有了进程在CPU运行的权重之后，内核就可以根据权重值计算出进程的虚拟运行时间（virtual runtime）。什么是“虚拟运行时间”，就是内核根据进程运行的实际时间和权重计算出来的一个时间，CFS调度器只需要保证在同一个CPU上面运行的进程，其虚拟运行时间一致即可。

比如，进程A和进程B，权重分别为1024和820（nice值分别为0和1），在6ms的运行周期中，进程A获得的运行时间6*1024/(1024+820) = 3.3ms，进程B获得的运行时间为6*820/(1024+820) = 2.7ms。进程A的cpu使用比例是3.3/6x100%=55%，进程B的cpu使用比例是2.7/6x100%=45%。计算结果也符合上面说的“进程每降低一个nice值，将多获得10% CPU的时间”。使用下面的公式转换成虚拟运行时间：

vriture_runtime = wall_time * NICE_0_LOAD / weight

即：进程A的虚拟时间3.3 * 1024 / 1024 = 3.3ms，可以看出nice值为0的进程的虚拟时间和实际时间是相等的。进程B的虚拟时间是2.7 * 1024 / 820 = 3.3ms。

可以看出尽管A和B进程的权重值不一样，但是计算得到的虚拟时间是一样的。CFS调度器只要保证在同一个CPU上面运行的进程，其虚拟时间一致即可。

从上面虚拟运行时间的计算也可以知道，一个进程的虚拟允许时间越小，其权重反而是越大的，即虚拟运行时间小的进程被调度执行的权重更大。

为了避免浮点数运算，内核中采用先放大再缩小的方法以保证计算精度。内核又对前面计算虚拟运行时间的公式做了如下转换：

vriture_runtime = (wall_time * NICE_0_LOAD) / weight
= (wall_time * NICE_0_LOAD * 2 ^32 / weight) >> 32
= (wall_time * NICE_0_LOAD * inv_weight) >> 32 (其中inv_weight=(2^32 / weight))

为了方便计算inv_weight的值，内核定义了一个预分配数组sched_prio_to_wmult，其中每一项的值为(2^32 / sched_prio_to_weight[prio])：

// kernel/sched/core.c
const u32 sched_prio_to_wmult[40] = {
 /* -20 */     48388,     59856,     76040,     92818,    118348,
 /* -15 */    147320,    184698,    229616,    287308,    360437,
 /* -10 */    449829,    563644,    704093,    875809,   1099582,
 /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
};

内核中使用结构体load_weight来描述进程的权重信息：

// include/linux/sched.h
struct load_weight {
	unsigned long			weight;
	u32				inv_weight;
};

其中，成员weight存储进程的权重，而成员inv_weight存储2^32/ weight。

有了前面的铺垫，来看内核中对应的实现，内核中使用函数__calc_delta来将实际时间转换为虚拟时间，算法原理就是前面介绍到的公式：

// kernel/sched/fair.c
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	u64 fact = scale_load_down(weight);
	int shift = WMULT_SHIFT;

	__update_inv_weight(lw);

	if (unlikely(fact >> 32)) {
		while (fact >> 32) {
			fact >>= 1;
			shift--;
		}
	}

	/* hint to use a 32x32->64 mul */
	fact = (u64)(u32)fact * lw->inv_weight;

	while (fact >> 32) {
		fact >>= 1;
		shift--;
	}

	return mul_u64_u32_shr(delta_exec, fact, shift);
}

以下将前面的nice值、权重、虚拟运行时间的关系总结如下图：

vruntime

更新虚拟运行时间

由于更新进程调度实体以及就绪队列的虚拟运行时间的操作如此重要，所以内核中有一个专门的update_curr函数完成这个工作：

update_curr

这里，update_curr函数除了更新进程本身的虚拟运行时间之外，还要更新就绪队列的min_vruntime（最小虚拟运行时间），下面介绍到CFS调度算法时讲解释这个值的作用。

数据结构

前面描述了进程的优先级是如何与进程的虚拟运行时间相关联的，接着继续看与进程调度相关的核心数据结构。

task_struct中与调度相关的成员

task_struct中与调度算法相关的成员：

// include/linux/sched.h
struct task_struct {
	// ...
	int				prio;
	int				static_prio;
	int				normal_prio;

	const struct sched_class	*sched_class;
	struct sched_entity		se;

	unsigned int			policy;
	int				nr_cpus_allowed;
	cpumask_t			cpus_allowed;  
}

task_struct使用了如下几个成员表示进程的优先级，其中prio和normal_prio表示动态优先级，static_prio表示静态优先级。静态优先级在程序启动的时候就分配好了，可以使用nice命令进行修改。normal_prio是在进程运行过程中，根据静态优先级和调度策略动态计算出来的优先级。
结构体sched_class用来表示进程所所属的调度器类。
policy保存了进程的调度策略，其中有三个可能的值：
- SCHED_NORMAL用于普通进程，该类型使用完全公平调度器来处理；
- SCHED_BATCH和SCHED_IDLE：也使用完全公平调度器来处理，不过可以用于次要的进程。SCHED_BATCH用于非交互、CPU密集的批处理进程，这类进程绝不会抢占CFS调度器的另一个进程，因此不会干扰交互式进程。SCHED_IDLE类进程的重要级很低，因为权重最小。
- SCHED_FIFO和SCHED_RR：用于实现软实时进程。
cpus_allowed：是一个位域，在多处理器系统上使用，用来限制进程可以在哪些CPU上运行。

调度器类

sched_class是用于表示所有调度器算法的结构体，各种调度器算法需要实现里面的成员函数，可以用面向对象的思想理解为所有调度器的“基类”。

// kernel/sched/sched.c
struct sched_class {
	const struct sched_class *next;

	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
	void (*yield_task) (struct rq *rq);
	bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

	struct task_struct * (*pick_next_task) (struct rq *rq,
						struct task_struct *prev,
						struct rq_flags *rf);
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

	void (*set_curr_task) (struct rq *rq);
	void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
};

其中的几个重要成员如下：

enqueue_task：进程从睡眠状态切换到可运行状态时调用，意为向就绪队列放入一个进程。
dequeue_task：用于实现进程出队列操作，当进程从可运行状态切换到不可运行状态时调用。
yield_task：进程要让出对CPU的占用时，可使用系统调用sched_yield，最终会调用yield_task。
check_preempt_curr：用一个新创建的进程来抢占当前进程，比如当wake_up_new_task函数唤醒新进程就会使用这个函数。
pick_next_task：用于选择下一个将要执行的进程，而put_prev_task则在另一个进程代替当前运行的进程之前调用。这两个操作并不等价于将进程加入或撤出就绪队列。
task_tick：由周期性调度器调用，下面会谈到。

就绪队列

就绪队列用于维护所有当前可运行的进程，每个CPU上都有一个就绪队列，由结构体rq来表示：

// kernel/sched/sched.h
struct rq {
	unsigned int nr_running;

	#define CPU_LOAD_IDX_MAX 5
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];

	struct load_weight load;

	struct cfs_rq cfs;

	struct task_struct *curr, *idle, *stop;
	u64 clock;

  // ...
};

nr_running：就绪队列上可运行进程的数目。
load：提供CPU就绪队列当前负载的度量。
cpu_load：跟踪当前的负荷状态。
cfs：分别用于完全公平调度器的就绪队列。
curr：指向当前运行进程的task_struct结构体指针。
idle：指向当前idle进程的task_struct结构体指针，当当前没有进程在运行的时候执行该进程。
clock：用于实现就绪队列自身的时钟。

内核中用如下的宏来定义了per-CPU的变量runqueues：

// kernel/sched/sched.h
DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

也提供了另外一些与就绪队列相关的宏：

// kernel/sched/sched.h

// 得到该CPU的就绪队列
#define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))
// 得到当前CPU的就绪队列
#define this_rq()		this_cpu_ptr(&runqueues)
// 根据task_struct指针拿到对应CPU的就绪队列
#define task_rq(p)		cpu_rq(task_cpu(p))
// 得到cpu当前运行的进程task_struct指针
#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)

CFS调度器的就绪队列

前面看到就绪队列结构体rq中，使用结构体cfs_rq来维护CFS调度器的就绪进程，下面简单了解一下：

struct cfs_rq {
	struct load_weight load;
	unsigned int nr_running;

	u64 min_vruntime;

	struct rb_root_cached tasks_timeline;
};

其中：

load：就绪队列上所有进程的累积负载值。
nr_running：就绪队列上的进程数量。
min_vruntime：记录就绪队列上进程的最小虚拟运行时间。这个值是计算就绪队列虚拟运行时间的基础，大部分情况下是CFS红黑树最小子节点（最左节点）的虚拟运行时间，但实际情况下可能有时候会比最小子节点的虚拟运行时间稍大一些，后面将展开讨论。
tasks_timeline：将就绪队列上所有进程的虚拟运行时间维护的红黑树。

调度实体

CFS调度器可以操作的对象是比进程更一般的实体，所以又使用了sched_entity结构体来描述进程调度的实体信息：

// kernel/linux/sched.h
struct sched_entity {
	// 权重信息，在计算虚拟时间的时候会用到inv_weight成员。
	struct load_weight		load;
	unsigned long			runnable_weight;
	// CFS调度器使用红黑树维护调度的进程信息
	struct rb_node			run_node;
	// 进入就绪队列是为1
	unsigned int			on_rq;

	u64				exec_start;
	// 调度实体已经运行实际时间总合
	u64				sum_exec_runtime;
	// 调度实体已经运行的虚拟时间总合。
	u64				vruntime;
	u64				prev_sum_exec_runtime;
};

总结上面提到的rq、cfs_rq以及sched_entity结构体的关系如下图：

cfs_rq

即：rq结构体内部有一个类型为cfs_rq结构体的成员，用于维护CFS算法的运行队列，而cfs_rq内部又是使用红黑树结构来维护成员的，每个红黑树成员是sched_entity结构体类型的节点。

核心调度器

核心调度器指的是内核的进程调度框架，由内核来触发调度进程的时机，而如何选择进程的工作，交予调度器类来实现：

scheduler-core

核心调度器中，一共有以下几处地方有机会触发进程调度，下面来分别说明。

周期性调度器

周期性调度器的入口函数是scheduler_tick，内核会按照系统频率HZ来自动调用该函数，将scheduler_tick函数精简如下：

// kernel/sched/core.c
void scheduler_tick(void)
{
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
	struct task_struct *curr = rq->curr;

	// 调用调度类对应的task_tick方法，针对CFS调度类该函数是task_tick_fair。
	curr->sched_class->task_tick(rq, curr, 0);
}

可以看到，周期性调度器通过调度器算法的task_tick函数来完成调度工作，下面讲解CFS算法时详细分析。

主调度器

主调度器的入口函数是schedule，在内核中，当需要将CPU分配给与当前进程不同的另一个进程时，就会调用schedule函数来选择下一个可执行进程。schedule函数最终调用的是__schedule函数，所以这里将__schedule函数拆分来讲解。

// kernel/sched/core.c
static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct rq_flags rf;
	struct rq *rq;
	int cpu;

	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
	prev = rq->curr;

	switch_count = &prev->nivcsw;
	if (!preempt && prev->state) {
		if (unlikely(signal_pending_state(prev->state, prev))) {
			prev->state = TASK_RUNNING;	/* 1 */
		} else {
			deactivate_task(rq, prev, DEQUEUE_SLEEP | DEQUEUE_NOCLOCK);	/* 2 */
			prev->on_rq = 0;
	}

	next = pick_next_task(rq, prev, &rf);	/* 3 */
	clear_tsk_need_resched(prev);	/* 4 */
	clear_preempt_need_resched();

	if (likely(prev != next)) {
		rq = context_switch(rq, prev, next, &rf);	/* 5 */
	}
}

如果当前进程处于可中断的睡眠状态，同时现在接收到了信号，那么将再次被提升为可运行进程。
否则就调用deactivate_task函数将当前进程变成不活跃状态，这个函数最终会调用调度器类的dequeue_task完成删除进程的工作。将进程的on_rq标志位置为0，表示不在就绪队列上了。
调用pick_next_task函数选择下一个执行的进程。
清除当前进程的TIF_NEED_RESCHED标志位，意味着不需要重调度。
如果下一个被调度执行进程不是当前进程，调用context_switch函数进行进程上下文切换。

与fork的交互

除了以上两种场景，即周期性调度器以及主调度器之外，fork创建出新进程的时候也会出现与调度器类的交互，其入口函数是sched_fork：

// kernel/sched/core.c
int sched_fork(unsigned long clone_flags, struct task_struct *p)
{ 
	if (p->sched_class->task_fork)
		p->sched_class->task_fork(p);
}

sched_fork函数中会调用到对应调度器类的task_fork成员函数来处理，下面讲到CFS调度器的时候再详细分析对应的函数。

另外，调用wake_up_new_task唤醒新的子进程执行时，也可能调用到抢占进程相关的操作，下面会分析到。

CFS调度器

概述

了解了优先级、虚拟运行时间、相关数据结构、内核调度框架之后，下面正式进入CFS调度器的讲解。

前面介绍了从进程的优先级出发，如何计算出进程在就绪队列中的时间权重，进而再计算出进程的虚拟运行时间。

CFS调度器内部维护一颗红黑树，红黑树的键值即为进程的虚拟运行时间，虚拟运行时间越小的进程，被调度执行的优先级越高，获得更多的CPU时间。

cfs

对比两个调度实体在红黑树中的先后顺序，也就只需要对比其中的虚拟运行时间即可：

// kernel/sched/fair.c
static inline int entity_before(struct sched_entity *a,
				struct sched_entity *b)
{
	return (s64)(a->vruntime - b->vruntime) < 0;
}

一个进程在刚刚加入到CFS就绪队列的红黑树中时，需要有一个基准值，即这个新加入的进程，应该和什么虚拟运行时间进行对比，找到它在红黑树中的合适位置。这个值由就绪队列中的最小虚拟运行时间来维护，对应的成员是min_vruntime。

为什么这个最小虚拟运行时间不能直接取最左子节点对应进程的虚拟运行时间？因为系统在运行，对应的里面的每个进程其虚拟运行时间也是一直在增加，因此每个就绪队列的最小虚拟运行时间也一直是增加的才对。正因为这样，这个值不能取最左子节点进程的虚拟运行时间，而是根据系统的情况一直累加，不能发生回退。

还需要注意的一点是，既然虚拟运行时间是一直累加的，那么在进程一直运行的情况下，就可能发生数据溢出现象，因此在对比两个虚拟运行时间大小的时候，不是直接比较而是判断的两者的差值（包括上面的entity_before函数也是比较的差值）：

// kernel/sched/fair.c
static inline u64 max_vruntime(u64 max_vruntime, u64 vruntime)
{
	s64 delta = (s64)(vruntime - max_vruntime);
	if (delta > 0)
		max_vruntime = vruntime;

	return max_vruntime;
}

下面首先讲就绪队列最小虚拟运行时间的计算逻辑。

最小虚拟运行时间的更新

前面讲解虚拟运行时间的计算时，已经介绍了对应的函数update_curr的核心流程，其中最后一步是更新CFS就绪队列的最小虚拟运行时间值，来看对应的update_min_vruntime函数。

// kernel/sched/fair.c
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);	/* 1 */
	u64 vruntime = cfs_rq->min_vruntime;	/* 2 */
 
	if (curr) {
		if (curr->on_rq)	
			vruntime = curr->vruntime;	/* 3 */
		else
			curr = NULL;
	}
 
	if (leftmost) { /* non-empty tree */
		struct sched_entity *se;
		se = rb_entry(leftmost, struct sched_entity, run_node);
 
		if (!curr)
			vruntime = se->vruntime;	/* 4 */
		else
			vruntime = min_vruntime(vruntime, se->vruntime);	/* 5 */
	}
 
	/* ensure we never gain time by being placed backwards. */
	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);	/* 6 *
}

首先根据CFS就绪队列的tasks_timeline成员，拿到红黑树的最左子节点。
拿到当期就绪队列的最小虚拟运行时间。
在当前就绪队列运行进程存在且该进程on_rq标志为1的情况下，使用该进程的虚拟运行时间。
在最左子节点存在的情况下，如果当前进程不存在，那么就取最左子节点的虚拟运行时间。
否则取当前进程以及最左子节点进程的虚拟运行时间的最小值。
更新CFS就绪队列的最小虚拟运行时间，其值取当前最小虚拟进程与前面拿到的较小的虚拟运行时间的较大值，这样就能保证CFS就绪队列的最小虚拟运行时间不会发生回退现象。

min_vruntime

之所以要保证CFS就绪队列的最小虚拟运行时间不回退，是因为CFS就绪队列中的红黑树排序是以调度实体的vruntime作为基准来进行计算的。vruntime值越小的节点，说明虚拟运行时间越少，对应的当前被调度的优先级就越往前，会被更快的调度来执行。

在进程运行的时候，vruntime值稳定增加，于是在红黑树中就是向右边移动。
进程在睡眠时，vruntime值保持不变，而每个队列的min_vruntime时间在增加，那么当睡眠进程被唤醒时（比如等待IO事件），其在红黑树中的位置就靠左，因为其键值变小了，于是会被更快的执行。

place_entity函数

place_entity函数属于CFS调度器算法内部使用的一个函数，其作用是调整进程调度实体的虚拟运行时间，传入的第三个参数initial为1的情况下表示是新创建的进程，否则是被唤醒的进程。

// kernel/sched/fair.c
static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	u64 vruntime = cfs_rq->min_vruntime;

	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice(cfs_rq, se);	/* 1 */

	if (!initial) {
		unsigned long thresh = sysctl_sched_latency;

		if (sched_feat(GENTLE_FAIR_SLEEPERS))
			thresh >>= 1;

		vruntime -= thresh;	/* 2 */
	}

	se->vruntime = max_vruntime(se->vruntime, vruntime);	/* 3 */
}

initial为1的情况下，表示是新创建的进程，此时将加上一个虚拟时间表示惩罚，因为虚拟时间越大在红黑树中位置就越靠右，被调度执行的顺序也越在后面。计算这个惩罚时间的函数是sched_vslice，后面展开解释。
这种情况是针对被唤醒的进程，期望它能够更快的得到调度执行，所以这里减去一个虚拟运行时间做为补偿。
调度实体的虚拟运行时间，取上面计算出来的时间以及自身的虚拟运行时间的较大值，保证不会发生回退情况。

接着看计算惩罚新创建进程虚拟运行时间的函数sched_vslice：

// kernel/sched/fair.c
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);	/* 1 */

	slice = __calc_delta(slice, se->load.weight, load);	/* 2 */

	return slice;
}

通过__sched_period函数计算调度周期时间。
将第一步中计算得到的周期时间通过__calc_delta函数转换为虚拟运行时间。__calc_delta()函数有两个功能，除了可以把计算进程运行时间转换成虚拟时间以外，还有第二个功能：计算调度实体se的权重占整个就绪队列权重的比例，然后乘以调度周期时间即可得到当前调度实体应该运行的时间（参数weught传递调度实体se权重，参数lw传递就绪队列权重cfs_rq->load）。例如，就绪队列权重是3072，当前调度实体se权重是1024，调度周期是6ms，那么调度实体应该得到的时间是6*1024/3072=2ms。

创建新进程时

在调用fork函数创建子进程的时候，会调用sched_fork函数设置子进程调度器相关的信息。该函数会调用调度器类中的task_fork成员函数来完成工作，CFS调度器对应的函数就是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;

	cfs_rq = task_cfs_rq(current);
	curr = cfs_rq->curr;
	if (curr) {
		update_curr(cfs_rq);	/* 1 */
		se->vruntime = curr->vruntime;	/* 2 */
	}

	place_entity(cfs_rq, se, 1);	/* 3 */

	se->vruntime -= cfs_rq->min_vruntime;	/* 4 */
}

更新CFS就绪队列的虚拟运行时间信息。
初始化新创建的进程对应进程调度实体的虚拟运行时间，与当前进程（其父进程）一样。
place_entity函数在新创建进程以及进程被唤醒的时候都会被调用，新创建的情况下第三个参数为1。
以当前CPU的就绪队列最小虚拟时间为基准，对虚拟运行时间进行一定的补偿（虚拟时间越小，调度的顺位越靠前）。

在这里，需要就第四段代码做一个说明。进程在刚创建的时候，其虚拟运行时间是根据当时所在的CPU就绪队列的最小虚拟运行时间为基础计算的，而进程真正开始被调度执行的时候，其所在的CPU很有可能不是最开始创建时所在的CPU了，中间发生了进程在不同CPU之间的迁移。因为不同的CPU之间，其虚拟运行时间也不尽相同，所以这里要做一下处理。比如进程从虚拟运行时间更小的CPU A迁移到虚拟运行时间更大的CPU B上时，可能就会占便宜，因为这个进程比CPU B上面其他的进程虚拟运行时间都小，将获得更大的执行时间。反过来也是如此。

因此，内核对这部分相关情况的处理是：

进程刚创建时（函数task_fork_fair）：在以就绪队列的最小虚拟运行时间为基准设置其最初的虚拟运行时间时，还需要再减去队列的最小虚拟运行时间。
进程加入一个CFS就绪队列时（函数enqueue_entity）：虚拟运行时间要加上就绪队列的最小虚拟运行时间。
进程离开一个CFS就绪队列时（函数dequeue_entity）：虚拟运行时间要减去就绪队列的最小虚拟运行时间。

队列操作

入队列操作

CFS调度算法的入队列操作是函数是enqueue_task_fair，其最终会调用enqueue_entity函数完成一个调度实体入队列的操作，来看看这个函数的工作流程。

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	bool renorm = !(flags & ENQUEUE_WAKEUP) || (flags & ENQUEUE_MIGRATED);
	bool curr = cfs_rq->curr == se;

	if (renorm && curr)
		se->vruntime += cfs_rq->min_vruntime;	/* 1 */

	update_curr(cfs_rq);	/* 2 */

	if (renorm && !curr)
		se->vruntime += cfs_rq->min_vruntime;	/*3 */

	account_entity_enqueue(cfs_rq, se);	/* 4 */

	if (flags & ENQUEUE_WAKEUP)
		place_entity(cfs_rq, se, 0);	/* 5 */

	if (!curr)
		__enqueue_entity(cfs_rq, se);	/* 6 */

	se->on_rq = 1;	/* 7 */
}

如果传入的调度实体是当前进程，并且当前进程不是被唤醒或者迁移CPU，那么当前进程的虚拟运行时间就需要加上队列当前的最小虚拟运行时间。虚拟运行时间增加，意味着在红黑树中往右边移动，下一次会更晚的被调度到。这一步需要在下面调用update_curr函数之前进行。
调用update_curr更新当前CFS就绪队列的虚拟运行时间信息。
如果不是被唤醒或者迁移CPU，并且不是当前进程，那么task_fork_fair中减去的虚拟运行时间这里加回来。
flags有ENQUEUE_WAKEUP标志，意味着是被唤醒的进程，调用place_entity函数给予一定的补偿。
不是当前进程的情况下，调用__enqueue_entity函数将调度实体加入红黑树中。
将on_rq标志位置为1。

出队列操作

CFS调度算法的入队列操作是函数是dequeue_task_fair，其最终会调用dequeue_entity函数完成一个调度实体入队列的操作，来看看这个函数的工作流程。

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	update_curr(cfs_rq);	/* 1 */

	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);	/* 2 */

	se->on_rq = 0;	/* 3 */

	account_entity_dequeue(cfs_rq, se);	/* 4 */

	if (!(flags & DEQUEUE_SLEEP))
		se->vruntime -= cfs_rq->min_vruntime;	/* 5 */
}

更新CFS就绪队列的当前虚拟运行时间。
如果不是当前进程，调用__dequeue_entity从红黑树中删除该调度实体。
on_rq标志位置为0，表示不在就绪队列中。
调用account_entity_dequeue更新队列的权重信息。
如果进程不是由于睡眠导致的出队（比如是因为CPU迁移），那么进程的虚拟运行时间就需要减去就绪队列的最小虚拟运行时间。

选择下一个执行进程

CFS调度器选择下一个执行进程的操作由函数pick_next_task_fair完成，其主要流程如下：

pick_next_task_fair

下面逐个分析这几个函数。

put_prev_task

put_prev_task函数的作用，是将即将逝去执行权的当前进程，放回到其调度器的就绪队列中，核心工作由put_prev_entity函数完成：

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
	if (prev->on_rq)                            /* 1 */
		update_curr(cfs_rq);
	if (prev->on_rq) {

		__enqueue_entity(cfs_rq, prev);         /* 2 */

		update_load_avg(cfs_rq, prev, 0);       /* 3 */
	}
	cfs_rq->curr = NULL;                        /* 4 */
}

如果进程的on_rq为1，表示当进程被剥夺执行权的时候，还是在就绪队列上面的，那么极有可能就是被抢占了执行权。在这种情况下，需要调用update_curr函数更新就绪队列的虚拟运行时间。反之，如果进程不在就绪队列上了，这里并不做操作跳过更新，因为在deactivate_task函数中已经调用update_curr函数进行了更新。
如果进程还在就绪队列上，调用__enqueue_entity函数重新加入就绪队列的红黑树中。
调用update_load_avg函数更新就绪队列的负载信息。
将就绪队列的当前进程指针置为NULL。

pick_next_entity

pick_next_entity函数的作用是从红黑树中选择下一个调度进程的调度实体返回：

static struct sched_entity *
pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	struct sched_entity *left = __pick_first_entity(cfs_rq);	/* 1 */
	struct sched_entity *se;

	if (!left || (curr && entity_before(curr, left)))
		left = curr;	/* 2 */

	se = left; /* 3 */

	/* 4 */
	if (cfs_rq->skip == se) {
		struct sched_entity *second;

		if (se == curr) {	
			second = __pick_first_entity(cfs_rq);	/* 5 */
		} else {
			second = __pick_next_entity(se);	/* 6 */
			if (!second || (curr && entity_before(curr, second)))
				second = curr;	/* 7 */
		}

		if (second && wakeup_preempt_entity(second, left) < 1)
			se = second;	/* 8 */
	}

	if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
		se = cfs_rq->last;	/* 9 */

	if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
		se = cfs_rq->next;	/* 10 */

	return se;
}

调用__pick_first_entity函数，取红黑树最左子节点的调度实体，根据我们前面的分析，这是目前虚拟运行时间最小的进程。
如果left为NULL，或者当前进程curr的虚拟运行时间比left节点更小，说明curr进程是主动放弃了执行权力，且其优先级比最左子节点的进程更优，此时将left指向curr。
此时left存储的是目前最优的调度实体指针，se保存下来。
cfs_rq->skip存储了需要调过不参与调度的进程调度实体，如果我们挑选出来的最优调度实体se正好是skip，就需要重新作出选择。
如果前面选择的se指针，正好是当前进程，这样就重新__pick_first_entity拿到当前红黑树的最左子节点。
否则，skip = se = left的情况，调用__pick_next_entity选择se的下一个子节点。
如果second == NULL，说明没有次优的进程，或者curr不为NULL的情况下，且curr进程比second进程更优，就将second指向curr，即curr是最优的进程。
在second不为NULL，且left和second的vruntime的差距是否小于sysctl_sched_wakeup_granularity的情况下，那么second进程能抢占left的执行权。
判断上一个执行的进程能否抢占left的执行权。
判断next的执行权能否抢占left的执行权。

set_next_entity

set_next_entity函数用于将调度实体存放的进程做为下一个可执行进程的信息保存下来。

static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if (se->on_rq) {
		__dequeue_entity(cfs_rq, se);	/* 1 */

		update_load_avg(cfs_rq, se, UPDATE_TG);	/* 2 */
	}

	cfs_rq->curr = se;	/* 3 */

	se->prev_sum_exec_runtime = se->sum_exec_runtime;	/* 4 */
}

__dequeue_entity用于将调度实体从红黑树中删除。对于即将被调度执行的进程，都会从红黑树中删除。而当进程被抢占后，会调用put_prev_entity函数重新插入到红黑树中。因此这里与put_prev_entity函数中插入红黑树的操作一一对应。
调用update_load_avg函数更新就绪队列的负载信息，在负载均衡的时候会用到。
更新就绪队列的当前在执行进程指针。
更新调度实体的prev_sum_exec_runtime成员，该成员用于统计当前进程已经运行的时间，check_preempt_tick函数中会使用到，做为判断进程是否能够被抢占的依据。

处理周期性调度器

CFS调度器中，处理周期性调度器的函数是task_tick_fair，实际工作由entity_tick函数负责，其核心流程如下：

entity_tick

其中的update_curr是更新就绪队列虚拟运行时间的函数，前面已经介绍过就不再阐述，重点看这里的check_preempt_tick函数。

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	unsigned long ideal_runtime, delta_exec;
	struct sched_entity *se;
	s64 delta;
 
	ideal_runtime = sched_slice(cfs_rq, curr);    /* 1 */
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;    /* 2 */
	if (delta_exec > ideal_runtime) {
		resched_curr(rq_of(cfs_rq));              /* 3 */
		clear_buddies(cfs_rq, curr);
		return;
	}
 
	if (delta_exec < sysctl_sched_min_granularity)    /* 4 */
		return;
 
	se = __pick_first_entity(cfs_rq);             /* 5 */
	delta = curr->vruntime - se->vruntime;
 
	if (delta < 0)                                /* 6 */
		return;
 
	if (delta > ideal_runtime)                    /* 7 */
		resched_curr(rq_of(cfs_rq));
}

sched_slice()函数上面已经分析过，计算curr进程在本次调度周期中应该分配的时间片。时间片用完就应该被抢占。
sum_exec_runtime与prev_sum_exec_runtime的差值delta_exec是当前进程已经运行的实际时间。
如果实际运行时间已经超过分配给进程的时间片，自然就需要抢占当前进程。设置TIF_NEED_RESCHED flag。
为了防止频繁过度抢占，我们应该保证每个进程运行时间不应该小于最小粒度时间sysctl_sched_min_granularity。因此如果运行时间小于最小粒度时间，不应该抢占。
从红黑树中找到虚拟时间最小的调度实体。
如果当前进程的虚拟时间仍然比红黑树中最左边调度实体虚拟时间小，也不应该发生调度。
这里把虚拟时间和实际时间比较，看起来很奇怪。感觉就像是bug一样，然后经过查看提交记录，作者的意图是：希望权重小的任务更容易被抢占。

唤醒抢占

当进程被唤醒时（wake_up_new_task、try_to_wake_up等），也是检查进程是否可以抢占当前进程执行权的时机，此时会调用check_preempt_curr来做这个抢占检查的工作：

void check_preempt_curr(struct rq *rq, struct task_struct *p, int flags)
{
	const struct sched_class *class;
 
	if (p->sched_class == rq->curr->sched_class) {
		rq->curr->sched_class->check_preempt_curr(rq, p, flags);   /* 1 */
	} else {
		for_each_class(class) {                                    /* 2 */
			if (class == rq->curr->sched_class)
				break;
			if (class == p->sched_class) {
				resched_curr(rq);
				break;
			}
		}
	}
}

唤醒的进程和当前的进程同属于一个调度类，直接调用调度类的check_preempt_curr函数检查抢占条件。
否则如果唤醒的进程和当前进程不属于一个调度类，就需要按照调度器类的优先级来选择。

CFS调度器的check_preempt_curr函数由check_preempt_wakeup实现：

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
	struct sched_entity *se = &curr->se, *pse = &p->se;
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
 
	if (wakeup_preempt_entity(se, pse) == 1)    /* 1 */
		goto preempt;
 
	return;
preempt:
	resched_curr(rq);                           /* 2 */
}

调用wakeup_preempt_entity函数检查唤醒的进程是否满足抢占当前进程的条件。
如果可以抢占当前进程，调用resched_curr函数，其内部实现是设置TIF_NEED_RESCHED flag。

wakeup_preempt_entity函数传入两个调度实体，返回对比结果，分为以下几种情况：

wakeup_preempt_entity

这里之所以要在大于se虚拟运行时间的情况下，需要保证大于gran值才返回1允许调度，是为了避免抢占过于频繁，导致大量上下文切换影响系统性能。默认情况下，wakeup_gran()函数返回的值是1ms根据调度实体se的权重计算的虚拟时间。

因此，满足抢占的条件就是，唤醒的进程的虚拟时间首先要比正在运行进程的虚拟时间小，并且差值还要大于一定的值才行（这个值是sysctl_sched_wakeup_granularity，称作唤醒抢占粒度）。

参考资料

《深入Linux内核架构》第2章《进程管理和调度》
CFS调度器（1）-基本原理
CFS调度器（2）-源码解析