Linux内核之进程管理与调度(二)

x86-32位Linux2.6.24x86-32 Linux2.6.24

---

概念

在多道程序设计系统中，系统中可以同时运行多个程序，至少在用户看起来是这样的。但是实际上，系统上真正并行执行的进程数量最多等于系统的处理器数量(也就是我们常说的核心数量)，之所以在用户感知是大量程序并发执行，是因为操作系统负责把多个进程在处理器上轮流执行，又因为处理器的执行速度和我们人类感知速度不在一个量级上，这才给我们造成了一种多个程序并发执行的错觉。

task_struct

1. 使用具体的调度策略选择合适的进程使用CPU
2. 进行进程间的上下文切换

内核必须提供一种方法，在各个进程之间尽可能公平的共享CPU时间，而同时又要考虑不同任务的优先级。完成这样一种目的，有许多方法，各有利弊，这里不做争论，本文只对Linux2.6.24版本的调度策略进行介绍。

schedule()kernel/sched.c

1. 在所处理器系统上(SMP)，必须要注意几个细节，以避免调度器自相干扰
2. 不仅实现了优先调度，还实现了Posix标准需要的其他两种软实时策略
3. 使用goto语句以生成最优的汇编代码(对结构化程序设计的所有原理背道而驰，但是性能赞)

本节后面的介绍中将暂时忽略实时进程，只考虑完全公平调度器(在介绍源码实现时会对实时调度进行介绍)，2.6.24版本的Linux调度器一个杰出特性就是：它不需要时间片的概念，至少不需要传统的时间片。如果你对Linux2.6.11的O(1)调度器有所了解的话，相信你会非常喜爱2.6.24版本的调度器实现，相比于2.6.11各种启发式规则以及各种时间片概念计算，2.6.24将会显得非常清晰易懂，等后面我介绍完源码后，相信你一定会深有体会。传统的调度器对系统中的进程分别计算时间片，使进程运行直至时间片用尽，所有进程的时间片都已经用尽时了，则需要重新计算(为了简单描述，实际上对O(1)调度器做了非常非常大的简化，简化到甚至严格上来说是错误的，不过不用纠结，这不是本文的重点，本文重点是为了突出介绍CFS)。相比之下，当前版本的调度器只考虑进程的等待时间，即进程在就绪队列中已经等待了多长时间，对CPU时间需求最严格的进程被调度执行。

对于严格的CFS来说，应该是保证系统中的每个进程都被公平的对待(CFS的理论概念这里就不赘述了，不影响我们理解Linux的实现，一点儿也不)，但是由于一些现实因素的影响，Linux没有采用这种思想：

1. 进程的不同优先级必须得到考虑，更加重要的进程必须比相对次要的进程获得更多的CPU时间
2. 进程不能切换得太频繁，因为上下文切换(从一个进程切换到另一个进程)，是有一定开销的。在切换太频繁时，过多时间花费在进程切换过程中，而不是用于实际工作。
3. 两次相邻的任务切换间，时间也不能太长，否则会积累较大的不公平(其他进程等待太久)，对于多媒体系统来说，进程运行时间太长会导致延迟增大

另外，如果编译Linux内核时激活了调度器统计，那么会在运行时生成/proc/sched_debug，其中包含了调度器当前状态所有方面的信息。

调度时机

在Linux内核实现中，通常会在什么时候选择执行进程调度呢，换句话说，Linux的调度时机有哪些呢？主要有以下几种：

中断异常系统调用

内核实现

task_struct

1. 使用具体的调度策略选择合适的进程使用CPU
2. 进行进程间的上下文切换

数据结构

调度器使用一系列数据结构，来排序和管理系统中的进程。调度器的工作方式与这些结构的设计密切相关。几个组件在许多方面彼此交互。如图所示： 可以看到，图中清晰的描述了各个组件之间的交互：

1. 无论是主调度器还是周期性调度器，都通过具体的调度器类来选择合适的进程
2. 调度器选择进程后，需要执行进程间切换，此时需要借助CPU帮助
3. 周期性调度器被时钟中断触发执行(实际上时钟中断会触发CPU执行特定的中断处理程序，因此还是和CPU交互)
4. 系统中的进程同一时刻只能属于一个调度器类

在后面的介绍中，除非特别说明，否则我将核心调度器和周期性调度器统称为通用调度器。正如上面说的，每个进程都刚好属于某个调度器类，各个调度器类负责管理所属的进程，而通用调度器自身完全不涉及进程管理，其工作完全委托给调度器类。如果你学习过一门面向对象语言，那么可以这么理解：所有的调度器类可以理解为实现了特定接口的实现类，而通用调度器只需要调用接口方法实现特定的工作，而实际上不需要知道具体是什么调度器类；另外，不同调度器类之间也不需要相互交互。

task_struct中调度相关字段

task_struct

struct task_struct {
    int prio, static_prio, normal_prio;
    unsigned int rt_priority;
    struct list_head run_list;
    constb struct sched_class *sched_class;
    struct sched_entity se;
    unsigned int policy;
    cpumask_t cpus_allowed;
    unsigned int time_slice;
}

优先级

前面就有提到过，并非系统上所有的进程都同样重要(氪金玩家当然更重要.-.)。不那么紧急的进程不需要太多的关注，而重要的工作应该尽可能快速完成。为了确定特定进程的重要性，Linux给进程增加了相对优先级属性。Linux采用了3个成员来表示进程的优先级。

静态优先级(static_prio)nicesched_setscheduler普通优先级(normal_prio)动态优先级(prio)

实时优先级

rt_priority值越大，优先级越低

调度类

sched_class

调度实体

Linux该版本开始，调度器不限于调度进程，还可以调度更大的实体。这样的特点可以方便实现组调度：可用的CPU时间可以首先在一般的进程组(比如所有进程可以简单的按照用户分组)之间分配，然后把进程组分配到的时间再在进程之间分配。

sched_entity

调度策略

policy

SCHED_NORMALSCHED_BATCHSCHED_IDLESCHED_BATCH冷处理SCHED_IDLESCHED_IDLEIDLESCHED_RRSCHED_FIFOSCHED_RRSCHED_FIFO

CPU控制位

cpu_allows

循环调度器相关

run_listtime_slicerun_listtime_slice

辅助函数/标志

辅助标志

TIF_NEED_RESCHED

辅助函数

rt_policy()

static inline int rt_policy(int policy)
{
    // 如果是实时策略，返回true
	if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))
		return 1;
	return 0;
}

task_has_rt_policy

static inline int task_has_rt_policy(struct task_struct *p)
{
	return rt_policy(p->policy);
}

rt_prio

MAX_RT_PRIO = 100

static inline int rt_prio(int prio)
{
	if (unlikely(prio < MAX_RT_PRIO))
		return 1;
	return 0;
}

真正的辅助函数远不止这些，但是没关系，后面用到具体的函数之前，我会先介绍函数的作用，必要时会附带源码介绍。

调度器类

调度器类提供了通用调度器和各个调度器方法之间的关联。调度器类由特定数据结构中汇集的几个函数指针表示。通用调度器请求的各个操作都可以由一个指针表示，这种面向对象的设计使得通用调度器无需了解各个调度器类的内部实现(就像前面说的那样)。

我们暂时不考虑针对多处理器的扩展，调度器类结构如下所示

struct sched_class {
	const struct sched_class *next;

	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
	void (*yield_task) (struct rq *rq);

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

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

#ifdef CONFIG_SMP // 针对多处理器系统的增强功能，其实主要是多处理器间的负载均衡
	unsigned long (*load_balance) (struct rq *this_rq, int this_cpu,
			struct rq *busiest, unsigned long max_load_move,
			struct sched_domain *sd, enum cpu_idle_type idle,
			int *all_pinned, int *this_best_prio);

	int (*move_one_task) (struct rq *this_rq, int this_cpu,
			      struct rq *busiest, struct sched_domain *sd,
			      enum cpu_idle_type idle);
#endif

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

sched_classsched_class.next

上面这句话可能不太好理解，下面通过源码和一张图来帮助理解调度器类之间的关系

#define sched_class_highest (&rt_sched_class)

const struct sched_class rt_sched_class = {
	.next			= &fair_sched_class, // 可以看到rt调度器类后面就是cfs
	.enqueue_task		= enqueue_task_rt,
	.dequeue_task		= dequeue_task_rt,
	.yield_task		= yield_task_rt,

	.check_preempt_curr	= check_preempt_curr_rt,

	.pick_next_task		= pick_next_task_rt,
	.put_prev_task		= put_prev_task_rt,

#ifdef CONFIG_SMP
	.load_balance		= load_balance_rt,
	.move_one_task		= move_one_task_rt,
#endif

	.set_curr_task          = set_curr_task_rt,
	.task_tick		= task_tick_rt,
};

static const struct sched_class fair_sched_class = {
	.next			= &idle_sched_class, // 可以看到cfs调度器后面就是idle
	.enqueue_task		= enqueue_task_fair,
	.dequeue_task		= dequeue_task_fair,
	.yield_task		= yield_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
	.load_balance		= load_balance_fair,
	.move_one_task		= move_one_task_fair,
#endif

	.set_curr_task          = set_curr_task_fair,
	.task_tick		= task_tick_fair,
	.task_new		= task_new_fair,
};

static 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,

