CFS调度器（2）-源码解析

前言

经通过上一篇文章《CFS调度器-基本原理》，我们可以了解到CFS调度器基本工作原理。本篇文章主要集中在Linux CFS调度器源码解析。

注：文章代码分析基于Linux-4.18.0。

进程的创建

进程的创建是通过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)
{
	p->state = TASK_NEW;
	p->prio = current->normal_prio;
	p->sched_class = &fair_sched_class;         /* 1 */

	if (p->sched_class->task_fork)
		p->sched_class->task_fork(p);           /* 2 */

	return 0;
}

task_struct

CFS调度类fair_sched_class方法如下：

const struct sched_class fair_sched_class = {
	.next				= &idle_sched_class,
	.enqueue_task		= enqueue_task_fair,
	.dequeue_task		= dequeue_task_fair,
	.yield_task			= yield_task_fair,
	.yield_to_task		= yield_to_task_fair,
	.check_preempt_curr	= check_preempt_wakeup,
	.pick_next_task		= pick_next_task_fair,
	.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);
}

1. cfs_rq是CFS调度器就绪队列，curr指向当前正在cpu上运行的task的调度实体。
2. update_curr()函数是比较重要的函数，在很多地方调用，主要是更新当前正在运行的调度实体的运行时间信息。
3. 初始化当前创建的新进程的虚拟时间。
4. place_entity()函数在进程创建以及唤醒的时候都会调用，创建进程的时候传递参数initial=1。主要目的是更新调度实体得到虚拟时间（se->vruntime成员）。要和cfs_rq->min_vruntime的值保持差别不大，如果非常小的话，岂不是要上天（疯狂占用cpu运行）。
5. 这里为什么要减去cfs_rq->min_vruntime呢？因为现在计算进程的vruntime是基于当前cpu上的cfs_rq，并且现在还没有加入当前cfs_rq的就绪队列上。等到当前进程创建完毕开始唤醒的时候，加入的就绪队列就不一定是现在计算基于的cpu。所以，在加入就绪队列的函数中会根据情况加上当前就绪队列cfs_rq->min_vruntime。为什么要这样处理呢？假设cpu0上的cfs就绪队列的最小虚拟时间min_vruntime的值是1000000，此时创建进程的时候赋予当前进程虚拟时间是1000500。但是，唤醒此进程加入的就绪队列却是cpu1上CFS就绪队列，cpu1上的cfs就绪队列的最小虚拟时间min_vruntime的值是如果是9000000，那么该进程在cpu1上运行肯定是“乐坏”了，疯狂的运行啊。现在的处理计算得到的调度实体的虚拟时间是1000500 - 1000000 + 9000000 = 9000500，因此事情就不是那么的糟糕。

下面就对update_curr()一探究竟。

static void update_curr(struct cfs_rq *cfs_rq)
{
	struct sched_entity *curr = cfs_rq->curr;
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;

	if (unlikely(!curr))
		return;

	delta_exec = now - curr->exec_start;                    /* 1 */
	if (unlikely((s64)delta_exec <= 0))
		return;

	curr->exec_start = now;
	curr->sum_exec_runtime += delta_exec;
	curr->vruntime += calc_delta_fair(delta_exec, curr);    /* 2 */
	update_min_vruntime(cfs_rq);                            /* 3 */
}

1. delta_exec计算本次更新虚拟时间距离上次更新虚拟时间的差值。
2. 更新当前调度实体虚拟时间，calc_delta_fair()函数根据上面说的虚拟时间的计算公式计算虚拟时间（也就是调用__calc_delta()函数）。
3. 更新CFS就绪队列的最小虚拟时间min_vruntime。min_vruntime也是不断更新的，主要就是跟踪就绪队列中所有调度实体的最小虚拟时间。如果min_vruntime一直不更新的话，由于min_vruntime太小，导致后面创建的新进程根据这个值来初始化新进程的虚拟时间，岂不是新创建的进程有可能再一次疯狂了。这一次可能就是cpu0创建，在cpu0上面疯狂。

我们就看看update_min_vruntime()是怎么更新min_vruntime的。

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);
	u64 vruntime = cfs_rq->min_vruntime;

	if (curr) {
		if (curr->on_rq)
			vruntime = curr->vruntime;
		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;
		else
			vruntime = min_vruntime(vruntime, se->vruntime);
	}

	/* ensure we never gain time by being placed backwards. */
	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}

