上一篇文章主要介绍了x86-32位平台下Linux2.6.24版本下进程的创建、执行、内核线程、退出几部分内容，本节主要介绍进程调度相关内容，主要包括：Linux2.6.24下调度器实现、内核抢占实现、进程切换细节、调度时机等。除非特别说明，本文源码均基于x86-32 Linux2.6.24，并且默认开启内核抢占；并且对于超出本节内容的部分：比如中断、异常等，不会进行深入介绍。

概念

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

在Linux内核中，内核跟踪了每个进程的描述符task_struct，并且通过若干结构与其他进程连接起来。调度器要做的事情就是：在程序之间共享CPU时间，创造并行执行的错觉。调度器功能主要有两个：

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

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

schedule()函数是Linux调度的起点，即进程调度的唯一入口，定义在kernel/sched.c中，是内核中最常见的代码之一。 Linux调度器的实现受到了一下若干因素的影响：

  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的调度时机有哪些呢？主要有以下几种：

  1. 进程状态转换时刻：进程终止、进程睡眠。例如：进程执行sleep或exit时，会显式调用schedule()
  2. 周期性调度器检查到当前进程运行时间超出限制(时钟中断出发)，后面会说到周期性调度器
  3. 设备驱动程序执行长而重复的工作时，每次循环都检查是否需要进行调度，如果需要则调用schedule()
  4. 从中断、异常、系统调用返回，检查进程标志(后面会介绍)来判断是否需要调度，如果需要则调用schedule()

内核实现

在Linux内核中，内核跟踪了每个进程的描述符task_struct，并且通过若干结构与其他进程连接起来。调度器要做的事情就是：在程序之间共享CPU时间，创造并行执行的错觉。调度器功能主要有两个：

  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)：进程启动时分配的优先级，可以使用nice和sched_setscheduler系统调用修改，否则在进程运行时保持不变。
  • 普通优先级(normal_prio)：基于进程静态优先级和调度策略计算出的优先级。因此如果普通进程和实时进程具有相同的静态优先级，它们的调度策略不同，所以计算而来的普通优先级也不同
  • 动态优先级(prio)：在某些情况下，内核需要暂时提高进程的优先级(内核同步的实时互斥量可能会提高动态优先级从而使得优先级较低的进程先运行，不是本文重点，忽略之)，因此需要新增一个优先级，也就是动态优先级来表示。由于此改变不是永久的，因此静态优先级和普通优先级不受影响。

实时优先级

rt_priority标识实时进程的优先级。该值不会代替先前讨论的那些值。最高实时优先级为0，最低实时优先级为99。值越大，优先级越低

调度类

sched_class表示进程所属的调度类，参考上面的图，可以发现每个进程属于且仅属于一个调度类

调度实体

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

要实现这样的目标，就要求调度器不直接操作进程，而是处理可调度实体。一个实体由sched_entity表示。最简单的情况下，调度器调度各个进程，由于调度器只能调度调度实体，因此Linux在task_struct中内嵌了sched_entity结构，使得task_struct也成为了一个调度实体

调度策略

policy保存了对该进程应用的调度策略，Linux目前支持5个可能的值

  • SCHED_NORMAL用于普通进程，我们后面也是主要讲述此类进程。它们通过完全公平调度器来处理。另外SCHED_BATCH和SCHED_IDLE也通过完全公平调度器来处理，不过可以用于次要的进程。
  • SCHED_BATCH用于非交互，CPU使用密集的批处理进程。调度决策对此类进程给予冷处理：他们绝不会抢占CFS调度器的另一个进程，因此绝不会干扰交互式进程。如果不使用nice降低进程的静态优先级，同时又不希望该进程影响系统的交互性，此时最适合使用该调度器类。
  • SCHED_IDLE进程重要性最低，因为其相对权重是最小的(后面介绍权重计算时会说)。SCHED_IDLE一般是IDLE进程，在系统中没有课可运行进程时，会调度IDLE进程运行
  • SCHED_RR和SCHED_FIFO用于实现软实时进程。其中SCHED_RR实现了一种循环方法，而SCHED_FIFO则使用先进先出机制。这两类策略不是由完全公平调度器类处理，而是有实时调度器类处理，后面也会介绍这些调度器实现。