	.check_preempt_curr	= check_preempt_wakeup,

	.pick_next_task		= pick_next_task_fair,
	.put_prev_task		= put_prev_task_fair,

#ifdef CONFIG_SMP
	.load_balance		= load_balance_fair,
	.move_one_task		= move_one_task_fair,
#endif

	.set_curr_task          = set_curr_task_fair,
	.task_tick		= task_tick_fair,
	.task_new		= task_new_fair,
};

调度器之间的关系如图所示 然后schedule()函数在选择下一个占用CPU的进程时，会按照这个顺序搜寻，因此最先查看实时调度器类队列中有没有可运行进程，然后才是cfs调度器，最后才是idle调度器。

enqueue_taskdequeue_taskyield_tasksched_yieldyield_taskcheck_preempt_currwake_up_new_taskpick_next_taskput_prev_taskset_curr_tasktask_ticknew_task

以上各个函数后面会一一介绍其源码。

就绪队列

就绪队列

就绪队列是通用调度器许多操作的起点，但是要注意的是：进程并不是由就绪队列成员直接管理的，进程管理是各个调度器类的职责，因此在各个就绪队列中嵌入了特定于调度器类的子就绪队列。CPU就绪队列数据结构如下所示：

struct rq {
    ...
	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	unsigned long nr_running;
	#define CPU_LOAD_IDX_MAX 5
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
	/* capture load from *all* tasks on this cpu: */
	struct load_weight load;


	struct cfs_rq cfs;
	struct rt_rq rt;

	struct task_struct *curr, *idle;

	u64 clock, prev_clock_raw;
    ....
};

需要说明的是，为了简单起见，上面的rq结构省略了很多统计相关的字段和其它若干字段。

nr_runningloadcpu_loadcfsrtcurrtask_structidletask_structclockprev_clock_rawupdata_rq_clock

runqueues

static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

辅助函数

内核定义了一些就绪队列相关的宏

// 找到指定cpu对应的rq
#define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))
// 找到当前cpu对应的rq
#define this_rq()		(&__get_cpu_var(runqueues))
// 找到指定进程所在的rq
#define task_rq(p)		cpu_rq(task_cpu(p))
// 找到指定cpu上正在运行的进程
#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)

调度实体

前面说过，当前版本的Linux能够调度实体，而进程也是通过内嵌调度实体的方式才能被调度器调度，下面就看一下调度实体数据结构定义：

struct sched_entity {
    ...
	struct load_weight	load;		/* for load-balancing */
	struct rb_node		run_node;
	unsigned int		on_rq;

	u64			exec_start;
	u64			sum_exec_runtime;
	u64			vruntime;
	u64			prev_sum_exec_runtime;
    ....
};

loadrun_nodeon_rqtime相关updata_currexec_startexec_startsum_exec_runtimevruntimeprev_sum_exec_runtimesum_exec_runtimeprev_sum_exec_runtimesum_exec_runtime-prev_sum_exec_runtime

优先级处理

从用户的角度来看，优先级非常简单，只是某个范围内的数字而已。但实际上，内核对优先级的处理远不止这么简单，相反，处理优先级还是比较复杂的。

优先级内核表示

nice

// 普通进程最小优先级数值
#define MAX_USER_RT_PRIO	100
// 实时进程的最大优先级数值
#define MAX_RT_PRIO		MAX_USER_RT_PRIO
// 普通进程的最大优先级数值
#define MAX_PRIO		(MAX_RT_PRIO + 40)
// 普通进程默认优先级为120
#define DEFAULT_PRIO		(MAX_RT_PRIO + 20)

// 将nice值转换为对应的优先级
#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)
// 将prio值转换为nice值
#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)
// 获取指定进程的nice值
#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio)

计算优先级

Linux有三种优先级，分别是静态优先级、普通优先级、动态优先级，那么他们是如何计算的呢？static_prio是计算的起点，另外两种优先级都可以通过该优先级计算出来：

// 该函数同时修改了normal_prio和prio
p->prio = effective_prio(p);

static int effective_prio(struct task_struct *p)
{
    // 计算normal_prio
	p->normal_prio = normal_prio(p);
	/*
	 * If we are RT tasks or we were boosted to RT priority,
	 * keep the priority unchanged. Otherwise, update priority
	 * to the normal priority:
	 */
    // 如果该进程p的动态优先级
    // 数值上属于普通，那么返回normal_prio
    // 再结合外面的赋值操作，可以知道此时prio=normal_prio
	if (!rt_prio(p->prio))
		return p->normal_prio;
    // 如果进程的动态优先级 <= 100
    // 即属于实时进程，则prio不变
	return p->prio;
}


static inline int normal_prio(struct task_struct *p)
{
	int prio;
    
    // 如果进程的调度策略为实时调度策略
    // 则普通优先级为100 - 1 - 实时优先级
	if (task_has_rt_policy(p))
		prio = MAX_RT_PRIO-1 - p->rt_priority;
	else
        // 否则普通优先级 = static_prio
		prio = __normal_prio(p);
	return prio;
}

static inline int __normal_prio(struct task_struct *p)
{
	return p->static_prio;
}

efficative_prio

进程分支出子进程时，子进程的静态优先级和普通优先级继承自父进程，子进程的动态优先级设置为父进程的普通优先级，这是为了防止父进程临时提高的实时优先级泄露给子进程。

优先级作用

Linux为什么要设置三种优先级呢？三种优先级又各有什么作用呢？下面就来详细说一下，首先需要认识到一点，我们所说的实时优先级数值和非实时优先级数值(即0-99和100-139)，统统指的是prio，也就是动态优先级。因此下面如果不做特别说明，那么优先级指的就是动态优先级。

静态优先级动态优先级普通优先级实时优先级

MAX_RT_PRIO-1 - p->rt_prioritysched_setscheduler

计算权重负荷

前面说了，普通进程依赖静态优先级计算权重，权重对于CFS调度器来说非常重要，而对于实时进程来说，虽然也会计算权重，但是实际上实时调度器在调度实时进程时根本不会用到。因此下面介绍的权重负荷，实际上是针对CFS调度器调度的非实时进程。

task_struct.se.loadload_weight

struct load_weight {
	unsigned long weight, inv_weight;
};

weightinv_weight1/weightinv_weight

Linux是这样设计的：进程每降低一个nice值，则多获得10%的CPU时间，相反的每升高一个nice值，则放弃10%的时间。为了实现这样的设计策略，内核将优先级转换为权重值，转换表如下：

static const int 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,
};

/*
 * Inverse (2^32/x) values of the prio_to_weight[] array, precalculated.
 *
 * In cases where the weight does not change often, we can use the
 * precalculated inverse to speed up arithmetics by turning divisions
 * into multiplications:
 */
static const u32 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,
};

1.25

set_load_weight

static void set_load_weight(struct task_struct *p)
{
    // 如果是实时策略，那么由实时调度器调度，
    // 那么其权重是最高优先级(100)
    // 的普通进程权重的2倍
	if (task_has_rt_policy(p)) {
		p->se.load.weight = prio_to_weight[0] * 2;
		p->se.load.inv_weight = prio_to_wmult[0] >> 1;
		return;
	}

	/*
	 * SCHED_IDLE tasks get minimal weight:
	 */
    // 如果是CFS调度器调度的进程，但是IDLE策略
    // 则将其权重设置的非常低，为2
	if (p->policy == SCHED_IDLE) {
		p->se.load.weight = WEIGHT_IDLEPRIO;
		p->se.load.inv_weight = WMULT_IDLEPRIO;
		return;
	}
    
    // 对于调度器调度的除了IDLE的CFS的进程，根据静态优先级正常设置权重
	p->se.load.weight = prio_to_weight[p->static_prio - MAX_RT_PRIO];
	p->se.load.inv_weight = prio_to_wmult[p->static_prio - MAX_RT_PRIO];
}

#define WEIGHT_IDLEPRIO		2
#define WMULT_IDLEPRIO		(1 << 31)

inc_nr_running

static void inc_nr_running(struct task_struct *p, struct rq *rq)
{
	rq->nr_running++;
	inc_load(rq, p);
}

static inline void inc_load(struct rq *rq, const struct task_struct *p)
{
	update_load_add(&rq->load, p->se.load.weight);
}

static inline void update_load_add(struct load_weight *lw, unsigned long inc)
{
	lw->weight += inc;
}

通用调度器