我们继续place_entity()函数。

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
	u64 vruntime = cfs_rq->min_vruntime;

	/*
	 * The 'current' period is already promised to the current tasks,
	 * however the extra weight of the new task will slow them down a
	 * little, place the new task so that it fits in the slot that
	 * stays open at the end.
	 */
	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice(cfs_rq, se);               /* 1 */

	/* sleeps up to a single latency don't count. */
	if (!initial) {
		unsigned long thresh = sysctl_sched_latency;

		/*
		 * Halve their sleep time's effect, to allow
		 * for a gentler effect of sleepers:
		 */
		if (sched_feat(GENTLE_FAIR_SLEEPERS))
			thresh >>= 1;

		vruntime -= thresh;                                 /* 2 */
	}

	/* ensure we never gain time by being placed backwards. */
	se->vruntime = max_vruntime(se->vruntime, vruntime);    /* 3 */
}

1. 如果是创建进程调用该函数的话，参数initial参数是1。因此这里是处理创建的进程，针对刚创建的进程会进行一定的惩罚，将虚拟时间加上一个值就是惩罚，毕竟虚拟时间越小越容易被调度执行。惩罚的时间由sched_vslice()计算。
2. 这里主要是针对唤醒的进程，针对睡眠很久的的进程，我们总是期望它很快得到调度执行，毕竟人家睡了那么久。所以这里减去一定的虚拟时间作为补偿。
3. 我们保证调度实体的虚拟时间不能倒退。为何呢？可以想一下，如果一个进程刚睡眠1ms，然后醒来后你却要奖励3ms（虚拟时间减去3ms），然后他竟然赚了2ms。作为调度器，我们不做亏本生意。你睡眠100ms，奖励你3ms，那就是没问题的。

新创建的进程惩罚的时间是多少

有上面可知，惩罚的时间计算函数是sched_vslice()函数。

static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

calc_delta_fair()函数上面已经分析过，计算实际运行时间delta对应的虚拟时间。这里的delta是sched_slice()函数计算。

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 */

	for_each_sched_entity(se) {                                     /* 2 */
		struct load_weight *load;
		struct load_weight lw;

		cfs_rq = cfs_rq_of(se);
		load = &cfs_rq->load;                                       /* 3 */

		if (unlikely(!se->on_rq)) {
			lw = cfs_rq->load;

			update_load_add(&lw, se->load.weight);
			load = &lw;
		}
		slice = __calc_delta(slice, se->load.weight, load);         /* 4 */
	}
	return slice;
}

1. __sched_period()前面已经提到了，根据就绪队列调度实体个数计算调度周期。
2. 针对没有使能组调度的情况下，for_each_sched_entity(se)就是for (; se; se = NULL)，循环一次。
3. 得到就绪队列的权重，也就是就绪队列上所有调度实体权重之和。
4. __calc_delta()函数有两个功能，除了上面说的可以计算进程运行时间转换成虚拟时间以外，还有第二个功能：计算调度实体se的权重占整个就绪队列权重的比例，然后乘以调度周期时间即可得到当前调度实体应该运行的时间（参数weught传递调度实体se权重，参数lw传递就绪队列权重cfs_rq->load）。例如，就绪队列权重是3072，当前调度实体se权重是1024，调度周期是6ms，那么调度实体应该得到的时间是6*1024/3072=2ms。

新进程加入就绪队列

经过do_fork()的大部分初始化工作完成之后，我们就可以唤醒新进程准别运行。也就是将新进程加入就绪队列准备调度。唤醒新进程的流程如下图。

do_fork()--->_do_fork()--->wake_up_new_task()--->activate_task()--->enqueue_task()--->enqueue_task_fair()
                                   |
                                   +------------>check_preempt_curr()--->check_preempt_wakeup()

wake_up_new_task()负责唤醒新创建的进程。简化一下函数如下。

void wake_up_new_task(struct task_struct *p)
{
	struct rq_flags rf;
	struct rq *rq;

	p->state = TASK_RUNNING;
#ifdef CONFIG_SMP
	p->recent_used_cpu = task_cpu(p);
	__set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));   /* 1 */
#endif
	rq = __task_rq_lock(p, &rf);
	activate_task(rq, p, ENQUEUE_NOCLOCK);                                   /* 2 */
	p->on_rq = TASK_ON_RQ_QUEUED;
	check_preempt_curr(rq, p, WF_FORK);                                      /* 3 */
}