CPU控制位

cpu_allows是一个位域，在多处理器上使用，用来限制进程可以在哪些CPU上执行

循环调度器相关

run_list和time_slice是循环实时调度器所需要的，CFS并不需要这两个字段。其中run_list是一个表头，用于维护包含各进程的一个运行表，而time_slice则指定进程可使用CPU的剩余时间段

辅助函数/标志

辅助标志

对于Linux调度器来说，有一个非常重要的标志就是TIF_NEED_RESCHED标志。如果对活动进程设置了该标志，那么调度器即知道CPU将从该进程回收并赋予新进程。

辅助函数

  • 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_class的一个实。并且调度器类之间的层次结构是平坦的：实时进程最重要，完全公平进程其次，而IDLE进程只有在CPU无事可做时才会被调度执行，sched_class.next字段将不同的调度器类按照顺序连接起来，因此在选择合适进程执行时，会先在实时进程的队列中寻找，如果实时进程队列中没有合适的进程，然后才会去CFS就绪队列中寻找，以此类推。

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

#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_task：向调度器队列提供一个新进程。在进程从睡眠状态变为可运行状态时，会发生该操作。
  • dequeue_task：将进程从调度器队列中移除。进程从可运行状态变成不可运行状态时，就会发生该操作。当然，内核有可能因为其他原因将进程从调度器队列中去除，例如：进程的优先级改变，从CFS进程变成了实时进程，那么就需要把进程从CFS调度器的队列中移除，并且添加到实时调度器队列中。另外需要注意的是，这里虽然说的是调度器队列，但是调度器不一定使用队列的方式来管理进程，比如CFS调度器就是用红黑树来管理进程；因此这里说的队列是一种抽象的说法。
  • yield_task：进程自愿放弃对处理器控制权时，可以使用sched_yield系统调用，此时内核将会调用进程所属调度器类的yield_task方法。
  • check_preempt_curr：用一个新唤醒的进程来抢占当前进程。例如do_fork中创建新进程后会调用wake_up_new_task唤醒新进程，该函数那不可能会调用此函数
  • pick_next_task用于选择下一个将要运行的进程，而put_prev_task则在用另外一个进程代替当前运行进程之前调用。
  • set_curr_task在进程调度策略发生变化时调用
  • task_tick在每次激活周期性调度器时，由周期性调度器调用
  • new_task用于建立fork系统调用和调度器之间的关联，每次新进程建立后会调用new_task通知调度器

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

就绪队列

通用调度器用于管理活动进程的主要数据结构之一就是就绪队列。注意要和上面说的调度器类队列区分开来，调度器类队列是每个调度器类各自管理的队列。而就绪队列则是属于CPU的，每个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;
	struct rt_rq rt;

	struct task_struct *curr, *idle;

	u64 clock, prev_clock_raw;
    ....
};

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

  • nr_running：记录了当前队列上可运行进程的数目，不考虑其优先级和调度类
  • load：提供了就绪队列当前负荷的度量。队列负荷本质上与队列上当前活动进程数目成正比。其中各个进程又有优先级的作为权重。每个就绪队列的虚拟时钟速度就是基于这些信息。后面会详细介绍
  • cpu_load：用于跟踪当前cpu负荷状态，多cpu间负载均衡会使用
  • cfs：嵌入的属于cfs调度器类的调度器队列
  • rt：嵌入的属于实时调度器类的调度器队列
  • curr：指向当前运行进程的task_struct实例
  • idle：指向idle进程的task_struct实例，在没有其他可运行进程时执行
  • clock和prev_clock_raw用于实现就绪队列自身的时钟。每次调用周期性调度器时，都会更新clock的值。另外内核还提供了标准函数updata_rq_clock，可在操作调度器队列的调度器中多处使用。