调度器的实现基于两个函数：周期性调度器和主调度器。这些函数根据进程的优先级分配CPU时间。下面将分别对周期性调度器和主调度器进行介绍

周期性调度器

scheduler_tick

1. 管理内核中与整个系统和各个进程的调度相关的统计量，主要是对各种计数器加1
2. 激活负责当前进程的调度器类的周期性调度方法

void scheduler_tick(void)
{
    // 获取当前cpu的就绪队列
	int cpu = smp_processor_id();
	struct rq *rq = cpu_rq(cpu);
    // 获取当前就绪队列上正在运行的进程
	struct task_struct *curr = rq->curr;
	u64 next_tick = rq->tick_timestamp + TICK_NSEC;

	spin_lock(&rq->lock);
    // 主要工作就是更新当前队列的clock
	__update_rq_clock(rq);
	/*
	 * Let rq->clock advance by at least TICK_NSEC:
	 */
    // 这里可以理解为时钟偶尔出错时的一种保护工作
	if (unlikely(rq->clock < next_tick))
		rq->clock = next_tick;
	rq->tick_timestamp = rq->clock;
    // 更新cpu负载，其实就是利用就绪队列的负荷做一些计算，感兴趣
    // 可以自己看一下
	update_cpu_load(rq);
    // 如果当前进程不是idle，那么调用指定调度器类的周期性方法
	if (curr != rq->idle) /* FIXME: needed? */
		curr->sched_class->task_tick(rq, curr);
	spin_unlock(&rq->lock);

#ifdef CONFIG_SMP
    // 多处理器下的负载均衡
	rq->idle_at_tick = idle_cpu(cpu);
	trigger_load_balance(rq, cpu);
#endif
}


static void __update_rq_clock(struct rq *rq)
{
	u64 prev_raw = rq->prev_clock_raw;
	u64 now = sched_clock();
	s64 delta = now - prev_raw;
	u64 clock = rq->clock;

#ifdef CONFIG_SCHED_DEBUG
	WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());
#endif
	/*
	 * Protect against sched_clock() occasionally going backwards:
	 */
    // 防止时钟向后跳，造成增长值为负数
	if (unlikely(delta < 0)) {
		clock++;
		rq->clock_warps++;
	} else {
		/*
		 * Catch too large forward jumps too:
		 */
        // 防止时钟跳的太多...
		if (unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)) {
			if (clock < rq->tick_timestamp + TICK_NSEC)
				clock = rq->tick_timestamp + TICK_NSEC;
			else
				clock++;
			rq->clock_overflows++;
		} else {
			if (unlikely(delta > rq->clock_max_delta))
				rq->clock_max_delta = delta;
			clock += delta;
		}
	}
    // 可以看到上面做了很多的预防工作，实际上就是把队列的时钟增加
	rq->prev_clock_raw = now;
	rq->clock = clock;
}

可以看到周期性调度器在时钟中断的触发下周期性执行，每次执行都会更新当前cpu就绪队列的时钟，当前cpu负载，然后调用当前进程所属的调度器类的周期性调度方法，(另外多说一句，多处理器下每个处理器都有自己的周期性时钟)。对于调度器类的周期性方法这里暂时不讨论，在后面的章节会着重介绍。

主调度器

schedule()TIF_NEED_RESCHED

asmlinkage void __sched schedule(void)
{
	struct task_struct *prev, *next;
	long *switch_count;
	struct rq *rq;
	int cpu;

need_resched:
    // 禁止内核抢占
	preempt_disable();
    // 获取当前处理器及对应就绪队列
	cpu = smp_processor_id();
	rq = cpu_rq(cpu);
    // 中心无关忽略之
	rcu_qsctr_inc(cpu);
    // 获取当前运行进程
	prev = rq->curr;
	switch_count = &prev->nivcsw;
    // 释放当前进程的大内核锁(如果有的话)
	release_kernel_lock(prev);
need_resched_nonpreemptible:
    // debug信息，忽略之
	schedule_debug(prev);

	/*
	 * Do the rq-clock update outside the rq lock:
	 */
    // 关闭本地中断
	local_irq_disable();
    // 更新一下子当前就绪队列的时钟
	__update_rq_clock(rq);
    // 获取当前队列的自旋锁
	spin_lock(&rq->lock);
    // 清除当前进程的`TIF_NEED_RESCHED`标志
	clear_tsk_need_resched(prev);
    
    // 如果当前进程不处于运行状态并且不属于内核态抢占
    // 这里主要作用是防止将非RUNNING状态的进程从就绪队列中移除
    // 可以参考下http://linuxperf.com/?p=38 讲的非常棒
    // 如果设置了PREEMPT\_ACTIVE，说明该进程是由于内核抢占而被调离CPU的，
    // 这时不把它从Run Queue里移除；如果PREEMPT\_ACTIVE没被设置
    //（进程不是由于内核抢占而被调离），还要看一下它有没有未处理的信号，
    // 如果有的话，也不把它从Run Queue移除。  总之，只要不是主动呼叫schedule()，
    // 而是因被抢占而调离CPU的，进程就还在运行队列中，还有机会运行。
	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        // 如果当前进程处于可中断睡眠状态并且有挂起的信号，那么修改
        // 当前进程状态为RUNNING
		if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
				unlikely(signal_pending(prev)))) {
			prev->state = TASK_RUNNING;
		} else {
            // 否则说明当前进程要么处于其他不可运行状态
            // 要么没有挂起的信号，则将当前进程从就绪队列中移除
			deactivate_task(rq, prev, 1);
		}
		switch_count = &prev->nvcsw;
	}
    
    // 负载均衡
	if (unlikely(!rq->nr_running))
		idle_balance(cpu, rq);
    
    // 调用指定调度器类的函数
	prev->sched_class->put_prev_task(rq, prev);
    // 一会儿介绍
	next = pick_next_task(rq, prev);

	sched_info_switch(prev, next);
    
    // 如果选出来的下一个进程和当前进程不是同一个进程
    // 那么说明即将执行进程切换
	if (likely(prev != next)) {
        // 更新统计信息
		rq->nr_switches++;
        // 重新设置就绪队列的运行进程
		rq->curr = next;
        // 增加进程切换次数
		++*switch_count;
        
        // 执行进程切换
		context_switch(rq, prev, next); /* unlocks the rq */
	} else
		spin_unlock_irq(&rq->lock);
    
    // 如果新进程在执行schedule前持有大内核锁，那么这里重新尝试获取
    // 如果获取失败则重新调度。因为进程上一次被切换出去时，如果占有了
    // 大内核锁，那么schedule会暂时释放掉，因此这里会重新获取
	if (unlikely(reacquire_kernel_lock(current) < 0)) {
		cpu = smp_processor_id();
		rq = cpu_rq(cpu);
		goto need_resched_nonpreemptible;
	}
    // 开中断，但是不再执行尝试调度逻辑
	preempt_enable_no_resched();
    // 如果新的进程又被设置了TIF_NEED_RESCHED标志，那么
    // 重新选择进程
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
		goto need_resched;
}

可以看到，当前进程如果是因为被抢占而导致失去CPU，那么不会把当前进程从就绪队列中移除，而如果是主动让的CPU，说明此时进程正在某等待队列上等待指定条件，那么会将当前进程从就绪队列中删除

put_prev_taskpick_next_taskcontext_switch

on_rq==1on_rq=1on_rq

1. 该进程正在调度器队列中
2. 该进程不在调度器队列中，但是正在使用CPU

on_rq=1on_rq=1

pick_next_taskcontext_switchpick_next_task

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev)
{
	const struct sched_class *class;
	struct task_struct *p;

	/*
	 * Optimization: we know that if all tasks are in
	 * the fair class we can call that function directly:
	 */
    // 一个小优化，如果当前就绪队列活动进程数量等于cfs
    // 调度器队列的活动进程数量，那么可以直接调用cfs调度器
    // 相关函数寻找下一个进程
	if (likely(rq->nr_running == rq->cfs.nr_running)) {
        // 调用cfs调度器队列的pick_next_task方法寻找合适进程
		p = fair_sched_class.pick_next_task(rq);
        // 如果找到则直接返回
		if (likely(p))
			return p;
	}
    
	class = sched_class_highest;
    // 遍历rt，cfs调度器队列，寻找合适进程
	for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		/*
		 * Will never be NULL as the idle class always
		 * returns a non-NULL p:
		 */
		class = class->next;
	}
}

sched_class_highestpick_next_tasksched_class_highestrt_sched>cfs>idle

context_switch

static inline void
context_switch(struct rq *rq, struct task_struct *prev,
	       struct task_struct *next)
{
    // 需要注意的是，schedule()函数的开头就禁止了抢占
    // 禁止了本地中断，并且获取了就绪队列的自旋锁
	struct mm_struct *mm, *oldmm;
    