1. 通过调用select_task_rq()函数重新选择cpu，通过调用调度类中select_task_rq方法选择调度类中最空闲的cpu。
2. 将进程加入就绪队列，通过调用调度类中enqueue_task方法。
3. 既然新进程已经准备就绪，那么此时需要检查新进程是否满足抢占当前正在运行进程的条件，如果满足抢占条件需要设置TIF_NEED_RESCHED标志位。

CFS调度类对应的enqueue_task方法函数是enqueue_task_fair()，我们将部分和组调度相关的代码删除，简洁的代码看起来才赏心悦目。

static void
enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;

	for_each_sched_entity(se) {                       /* 1 */
		if (se->on_rq)                                /* 2 */
			break;
		cfs_rq = cfs_rq_of(se);
		enqueue_entity(cfs_rq, se, flags);            /* 3 */
	}

	if (!se)
		add_nr_running(rq, 1);

	hrtick_update(rq);
}

1. 组调度关闭的时候，这里就是循环一次，不用纠结。
2. on_rq成员代表调度实体是否已经在就绪队列中。值为1代表在就绪队列中，当然就不需要继续添加就绪队列了。
3. enqueue_entity，从名字就可以看得出来是将调度实体加入就绪队列，我们称之为入队（enqueue）。

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 we're the current task, we must renormalise before calling
	 * update_curr().
	 */
	if (renorm && curr)
		se->vruntime += cfs_rq->min_vruntime;

	update_curr(cfs_rq);                        /* 1 */

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

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

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

	if (!curr)
		__enqueue_entity(cfs_rq, se);           /* 5 */
	se->on_rq = 1;                              /* 6 */
}

1. update_curr()顺便更新当前运行调度实体的虚拟时间信息。
2. 还记得之前在task_fork_fair()函数最后减去的min_vruntime吗？现在是时候加回来了。
3. 更新就绪队列相关信息，例如就绪队列的权。
4. 针对唤醒的进程（flag有ENQUEUE_WAKEUP标识），我们是需要根据情况给予一定的补偿。之前也说了place_entity()函数的两种情况下的作用。当然这里针对新进程第一次加入就绪队列是不需要调用的。
5. __enqueue_entity()才是将se加入就绪队列维护的红黑树中，所有的se以vruntime为key。
6. 所有的操作完毕也意味着se已经加入就绪队列，置位on_rq成员。

account_entity_enqueue()函数到底更新了就绪队列哪些信息呢？

static void account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_add(&cfs_rq->load, se->load.weight);  /* 1 */
	if (!parent_entity(se))
		update_load_add(&rq_of(cfs_rq)->load, se->load.weight);    /* 2 */
#ifdef CONFIG_SMP
	if (entity_is_task(se)) {
		struct rq *rq = rq_of(cfs_rq);

		account_numa_enqueue(rq, task_of(se));
		list_add(&se->group_node, &rq->cfs_tasks);                 /* 3 */
	}
#endif
	cfs_rq->nr_running++;                                          /* 4 */
}

struct rq

vruntime溢出怎么办

虽然调度实体se的vruntime成员是u64类型，可以保存非常大的数。但是当达到2 ⁶⁴ ns后就溢出了。那么溢出会有问题吗？我们先看看__enqueue_entity()函数加入就绪队列的代码。

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
	struct rb_node *parent = NULL;
	struct sched_entity *entry;
	bool leftmost = true;

	/*
	 * Find the right place in the rbtree:
	 */
	while (*link) {
		parent = *link;
		entry = rb_entry(parent, struct sched_entity, run_node);
		/*
		 * We dont care about collisions. Nodes with
		 * the same key stay together.
		 */
		if (entity_before(se, entry)) {
			link = &parent->rb_left;
		} else {
			link = &parent->rb_right;
			leftmost = false;
		}
	}

	rb_link_node(&se->run_node, parent, link);
	rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);
}

我们通过便利红黑树查找符合插入节点的位置。利用entity_before()函数比较两个调度实体se的vruntime值大小，以确定搜索方向。

static inline int entity_before(struct sched_entity *a, struct sched_entity *b)
{
	return (s64)(a->vruntime - b->vruntime) < 0;
}