系统中所有就绪队列都在runqueues数组中，该数组每个元素分别对应于系统中的一个cpu。在单处理器系统中，由于只有一个cpu，因此数组只有一个元素。

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;
    ....
};
  • load：当前调度实体的权重，决定了调度器中各个实体占队列总负荷的比例。计算负荷权重是调度器的一项重任，因此CFS调度器所需要的虚拟时钟速度最终依赖于负荷，后面会详细介绍
  • run_node：树节点，使得调度实体可以以红黑树的方式进行组织
  • on_rq：表示该实体当前是否就在就绪队列上接受调度
  • time相关：进程运行时，我们需要记录消耗的CPU时间，以用于完全公平调度器。sum_exec_runtime即用于该目的。跟踪运行时间是由updata_curr不断积累完成的。每次调用时，会计算当前时间和exec_start之间的差值，同时更新exec_start为当前时间。差值责备添加到sum_exec_runtime中
  • vruntime：在进程执行期间虚拟时钟上流逝的时间数量由vruntime记载
  • prev_sum_exec_runtime：在进程被撤销CPU时，会将sum_exec_runtime保存到prev_sum_exec_runtime中。周期性调度器会根据sum_exec_runtime-prev_sum_exec_runtime差值来判断当前进程是否已经占用CPU过久，如果超过某个限制，则强制进行进程切换。

优先级处理

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

优先级内核表示

在用户空间可以通过nice调用设置进程的静态优先级，进程的nice值在[-2019]之间。nice值越低，表明优先级越高。内核使用一个简单的数值范围，从[0139]来表示内部优先级。优先级和数值关系相反，如图所示： Linux提供了一些宏用于在不同表示形式之间转换

// 普通进程最小优先级数值
#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，也就是动态优先级。因此下面如果不做特别说明，那么优先级指的就是动态优先级。

  1. 静态优先级：该优先级可以通过nice设置，主要用于CFS调度器调度的非实时进程，此类进程的权重就是通过静态优先级计算得出来的，而对于实时优先级进程，并没有用到静态优先级。
  2. 动态优先级：动态优先级表示进程当前是实时进程还是非实时进程(prio < 100则说明进程当前是实时进程，否则是非实时进程)，该类优先级只对实时进程有用，而对于非实时进程，它们被CFS调度器调度，他们具体的优先程度取决于他们的权重，也就是间接的取决于静态优先级
  3. 普通优先级：说到这里你可能会疑惑，前面两个静态优先级和动态优先级一个影响非实时进程，一个影响实时进程，那么为什么还需要普通优先级呢？如果仅是这样，确实是不需要普通优先级。但是问题在于，Linux有时候需要将非进程优先级短暂的提高到实时优先级，而这个提高并不是长久的，因此需要额外用一个普通优先级来表示。
  4. 实时优先级：实时优先级(rt_priority)，只会影响实时进程的普通优先级计算，从而进一步影响到动态优先级，非实时进程并不会用到这一优先级。

对于非实时优先级，它并不考虑实时优先级，它的另外三种优先级总是想等，即总是等于静态优先级。 而对于实时进程，它并不考虑静态优先级，它的普通优先级为MAX_RT_PRIO-1 - p->rt_priority，即受到rt_priority的影响；而动态优先级，在创建时继承自父进程的普通优先级，当然也可以通过sched_setscheduler设置。该函数会修改实时优先级。如果sched_setscheduler希望将进程修改为实时进程，那么在同时也会修改静态优先级和动态优先级，如果希望将进程修改为普通进程，那么会将进程除了实时优先级之外的三种优先级都设置为静态优先级，而刚刚也说了，普通进程不使用实时优先级(set_scheduler做的工作当然不止这些，但是只需要涉及到优先级部分就够了)。

计算权重负荷

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

需要注意的是，对于普通进程，创建时静态优先级是继承自父进程的，因此它的权重也和父进程一样，因此可以直接从父进程拷贝就好，不需要做改变。只有在静态优先级改变(比如nice系统调用)时，才需要对权重进行相应的修改。进程的权重保存在task_struct.se.load字段中，该字段是load_weight类型：