    // 释放schedule()函数中获取的就绪队列自旋锁
    // 并且根据编译内核时的配置决定是否允许本地中断
	prepare_task_switch(rq, prev, next);
	mm = next->mm;
	oldmm = prev->active_mm;
	/*
	 * For paravirt, this is coupled with an exit in switch_to to
	 * combine the page table reload and the switch backend into
	 * one hypercall.
	 */
    // 进入懒惰cpu模式
	arch_enter_lazy_cpu_mode();
    // 如果即将占用cpu的进程mm为空
    // 说明该进程是内核线程，那么需要借用切换出去进程的
    // mm结构，并且增加引用计数，进入懒惰tlb模式
	if (unlikely(!mm)) {
		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);
		enter_lazy_tlb(oldmm, next);
	} else
        // 否则说明新运行进程是正常进程，这里
        // 包含一些硬件相关操作，其中就包括
        // 重新加载cr3寄存器，切换页表
		switch_mm(oldmm, mm, next);
    
    // 如果被切换出去的进程是内核线程
    // 那么清理内核线程临时占用的mm
    // 并且设置就绪队列的prev_mm
	if (unlikely(!prev->mm)) {
		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}
	/*
	 * Since the runqueue lock will be released by the next
	 * task (which is an invalid locking op but in the case
	 * of the scheduler it's an obvious special-case), so we
	 * do an early lockdep release here:
	 */
#ifndef __ARCH_WANT_UNLOCKED_CTXSW
	spin_release(&rq->lock.dep_map, 1, _THIS_IP_);
#endif

	/* Here we just switch the register state and the stack. */
    // 执行硬件切换
	switch_to(prev, next, prev);

    // 屏障
	barrier();
	/*
	 * this_rq must be evaluated again because prev may have moved
	 * CPUs since it called schedule(), thus the 'rq' on its stack
	 * frame will be invalid.
	 */
    // 这里已经属于切换后，因此执行这里逻辑的永远都是
    // 新切换进来的进程，对应prepare_task_switch，做一些收尾工作
	finish_task_switch(this_rq(), prev);
}

switch_tofinish_task_switchswitch_to

#define switch_to(prev,next,last) do {					\
	unsigned long esi,edi;						\
	asm volatile("pushfl\n\t"		/* Save flags */	\
		     "pushl %%ebp\n\t"					\ // 将eflags和ebp压到prev内核栈
		     "movl %%esp,%0\n\t"	/* save ESP */		\ // 将esp保存到prev->thread.esp
		     "movl %5,%%esp\n\t"	/* restore ESP */	\ // 将next->thread.esp加载到esp
                                                        \ //这两步实际上就是进行内核栈切换
		     "movl $1f,%1\n\t"		/* save EIP */		\ // 将标号1初地址保存到prev->thread.eip中
                                                        \ // 这样的话prev重新被调度执行时就会从1开始执行
		     "pushl %6\n\t"		/* restore EIP */	\    // 加载next进程的eip，这两步实际上是切换ip
		     "jmp __switch_to\n"				\        // 调用__switch_to函数
		     "1:\t"						\                // 从__switch_to返回的实际上已经是next了
		     "popl %%ebp\n\t"					\        // 此时next有两种情况，如果是之前被调度过，那么此时
		     "popfl"						\            // next的ip一定指向标号1，因此从1开始执行最后返回
		     :"=m" (prev->thread.esp),"=m" (prev->thread.eip),	\ // 如果next是新进程，那么根据fork代码可以
		      "=a" (last),"=S" (esi),"=D" (edi)			\   // 得知，此时next的ip指向ret_from_fork，因此next
		     :"m" (next->thread.esp),"m" (next->thread.eip),	\ // 此时会跳转执行ret_from_fork函数
		      "2" (prev), "d" (next));				\
} while (0)
    
// 参数为switch_to中的ax中的prev和dx中的next    
struct task_struct fastcall * __switch_to(struct task_struct *prev_p, struct task_struct *next_p)
{
	struct thread_struct *prev = &prev_p->thread,
				 *next = &next_p->thread;
    // 获取当前cpu
	int cpu = smp_processor_id();
    // 获取当前cpu的tss段
	struct tss_struct *tss = &per_cpu(init_tss, cpu);

	/* never put a printk in __switch_to... printk() calls wake_up*() indirectly */
   // 进入懒惰fpu模式，前面介绍过(具体是本文的前面还是上一篇文章忘了)
    // 主要的做法就是，假设A为prev进程，B为next进程
    // 那么如果A使用了fpu寄存器，这里将fpu等寄存器内容保存A的thread_info中
    // 但是并不会加载B的fpu信息，二是设置cr0寄存器的TS标志
    // 只有等B使用fpu相关寄存器时时，如果TS置位那么会产生一个异常
    // 这时候内核捕捉到这个异常，才会记载B的fpu
	__unlazy_fpu(prev_p);


	/* we're going to use this soon, after a few expensive things */
    // fpu相关的东西，不想深究
	if (next_p->fpu_counter > 5)
		prefetch(&next->i387.fxsave);

	/*
	 * Reload esp0.
	 */
    // 加载next的esp0寄存器，在进程创建时候有说过
    // 这里的esp0可以简单理解为进程内核栈基地址
    // (实际上有细微偏差，指向内核基地址靠下一点点，不过这里理解就行)
    // 这里实际上就是把next进程的内核堆栈加载到tss中
    // 这样当执行系统调用/中断异常时，cpu就能通过tss获取到
    // 进程内核栈的位置
	load_esp0(tss, next);

	/*
	 * Save away %gs. No need to save %fs, as it was saved on the
	 * stack on entry.  No need to save %es and %ds, as those are
	 * always kernel segments while inside the kernel.  Doing this
	 * before setting the new TLS descriptors avoids the situation
	 * where we temporarily have non-reloadable segments in %fs
	 * and %gs.  This could be an issue if the NMI handler ever
	 * used %fs or %gs (it does not today), or if the kernel is
	 * running inside of a hypervisor layer.
	 */
    // 上面英文翻译:保存掉%gs。不需要保存%fs，因为它在进入时被保存在堆栈中。 
    // 不需要保存%es和%ds，因为这些都是在内核内的内核段。 在设置新的TLS描述符之前这样做，
    // 可以避免我们在%fs和%gs中暂时有不可重载的段的情况。 
    // 如果NMI处理程序曾经使用%fs或%gs（现在没有），或者如果内核在管理程序层内运行，这可能是一个问题。
    
    // Linux x86如何使用gs和fs: https://zhuanlan.zhihu.com/p/435518616
    // 需要注意这篇文章里说的是x86-64，实际上x86-32下内核使用fs记录per_cpu变量
    
    // 保存prev的gs寄存器
	savesegment(gs, prev->gs);

	/*
	 * Load the per-thread Thread-Local Storage descriptor.
	 */
    // 加载新进程的tls
	load_TLS(next, cpu);

	/*
	 * Restore IOPL if needed.  In normal use, the flags restore
	 * in the switch assembly will handle this.  But if the kernel
	 * is running virtualized at a non-zero CPL, the popf will
	 * not restore flags, so it must be done in a separate step.
	 */
    // iopl相关的，暂时懒得看
	if (get_kernel_rpl() && unlikely(prev->iopl != next->iopl))
		set_iopl_mask(next->iopl);

	/*
	 * Now maybe handle debug registers and/or IO bitmaps
	 */
    // debug啥的东西，懒得看
	if (unlikely(task_thread_info(prev_p)->flags & _TIF_WORK_CTXSW_PREV ||
		     task_thread_info(next_p)->flags & _TIF_WORK_CTXSW_NEXT))
		__switch_to_xtra(prev_p, next_p, tss);

	/*
	 * Leave lazy mode, flushing any hypercalls made here.
	 * This must be done before restoring TLS segments so
	 * the GDT and LDT are properly updated, and must be
	 * done before math_state_restore, so the TS bit is up
	 * to date.
	 */
    // 
    // 和之前的进入懒惰cpu模式对应。hmm，只知道
    // 懒惰tlb和懒惰fpu，至于懒惰cpu，不太清楚..
	arch_leave_lazy_cpu_mode();

	/* If the task has used fpu the last 5 timeslices, just do a full
	 * restore of the math state immediately to avoid the trap; the
	 * chances of needing FPU soon are obviously high now
	 */
    // fpu，懒得深究
	if (next_p->fpu_counter > 5)
		math_state_restore();

	/*
	 * Restore %gs if needed (which is common)
	 */
    // 如果需要的话，加载新进程的gs寄存器
	if (prev->gs | next->gs)
		loadsegment(gs, next->gs);
    