假设要插入a的vruntime是101，b的vruntime是100，那么entity_before()函数返回0。现在假设a的vruntime溢出了，vruntime是5（我们期望是2 ⁶⁴ + 5，但是很遗憾溢出结果是5），b的vruntime即将溢出，vruntime的值是2 ³² - 2。那么调度实体a的vruntime无论是5还是2 ⁶⁴ + 5，entity_before()函数都会返回0。因此计算结果保持了一致性，所以溢出是没有任何问题的。要看懂这里的代码，需要对负数在计算机中表示形式有所了解。

同样样的 C语言 技巧还应用在就绪队列min_vruntime成员，试想min_vruntime同样式u64类型也是存在溢出的时候。min_vruntime的溢出是否会有问题呢？其实也不会，我们继续看一下update_min_vruntime函数最后一条代码， cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime); max_vruntime()函数也利用了类似entity_before()函数的技巧。所以min_vruntime溢出也不会有问题。max_vruntime()依然可以返回正确的结果。

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

抢占当前进程条件

当唤醒一个新进程的时候，此时也是一个检测抢占的机会。因为唤醒的进程有可能具有更高的优先级或者更小的虚拟时间。紧接上节唤醒新进程后调用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;
			}
		}
	}
}

1. 唤醒的进程和当前的进程同属于一个调度类，直接调用调度类的check_preempt_curr方法检查抢占条件。毕竟调度器自己管理的进程，自己最清楚是否适合抢占当前进程。
2. 如果唤醒的进程和当前进程不属于一个调度类，就需要比较调度类的优先级。例如，当期进程是CFS调度类，唤醒的进程是RT调度类，自然实时进程是需要抢占当前进程的，因为优先级更高。

现在考虑唤醒的进程和当前的进程同属于一个CFS调度类的情况。自然调用的就是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 */
}

1. 检查唤醒的进程是否满足抢占当前进程的条件。
2. 如果可以抢占当前进程，设置TIF_NEED_RESCHED flag。

wakeup_preempt_entity()函数如下。

/*
 * Should 'se' preempt 'curr'.    
 */
static int wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
{
	s64 gran, vdiff = curr->vruntime - se->vruntime;

	if (vdiff <= 0)                    /* 1 */
		return -1;

	gran = wakeup_gran(se);
	if (vdiff > gran)                  /* 2 */
		return 1;

	return 0;
}

wakeup_preempt_entity()函数可以返回3种结果。se1、se2、se3及curr调度实体的虚拟时间如下图所示。如果curr虚拟时间比se小，返回-1；如果curr虚拟时间比se大，并且两者差值小于gran，返回0；否则返回1。默认情况下，wakeup_gran()函数返回的值是1ms根据调度实体se的权重计算的虚拟时间。因此，满足抢占的条件就是，唤醒的进程的虚拟时间首先要比正在运行进程的虚拟时间小，并且差值还要小于一定的值才行（这个值是sysctl_sched_wakeup_granularity，称作唤醒抢占粒度）。这样做的目的是避免抢占过于频繁，导致大量上下文切换影响系统性能。

se3             se2    curr         se1
------|---------------|------|-----------|--------> vruntime
          |<------gran------>|
                         

     wakeup_preempt_entity(curr, se1) = -1
     wakeup_preempt_entity(curr, se2) =  0
     wakeup_preempt_entity(curr, se3) =  1

周期性调度

周期性调度是指 Linux 定时周期性地检查当前任务是否耗尽当前进程的时间片，并检查是否应该抢占当前进程。一般会在定时器的中断函数中，通过一层层函数调用最终到scheduler_tick()函数。

void scheduler_tick(void)
{
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
	struct task_struct *curr = rq->curr;
	struct rq_flags rf;

	sched_clock_tick();
	rq_lock(rq, &rf);
	update_rq_clock(rq);
	curr->sched_class->task_tick(rq, curr, 0);        /* 1 */
	cpu_load_update_active(rq);
	calc_global_load_tick(rq);
	rq_unlock(rq, &rf);
	perf_event_task_tick();
#ifdef CONFIG_SMP
	rq->idle_balance = idle_cpu(cpu);
	trigger_load_balance(rq);                         /* 2 */
#endif
}

1. 调用调度类对应的task_tick方法，针对CFS调度类该函数是task_tick_fair。
2. 触发负载均衡，以后有时间可以详谈。

task_tick_fair()函数如下。

static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &curr->se;

	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
		entity_tick(cfs_rq, se, queued);
	}
}

for循环是针对组调度，组调度未打开的情况下，这里就是一层循环。