struct load_weight {
	unsigned long weight, inv_weight;
};
  • weight: 表示权重
  • inv_weight: 标识被负荷权重除的结果，什么意思呢？这里都是用了普通的long类型，因此内核是无法直接存储1/weight的，而比需要借助乘法和移位来完成，所以就保存了inv_weight，inv_weight = 2^32 / 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,
};

对内核使用的[039]范围中的每个nice(对应用户设置的[-2019])，该数组都有一个对应项。各数组之间的乘数因子是1.25。为什么采用1.25这个因子呢？我们举个例子说明一下：假设进程A和B的nice值都是0，那么两个进程的权重都是1024，并且两个进程占用的CPU份额相等，各50%。即(1024+1024) / 1024 = 0.5。 如果进程B的nice增加1，那么B的CPU份额就需要减少10%，也就是说A得到CPU份额的55%，而B得到45%，这样的话就需要B的权重为1024 / 0.55 - 1024 = 820。此时B的CPU份额就是820 / (820 + 1024) = 0.45，因此乘数因子就应该是1024 / 820 = 1.25。

在执行静态优先级优先级到权重的转换时，也需要转换实时进程，虽然并没有用到(至少2.6.24没有用到)，内核通过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)

如果你还有印象的话，就会发现属于每CPU的就绪队列中也关联到一个负荷权重。每次进程被添加到就绪队列中时，内核就会调用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实现。如果系统正在活动中，那么内核会按照频率HZ自动调用该函数(时钟中断)。如果没有进程在等待调度，那么在计算机电量不足的情况下，也可以关闭该调度器以减少耗电。该函数主要有两个任务

  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负载，然后调用当前进程所属的调度器类的周期性调度方法，(另外多说一句，多处理器下每个处理器都有自己的周期性时钟)。对于调度器类的周期性方法这里暂时不讨论，在后面的章节会着重介绍。

主调度器

在内核的许多地方，如果要讲CPU分配给与当前进程不同的另外一个进程，都会直接调用主调度器函数schedule()，在从系统调用返回之后(实际上不止于此，从中断、异常返回时也会检查)，内核也会检查当前进程是否设置了TIF_NEED_RESCHED，如果设置了该标志，那么就会调用scheduler()函数寻找一个新的可执行进程替换当前进程。下面就来着重看一下schedule()函数的内核实现：

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，说明此时进程正在某等待队列上等待指定条件，那么会将当前进程从就绪队列中删除

schedule函数主要工作为：调用当前进程所属调度器类方法put_prev_task，该方法不同的调度器类实现不同，主要工作就是在当前进程失去cpu之前做一些工作(例如对于CFS调度器，如果当前进程的on_rq==1，则会将当前进程重新放回队列中)；然后调用pick_next_task函数获取下一个合适的进程，该函数主要去调用调度器队列的相应函数，如果成功找到了合适的进程，并且和当前进程不相同，那么后面会执行context_switch进行实际的切换。

需要注意的是，如果进程的on_rq==1，那么表明当前进程属于某个队列管理，即使它目前不在该队列上。比如CFS调度器来说，在选择新的进程执行时，会把当前进程从CFS管理的红黑树上移除，也就是说正在运行的CFS调度器管理的进程实际上并不在队列中，但是该进程的on_rq=1。这里需要区分，on_rq表示一个进程是否属正在被某个调度器队列管理，这个管理由两层含义：

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

因此对于CFS调度器来说，如果进程在调度器队列中，那么on_rq=1恒成立，反过来却不然；因为被调度器选中占用CPU的进程虽然不在调度器队列中，但是它仍然属于调度器队列管理，因此on_rq=1。

下面将依次介绍pick_next_task 和context_switch函数，首先介绍pick_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_highest链表，中的调度器类，然后调用指定调度器类的pick_next_task函数选择合适的进程，而sched_class_highest链表中调度器类的数量就决定了调度器类的优先级，根据前面说的rt_sched>cfs>idle