    // 将next写入每cpu变量中，后面通过current宏获取当前cpu
    // 的当前进程，就是这里的功劳
    // 传统的current红灯是根据内核sp获取到thread_info，然后根据
    // thread_info获取到task_struct
    // 不过x86平台上做了优化，通过没cpu变量实现
    // 每次进程切换时都会将当前运行的进程写入到当前cpu的每cpu
    // 变量中，通过current宏获取时也是从每cpu变量中获取
	x86_write_percpu(current_task, next_p);
    
	return prev_p;
}

至于switch_to涉及到所谓的"三个"进程的问题，网上很多说明，其实也不难理解，这里就不说了(懒得再打字了..)

context_switchfinish_task_switch

static void finish_task_switch(struct rq *rq, struct task_struct *prev)
	__releases(rq->lock)
{
	struct mm_struct *mm = rq->prev_mm;
	long prev_state;
   
	rq->prev_mm = NULL;

	/*
	 * A task struct has one reference for the use as "current".
	 * If a task dies, then it sets TASK_DEAD in tsk->state and calls
	 * schedule one last time. The schedule call will never return, and
	 * the scheduled task must drop that reference.
	 * The test for TASK_DEAD must occur while the runqueue locks are
	 * still held, otherwise prev could be scheduled on another cpu, die
	 * there before we look at prev->state, and then the reference would
	 * be dropped twice.
	 *		Manfred Spraul <manfred@colorfullife.com>
	 */
    // 如果被切换出去的进程状态为`DEAD`，则由新进程负责
    // 释放一次旧进程的结构
	prev_state = prev->state;
	finish_arch_switch(prev);
    // 如果prepare_task_switch中没有开中断
    // 那么这里打开中断，否则这里什么都不做
	finish_lock_switch(rq, prev);
	fire_sched_in_preempt_notifiers(current);
	if (mm)
		mmdrop(mm);
	if (unlikely(prev_state == TASK_DEAD)) {
		/*
		 * Remove function-return probe instances associated with this
		 * task and put them back on the free list.
		 */
		kprobe_flush_task(prev);
		put_task_struct(prev);
	}
}

CFS调度器

通过前面的介绍可以看到，主调度器和周期性调度器主要调用进程所属的调度器类的相关方法。

数据结构

首先，我们需要介绍一下CFS就绪队列，我们回顾一下CPU就绪队列的内容，可以发现CPU就绪队列中嵌入了调度器队列

struct rq {
    ...
	/*
	 * nr_running and cpu_load should be in the same cacheline because
	 * remote CPUs use both these fields when doing load calculation.
	 */
	unsigned long nr_running;
	#define CPU_LOAD_IDX_MAX 5
	unsigned long cpu_load[CPU_LOAD_IDX_MAX];
	/* capture load from *all* tasks on this cpu: */
	struct load_weight load;


	struct cfs_rq cfs; // cfs调度器队列
	struct rt_rq rt;   // rt调度器队列

	struct task_struct *curr, *idle;

	u64 clock, prev_clock_raw;
    ....
};

CFS虚拟时钟

update_curr

static void update_curr(struct cfs_rq *cfs_rq)
{
    // 获取就绪队列正在运行的进程
	struct sched_entity *curr = cfs_rq->curr;
    // 获取就绪队列当前时钟
	u64 now = rq_of(cfs_rq)->clock;
	unsigned long delta_exec;
    
    // 如果就绪队列中没有进程正在使用cpu，那么直接返回
	if (unlikely(!curr))
		return;

	/*
	 * Get the amount of time the current task was running
	 * since the last time we changed load (this cannot
	 * overflow on 32 bits):
	 */
    // 计算两次更新的时间差
	delta_exec = (unsigned long)(now - curr->exec_start);
    
    // 主要逻辑
	__update_curr(cfs_rq, curr, delta_exec);
    // 更新exec_start，下次计算时使用
	curr->exec_start = now;
    
    // 如果当前的调度实体是进程，那么做一些cpu统计信息
	if (entity_is_task(curr)) {
		struct task_struct *curtask = task_of(curr);

		cpuacct_charge(curtask, delta_exec);
	}
}

update_curr__update_curr

static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
	      unsigned long delta_exec)
{
	unsigned long delta_exec_weighted;
	u64 vruntime;
    // 调度器统计信息，忽略
	schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));
    // 增加当前进程执行的物理时间总和
	curr->sum_exec_runtime += delta_exec;
    // 调度器统计信息，忽略
	schedstat_add(cfs_rq, exec_clock, delta_exec);
    // 这里就是主要的步骤，根据进程运行的物理时间和进程权重信息
    // 计算进程运行的虚拟时间，一会儿单独介绍
	delta_exec_weighted = delta_exec;
	if (unlikely(curr->load.weight != NICE_0_LOAD)) {
		delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
							&curr->load);
	}
    // 更新进程的虚拟时间
	curr->vruntime += delta_exec_weighted;

	/*
	 * maintain cfs_rq->min_vruntime to be a monotonic increasing
	 * value tracking the leftmost vruntime in the tree.
	 */
    // 如果当前cfs队列不为空
	if (first_fair(cfs_rq)) {
        // 取当前进程的虚拟时间和cfs队列中虚拟时间最小的进程
        // 两者中小的那一个
		vruntime = min_vruntime(curr->vruntime,
				__pick_next_entity(cfs_rq)->vruntime);
	} else
		vruntime = curr->vruntime;
    
    // 更新cfs队列的最小虚拟时间，注意这里使用max来保证
    // 最小虚拟时间一定是单调递增的
	cfs_rq->min_vruntime =
		max_vruntime(cfs_rq->min_vruntime, vruntime);
}

可以看到物理时间到进程虚拟时间的转换主要是以下代码段实现的：

delta_exec_weighted = delta_exec;
if (unlikely(curr->load.weight != NICE_0_LOAD)) {
	delta_exec_weighted = calc_delta_fair(delta_exec_weighted,
						&curr->load);
} 

calc_delta_fair()

delta_exec_weighted = delta_exec * NICE_0_LOAD / curr->load.weight

NICE_0_LOAD = 1024， 就是nice值为0进程的权重，本文的前面有介绍

nice值越低，则虚拟时间增长越慢

但实际上却并非如此，我们可以看到，两个权重不同的进程，它们运行相同的时间，权重大(nice值小)的进程虚拟时间增长的更慢，因此在红黑树中向右移动的速度就慢(随着进程的运行，虚拟时间增大，在红黑树中的位置会逐渐向右移)，因此被cfs调度器选中执行的次数就多一下，这样一来，进程实际占用cpu的时间(物理时间)就多一些。通过这种方式，权重大的进程占用的cpu物理时间更多，实现了我们希望的：重要的进程能够更多的使用cpu。

延迟跟踪

调度延迟

sysctl_sched_latencysysctl_sched_min_granularitysched_nr_latencysched_nr_latencysysctl_sched_latency

sysctl_sched_latencysysctl_sched_min_granularitysched_nr_latencysched_periodsysctl_sched_latency

static u64 __sched_period(unsigned long nr_running)
{
	u64 period = sysctl_sched_latency;
	unsigned long nr_latency = sched_nr_latency;
    
    
	if (unlikely(nr_running > nr_latency)) {
		period *= nr_running;
		do_div(period, nr_latency);
	}

	return period;
}

sysctl_sched_latencysysctl_sched_latencynr_runningsched_nr_latency

sched_slice

static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    // 根据就绪队列的活动进程数计算延迟周期
	u64 slice = __sched_period(cfs_rq->nr_running);
    // 根据当前进程的权重和就绪队列的权重，计算当前进程应该分配到的虚拟时间
	slice *= se->load.weight;
	do_div(slice, cfs_rq->load.weight);

	return slice;
}

上面函数等价于该公式：

time = cfs_queue_time * curr_weight / cfs_queue_weight

前面说过，就绪队列的权重是就绪队列所有活动进程权重的累加。内核获取进程调度周期内应该分配的物理时间主要目的是防止进程运行时间过长，周期性调度器每次执行时都会计算当前进程占用cpu的实际物理时间delta，如果该delta超过了进程被分配的物理时间，那么就执行抢占。

上面介绍了如何获取就绪队列中的进程应该分配到的物理时间，内核有时也需要知道该物理时间等价的虚拟时间

static u64 __sched_vslice(unsigned long rq_weight, unsigned long nr_running)
{
    // 计算就绪队列的延迟周期(调度周期)
	u64 vslice = __sched_period(nr_running);
    
    // 计算该进程应该被分配到的虚拟时间
	vslice *= NICE_0_LOAD;
	do_div(vslice, rq_weight);

	return vslice;
}

可以看到计算公式如下:

vtime = cfs_queue_time * NICE_0_LOAD / cfs_queue_weight

前面说到过，物理时间到虚拟时间的转换公式为

vtime = time * NICE_0_LOAD / weight

然后对比上面两个获取time和vtime的公式可以看到，这两个公式结合化简后就上物理时间到虚拟时间的公式

队列操作

enqueue_task_fairdequeue_task_fair