entity_tick()是主要干活的。

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
{
	/*
	 * Update run-time statistics of the 'current'.
	 */
	update_curr(cfs_rq);                      /* 1 */

	if (cfs_rq->nr_running > 1)
		check_preempt_tick(cfs_rq, curr);     /* 2 */
}

1. 调用update_curr()更新当前运行的调度实体的虚拟时间等信息。
2. 如果就绪队列就绪态的调度实体个数大于1需要检查是否满足抢占条件，如果可以抢占就设置TIF_NEED_RESCHED flag。

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));
}

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

针对以上每一次周期调度（scheduling tick ）流程可以总结如下。

1. 更新当前正在运行进程的虚拟时间。

2. 检查当前进程是否满足被抢占的条件。

   • if (delta_exec > ideal_runtime)，然后置位TIF_NEED_RESCHED。

3. 检查TIF_NEED_RESCHED flag。

   • 如果置位，从就绪队列中挑选最小虚拟时间的进程运行。
   • 将当前被强占的进程重新加入就绪队列红黑树上（enqueue task）。
   • 从就绪队列红黑树上删除即将运行进程的节点（dequeue task）。

如何选择下一个合适进程运行

当进程被设置TIF_NEED_RESCHED flag后会在某一时刻触发系统发生调度或者进程调用schedule()函数主动放弃cpu使用权，触发系统调度。我们就以schedule()函数为例分析。

asmlinkage __visible void __sched schedule(void)
{
	struct task_struct *tsk = current;

	sched_submit_work(tsk);
	do {
		preempt_disable();
		__schedule(false);
		sched_preempt_enable_no_resched();
	} while (need_resched());
}

主要干活的还是__schedule()函数。

static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	struct rq_flags rf;
	struct rq *rq;
	int cpu;

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

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

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

	if (likely(prev != next)) {
		rq->curr = next;
		rq = context_switch(rq, prev, next, &rf);    /* 4 */
	}

	balance_callback(rq);
}

1. 针对主动放弃cpu进入睡眠的进程，我们需要从对应的就绪队列上删除该进程。
2. 选择下个合适的进程开始运行，该函数前面已经分析过。
3. 清除TIF_NEED_RESCHED flag。
4. 上下文切换，从prev进程切换到next进程。

CFS调度类pick_next_task方法是pick_next_task_fair()函数。

static struct task_struct *
pick_next_task_fair(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;
	struct task_struct *p;
	int new_tasks;

again:
	if (!cfs_rq->nr_running)
		goto idle;

	put_prev_task(rq, prev);                        /* 1 */
	do {
		se = pick_next_entity(cfs_rq, NULL);        /* 2 */
		set_next_entity(cfs_rq, se);                /* 3 */
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);                               /* 4 */

	p = task_of(se);
#ifdef CONFIG_SMP
	list_move(&p->se.group_node, &rq->cfs_tasks);
#endif

	if (hrtick_enabled(rq))
		hrtick_start_fair(rq, p);

	return p;
idle:
	new_tasks = idle_balance(rq, rf);

	if (new_tasks < 0)
		return RETRY_TASK;

	if (new_tasks > 0)
		goto again;

	return NULL;
}

1. 主要是处理prev进程的后事，当进程让出cpu时就会调用该函数。
2. 选择最适合运行的调度实体。
3. 选择出来的调度实体se还需要继续加工一下才能投入运行，加工的活就是由set_next_entity()函数负责。
4. 针对没有使能组调度的情况下，循环一次就结束了。

put_prev_task()究竟处理了哪些后事呢？CFS调度类put_prev_task方法的函数是put_prev_task_fair()。

static void put_prev_task_fair(struct rq *rq, struct task_struct *prev)
{
	struct sched_entity *se = &prev->se;
	struct cfs_rq *cfs_rq;

	for_each_sched_entity(se) {           /* 1 */
		cfs_rq = cfs_rq_of(se);
		put_prev_entity(cfs_rq, se);      /* 2 */
	}
}

1. 针对组调度情况，暂不考虑。
2. put_prev_entity()是主要干活的部分。

put_prev_entity()函数如下。

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
	/*
	 * If still on the runqueue then deactivate_task()
	 * was not called and update_curr() has to be done:
	 */
	if (prev->on_rq)                            /* 1 */
		update_curr(cfs_rq);

	if (prev->on_rq) {
		/* Put 'current' back into the tree. */
		__enqueue_entity(cfs_rq, prev);         /* 2 */
		/* in !on_rq case, update occurred at dequeue */
		update_load_avg(cfs_rq, prev, 0);       /* 3 */
	}
	cfs_rq->curr = NULL;                        /* 4 */
}