选择合适进程的逻辑其实非常简单，就是找到合适的调度器类，然后调用调度器类的方法从调度器队列中寻找合适的进程，下面我们来看看schedule函数的另一个重点，进程切换函数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_to和finish_task_switch，首先介绍实际执行切换的函数switch_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_switch的最后一个函数finish_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虚拟时钟

下面主要看一下CFS如何实现虚拟时钟，前面说到过，CFS调度算法依赖于虚拟时钟，用来度量等待进程在完全公平系统中所能得到的CPU时间。但是到目前为止，我们并没有在介绍过的任何数据结构中发现虚拟时钟。这是因为虚拟时钟可以根据进程权重和物理时间直接推算出来。所有与虚拟时钟相关的计算都在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主要工作就是计算出两次统计时间的物理差值，该差值就是这段时间进程实际占用cpu的物理时间，然后调用__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值为0的进程，它的物理时间和虚拟时间流速是一样的，而对于其他进程：nice值越低，则虚拟时间增长越慢，记住这点，这对于cfs调度器来说非常重要。为什么重要呢？cfs调度器队列是一个红黑树组织，cfs调度器会根据进程的虚拟时间进行排序，也就是说，虚拟时间越小的进程，越靠近红黑树的左边。并且cfs调度器在选择下一个合适进程时，总是选择红黑树最左边的进程，也就是虚拟时间最小的进程，因为cfs调度器只看虚拟时间，虚拟时间小的进程在cfs看来占用cpu少，受到了不公平的对待，因此cfs总是会选择虚拟时间小的进程来执行。

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

延迟跟踪

Linux内核有个良好的概念被称为调度延迟，可以理解为每个可运行进程都应该至少执行一次的某个时间间隔值。该部分和几个内核变量给出

  1. sysctl_sched_latency，表明每个可运行进程至少运行一次的时间间隔，默认为20毫秒
  2. sysctl_sched_min_granularity：进程最短占用cpu时间，默认为4毫秒，主要是用来辅助计算sched_nr_latency
  3. sched_nr_latency：控制一个延迟周期中处理的最大活动进程数量，变相的由上面两个值控制。并且和sysctl_sched_latency以及活动进程数量计算延迟周期(调度周期)。

当sysctl_sched_latency和sysctl_sched_min_granularity任意一个改变时，都会重新计算sched_nr_latency。但是如果就绪队列中有过多的可运行进程，那么也会调用sched_period对sysctl_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_latency = sysctl_sched_latency*nr_running / sched_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的公式可以看到，这两个公式结合化简后就上物理时间到虚拟时间的公式

队列操作

前面说过，每个调度器类都包含入队/出队函数，这里主要介绍cfs调度器的队列操作函数：enqueue_task_fair和dequeue_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调度器的入队操作，就介绍完了，这里总结一下整体流程(只针对调度实体为进程)

  1. 如果进程on_rq=1，说明进程已经被当前调度器队列管理，直接返回
  2. 调用enqueue_entity将进程入队
  3. 更新当前cfs队列最小虚拟时间，更新调度器统计量，更新该队列正在运行进程虚拟运行时间
  4. 如果进程是刚刚被唤醒，那么对进程的虚拟运行时间进行调整，对其进行一定程度的奖励
  5. 更新调度器统计信息
  6. 如果进程不是cfs队列上正在运行的进程，那么说明该进程确实不被队列管理，因此把进程添加到cfs队列中(红黑树中)
  7. 更新队列和进程相关信息：nr_running++、cfs_rq.load.weight增大、进程on_rq置1

出队操作

介绍完出队操作，下面来介绍入队操作，cfs调度器的入队操作主要是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);
}

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

放回和选择

放回正在运行进程

回忆一下schedule函数，在调用pick_next_task之前，会先调用put_prev_task用于将正在运行的进程放回到就绪队列中，我们来看一下cfs调度器是如何实现的：

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