入队操作

static void enqueue_task_fair(struct rq *rq, struct task_struct *p, int wakeup)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;
    // 可能是组调度，但是这里可以忽略，简单的认为
    // se只有一个，只循环一次，调度进程
	for_each_sched_entity(se) {
        // 如果on_rq为1，那么说明已经被就绪队列管理
        // 前面说过，此时可能在队列中，也可能不在
        // 但无论如何是属于队列管理的，因此这里不做任何操作
		if (se->on_rq)
			break;
        // 获取调度实体所属的cfs就绪队列
		cfs_rq = cfs_rq_of(se);
        // 调用该函数， wakeup表示进程是否最近才被唤醒
        // 并转为运行状态，此时wake_up = 1
        // 如果此前就是可运行进程，那么wakeup = 0
		enqueue_entity(cfs_rq, se, wakeup);
		wakeup = 1;
	}
}

enqueue_entity

static void
enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int wakeup)
{
	/*
	 * Update run-time statistics of the 'current'.
	 */
    // 更新调度器队列最小运行虚拟时间和一些统计信息
    // 以及当前进行虚拟运行时间，前面说过
	update_curr(cfs_rq);
    
    // 如果进程是最近才被唤醒而加入到就绪队列中
    // 那么需要一些额外操作，一会儿说
	if (wakeup) {
		place_entity(cfs_rq, se, 0);
		enqueue_sleeper(cfs_rq, se);
	}
    // 统计信息，忽略
	update_stats_enqueue(cfs_rq, se);
	check_spread(cfs_rq, se);
    // 如果进程正在运行，那么不加入到就绪队列中
    // 前面说过，正在运行的进程on_rq=1，但是
    // 实际上并不在队列上
	if (se != cfs_rq->curr)
		__enqueue_entity(cfs_rq, se);
    // 修改进程on_rq，增加就绪队列活动进程数量以及更新权重
	account_entity_enqueue(cfs_rq, se);
}

static void
account_entity_enqueue(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	update_load_add(&cfs_rq->load, se->load.weight);
	cfs_rq->nr_running++;
	se->on_rq = 1;
}

如果进程刚被唤醒然后加入到就绪队列，那么此时进程可能睡眠了很久，即它的虚拟时间已经很久没有增加了，可能落后就绪队列的最小虚拟时间很多，积累了很大的不公平值，如果我们不加处理，直接添加到就绪队列上，那么该进程在接下来可能会长久的占用cpu，导致其他进程饥饿(因为它的虚拟时间落后就绪队列最小虚拟时间很多，因此执行若干次后，可能仍然位于红黑树最左边)，因此需要额外的处理

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

	vruntime = cfs_rq->min_vruntime;
    
    // 如果设置了TREE_AVG调度器特性(实际上这只是特性的后缀名，忽略细节)
    // 并且就绪队列红黑树中存在最右边节点
    // 那么计算红黑树中最大虚拟时间和最小虚拟时间的平均值
	if (sched_feat(TREE_AVG)) {
		struct sched_entity *last = __pick_last_entity(cfs_rq);
		if (last) {
			vruntime += last->vruntime;
			vruntime >>= 1;
		}// 否则如果设置了APPROX_AVG标志，那么计算
	} else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running)
        // sched_vslice(cfs_rq)/2计算当前就绪队列虚拟时间一半
        // 添加到vruntime上
		vruntime += sched_vslice(cfs_rq)/2;
    
    // 需要注意的是，上面对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.
	 */
    // initial表示当前进程是否是刚刚创建的
    // 进程创建需要时间，这段时间可以理解为是子进程
    // 向父进程借的时间，因此如果START_DEBIT如果被设置，
    // 那么需要适当增大子进程的虚拟时间
	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice_add(cfs_rq, se);

    // 如果initial没有置位，说明当前进程是刚被唤醒而加入
    // 就绪队列的进程
	if (!initial) {
		/* sleeps upto a single latency don't count. */
        // 这里考虑到进程睡眠了一段时间，因此做一些奖励措施
		if (sched_feat(NEW_FAIR_SLEEPERS) && entity_is_task(se))
			vruntime -= sysctl_sched_latency;

		/* ensure we never gain time by being placed backwards. */
        // 比较进程当前虚拟时间和上面计算的时间，去最大值
        // 避免这样一种情况：进程睡眠了1ms，但是通过上面的计算
        // 进程反而vruntime减少了3ms，因此进程实际上赚了
        // 通过睡眠获得了更多的运行时间，这是不允许的，因此
        // 保证了进程无论睡眠多久，奖励后的vruntime都不可能
        // 比原来的vruntime更小
		vruntime = max_vruntime(se->vruntime, vruntime);
	}
    
    // 设置进程的vruntime
	se->vruntime = vruntime;
}

该函数实际上对进程的虚拟时间进行调整

1. 对于刚创建的进程，如果没有开启任何调度器特性，那么新进程的虚拟时间就是队列的最小时间，因此新进程会尽快的得到调度，如果设置了一些调度器特性，那么会根据这些特性对新进程的虚拟时间进行调整(一般是增大)，这样可以防止父进程通过创建新进程来不断获取CPU时间(这里计算出来的新进程的虚拟时间可能会大于父进程的虚拟时间，这样的话按照之前的说法，那新进程就不能够保证在父进程之前执行，因此实际上如果设置了标志要求子进程必须先执行，那么内核会通过交换父子进程的虚拟时间来保证子进程一定先于父进程，后面会说到)
2. 对于刚唤醒的进程，它可能睡眠了很久，也可能只是睡眠了一会儿，那么我们需要对睡眠进程进行奖励，该奖励措施要符合这样的原则：对于睡眠很久的进程，不能够奖励太多，否则将会导致队列中的其他进程饥饿；对于短时间睡眠的进程，奖励的时间不能比它睡眠的时间还要长，防止进程通过短睡眠获取更多的CPU时间。

对于CFS调度器的入队操作，就介绍完了，这里总结一下整体流程(只针对调度实体为进程)

on_rq=1enqueue_entitynr_running++cfs_rq.load.weight增大进程on_rq置1

出队操作

dequeue_task_fair

static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int sleep)
{
	struct cfs_rq *cfs_rq;
	struct sched_entity *se = &p->se;
    // 和前面一样，我们忽略这样一个for循环
    // 假设只循环一次
	for_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);
        // 核心逻辑
		dequeue_entity(cfs_rq, se, sleep);
		/* Don't dequeue parent if it has other entities besides us */
		if (cfs_rq->load.weight)
			break;
		sleep = 1;
	}
}

static void
dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int sleep)
{
	/*
	 * Update run-time statistics of the 'current'.
	 */
    // 更新cfs队列最小虚拟时间，更新统计信息
    // 更新该队列正在运行进程的虚拟运行时间
	update_curr(cfs_rq);
  
	update_stats_dequeue(cfs_rq, se);
    // 统计信息，忽略
	if (sleep) {
#ifdef CONFIG_SCHEDSTATS
		if (entity_is_task(se)) {
			struct task_struct *tsk = task_of(se);

			if (tsk->state & TASK_INTERRUPTIBLE)
				se->sleep_start = rq_of(cfs_rq)->clock;
			if (tsk->state & TASK_UNINTERRUPTIBLE)
				se->block_start = rq_of(cfs_rq)->clock;
		}
#endif
	}
    
    // 如果该进程不是队列正在运行进程，那么从队列(红黑树)中
    // 移除
	if (se != cfs_rq->curr)
		__dequeue_entity(cfs_rq, se);
    // 和入队操作相反：nr_running--, cfs_rq.load.weight减少
    // 进程的on_eq置0
	account_entity_dequeue(cfs_rq, se);
}

可以看到出队操作完全和入队操作相反，逻辑也不复杂。

放回和选择

放回正在运行进程

pick_next_taskput_prev_task

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) {
		cfs_rq = cfs_rq_of(se);
        // 核心逻辑
		put_prev_entity(cfs_rq, se);
	}
}


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:
	 */
    // 对进程来说调度实体都on_rq=1
    // 因此和前面一样，更新调度器最小虚拟时间
    // 调度器统计信息，进程虚拟运行时间
	if (prev->on_rq)
		update_curr(cfs_rq);
    // 忽略
	check_spread(cfs_rq, prev);
	if (prev->on_rq) {
        // hmm又是统计信息，不看
		update_stats_wait_start(cfs_rq, prev);
		/* Put 'current' back into the tree. */
        // 把进程放到红黑树上
		__enqueue_entity(cfs_rq, prev);
	}
    
    // 一般调用该函数发生在进程切换时，把正在占用cpu的就列当前进程
    // 放回队列中，然后选择下一个进程
    // 因此对于进程来说，这里curr指向的就是将要放回队列的实体
	cfs_rq->curr = NULL;
}

put_prev_taskupdate_curr