1. 如果prev进程依然在就绪队列上，极有可能是prev进程被强占的情况。在让出cpu之前需要更新进程虚拟时间等信息。如果prev进程不在就绪队列上，这里可以直接跳过更新。因为，prev进程在deactivate_task()中已经调用了update_curr()，所以这里就可以省略了。
2. 如果prev进程依然在就绪队列上，我们需要重新将prev进程插入红黑树等待调度。
3. update_load_avg()是更新prev进程的负载信息，这些信息在负载均衡的时候会用到。
4. 后事已经处理完毕，就绪队列的curr指针也应该指向NULL，代表当前就绪队列上没有正在运行的进程。

prev进程的后事已经处理完毕，接下来继承大统的进程需要借助set_next_entity()函数昭告天下。

static void
set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	/* 'current' is not kept within the tree. */
	if (se->on_rq) {
		__dequeue_entity(cfs_rq, se);                   /* 1 */
		update_load_avg(cfs_rq, se, UPDATE_TG);         /* 2 */
	}
	cfs_rq->curr = se;                                  /* 3 */
    update_stats_curr_start(cfs_rq, se);                /* 4 */
	se->prev_sum_exec_runtime = se->sum_exec_runtime;   /* 5 */
}

1. __dequeue_entity()是将调度实体从红黑树中删除，针对即将运行的进程，我们都会从红黑树中删除当前进程。当进程被强占后，调用put_prev_entity()函数会重新插入红黑树。因此这个地方和put_prev_entity()函数中加入红黑树是个呼应。
2. 更新进程的负载信息。负载均衡会使用。
3. 更新就绪队列curr成员，昭告天下，“现在我是当前正在运行的进程”。
4. update_stats_curr_start()函数就一句话，更新调度实体exec_start成员，为update_curr()函数统计时间做准备。
5. check_preempt_tick()函数用到，统计当前进程已经运行的时间，以此判断是否能够被其他进程抢占。

进程的睡眠

在__schedule()函数中，如果prev进程主动睡眠。那么会调用deactivate_task()函数。deactivate_task()函数最终会调用调度类dequeue_task方法。CFS调度类对应的函数是dequeue_task_fair()，该函数是enqueue_task_fair()函数反操作。

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;
	int task_sleep = flags & DEQUEUE_SLEEP;

	for_each_sched_entity(se) {                 /* 1 */
		cfs_rq = cfs_rq_of(se);
		dequeue_entity(cfs_rq, se, flags);      /* 2 */
	}

	if (!se)
		sub_nr_running(rq, 1);
}

1. 针对组调度操作，没有使能组调度情况下，循环仅一次。
2. 将调度实体se从对应的就绪队列cfs_rq上删除。

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 */
}

1. 借机更新当前正在运行进程的虚拟时间信息，如果当前dequeue的进程就是当前正在运行的进程的话，那么此次update_curr()就很有必要了。
2. 针对当前正在运行的进程来说，其对应的调度实体已经不在红黑树上了，因此不用在调用__dequeue_entity()函数从红黑树上参数对用的节点。
3. 调度实体已经从就绪队列的红黑树上删除，因此更新on_rq成员。
4. 更新就绪队列相关信息，例如权重信息。稍后介绍。
5. 如果进程不是睡眠（例如从一个CPU迁移到另一个CPU），进程最小虚拟时间需要减去当前就绪队列对应的最小虚拟时间，原因之前也说了。迁移之后会在enqueue的时候加上对应的CFS就绪队列最小拟时间。

account_entity_dequeue()和前面说的account_entity_enqueue()操作相反。account_entity_dequeue()函数如下。

static void account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_sub(&cfs_rq->load, se->load.weight);      /* 1 */
	if (!parent_entity(se))
		update_load_sub(&rq_of(cfs_rq)->load, se->load.weight);
#ifdef CONFIG_SMP
	if (entity_is_task(se)) {
		account_numa_dequeue(rq_of(cfs_rq), task_of(se));
		list_del_init(&se->group_node);                   /* 2 */
	}
#endif
	cfs_rq->nr_running--;                                 /* 3 */
}

1. 从就绪队列权重总和中减去当前dequeue调度实体的权重。
2. 从链表中删除调度实体se。
3. 就绪队列中可运行调度实体计数减1。

标签:CFS