就像schedule函数看到的那样，在将正在运行的进程切换下来之前，需要先调用put_prev_task函数做一些处理工作，主要是继续调用update_curr进行万年不变的更新，然后将进程放回到队列(红黑树)中，然后将cfs队列的curr置空(在选择下一个进程时会重新设置)。

选择下一个进程

还是schedule函数中的逻辑，将正在运行的进程放回到就绪队列中后，接着调用pick_next_task_fair(我们现在假设没有实时进程，因此一定会调用cfs调度器的pick_next_task，也就是该函数)选择下一个合适进程执行：

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函数中没有介绍的调度器类相关的部分已经介绍完了，可以回顾一下schedule函数，看看基于cfs调度器的进程是如何执行schedule函数的。需要注意的是，在上面的介绍中，为了方便起见，直接把调度实体等价为进程，但是实际上这是不准确的，进程是调度实体，反过来则不一定！！

周期性调度器

前面实际上已经介绍了scheduler_tick函数，该函数由本地时钟周期性触发执行，主要工作是更新该cpu就绪队列的clock时钟，然后就绪队列curr指向进程所属的调度器类的task_tick函数，下面就看一下cfs调度器的周期性函数task_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_PREEMPT，那么进程被唤醒时会执行check_preempt_wakeup函数，该函数如果检测到WAKEUP_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);

好了让我们继续介绍cfs周期性调度的核心逻辑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);
}

可以看到cfs对于周期性调度的处理非常简单，首先调用update_curr更新队列最小虚拟时间，统计信息，进程此次被调度执行以来使用cpu时间总和以及进程虚拟时间。然后判断当前进程是否运行的物理时间超过了它被分配的份额，如果超过则设置进程的TIF_NEED_SCHED标志执行抢占，否则什么也不做。

唤醒抢占

当调用try_to_wake_up和wake_up_new_task函数尝试唤醒进程时，会调用check_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_curr函数，cfs调度器通过check_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);
}

可以看到cfs的唤醒抢占逻辑也并不复杂。但是需要注意的是，我们回顾do_fork函数，do_fork会调用wake_up_new_task函数，如果新进程属于cfs调度器，那么最终会调用check_preempt_wakeup检查新进程是否需要抢占父进程，一般来说我们时希望子进程先于父进程执行的，因为这样能够更好利用写时复制避免很多无效的拷贝操作。但是从这里可以看到，如果关闭了唤醒抢占调度器特性，或者sysctl_sched_wakeup_granularity设置的过大，那么子进程很有可能不会抢占父进程，看起来这是个issue，高版本应该会修复。

处理新进程

回顾前面的sched_class类，还有一个函数我们需要考虑的就是task_new_fair，该函数调用过程do_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对新进程的处理逻辑也是比较清晰的。

到目前为止，除了多处理器下的负载均衡相关部分，cfs调度器类的所有功能就已经介绍完毕了，接下来让我们来看一下wake_up_new_task函数，该函数在do_fork中被调用，但是在介绍fork时并没有深入介绍该函数，通过前面的介绍可以发现该函数涉及到两个调度器函数，分别是check_preempt_wakeup和task_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_fork的过程，do_fork --> copy_process --> sched_fork最终调用sched_fork和调度器建立联系。sched_fork主要是初始化进程的调度器类和调度实体，然后在多处理器系统下进行处理器间负载均衡，把新进程绑定到合适的cpu上；

接着do_fork --> wake_up_new_task，该函数的作用已经介绍过了，主要是计算新进程的动态优先级，将进程添加到进程所属调度器的调度器队列中(这里假设是cfs调度器)，这个过程还会调用update_curr更新调度器最小虚拟时间、进程自占用cpu以来的cpu物理时间总和，进程虚拟时间，并且增加cfs队列的nr_running和load.weight；

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

睡眠进程唤醒