选择下一个进程

pick_next_task_fair

static struct task_struct *pick_next_task_fair(struct rq *rq)
{
	struct cfs_rq *cfs_rq = &rq->cfs;
	struct sched_entity *se;
    // 如果没有合适进程，直接返回
	if (unlikely(!cfs_rq->nr_running))
		return NULL;

	do {
        // 核心逻辑
		se = pick_next_entity(cfs_rq);
        // 组调度相关的，不用理会
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);

	return task_of(se);
}

static struct sched_entity *pick_next_entity(struct cfs_rq *cfs_rq)
{
	struct sched_entity *se = NULL;
    // 如果就绪队列存在最左节点，即不为空
	if (first_fair(cfs_rq)) {
        // 从队列中拿出最左节点，此时并没有
        // 把进程从树中删除
		se = __pick_next_entity(cfs_rq);
        // 核心逻辑
		set_next_entity(cfs_rq, se);
	}

	return se;
}


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) {
		/*
		 * Any task has to be enqueued before it get to execute on
		 * a CPU. So account for the time it spent waiting on the
		 * runqueue.
		 */
		update_stats_wait_end(cfs_rq, se);
        // 这里把将要运行的进程出队，因此可以看到
        // cfs队列curr指向的进程是正在占用cpu执行的进程
        // 是不在红黑树中的
		__dequeue_entity(cfs_rq, se);
	}
    // 统计信息
	update_stats_curr_start(cfs_rq, se);
    // 和前面的put_prev_task_fair对应，重新设置curr
	cfs_rq->curr = se;
    // 统计信息，忽略
#ifdef CONFIG_SCHEDSTATS
	/*
	 * Track our maximum slice length, if the CPU's load is at
	 * least twice that of our own weight (i.e. dont track it
	 * when there are only lesser-weight tasks around):
	 */
	if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
		se->slice_max = max(se->slice_max,
			se->sum_exec_runtime - se->prev_sum_exec_runtime);
	}
#endif
    // 前面说过的，周期性调度器计算这两个字段的差值，获取
    // 进程此次移动执行了多久(物理时间)，然后进程最大能够
    // 使用的CPU份额做比较，如果超出则执行抢占
    // 进程执行过程中通过update_curr不断记录总的物理时间
    // 然后在被选中时将其赋值给prev_sum_exec_runtime
	se->prev_sum_exec_runtime = se->sum_exec_runtime;
}

schedule

周期性调度器

scheduler_ticktask_ticktask_tick_fair

static void task_tick_fair(struct rq *rq, struct task_struct *curr)
{
	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);
	}
}

static void entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	/*
	 * Update run-time statistics of the 'current'.
	 */
    // 更新最小虚拟时间，统计信息，进程此次执行cpu时间和，进程虚拟时间
	update_curr(cfs_rq);
    
    // 如果cfs队列中有除了当前进程之外的其他活动进程
    // 或者没有设置抢占唤醒特性，调用check_preempt_tick
	if (cfs_rq->nr_running > 1 || !sched_feat(WAKEUP_PREEMPT))
		check_preempt_tick(cfs_rq, curr);
}

WAKEUP_PREEMPTcheck_preempt_wakeupWAKEUP_PREEMPT

sysctl_sched_min_wakeup_latency

gran = sysctl_sched_wakeup_granularity;
if (unlikely(se->load.weight != NICE_0_LOAD))
	gran = calc_delta_fair(gran, &se->load);

if (pse->vruntime + gran < se->vruntime)
	resched_task(curr);

check_preempt_tick

static void
check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	unsigned long ideal_runtime, delta_exec;
    // 计算当前进程应该占有的cpu物理时间份额
	ideal_runtime = sched_slice(cfs_rq, curr);
    // 计算进程占用cpu以来执行的物理时间
	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
    // 如果超过份额，则执行抢占
	if (delta_exec > ideal_runtime)
        // 主要是设置TIF_NEED_SCHED标志，然后在适当的时机执行调度
        // 在smp系统下可能会执行一些负载均衡
		resched_task(rq_of(cfs_rq)->curr);
}

update_currTIF_NEED_SCHED

唤醒抢占

try_to_wake_upwake_up_new_taskcheck_preempt_curr

static inline void check_preempt_curr(struct rq *rq, struct task_struct *p)
{
	rq->curr->sched_class->check_preempt_curr(rq, p);
}

check_preempt_currcheck_preempt_wakeup

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p)
{
	struct task_struct *curr = rq->curr;
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
	struct sched_entity *se = &curr->se, *pse = &p->se;
	unsigned long gran;
    
    // 如果新进程动态优先级数值上属于实时进程
    // 那么一定会抢占当前进程，此时只需要调用update_curr
    // 再做一次更新统计，然后设置当前进程的TIF_NEED_SCHED标志
    // 抢占当前进程
	if (unlikely(rt_prio(p->prio))) {
		update_rq_clock(rq);
		update_curr(cfs_rq);
		resched_task(curr);
		return;
	}
	/*
	 * Batch tasks do not preempt (their preemption is driven by
	 * the tick):
	 */
    // 如果被唤醒的进程调度策略为SCHED_BATCH
    // 那么不会执行抢占
	if (unlikely(p->policy == SCHED_BATCH))
		return;

    // 如果调度器没有开启唤醒抢占特性
    // 那么也不会执行抢占
	if (!sched_feat(WAKEUP_PREEMPT))
		return;
    // 忽略
	while (!is_same_group(se, pse)) {
		se = parent_entity(se);
		pse = parent_entity(pse);
	}
    
    // 这就是前面说的，避免抢占太过频繁
	gran = sysctl_sched_wakeup_granularity;
	if (unlikely(se->load.weight != NICE_0_LOAD))
		gran = calc_delta_fair(gran, &se->load);

	if (pse->vruntime + gran < se->vruntime)
        // 如果最终还是需要执行抢占，则设置当前进程的TIF_NEED_SCHED标志
		resched_task(curr);
}

do_forkdo_forkwake_up_new_taskcheck_preempt_wakeup

处理新进程

sched_classtask_new_fairdo_fork --> wake_up_new_task --> task_new --> task_new_fair

static void task_new_fair(struct rq *rq, struct task_struct *p)
{
	struct cfs_rq *cfs_rq = task_cfs_rq(p);
	struct sched_entity *se = &p->se, *curr = cfs_rq->curr;
	int this_cpu = smp_processor_id();

	sched_info_queued(p);
    // 万年不变，更新统计信息
	update_curr(cfs_rq);
    // 前面介绍过，调整新进程的虚拟时间
	place_entity(cfs_rq, se, 1);

	/* 'curr' will be NULL if the child belongs to a different group */
    // 如果设置了sysctl_sched_child_runs_first表明希望子进程能够先执行
    // 如果子进程和父进程将要运行在同一个cpu上但是子进程计算出来的
    // 虚拟时间大于父进程，那么这里需要交换虚拟时间来保证子进程先执行
	if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
			curr && curr->vruntime < se->vruntime) {
		/*
		 * Upon rescheduling, sched_class::put_prev_task() will place
		 * 'current' within the tree based on its new key value.
		 */
		swap(curr->vruntime, se->vruntime);
	}
    // 将子进程添加到cfs队列中，前面介绍过
    // 主要是添加到红黑树中，然后增加nr_running
    // load.weight以及进程的on_rq置1
	enqueue_task_fair(rq, p, 0);
    // 设置当前进程(一般是父进程)的TIF_NEED_SCHED标志
    // 表明执行抢占
	resched_task(rq->curr);
}

可以看到，cfs对新进程的处理逻辑也是比较清晰的。

wake_up_new_taskdo_forkforkcheck_preempt_wakeuptask_new_fair

void fastcall wake_up_new_task(struct task_struct *p, unsigned long clone_flags)
{
	unsigned long flags;
	struct rq *rq;

	rq = task_rq_lock(p, &flags);
	BUG_ON(p->state != TASK_RUNNING);
	update_rq_clock(rq);
    
    // 计算新进程p的动态优先级
	p->prio = effective_prio(p);
    
    // 如果新进程所属的调度器类实现了task_new并且父进程
    // 不属于调度器管理，由于新进程是拷贝自父进程
    // 那么此时新进程on_eq也为0，也不属于调度器管理，那么
    // 需要把新进程添加到调度器队列中
	if (!p->sched_class->task_new || !current->se.on_rq) {
        // 其实就是对入队操作的一个封装
        // 对于cfs来说，就是加入到队列中，更新调度器信息
        // 然后增加nr_running，load_weight,on_rq=1
		activate_task(rq, p, 0);
	} else {
		/*
		 * Let the scheduling class do new task startup
		 * management (if any):
		 */
        // 否则只需要调用task_new(对cfs来说就是task_new_fair)
		p->sched_class->task_new(rq, p);
        // 然后增加nr_running和load.weight
		inc_nr_running(p, rq);
	}
    // 检查是否进行抢占
	check_preempt_curr(rq, p);
	task_rq_unlock(rq, &flags);
}

到目前为止，除了smp系统下的相关处理，cfs调度器的所有功能都已经介绍完毕了。下面将从具体案例出发，说明调度器是如何工作的：

示例

新进程启动

do_forkdo_fork --> copy_process --> sched_forksched_forksched_fork

do_fork --> wake_up_new_taskupdate_curr

然后会调整新进程的初始虚拟时间，并且在必要时可能会和父进程交换虚拟时间保证子进程先于父进程执行，然后判断是否需要抢占当前进程，如果需要抢占则设置当前运行进程的TIF_NEED_SCHED。

睡眠进程唤醒

try_to_wake_upcheck_preemt_currcheck_preempt_currcheck_preemt_wakeup

周期性调度抢占

scheduler_ticktask_ticktask_tick_fairupdate_currcheck_preempt_tickTIF_NEED_SCHED

实时调度器

Linux目前版本的实时调度器有两种策略，一种是轮转时间，一种是先进先出。这两种策略实现比较简单，就不过多介绍了，感兴趣可以直接看源码。

SMP增强

到目前为止，和CFS调度器相关的功能都已经介绍完了，但实际上Linux做的更多，尤其是对于SMP系统。下面就来具体看一看：

多处理器负载均衡

多处理器上，内核需要考虑几个额外的问题，以确保良好的调度：

1. CPU负荷必须尽可能公平地在所有处理器上共享，如果某个处理器非常繁忙而另外的处理器非常空闲，这样肯定是不合理的
2. 进程与某些CPU的亲和性必须是可设置的。例如在4个CPU系统中，可以将计算密集型程序绑定到前3个CPU，而剩余的交互式进程则运行在第四个CPU上。
3. 内核必须能够讲进程从一个CPU迁移到另外一个。但是这不能随意使用，因为这会严重影响性能。例如缓存失效。而在大型系统上，CPU与迁移进程此前使用的物理内存距离可能有若干米，因此这样一来进程对内存的访问代价很高

task_structcpus_allowedsched_setaffinity

负载均衡简单的说就是：检查各个cpu之间的负载，如果发现某个cpu负载过高，则在处理器之间进行负载均衡，将高负载处理器上的进程向低负载处理器上迁移。

scheduler_tick

另外可能聪明的读者已经想到了，一个进程可能在不同的处理器上执行，那么如果不同处理器就绪队列的cfs调度器队列虚拟运行时间不同，那么进程可能会吃亏或者占便宜。举个例子：进程先在队列A上，队列A的最小虚拟时间为1000，此时进程的虚拟时间为1500，不久后进程被迁移到队列B上，而队列B的最小虚拟时间为1800，那么一旦进程被迁移到队列B，那么进程会立刻被执行，因为两个队列的最小虚拟时间不同，进程在两个队列红黑树上的位置也不同。

vruntime - 该队列的最小虚拟时间

有一篇文章挺不错的，贴一下：文章

内核抢占和低延迟相关

内核抢占

对于不支持内核抢占的内核，在系统调用后返回用户状态之前，或在内核中某些指定的点上，会调用调度器；而在除了这些情况之外，内核是无法抢占的。如果内核处于相对较长的操作中，比如文件系统和内存管理相关的任务，这样可能会带来一些问题。内核代表特定的进程执行相当长的时间，其他进程则无法运行。这样可能会导致系统延迟增加，给用户体验到差劲儿的响应。如果多媒体应用长时间无法得到CPU，可能会发生视频和音频漏失现象。

为了解决这种问题，Linux退出了内核抢占，如果在编译内核时启用对内核抢占的支持，那么高优先级的进程如果有事情需要完成，那么不仅用户应用程序可以被抢占，内核也可以被抢占。内核抢占是2.5版本添加的，尽管使内核可抢占所需要的改动非常少，但该机制不像抢占用户空间进程那样容易实现。如果内核无法一次性完成某些操作(例如对数据结构的操作)，那么可能会出现竞态条件而使系统不一致。

因此内核不能再任意点上被中断抢占。不过幸好，大多数不能中断的点已经被SMP实现标识出来了，并且在实现内核抢占时可以重用这些信息。内核的某些易于出现问题的部分每次只能由一个处理器访问，这些部分使用自旋锁保护：到达临界区的第一个处理器会获得锁，而其他想要访问的处理器会一直等待知道第一个处理器释放锁。

如果内核可以被抢占，即使单处理器系统也会像SMP系统。考虑正在临界区内部工作的内核被抢占的情况。下一个进程也在内核态工作，凑巧也要访问同一个临界区，这样就会出现问题。因此每次内核进入临界区时，都必须禁止内核抢占。

thread_info抢占计数器

struct thread_info {
    int preempt_count
}

preempt_count==0dec_preempt_countinc_preempt_countpreempt_countinc_preempt_countdec_preempt_countpreempt_count

除此之外，内核还提供了更多的函数用于抢占处理：

preempt_disable

inc_preempt_count

#define preempt_disable() \
do { \
	preempt_count_inc(); \
	barrier(); \
} while (0)

preempt_check_resched

会检测是否有必要进行调度，如果有必要则进行：

#define preempt_check_resched() \
do { \
    // 如果当前进程设置了TIF_NEED_SCHED标志，则执行内核抢占
	if (unlikely(test_thread_flag(TIF_NEED_RESCHED))) \
		preempt_schedule(); \
} while (0)


asmlinkage void __sched preempt_schedule(void)
{
	struct thread_info *ti = current_thread_info();
#ifdef CONFIG_PREEMPT_BKL
	struct task_struct *task = current;
	int saved_lock_depth;
#endif
	/*
	 * If there is a non-zero preempt_count or interrupts are disabled,
	 * we do not want to preempt the current task. Just return..
	 */
    // 如果抢占计数器不为0，或者中断被禁止，则不执行抢占直接返回
	if (likely(ti->preempt_count || irqs_disabled()))
		return;

	do {
        // 设置PREEMPT_ACTIVE，实际上PREEMPT_ACTIVE是
        // preempt_count计数器最高位
		add_preempt_count(PREEMPT_ACTIVE);

		/*
		 * We keep the big kernel semaphore locked, but we
		 * clear ->lock_depth so that schedule() doesnt
		 * auto-release the semaphore:
		 */
       // 大内核锁相关，忽略
#ifdef CONFIG_PREEMPT_BKL
		saved_lock_depth = task->lock_depth;
		task->lock_depth = -1;
#endif
        // 执行调度
		schedule();
#ifdef CONFIG_PREEMPT_BKL
		task->lock_depth = saved_lock_depth;
#endif
        // 复位PREEMPT_ACTIVE
		sub_preempt_count(PREEMPT_ACTIVE);

		// 内存屏障
		barrier();
        // 当该进程下次被恢复执行时又被设置了TIF_NEED_RESCHED标志
        // 则再次执行调度
	} while (unlikely(test_thread_flag(TIF_NEED_RESCHED)));
}

PREEMPT_ACTIVEschedule

preempt_enable

preempt_disablepreempt_count

#define preempt_enable() \
do { \
    // 递减抢占计数器
	preempt_enable_no_resched(); \
	barrier(); \
    // 检测是否需要执行调度，如需要则执行调度
	preempt_check_resched(); \
} while (0)

preempt_enable_no_resched

递减抢占计数器以允许内核抢占，但是不进行重新调度。

低延迟

schedule

cond_resched

int __sched cond_resched(void)
{
    // 如果当前进程的TIF_NEED_SCHED标志和抢占计数器
	if (need_resched() && !(preempt_count() & PREEMPT_ACTIVE)) {
		__cond_resched();
		return 1;
	}
	return 0;
}

static void __cond_resched(void)
{
    // 忽略
#ifdef CONFIG_DEBUG_SPINLOCK_SLEEP
	__might_sleep(__FILE__, __LINE__);
#endif
	/*
	 * The BKS might be reacquired before we have dropped
	 * PREEMPT_ACTIVE, which could trigger a second
	 * cond_resched() call.
	 */
	do {
        // 设置内核抢占标志
		add_preempt_count(PREEMPT_ACTIVE);
        // 执行调度
		schedule();
        // 复位内核抢占标志
		sub_preempt_count(PREEMPT_ACTIVE);
        // 进程重新执行时再次检查
	} while (need_resched());
}

cond_resched

for (;;) {
    // 读数据
    if (exit_condition)
        continue;
}

cond_resched

for (;;) {
    cond_resched();
    // 读数据
    if (exit_condition)
        continue;
}

内核代码已经仔细核查过，以找出长时间运行的函数，并在适当的地方插入该函数，这样即使内核没有开启内核抢占，也能够保证较高的响应速度。

小结

cond_resched