当一个进程从睡眠状态被唤醒时，内核一般调用try_to_wake_up来唤醒睡眠进程，该函数会调用check_preemt_curr，check_preempt_curr是调度器类函数，不同的调度器类实现不同，cfs调度器的实现函数为check_preemt_wakeup函数，该函数判断被唤醒进程和正在运行进程的虚拟时间来判断是否需要执行抢占(当然这里说的很简单，省略了很多过程，可以回顾前面看详细过程)；如果需要执行抢占，则设置当前进程的TIF_NEED_SCHED标志。

周期性调度抢占

周期性调度由cpu本地定时时钟周期性触发执行，周期新函数就是scheduler_tick，该函数首先会更新就绪队列的时钟(是就绪队列而不是调度器队列，注意区分)，然后会调用调度器类的task_tick函数，cfs的实现函数是task_tick_fair函数，该函数主要是先调用update_curr更新一些量，然后调用check_preempt_tick比较进程自占用cpu以来使用的cpu物理时间和该进程被分配到的最大cpu份额，如果超过该份额，那么设置该进程的TIF_NEED_SCHED标志。

实时调度器

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

SMP增强

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

多处理器负载均衡

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

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

进程对于特定CPU的亲和性，定义在task_struct的cpus_allowed成员中，Linux提供了sched_setaffinity系统调用，可以修改进程与CPU的现有分配关系。

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

周期性调度器scheduler_tick的末尾会触发软中断，该软中断在合适的时候进行负载均衡。具体更加详细的东西，暂时不想看了，以后再说吧。

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

目前2.6版本还是存在这个bug的，但是高版本实际上已经解决了，如何解决这个问题呢？其实也非常简单，进程在添加到队列中时，将进程的虚拟运行时间修改为vruntime - 该队列的最小虚拟时间，也就是这里只存储了差值，当进程从调度队列上拿出来执行时，再加上队列的最小虚拟时间。这样一来即使进程在不同队列上迁移，那么进程也不太会占便宜。

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

内核抢占和低延迟相关

内核抢占

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

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

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

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

内核如何确定此时能否被抢占呢？回想一下系统中每个进程都有一个特定于体系结构的thread_info结构，该结构包含了一个抢占计数器。

struct thread_info {
    int preempt_count
}

该字段确定了内核当前是否处于一个可以被抢占的位置。如果preempt_count==0那么内核可以被抢占，否则不行。该值不能直接操作，一般通过dec_preempt_count和inc_preempt_count。这两个分别对preempt_count加1减1。每次内核进入重要区域，需要禁止抢占时，都会调用inc_preempt_count。在退出该区域时，就会调用dec_preempt_count将抢占计数器减1。由于内核可能通过不同的路线进入某些重要的区域，特别是嵌套路线，因此preempt_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_ACTIVE是一个很大的值，主要用来告诉schedule函数，此次调度由内核抢占出发，这样能避免一种特殊情况(前文有说到)。

preempt_enable

该函数和上面的preempt_disable相反，递减preempt_count计数器以允许内核抢占，并且检查是否需要执行抢占：

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

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

低延迟

上面说的都是通过开启内核抢占来避免高延迟，但是如果没有开启内核抢占，内核也需要尽可能的提供良好的延迟时间。例如对于网络服务器很重要。如果一个网络请求到达，需要守护进程处理，那么该请求不应该被执行繁重IO操作的数据库过度延迟。也就是说，即使没有开启内核抢占，内核中耗时长的操作不应该完全占据整个系统。相反，这中耗时长的操作需要时不时的检测是否有另外一个进程变为可运行，并在必要的情况喜爱调用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;
}

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

小结

Linux 2.6.24采用了大名鼎鼎的CFS调度器，在实际应用时候表现很不错，并且相对于O(1)调度器，也没有各种启发式规则，表现也相对稳定。在实现时也比O(1)调度器要简单很多。另外，2.6内核也支持内核抢占，从而提供更好的响应时间，另外即使没有开启内核抢占，内核也会在内核耗时较长的函数中插入cond_resched函数检查是否需要调度，这样能够避免由于进程在内核执行时间过长而导致无法被抢占，进一步响应时间变长。