进程调度

1. 暂时以2.6.24内核版本讲解，该版本是CFS调度器注入Linux内核之后的第二个版本，在框架和数据结构上与4.x之后没有本质上的区别。但是由于4.x对CFS调度做了很大的优化，代码量暴增10倍之多，故不容易把握算法与框架的本质，所以暂时以麻雀虽小五脏俱全的2.6.24作为讲解数据结构方面的基础。
2. 主要讲解CFS调度类与调度框架，实时进程与其他类型的进程调度算法与CFS在框架上没有区别。
3. 在讲解代码实现时，修调整函数原本的封装结构，并且没有列出锁、中断、抢占等操作，这仅仅是为了更清晰的理解调度框架做了什么
4. 在一些算法和描述上参考了 JeanCheng CSDN博客专家的文章，原地址 目录索引

概述

分时系统

为了让所有共享CPU资源，并且进程响应时间尽可能快，后台作业的吞吐量尽可能高，尽可能避免进程的饥饿现象，低优先级和高优先级的进程尽可能调和等，Linux设计了一套本质上基于多个进程以 时间多路复用 的方式来调度所有进程的分时技术调度器 ———— 即将使用CPU的使用时间分片，每一个进程获得一片或多片时间，在某个进程消耗完自己的分得的时间资源后，由时间中断中来检查，然后强制切换到另一个进程，通过这样的快速切换，从表面上达到所有进程都同时运行的效果，其中何时切换进程并选择最优的进程来运行即为 调度策略。

进程优先级

为了从基本准则上公平的分配CPU运行时间资源，我们将进程按等级分类，优先级越高的进程分得的CPU使用时间越多，反之就越少。但是必须保证每一个进程在一定时间内都能运行，否则可能出现低优先级进程被 饿死 的现象，即表现为进程卡顿、甚至无法响应。所以在实际的调度过程中，需要按实际的作业场景再次将进程分类，并动态的调整他们的优先级，使其在需要时能及时的被调度运行，完成必要的工作后，随后立马放弃CPU的使用，让真正优先级高的进程再次调度运行。

进程分类

1. 按使用CPU的使用程度分类为I/O受限(I/O-bound)或CPU受限(CPU-bound)。I/O受限型也称作I/O密集型，这类进程频繁的使用I/O设备，并花费很多时间等待I/O操作的完成，他们IO数据就绪时要求立马得到响应，读取完数据之后又立马进入睡眠再次等待后续数据就绪，比如数据库服务器、文本编辑器等；CPU受限型也称为计算密集型，这类进程花费大量CPU时间进行数值计算，他们会一直使用CPU，基本不睡眠，比如图形渲染、科学计算等。

2. 按作业场景分类为交互式进程、批处理进程和实时进程。交互式进程，此类进程经常与用户进行交互，因此需要花费很多时间等待键盘和鼠标操作，当接受了用户的输入后，进程必须很快被唤醒，否则用户会感觉系统反应迟钝，比如图形界面的应用程序。批处理进程，此类进程不必与用户交互, 因此经常在后台运行。因为这样的进程不必很快相应, 所以常受到调度程序的怠慢，比如科学计算程序。实时进程，这些进程由很强的调度需要，这样的进程绝不会被低优先级的进程阻塞，并且他们的响应时间要尽可能的短，比如视频音频应用程序。

进程调度策略

为了更好的描述进程类型和和优先级与调度之间的关系，我们用调度策略来描述。不同的调度策略他们分配CPU使用时间的算法不同，且组织进程的结构可能也不相同，但是被调度器框架使用的方式相同。

调度器

主调度器

调度的最终目标是选择一个合适的进程在CPU上运行；而且还必须使暂时让出的CPU使用的进程的 状态得到保存，并使即将获得CPU使用的进程的 状态得到恢复。为完成这一些动作而设计的算法和实现，即为主调度器。

周期调度器

为了达到不需要编程者手工的插入相关的代码就能完成进程的调度，Linux 在以合理的使用主调度为目的，设计出周期调度器，即通过周期的在时间中断中触发调度检查并标记当前进程是否应被调度，如果应该被调度，则在时间中断结束后，调用主调度器强制剥夺当前进程的CPU使用。进程的调度可以对编程者透明化，从而达到简化编程的目的。

调度框架

调度框架在一定程度上是一个面向对象的实现，它使用运行队列作为管理进程调度的组织结构的入口，用调度实体来描述被调度的对象，并将这些对象的相同行为归纳为调度类。简而言之，调度框架使用调度器通过调度类来操控调度实体。

调度标志

内核通过在进程栈上设置一个标志来标识进程的特殊状态，其中就包括 调度标志 ———— TIF_NEED_RESCHED，如果被设置就表示该进程应该被调度，让出CPU资源。它存在 struct thread_info 的 flags 字段中，而整个结构体位于内核栈的栈低，内核通过 栈寄存器 可以快速的计算出其指针位置，在较新的内核代码中，使用了 per-cpu 变量来实现了。

调度实体

调度框架将进程（或进程组）分类调度，所属不同策略的被调度对象有着不同的属性，调度实现用调度实体来描述这些属性。如果将调度的实现看做面向对象，那么调度框架是容器，调度实体是容器中的元素基类，而进程或进程组这些调度单位则是基类的派生类。

运行队列

运行队列是调度实体在排队等待使用CPU的一种管理容器。在调度实现中，调度框架只识别运行队列，至于属于不同策略的调度实体要以怎样的方式组织，这依赖于相应的调度类在运行队列中实现的调度队列，每次对运行队列的操作被调度框架转变为对相应调度队列的操作。增加调度类（调度策略）就应该在运行队列中有相应的调度队列。

调度类

为了更好的升级旧的或实现新的调度策略，我们以面向对象的方式抽象出一系列实现调度的基本操作，这些操作的集合称为调度类（相当于接口类）。不同类型的调度实体归纳在不同的调度类，就获取不同的调度策略。

调度框架使用运行队列作为数据结构，调度类作为数据结构的操纵集合来实现调度。

主调度器实现最终被拆解为对调度实体进行如下的相应调度类实现的操作：

1. dequeue_task() 当前被调度的进程需要从运行队列移除。
2. put_prev_task() 当前被调度的进程会从运行状态转变为其他状态需要被重新放置，即重新排队或不再排队。
3. pick_next_task() 选择一个合适的进程来替换当前被调度的进程使用CPU。
4. task_tick() 时间中断使用该函数判断当前运行进程是否已经耗尽分得的CPU使用配额，如果是则标记 TIF_NEED_RESCHED。

在进程休眠后再次需要运行时，或在新创建的进程希望参与到调度中来，所以调度类还要实现以下主要的辅助操作：

1. enqueue_task() 排队到运行队列中，才能被调度框架重新选中。
2. check_preempt_curr() 重新排队的进程由于休眠过久，或比当前运行的进程优先级高（有可能是暂时提高），入队列时使用此接口抢占当前运行进程。
3. task_new() 在参与调度前，初始化新创建的进程。

本文章暂时忽略其他辅助操作，比如负载均衡。

调度实现

暂时忽略更大的组合调度单位，只考虑单一的进程调度
下面将以完全公平调度类为例来介绍新的基于调度类设计的调度实现。

调度策略与调度类

内核将进程的调度策略归纳为：

1. SCHED_NORMAL 普通非实时进程策略，大部分进程都属于该类调度策略。
2. SCHED_BATCH 批处理非实时进程策略，它是 SCHED_NORMAL 的分化版本，最大的不同就是优先级更低，而且肯定不会去抢占 SCHED_NORMAL 类型的进程。
3. SCHED_IDLE 空闲非实时进程策略，优先级最低，除非其他所有的进程都挂起等待各自的资源就绪，否则不会允许此类的进程。
4. SCHED_FIFO 先入先出的实时进程策略，高优先级的任务可以抢占低优先级的任务，但同优先级的进程除非自动放弃CPU，否则不会被主动剥离CPU使用权。而且肯定不会被非实时进程抢占。
5. SCHED_RR 与 SCHED_FIFO 类似，但在使用CPU到期时，会被强制剥夺CPU使用权，并放置在队列尾部，以轮转的方式使用CPU。
6. SCHED_DEADLINE 新支持的实时进程调度策略，针对突发型计算，且对延迟和完成时间高度敏感的任务适用。（暂时没有搞懂怎么回事）

内核预实现了以下的调度类来处理这些策略的进程调度：

1. dl_sched_class 服务 SCHED_DEADLINE 策略的进程调度。
2. rt_sched_class 服务 SCHED_RR 和 SCHED_FIFO 策略的进程调度，由于两种策略和优先级强关联的，所以调度队列的组织结构是一样的 ———— 都是优先级队列。
3. fair_sched_class 服务 SCHED_NORMAL 和 SCHED_BATCH 策略的进程调度，即著名的完全公平调度类。该策略是将优先级转变为权重，进而转换为虚拟运行时间进行排队，内核用红黑树来组织（以虚拟运行时间为键）待调度进程，并且能保证在一定调度周期内，所有的进程都能被调度一次，所以叫完全公平调度类。
4. idle_sched_class 服务 SCHED_IDLE 策略的进程调度，内核中每个CPU上只有一个这样的进程，即为 swapper pid 为0的零号进程。

内核将会以下列的优先级来组织调度类，即从优先级最高的调度类中选择下一个运行的进程：

dl_sched_class > rt_sched_class > fair_sched_class > idle_sched_class

进程的调度

首先，必须明确的是进程的状态与进程调度的关联，只有处于 TASK_RUNNING 的进程才可以参与调度 ———— 可以排队到相应的调度队列中。

调度发生的时机有以下列出的几处：

1. 由编程者主观的调用 schedule() 主调度器，即因为当前进程要等待一个未就绪的条件而暂停执行的调度。
2. 由时间中断在检查确定当前进程运行时间配额用完后，退出中断并完全将要返回可抢占状态时，调用 preempt_schedule_irq() 周期调度器而强制剥夺当前运行进程对CPU使用的调度。另外这种情况切换也会在从其他硬中断、系统调用或（缺页）异常返回用户态时触发。
3. 由于系统支持内核态抢占（从内核态的代码执行中切换进程上下文），在内核态离开原子上下文（使能软中断、自旋锁解锁等）时，调用 preempt_schedule() 抢占调度器触发的进程调度。

在系统启动时会初始化一个每隔一定时间触发的时钟中断，在时钟中断中对当前运行进程的运行时间进行更新，如果该进程需要被调度，就在进程上设置 TIF_NEED_RESCHED。因为上面已经提到从中断上下文返回时是一种调度时机，如果此时检查到进程的 TIF_NEED_RESCHED 已经设置，则最终执行 schedule() 主调度器进行调度。

数据结构介绍

1. 进程与调度相关的基本字段

进程使用调度实体的数据结构参与调度，这样设计还可以组合更大的调度单位，比如以进程组的方式调度。调度实体内嵌入进程描述符中，如下：

struct task_struct {
	/* 进程优先级
	 * prio: 动态优先级，范围为100~139，与静态优先级和补偿(bonus)有关，内核需要暂时提高进程的优先级, 因此需要用prio表示
	 * static_prio: 静态优先级，static_prio = 100 + nice + 20 (nice值为-20~19,所以static_prio值为100~139)
	 * normal_prio: 表示基于进程的静态优先级static_prio和调度策略计算出的优先级
	 */
	int prio,/**< 动态优先级*/ static_prio, /**<静态优先级*/normal_prio; /**<普通动态优先级*/
	const struct sched_class *sched_class; /**< 所属调度类*/

	struct sched_entity se; /**<完全公平调度队列中的节点（调度实体）*/

	unsigned int policy;/**<进程调度类型:SCHED_NORMAL、 SCHED_RR 或 SCHED_FIFO */
	cpumask_t cpus_allowed;/**<能执行该进程的CPU掩码*/
};

struct sched_entity {
	struct load_weight	load;		/**< 负载权重和重除 */
	struct rb_node		run_node; /**< 嵌入到红黑树的节点*/
	unsigned int		on_rq; /**< 是否在调度队列上*/

	u64			exec_start; /**< 开始计时的节拍*/
	u64			sum_exec_runtime; /**< 当前执行的总节拍*/
	u64			vruntime; /**< 虚拟运行时间*/
	u64			prev_sum_exec_runtime; /**< 上次调度以来的执行总节拍*/
}

struct load_weight {
	unsigned long weight /**< 权重*/, inv_weight/**< 除重系数*/;
};

1. 调度类

进程必然属于某一调度类，以使调度框架在调度的顶层实现函数中可以以同样的方式操作进程。

struct sched_class {
	/* 系统中多个调度类, 按照其调度的优先级排成一个链表
	 * 下一优先级的调度类
	 * 调度类优先级顺序: stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class
	 */
	const struct sched_class *next;

	/*  将进程加入到运行队列中，即将调度实体（进程）放入红黑树中，并对 nr_running 变量加1   */
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int wakeup);
	/*  从运行队列中删除进程，并对 nr_running 变量中减1  */
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int sleep);
	/*  放弃CPU，在 compat_yield sysctl 关闭的情况下，该函数实际上执行先出队后入队；在这种情况下，它将调度实体放在红黑树的最右端  */
	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);

	/* 当进程改变它的调度类或进程组时被调用 */
	void (*set_curr_task) (struct rq *rq);
	/* 该函数通常调用自 time tick 函数；它可能引起进程切换。这将驱动运行时（running）抢占 */
	void (*task_tick) (struct rq *rq, struct task_struct *p);
	/* 在进程创建时调用，不同调度策略的进程初始化不一样 */
	void (*task_new) (struct rq *rq, struct task_struct *p);
};

/*CFS调度类实现*/
static const struct sched_class fair_sched_class;

1. CFS 调度队列

不同的调度类虽然有相同行为，但是其实现不同，也需要不同的数据结构。

struct cfs_rq {
	unsigned long nr_running; /**< 排队的进程数目*/

	u64 min_vruntime; /**< 排队的进程中最小的虚拟时间*/

	struct rb_root tasks_timeline; /**< 组织红黑树*/
	struct rb_node *rb_leftmost; /**< 第一个排队的进程*/

	struct sched_entity *curr; /**< 当前正在被调度的进程*/
}

CFS调度队列通过红黑树组织，因为其管理的待调度进程通过 虚拟时间 来升序排序的，虚拟时间越小则越靠左边，而每次调度时都取最左边的进程，所以更容易被调度。

1. 运行队列

整个调度框架的数据结构总入口，调度框架和实现函数只识别运行队列，而具体的实现交于不同的调度类。每个CPU上有一个运行队列，以减少调度时带来的并发竞争。

struct rq {
	unsigned long nr_running; /**< 可运行进程的总数*/

	struct load_weight load; /**< 所管理的运行进程总负载权重，用于计算运行队列的基础虚拟时间*/

	struct cfs_rq cfs; /**< 完全公平调度队列*/

	unsigned long nr_uninterruptible; /**< 处于不可中断的进程数量*/

	struct task_struct *curr, *idle; /**< 当前运行的进程和swapper进程*/
	struct mm_struct *prev_mm; /**< 上下文切换中暂存的用户进程内存描述符*/

	/*调度器的自身时钟计数*/
	u64 clock/**<单调递增的节拍*/, prev_clock_raw/**< 系统节拍*/;
	u64 tick_timestamp; /**< 时钟中断时的当前时间戳*/
}

优先级的处理

调度框架将进程对CPU使用时间配额抽象为优先级，并数值范围 0~139 表示（120为默认值），数值越低，优先级越高。从 0~99 的范围专供实时进程使用，其余为普通进程（CFS调度类管理的进程）。在用户态还使用 nice 值 -20~19 来表示普通进程对其他进程的友好程度（0为默认值，负值是不友好），即让出更多的CPU使用时间，这个值映射到范围 100~139。

优先处理与转换的宏和数据如下：

#define MAX_USER_RT_PRIO	100
#define MAX_RT_PRIO		MAX_USER_RT_PRIO

#define MAX_PRIO		(MAX_RT_PRIO + 40)
#define DEFAULT_PRIO		(MAX_RT_PRIO + 20)

/*友好值与优先级的相互转换*/
#define NICE_TO_PRIO(nice)	((nice) + DEFAULT_PRIO)
#define PRIO_TO_NICE(prio)	((prio) - DEFAULT_PRIO)
#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio)

/*默认友好值的权重*/
#define SCHED_LOAD_SHIFT	10
#define SCHED_LOAD_SCALE	(1L << SCHED_LOAD_SHIFT)
#define NICE_0_LOAD		SCHED_LOAD_SCALE
#define NICE_0_SHIFT		SCHED_LOAD_SHIFT

内核在实现CFS时，使用权重来描述进程应该分得多少CPU时间，因为CFS只负责非实时进程，所以权重与 nice 值密切相关。一般这个概念是，进程每降低一个 nice 值（优先级提升）， 则多获得 10% 的CPU时间, 每升高一个 nice 值（优先级降低）, 则放弃 10% 的CPU时间。

为执行该策略，内核需要将优先级转换为权重值，并提供了一张优先级到权重转换表 prio_to_weight ，各个值之间的乘积因子为 1.25 ，此值是为达到 nice 值增减一个单位，CPU时间占比就相应的浮动 10% 而设定的。由于在计算过程中需要使用除法，内核还提供一张 定点数除法 的倒数表 prio_to_wmult 数组，这两个数组中的数据是一一对应的，用来帮助内核进行浮点运算。

对于CFS调度类，内核不仅使用权重来衡量进程在一定CPU时间周期分得的时间配额，还是使用权重来衡量进程运行的虚拟时间的快慢 ———— 权重越大，流失得越慢。计算相当公式如下：

• 当 nice != NICE_0_LOAD 虚拟时间 vruntime = real_exec_time * (NICE_0_LOAD / weight)
• 当 nice == NICE_0_LOAD 虚拟时间 vruntime = real_exec_time

可见权重越大，虚拟时间也流失得越慢，在上面介绍的CFS调度队列红黑树中排队越靠前。

调度的初始化

内核将在系统启动时初始化调度框架的数据结构。在 start_kernel() 中调用 sched_init() 函数初始化 rq，并初始化第一个进程 ———— 即 swapper 进程的调度相关的数据结构。

void sched_init(void)
{
	for_each_possible_cpu(i) {
		struct rt_prio_array *array;
		struct rq *rq;

		rq = cpu_rq(i);
		init_cfs_rq(&rq->cfs, rq);
		...
	}

	...

	set_load_weight(&init_task);

	...

	open_softirq(SCHED_SOFTIRQ, run_rebalance_domains, NULL);

	...

	init_idle(current, smp_processor_id());

	current->sched_class = &fair_sched_class;
}

初始化 idle 进程的各个字段，注意 idle 一定是运行队列的第一个运行的进程

void init_idle(struct task_struct *idle, int cpu)
{
	struct rq *rq = cpu_rq(cpu);
	unsigned long flags;

	idle->se.on_rq = 0;
	idle->se.exec_start = 0;
	idle->se.sum_exec_runtime = 0;
	idle->se.prev_sum_exec_runtime	= 0;

	INIT_LIST_HEAD(&idle->run_list);

	/*保证不会被意外唤醒，已经处于运行状态*/

	idle->state = TASK_RUNNING;

	idle->se.exec_start = sched_clock();

	/*设置为最大优先级值，优先级最低*/

	idle->prio = idle->normal_prio = MAX_PRIO;
	idle->cpus_allowed = cpumask_of_cpu(cpu);

	/*设置运行CPU*/

	task_thread_info(idle)->cpu = cpu;

	...

	/*idle是第一个已运行的进程*/

	rq->curr = rq->idle = idle;
	idle->oncpu = 1;

	...

	idle->sched_class = &idle_sched_class;
}

该函数主要是遍历运行队列的 per-cpu 结构，对运行队列进行初始化，包括其中的CFS调度队列。之后初始化零号进程的调度相关字段，注意此时故意将 swapper 进程设置为 CFS 调度策略，是为随后 在 rest_init() 中创建 其他内核线程和一号 init 进程，因为子进程会继承大部分父进程的调度属性，包括调度策略，在完成最终初始化后，swapper 才变身归纳到 idle_sched_class 调度策略，并使能抢占以让其他进程或线程运行，随后只会执行 cpu_idle() 死循环函数直到关机。而一号 init 进程在创建初期还是执行在内核态的内核线程，它在此形态下还负责继续完成启动内核的多核启动；通过 smp_init() 和 sched_init_smp() 函数内核将完成其他CPU的启动和相关数据的初始化，最重要的是注册 per-cpu 初始化回调链（参见 register_cpu_notifier() 的使用）、克隆启动CPU上的 swapper 进程（克隆的进程不会驻留在进程组织结构中，但是占用了pid号）、初始化调度域（负载平衡章节）等（由于此部分涉及很多硬件相关的知识，我也弄不清怎么回事，就不能一一列举功能）；随后 init 进程执行 run_init_process("/sbin/init"); 转变为一个用户态进程，负责所有用户态僵死进程的回收工作。

static void rest_init(void)
{
	int pid;

	/*创建一些内核线程，但是还没启用抢占，不会被调度*/

	kernel_thread(kernel_init, NULL, CLONE_FS | CLONE_SIGHAND);

	...

	/*
	 * 启用抢占，手动的调度一次，这里发生内核初始化以来的第一次进程切换
	 * 当前运行进程恰好是 idle 进程，此后会选择其他内核线程来运行
	 */

	preempt_enable_no_resched();
	schedule();
	preempt_disable();

	cpu_idle();
}

周期调度器

周期调度器由 scheduler_tick() 实现时间信息的统计和判断是否应该剥夺当前运行进程对CPU的使用，该函数由时钟硬中断在固定时间内触发，如果进程对CPU时间配额耗尽，则进行简单标记，在退出中断上下文时再配合主调度器 schedule() 进行强制调度，它是以一种对进程透明的、公平的为所有进程分配CPU时间配额的重要手段。

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

	/*更新运行队列自己的节拍，单调递增*/

	__update_rq_clock(rq);

	...

	/*
     * 如果当前不是idle进程，则更新运行进程的信息
	 * 这可能会导致在时间中断结束时重新选择一个可运行的进程进行调度
     * 
	 * @see task_tick_fair()
	 */

	if (curr != rq->idle)
		curr->sched_class->task_tick(rq, curr);

	...
}

主要是更新运行队列的虚拟时钟节拍，每个运行队列有自己的时间节拍概念，是因为时钟中断的实现不同和各个运行队列调度频繁程度不同，而调度又是基于分时机制的，所以为了较为精准计算运行的进程何时应该被抢占何时应该被调度，运行队列使用各自虚拟时钟节拍来计算相关的时间参数。内核使用开机后流失的纳秒时间来描述运行队列的节拍，使用 __update_rq_clock() 来更新这些时间属性，保证其单调性。

系统在运行一段时间后，不同的CPU上调用 fork() 的次数不同，导致进程在全局的运行队列里数量不平衡，内核需要以一种参数来描述这一情况，并以此为标准来进行负载平衡，将进程从繁忙的CPU运行队列中迁移到空闲的CPU运行队列中。 update_cpu_load() 负载完成负载计算，其本质上存储当前负载的一系列历史平均值。

不同进程其调度策略不同，运行时间统计信息和组织结构也不同，但是他们都需要周期的检查当前运行的进程是否应该被抢占，所以各个调度实现了自己的响应节拍的方法，由调度类的 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);

		/* 更新运行时统计信息*/

		update_curr(cfs_rq);

		/*判断当前进程是否能被抢占*/

		if (cfs_rq->nr_running > 1)
			check_preempt_tick(cfs_rq, 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;
	unsigned long delta_exec_weighted;

	delta_exec = (unsigned long)(now - curr->exec_start);

	/*（累加）统计时间信息*/

	curr->sum_exec_runtime += delta_exec;
	delta_exec_weighted = delta_exec;

	/*
     * 累加虚拟运行时间
	 * 1. 如果是 0 nice 的进程，虚拟运行时间即为真实运行时间
	 * 2. 否则使用权重计算得到 与优先级成反比的虚拟运行时间（权重越大增长得越慢）
	 * 计算公式 curr−>vruntime += delta_exec * NICE_0_LOAD / curr−>se−>load.weight
	 */

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

	/*
	 * 保证调度队列的最小虚拟时间 min_vruntime 单调递增 但是小于 排队的最小虚拟时间
	 * __pick_next_entity() 即第一个 调度队列中排队的进程
	 */

	if (first_fair(cfs_rq)) {
		vruntime = min(curr->vruntime, __pick_next_entity(cfs_rq)->vruntime);
	} else {
		vruntime = curr->vruntime;
	}

	cfs_rq->min_vruntime = max(cfs_rq->min_vruntime, vruntime);

	/*重置计时节拍*/
	curr->exec_start = now;
}

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
	unsigned long ideal_runtime, delta_exec;

	/*计算理想的运行时间（片）*/

	ideal_runtime = sched_slice(cfs_rq, curr);

	/*计算实际的运行时间*/

	delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;

	/*如果时间运行时间大于理想的运行时间，则应该被抢占（让出CPU）*/

	if (delta_exec > ideal_runtime)
		resched_task(rq_of(cfs_rq)->curr);
}

从 update_curr() 函数可以得知每次时钟中断都会增加运行进程的虚拟运行时间，如果进程的权重是 NICE_0_LOAD （即进程的 nice 值为120的默认值），那么虚拟运行时间就是真实运行时间，否则会或多或少的增加虚拟运行时间。一旦进程改变其 nice 值，内核才会使用静态表将真实运行时间进行一个成反比的转换，就会出现 nice 值越小虚拟运行时间增长得越慢，而进程在排队到以虚拟运行时间为键组织在一棵红黑树中时，就越靠近最左边的进程，从而被优先调度。

每次时钟到来后，都检查当前的真实时间是否达到了理想的运行时间。理想运行时间是通过 sched_slice() 计算得到的，相当于它将一定调度周期的时间（称为调度延迟，由sysctl_sched_latency控制）以进程的权重在权重总和（调度队列中所有进程权重的和）的占比为依据，来分配CPU时间配额。一旦超过理想运行时间，就使用 resched_task() 进行标记，随后进程被抢占。通过这样的手段可以保证排队的进程在一定延迟时间内都能被调度运行一次，因为红黑树中的进程总是向左移动的（运行中的进程虚拟时间增加，而排队的进程虚拟时间不变，所以低优先级的排队进程有运行的机会）。

CFS的分时是将降低当前运行进程对其他待调度进程造成的延迟为目标的调度算法，在一定的调度周期内，调度队列内所有的进程都被调度运行一次，即公平对待每个进程。上面这几个函数就包含了调度实现中的时间统计和衡量算法：

1. 调度框架在运行队列记录一个私有的从开机以来的纳秒节拍绝对时间，并且每次在需要调度时（使用 __update_rq_clock()）刷新。
2. CFS调度类中的调度进程各自有一个总的执行时间节拍，并以总时间节拍与优先级成反比的算法记录了一个虚拟时间
3. 这两个时间都只在运行的时候累加。
4. 通过比较前后两次调度总执行时间差得出单次运行时长和优先级正比得出的理想运行时长，总时间用于判断何时应该让出CPU。
5. 虚拟时间则决定红黑树中的位置，靠前则优先调度。

static void resched_task(struct task_struct *p)
{
	int cpu;

	/*已经处于重新调度的状态*/
	if (unlikely(test_tsk_thread_flag(p, TIF_NEED_RESCHED)))
		return;

	/*设置调度标志*/

	set_tsk_thread_flag(p, TIF_NEED_RESCHED);

	/*如果是本地CPU，则将在下一个时钟到来时被调度*/

	cpu = task_cpu(p);
	if (cpu == smp_processor_id())
		return;

	/*
     * 如果目标进程被CPU轮训了，也不做任何操作，
	 * cpu_idle() 会在 swapper 进程被调度期间轮训查看可用进程
	 * 否则发起CPU间中断，强制将进程陷入内核中断中，以便立马被调度
	 */

	if (!tsk_is_polling(p))
		smp_send_reschedule(cpu);
}

其中 smp_send_reschedule() 是一个向 CPU 主动发起中断的功能函数，这个中断叫着 IPI 内部处理中断。它强制让目标 CPU 陷入中断，而调度时机恰好在中断处理之后，所以可以从其他 CPU 强制剥离目标 CPU 上正在运行的进程的 CPU 使用权。TLB 刷新 和 用户态使用信号唤醒进程 都是通过此技术实现。

主调度器

所有调度器都依赖主调度器，它不仅负责如何处理当前运行进程和如何选择下一个运行的进程，还负责进程上下文的切换。

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

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

	...

	/*发送切换时，需要更新运行队列的虚拟时钟*/

	__update_rq_clock(rq);

	...

	/*判断是否为主动放弃CPU*/

	if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
		if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
				unlikely(signal_pending(prev)))) {
			/*可中断，且有信号需要处理*/
			prev->state = TASK_RUNNING;
		} else {
			/*否则失效进程，从调度队列中移除*/
			deactivate_task(rq, prev, 1);

			...
		}
	}

    ...

	/*
     * 调用进程所属的调度类，重新放置运行当前运行的进程
	 * 1. 如果是被抢占则进程还在运行队列中，但是需要重新计算位置
	 * 2. 否则是主动让出CPU，忽略操作。
	 */

	put_prev_task(rq, prev);

	/*选择最优进程进行调度，可能是其他调度类的进程*/

	next = pick_next_task(rq, prev);

	/*清除重新调度的标志*/

	clear_tsk_need_resched(prev);

	if (likely(prev != next)) {
		rq->curr = next;

		/*上下文切换并解锁*/

		context_switch(rq, prev, next);
	} else {
        spin_unlock_irq(&rq->lock);
    }

	...

	/*因为运行队列解锁了，所以其他路径可能发起了强制抢占刚换入的进程*/

	if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
		goto need_resched;
}

每次切换时都会更新进程和运行队列的时间等属性，虽然从周期调度器来看，这一步有些多余，因为在 scheduler_tick() 中已经调用过此函数，在没有经历一个时钟周期的情况下再次调用，肯定是没有效果的，但是 schedule() 可以被主动调用，那么运行队列的和正在运行的进程的时间属性会丢失精度，对于CFS来说肯定有不公平的调度发生。

如果进程是主动放弃CPU，并且其状态是非 TASK_RUNNING 状态，那么需要将进程从调度队列的管理中移除，内核通过调度框架函数 deactivate_task() 来调用进程对应调度类的 dequeue_task() 实现函数，对于 CFS 的实现为 dequeue_task_fair()。对于 CFS 调度类，当前运行进程不在调度队列里，所以此处只是简单的更新统计信息，并不会有出队列的操作（但在其他的地方调用会有，比如更改进程的调度策略时）。

static void deactivate_task(struct rq *rq, struct task_struct *p, int sleep)
{
	/*如果处于不可中断状态，则增加统计*/
	if (p->state == TASK_UNINTERRUPTIBLE)
		rq->nr_uninterruptible++;

	p->sched_class->dequeue_task(rq, p, sleep);
	p->se.on_rq = 0;

	/*进程离开了运行队列，管理的进程数和总的权重需要减少*/
	rq->nr_running--;
	rq->load -= p->se.load.weight;
}

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_each_sched_entity(se) {
		cfs_rq = cfs_rq_of(se);

		/* 更新虚拟时钟 */

		update_curr(cfs_rq);

		/* 
		 * 正在执行的进程不在调度队列上
		 * idle 进程永远都不在调度队列上
		 * 休眠运行进程则从红黑树中移除
		 */

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

		/*进程离开了调度队列，管理的进程数和总的权重需要减少*/

		cfs_rq->load -= se->load.weight;
		cfs_rq->nr_running--;
		se->on_rq = 0;

		...
	}
}

但是如果进程还处于 TASK_RUNNING 状态，则需要再次排队，该动作由 put_prev_task() 实现，与 deactivate_task() 一样，都是框架函数，CFS 的实现为 put_prev_task_fair()，从实现中可以看到 prev->se.on_rq 是指示进程是否被调度队列和运行队列管理，而非单纯的表示是否在调度队列的用于排队进程的数据结构中。

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

		/*
         * 如果还处于运行状态，即没有调用
		 * deactivate_task()/dequeue_task() 弹出队列
		 */

		if (prev->se.on_rq) {

			/* 需要更新时间属性 */

			update_curr(cfs_rq);

			/* 将当前运行的进程重新插入调度队列中 */

			__enqueue_entity(cfs_rq, &prev->se);
		}

		/*置空当前运行进程，如果 pick_next_task() 再次从被调度队列中选取，又会被设置*/

		cfs_rq->curr = NULL;
	}
}

在调度框架将当前运行的进程再次排队或移除后，需要根据进程属于不同的调度类选择一个最优的进程来使用CPU，其规则就是从最高优先级的调度类开始查找，如果存在一个这样的进程就将其选择为即将运行的进程。这通过 pick_next_task() 框架函数来实现的，对于 CFS 的实现为 pick_next_task_fair()。从实现可以看出内核优先选择实时进程，如果没有再选择普通进程，如果所有的普通进程都在休眠，那么才会选择各自的 swapper 零号进程。

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

	/* 优化：我们知道所有的进程都在CFS中，则我们直接调用该类的pick函数 */

	if (likely(rq->nr_running == rq->cfs.nr_running)) {
		p = fair_sched_class.pick_next_task(rq);
		if (likely(p))
			return p;
	}

	/*
     * 否则按系统约定的，从最高优先级的调度类开始，
	 * 依次遍历查找一个优先的进程用于调度
	 */

	class = sched_class_highest;
	for ( ; ; ) {
		p = class->pick_next_task(rq);
		if (p)
			return p;
		class = class->next;
	}

	/*永远不可能返回NULL，因为有idle进程的存在*/

    BUG();
}

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 {
		if (first_fair(cfs_rq)) {
			se = __pick_next_entity(cfs_rq);
			if (se->on_rq) {

				/*出队列*/

				__dequeue_entity(cfs_rq, se);

				/*重置开始运行时间*/

				se->exec_start = rq_of(cfs_rq)->clock;

				/*保存上次运行的总时间，两个的差值就是本地调度执行的时间*/

				se->prev_sum_exec_runtime = se->sum_exec_runtime;

				/*将调度队列的当前运行进程设置为新选择的进程*/

				cfs_rq->curr = se;
			}
		}
		cfs_rq = group_cfs_rq(se);
	} while (cfs_rq);

	return task_of(se);
}

接下来就是切换上下文，在切换前必须调用 clear_tsk_need_resched() 清零 TIF_NEED_RESCHED ，因为这个标志存在进程的内核栈上。而且有可能选择的进程还是当前运行的进程，所以可能并不会发送上下文切换，切换一旦完成，后续的代码就是在另外一个进程上下文中运行了，这看上去有些奇怪。上下文切换和硬件架构有直接关系，由 context_switch() 实现核心代码采用汇编编写，严格说来这部分不属于调度框架，主要有以下的动作：

1. 切换内存虚地址空间的切换。如果是用户进程才会真正发生虚地址的切换，而如果是内核线程，仅做一个标记，此后不再响应IPI来带的TLB刷新动作。
2. CPU硬件上下文的切换，主要是寄存器的状态的保存与恢复，不同CPU架构肯定实现不同。
3. 完成切换 finish_task_switch() ，如果需要会真正的回收虚地址内存描述符和进程描述符，因为只有完成切换后，才能真正的结束对他们的引用。

上下文切换的主干部分如下。

static void context_switch(struct rq *rq, struct task_struct *prev,
        struct task_struct *next)
{
	struct mm_struct *mm, *oldmm;

	mm = next->mm;
	oldmm = prev->active_mm;

	if (unlikely(!mm)) {

		/*内核线程，借用上一个用户进程的虚地址描述符*/

		next->active_mm = oldmm;
		atomic_inc(&oldmm->mm_count);

		/*进入惰性TLB模式，不想要TLB刷新（通过IPI）*/

		enter_lazy_tlb(oldmm, next);
	} else {

		/*用户进程，加载它的页表*/

		switch_mm(oldmm, mm, next);
	}

	if (unlikely(!prev->mm)) {

		/*
         * 还原借用的 mm_struct ，并存储在运行队列里，
		 * 待切换结束后才能尝试释放它（本次切换可能又被借用了）
         */

		prev->active_mm = NULL;
		rq->prev_mm = oldmm;
	}

	...

	/* 切换硬件上下文 */

	switch_to(prev, next, prev);

	/*从当前时间来观察，到此就是另一个进程了*/

	/* 解锁运行队列，并释放上一个进程的资源引用 */

	finish_task_switch(this_rq(), prev);
}

由于当前执行栈属于进程的页表上的某个物理页，所以即使进程已经死亡也不能在切换前释放，对于进程描述符也是一样。它们都将在切换结束后，在另一个进程上下文中被回收。

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

	rq->prev_mm = NULL;

	/*必须在解锁前获取状态*/

	prev_state = prev->state;

	...

	finish_lock_switch(rq, prev);

	/*减少一次引用，如果为0则被回收*/

	if (mm)
		mmdrop(mm);
	if (unlikely(prev_state == TASK_DEAD)) {

		/*如果上一个进程已经死亡，说明是最后一次切换，释放内核对他的引用，如果为0则回收*/

		put_task_struct(prev);
	}
}

下面给出 32位 x86 平台的硬件上下文实现的汇编注解（我只能看懂32位汇编，而且内联汇编很晦涩）

/*原始内联汇编*/
#define switch_to(prev,next,last)                               \
do {                                                            \
    unsigned long esi,edi;                                      \
    asm volatile(                                               \
            "pushfl\n\t"       /* Save flags */                 \
            "pushl %%ebp\n\t"                                   \
            "movl %%esp,%0\n\t"	   /* save ESP */               \
            "movl %5,%%esp\n\t"    /* restore ESP */            \
            "movl $1f,%1\n\t"      /* save EIP */               \
            "pushl %6\n\t"         /* restore EIP */            \
            "jmp __switch_to\n\t"                               \
            "1:\n\t"                                            \
            "popl %%ebp\n\t"                                    \
            "popfl"                                             \
            :"=m" (prev->thread.esp),"=m" (prev->thread.eip),	\
             "=a" (last),"=S" (esi),"=D" (edi)                  \
            :"m" (next->thread.esp),"m" (next->thread.eip),	    \
             "2" (prev), "d" (next)                             \
    );                                                          \
} while (0)

/*等效汇编注解*/
ENTRY(switch_to)
	movl prev, %eax			// 存储将要切出的进程描述符prev到eax中
	movl next, %edx			// 存储将要切入的进程描述符next到edx中
	pushfl					// 保存eflags的值到prev的内核栈中 (1)
	pushl %ebp				// 保存栈的基址，返回上层函数调用需要使用 (2)
	movl %esp, 484(%eax)	// 保存栈顶到prev->thread.esp字段中
	movl 484(%edx), %esp	// 恢复next->thread.esp的到栈顶，切换了内核的栈（#）@see copy_thread()
	movl $1f, 480(%eax)		// 将下次切回该进程时，运行的起始指令地址存入prev->thread.eip中
	pushl 480(%edx)			// 将next->thread.eip压栈，指示切换后的运行起始指令地址 如果是新创建进程，
							// 则是 @see ret_from_fork 汇编标签 @see copy_thread()
	jmp __switch_to			// 跳转到C函数，当函数返回时，马上切换（上一条指令压栈的指令处）
1:
	popl %ebp				// 切出后切回该处，恢复栈基址，对应(2)
	popfl					// 切出后切回该处，恢复eflags寄存器，对应(1)
	movl %eax, last			// 存储上次被切出的进程描述符 @see __switch_to()

切换利用了 jmp 指令会在函数（__switch_to()）返回时（执行 ret ）跳转到被压入栈的指令地址处（即 switch_to() 调用处的下一条代码或汇编标签 1处），另外在 movl 484(%edx), %esp 执行后，改变内核栈就意味着改变当前进程。如果此处引用 current 的话，那就已经指向 next 的 task_struct 结构了。

到此就算完成两个进程之间的调度切换了，但是由于现在内核是可并发、可抢占的，所以还要再次检查新运行进程的调度标志，因为内核可能又被抢占（其他用户在其他CPU上发送了 IPI 中断信号要求本CPU重新调度）。

唤醒进程

在进程让出CPU后，如果需要及时的再次让其运行，可以使用 try_to_wake_up() 主动唤醒它，并且如果以非 TASK_RUNNING 让出CPU的进程（从上面的主调度器的实现可获知），此时进程不处于排队状态，它永远不会获得运行的机会（不允许运行的进程，甚至连 kill -9 pid 都不会响应，也就没办法终止它们），除非主动唤醒它。此函数的主要功能就是再次将没有排队的进程重新插入相应的调度队列中，并更新统计信息等。

static int try_to_wake_up(struct task_struct *p, unsigned int state, int sync)
{
	int cpu, orig_cpu, this_cpu, success = 0;
	unsigned long flags;
	long old_state;
	struct rq *rq;

	...

	rq = task_rq_lock(p, &flags);
	old_state = p->state;

	/*不处于期望的状态*/

	if (!(old_state & state))
		goto out;

	/*已在调度队列中，仅重置为运行态标记即可*/

	if (p->se.on_rq)
		goto out_running;

	cpu = task_cpu(p);
	orig_cpu = cpu;
	this_cpu = smp_processor_id();

	/*即使正在运行，也重新入队列激活*/

	...

	/*更新运行队列的虚拟时钟，因为 activate_task() 需要一个准确的时间信息*/

	update_rq_clock(rq);

	/*激活进程，即再次插入到调度队列中*/

	activate_task(rq, p, 1);

	/*
	 * 调用进程所属的调度类的方法，
	 * 判断是否应该抢占进程的目标运行队列正在运行的进程
	 */
	check_preempt_curr(rq, p);
	success = 1;

out_running:
	p->state = TASK_RUNNING;
out:
	task_rq_unlock(rq, &flags);

	return success;
}

主要的动作就是更新目标运行进程的时间属性、排队进程、检查抢占等。需要注意的是除CFS调度类，唤醒这样的正在运行的进程可能需要重新插入到相应的调度队列中。update_rq_clock() 更新运行队列的时间属性，因为排队进程到队列中需要一个准确的时间信息，而此时时间中断没有正确更新运行队列的虚拟节拍，可能就会导致新排队的进程在计算虚拟时间时发生错误，从而导致不公平的对待所有的进程。activate_task() 排队进程到调度队列中，这与 deactivate_task() 一样是框架函数，CFS调度类由 enqueue_task_fair() 实现。

static void activate_task(struct rq *rq, struct task_struct *p, int wakeup)
{
	/*如果被唤醒的进程是非中断状态，则修改统计*/

	if (p->state == TASK_UNINTERRUPTIBLE)
		rq->nr_uninterruptible--;

	/*
	 * 1. 入队列（根据被唤醒进程的调度类的具体实现而定），
	 * 2. 累加运行队列的总就绪进程数和总负载
	 */

	p->sched_class->enqueue_task(rq, p, wakeup);
	p->se.on_rq = 1;

	rq->nr_running++;
	rq->load += p->se.load.weight;
}

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

	for_each_sched_entity(se) {

		/*激活正在运行的进程将忽略*/

		if (se->on_rq)
			break;
		cfs_rq = cfs_rq_of(se);

		/*
		 * 更新进程的虚拟时钟
		 */

		update_curr(cfs_rq);

		if (wakeup) {

			/*从休眠中唤醒目标进程，为了排队计算一个新的虚拟时间*/

			place_entity(cfs_rq, se, 0);
		}

		/*入队列*/

		if (se != cfs_rq->curr)
			__enqueue_entity(cfs_rq, se);

		/*更新调度队列的统计信息*/

		cfs_rq->load += se->load.weight;
		cfs_rq->nr_running++;
		se->on_rq = 1;

		wakeup = 1;
	}
}

在排队中最重要的函数就是 place_entity() ，其名字有些歧义，它的主要功能就是为新排队的进程计算一个合适的、利于公平调度的虚拟时间，以使其在红黑树中有一个正确的位置。
因为休眠或新的进程它的虚拟时间一直没有向前推进，而已排队的进程虚拟时间却一直在推进，所以当休眠或新进程插入红黑树时，势必会很靠前，即使他运行许多周期之后还是小于其他进程的虚拟时间，这样肯定会将其他进程饿死，所以对休眠的进程进行一些运行时间补偿，但又不能将其他进程饿死，是该函数的核心思路。内核以当前调度队列的最小虚拟时间为基础，根据配置特性在该值上加减一小段时间来调整新排队进程的虚拟时间。

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

	vruntime = cfs_rq->min_vruntime;

	/*根据用户通过 sysctl 设置的调度特性 来补偿唤醒进程虚拟时间 */

	if (sched_feat(TREE_AVG)) {

		/*树中最大和最小虚拟时间的平均值*/

		struct sched_entity *last = __pick_last_entity(cfs_rq);
		if (last) {
			vruntime += last->vruntime;
			vruntime >>= 1;
		}
	} else if (sched_feat(APPROX_AVG) && cfs_rq->nr_running) {

		/*树中所有权重下平分一定调度延迟的时间片*/

		vruntime += sched_vslice(cfs_rq)/2;
	}

	/*新创建的进程，责罚一个平均延迟*/

	if (initial && sched_feat(START_DEBIT))
		vruntime += sched_vslice_add(cfs_rq, se);

	if (!initial) {

		/* 休眠进程稍微补偿一些*/

		if (sched_feat(NEW_FAIR_SLEEPERS) && entity_is_task(se))
			vruntime -= sysctl_sched_latency;

		/* 对休眠进程尽可能的责罚，取最大值 */

		vruntime = max_vruntime(se->vruntime, vruntime);
	}

	se->vruntime = vruntime;
}

创建进程

新创建的进程还从来没有参与过调度，所以需要特殊的函数来初始化、首次唤醒和切换，内核分别用 sched_fork() 、 wake_up_new_task() 和 schedule_tail() 来处理这些特殊情况。

内核通过从父进程那里继承一些调度属性，来初始化新进程的调度属性，通过 sched_fork() 完成。一般情况下，子进程都和父进程在同一个CPU上运行，除非此时有空闲的CPU或CPU处于严重的不平衡，才会选择出一个新的合适的CPU作为子进程的目标CPU；由于子进程继承了父进程的虚拟时间，当子进程被迁移到其他CPU上后，其他虚拟时间就和所在的调度队列的最小虚拟时间不匹配，如果不调整就会发生不公平的调度，内核会以两个调度队列的最小虚拟时间差来调整子进程虚拟时间。在父进程运行的过程中，有时会发生优先级临时提升的情况，比如正在处理实时互斥量，为了子进程不会继承这个临时的状态来以提升自己的优先级而造成安全隐患，内核将子进程的动态优先级还原。以上这两点就是 sched_fork() 的主要工作。

void sched_fork(struct task_struct *p, int clone_flags)
{
	/*如果没有负载均衡，则新进程与父进程在同一个CPU上运行*/
	int cpu = get_cpu();

	/*初始化调度实体*/
	p->se.exec_start = 0;
	p->se.sum_exec_runtime = 0;
	p->se.prev_sum_exec_runtime = 0;
	p->se.on_rq = 0;

	/*保证不会被意外的唤醒，因为它已在运行状态（假的）*/
	p->state = TASK_RUNNING;

#ifdef CONFIG_SMP
	/*自平衡，选择一个负载小的CPU来作为新进程的CPU*/
	cpu = sched_balance_self(cpu, SD_BALANCE_FORK);
#endif

	/*调整虚拟时间*/
	struct cfs_rq *old_cfsrq = &task_rq(p)->cfs;
	struct cfs_rq *new_cfsrq = &cpu_rq(cpu)->cfs;

	/* 从上层函数中继承父进程的虚拟时间 ：
	 *		p->se.vruntime = parent->se.vruntime;
	 * 由于新调度队列与原调度队列虚拟时间可能不同步
	 * 调整这个差值，防止不公平发生
	 */
	p->se.vruntime -= old_cfsrq->min_vruntime -
					 new_cfsrq->min_vruntime;

	/*设置CPU*/
	task_thread_info(p)->cpu = cpu;

	/*继承原始优先级*/
	p->prio = current->normal_prio;
	if (!rt_prio(p->prio))
		p->sched_class = &fair_sched_class;

	/*
	 * 配合首次切换
	 * @see finish_lock_switch() 对 运行队列 解锁时 启用抢占需要减1
	 */
	task_thread_info(p)->preempt_count = 1;
	put_cpu();
}

通过 wake_up_new_task() 进行首次唤醒，将进程排队到调度队列是主要的任务，每个调度类可能不同实现，对于没有 实现 task_new() 的调度类就使用 调度框架 函数 activate_task() 进行简单的入队列操作，否则使用特有的调度类 task_new() 来处理。对于CFS有 task_new_fair() 来处理普通进程的首次入队列操作。在入队列后，由于子进程可能被迁移到其他CPU，而其他CPU上正在运行的进程比此子进程的优先级低，所以再使用调度框架函数 check_preempt_curr() 来检查和处理这种情况。 task_new_fair() 主要完成入队列，和在父子进程返回用户态时，是否应该让子进程优先于父进程运行，默认是子进程滞后，那么它从父进程继承而来的虚拟时间会有一个增加（责罚），但如果配置（sysctl_sched_child_runs_first)需要让子进程先运行，则简单的交换它们的虚拟时间即可，当然这一切只会在父子进程将在同一个CPU上运行时会这样去考虑。

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);
	/*插入新进程到运行队列需要新的时钟信息，更新运行队列的时钟信息*/
	update_rq_clock(rq);

	/*计算动态优先级，基本上只会影响实时进程*/
	p->prio = effective_prio(p);

	/*入队列*/
	if (!p->sched_class->task_new || !current->se.on_rq) {
		activate_task(rq, p, 0);
	} else {
		p->sched_class->task_new(rq, p);
		rq->nr_running++;
		rq->load += p->se.load.weight;
	}
	/*检查是否应该抢占目标CPU上的当前运行进程*/
	check_preempt_curr(rq, p);
	task_rq_unlock(rq, &flags);
}

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

	/*下面计算虚拟运行时间，所以更新调度队列的时钟信息*/
	update_curr(cfs_rq);
	/*计算子进程的虚拟时间，有一定的时间惩罚，即默认是子进程滞后父进程运行*/
	place_entity(cfs_rq, se, 1);
	/*如果配置需要，则将子进程放置在父进程前运行，简单交换虚拟运行时间即可*/
	if (sysctl_sched_child_runs_first && this_cpu == task_cpu(p) &&
			curr && curr->vruntime < se->vruntime) {
		swap(curr->vruntime, se->vruntime);
	}
	/*入队列*/
	enqueue_task_fair(rq, p, 0);
	/* 抢占当前运行的进程，
	 * CFS类的进程在 fork() 之后肯定会抢占子进程所在队列上的运行进程
	 * 虽然可能被抢占的进程又会立马被调度（比如被抢占的进程是一个实时进程）
	 */
	resched_task(rq->curr);
}

通过 schedule_tail() 来完成第一切换，虽然这个函数非常的简单，但调用它的这个过程一个非常特别的事情。虽然子进程复制了父进程的所有状态，但是调度相关的信息却是特有的，从这个方面的来看，子进程是从来没有调度过的，所以不能像不同切换一样简单的将其上下文恢复到上次切换的状态，因为它根本就没有切换过。内核通过在 do_fork() 创建子进程的过程中给其标识一个特殊的标志 TIF_FORK（存储在 struct thread_info 的 flags 字段中），在首次进程调用 switch_to() 进程切换上下文时，内核一旦发现进程带有此标志（使用的是 test_and_clear_bit() 类似的操作），就强制跳转到汇编函数 ret_from_fork() 来完成子进程首次运行并返回用户态或内核态的任务。在此函数中调用 schedule_tail() 完成切换后的工作，而对于用户态的子进程 ret_from_fork() 强制设置 eax 为 0 值，这个寄存器是系统调用存储返回值的地方，在此处就是 fork() 系统调用的返回值，所以就造了 一次系统调用 返回两个不同的值，父进程返回子进程的进程号，子进程返回 0 。这样在用户态就形成了一个分叉的逻辑流，这也是 fork 命名的来源；对于内核态的线程，ret_from_fork() 就抹去内核栈的原来数据（因为此时内核栈还保存了父进程的状态）和去装载指定的内核线程回调函数，然后执行：

ENTRY(ret_from_fork)
	pushl %eax
	call schedule_tail
	GET_THREAD_INFO(%ebp)
	popl %eax
	pushl $0x0202			# Reset kernel eflags
	popfl
	jmp syscall_exit        # schedule_tail 执行完毕后 直接跳转到 系统调用退出 片段 返回用户态
END(ret_from_fork)

void schedule_tail(struct task_struct *prev)
{
	struct rq *rq = this_rq();

	/*prev 为让出CPU给子进程运行的进程*/
	finish_task_switch(rq, prev);
	if (current->set_child_tid)
		put_user(task_pid_vnr(current), current->set_child_tid);
}

进程迁移

内核通过一个内核线程来辅助进程迁移的完成，从而辅助负载均衡。

1. 初始化

内核通过通知链数据结构，在CPU启动后回调如下函数来启动迁移线程：

void __init migration_init(void)
{
	void *cpu = (void *)(long)smp_processor_id();
	/*本地CPU已经启动，所以直接调用*/
	migration_call(&migration_notifier, CPU_UP_PREPARE, cpu);
	migration_call(&migration_notifier, CPU_ONLINE, cpu);
	/*注册通知链回调，待内核完成额定初始化后，其他CPU启动时，回调执行*/
	register_cpu_notifier(&migration_notifier);
}

1. 通知链

static int __cpuinit
migration_call(struct notifier_block *nfb, unsigned long action, void *hcpu)
{
	struct task_struct *p;
	int cpu = (long)hcpu;
	unsigned long flags;
	struct rq *rq;

	switch (action) {
		...
	case CPU_UP_PREPARE:
		/*启动准备就绪时执行此路径*/
		p = kthread_create(migration_thread, hcpu, "migration/%d", cpu);
		if (IS_ERR(p))
			return NOTIFY_BAD;
		/*只为本CPU的迁移服务，所以绑定在本CPU上*/
		kthread_bind(p, cpu);
		rq = task_rq_lock(p, &flags);
		/*设置为最低优先级的实时进程*/
		__setscheduler(rq, p, SCHED_FIFO, MAX_RT_PRIO-1);
		task_rq_unlock(rq, &flags);
		cpu_rq(cpu)->migration_thread = p;
		break;

	case CPU_ONLINE:
		/*完全启动后执行此路径*/
		wake_up_process(cpu_rq(cpu)->migration_thread);
		break;
		...
	}
}

1. 迁移线程

通过迁移队列来收集迁移的请求。

static int migration_thread(void *data)
{
	int cpu = (long)data;
	struct rq *rq;

	rq = cpu_rq(cpu);
	...
	while (!kthread_should_stop()) {
		struct migration_req *req;
		struct list_head *head;

		spin_lock_irq(&rq->lock);

		/*迁移线程还负载异步的负载均衡
		 *该标志会在 scheduler() --> load_balance() 时设置
		 */
		if (rq->active_balance) {
			active_load_balance(rq, cpu);
			rq->active_balance = 0;
		}

		head = &rq->migration_queue;
		/*没有迁移请求，则休眠等待*/
		if (list_empty(head)) {
			spin_unlock_irq(&rq->lock);
			schedule();
			set_current_state(TASK_INTERRUPTIBLE);
			continue;
		}
		/*依次弹出请求处理*/
		req = list_entry(head->next, struct migration_req, list);
		list_del_init(head->next);

		spin_unlock(&rq->lock);
		/*迁移*/
		__migrate_task(req->task, cpu, req->dest_cpu);
		local_irq_enable();
		/*通知等待迁移的路径，迁移已完成*/
		complete(&req->done);
	}
	return 0;
	...
}

1. 请求迁移

static int
migrate_task(struct task_struct *p, int dest_cpu, struct migration_req *req)
{
	struct rq *rq = task_rq(p);

	/*
	 * 如果没有调度排队，且进程没有在原CPU上运行，那么没有竞争，直接转移到目标CPU即可。
	 */
	if (!p->se.on_rq && !task_running(rq, p)) {
		set_task_cpu(p, dest_cpu);
		return 0;
	}

	/*初始化请求*/
	init_completion(&req->done);
	req->task = p;
	req->dest_cpu = dest_cpu;
	/*排队请求*/
	list_add(&req->list, &rq->migration_queue);

	return 1;
}

1. 处理迁移

static int __migrate_task(struct task_struct *p, int src_cpu, int dest_cpu)
{
	struct rq *rq_dest, *rq_src;
	int ret = 0, on_rq;

	if (unlikely(cpu_is_offline(dest_cpu)))
		return ret;

	rq_src = cpu_rq(src_cpu);
	rq_dest = cpu_rq(dest_cpu);

	double_rq_lock(rq_src, rq_dest);
	/* Already moved.
	 * 加锁后再次检查 因为迁移请求时异步的，进程已不在原CPU上运行
	 * 那么迁移请求就是失效的
	 */
	if (task_cpu(p) != src_cpu)
		goto out;
	/* Affinity changed (again).
	 * 迁移进程 已不再运行 在目标CPU上运行
	 * 那么迁移请求就是无效的
	 */
	if (!cpu_isset(dest_cpu, p->cpus_allowed))
		goto out;

	/*原进程在运行队列中，则需要出队列*/
	on_rq = p->se.on_rq;
	if (on_rq)
		deactivate_task(rq_src, p, 0);

	/*更改进程的运行CPU*/
	set_task_cpu(p, dest_cpu);
	/*原进程已排队，那么相应的，应该在迁移后，主动排队到运行队列中
	 *如果是一个高优先级的进程，还应该抢占目标CPU当前运行的进程
	 */
	if (on_rq) {
		activate_task(rq_dest, p, 0);
		check_preempt_curr(rq_dest, p);
	}
	ret = 1;
out:
	double_rq_unlock(rq_src, rq_dest);
	return ret;
}

上述的算法核心遵从以下的事实，迁移进程时，由该进程所在的运行队列的 CPU 上辅助内核线程来完成，因为我们要保证迁移时，被迁移的进程不能处于运行状态，即使中断上下文也不行，因为中断可借用被迁移进程的内核栈。而该辅助线程永远都不会移动到其他CPU上运行，只要唤醒了该线程，那么就可以安全的移动被迁移进程了。

额外的调度框架函数

1. 手动让出 CPU 回调

系统为了支持用户态手动让出 CPU，而实现 sched_yield() 系统调用，会调用 调度类回调 yield_task() （如果需要实现该函数的话）。

对于 CFS ，其实现如下：

static void yield_task_fair(struct rq *rq)
{
	struct task_struct *curr = rq->curr;
	struct cfs_rq *cfs_rq = task_cfs_rq(curr);
	struct sched_entity *rightmost, *se = &curr->se;

	/* 我们是唯一的可运行进程，则直接返回，因为我们无论如何操作我们都会接着运行 */
	if (unlikely(cfs_rq->nr_running == 1))
		return;
	/* 找到当前状态下最晚被调度的进程，即红黑树的最右边的进程 */
	rightmost = __pick_last_entity(cfs_rq);
	/* 我们已经运行了太久，本来就会成为下一轮最晚调度的进程，则直接返回 */
	if (unlikely(rightmost->vruntime < se->vruntime))
		return;
	/*仅需要晚于最晚调度的进程既可以*/
	se->vruntime = rightmost->vruntime + 1;
}

上面的一些操作就是为了能是主动让出CPU的进程在当前状态下最晚被调度，即出入队列后能位于红黑树的最右边。

1. 重置调度信息回调

系统为了实现修改调度策略或优先级，比如 sched_setscheduler() 等，会调用 调度类回调 set_curr_task() 来重置调度信息。

对于 CFS ，其实现如下：

static void set_curr_task_fair(struct rq *rq)
{
	struct sched_entity *se = &rq->curr->se;
	for_each_sched_entity(se) {
		/*更新开始运行时间*/
		se->exec_start = rq_of(cfs_rq)->clock;
		/*将调度队列的当前运行进程设置为新选择的进程*/
		cfs_rq->curr = se;
		/*保存上次运行的总时间*/
		se->prev_sum_exec_runtime = se->sum_exec_runtime;
	}
}

相关系统调用

nice()

nice() 系统调用，改变友好值，传递负值为提升优先级（需要管理员权限），从而变得对其他进程不友好，这个也是该系统调用的命名由来。其参数范围为 -40 ~ 40，不在该范围的值，会被截断到该范围。最终的核心实现为 set_user_nice()

void set_user_nice(struct task_struct *p, long nice)
{
	int old_prio, delta, on_rq;
	unsigned long flags;
	struct rq *rq;

	/*锁定运行队列*/
	rq = task_rq_lock(p, &flags);
	/*由于要改变进程在调度列队中的位置，所以需要更新时钟信息*/
	update_rq_clock(rq);
	/*
	 * 如果是实时进程 需要通过 sched_setscheduler() 来改变
	 * 我们仅改变静态优先级，直到改变 调度策略 后生效
	 */
	if (task_has_rt_policy(p)) {
		p->static_prio = NICE_TO_PRIO(nice);
		goto out_unlock;
	}
	on_rq = p->se.on_rq;
	if (on_rq) {
		/*出队列，减去总的权重*/
		dequeue_task(rq, p, 0);
		dec_load(rq, p);
	}

	/*重新计算动、静态优先级，以及权重*/
	p->static_prio = NICE_TO_PRIO(nice);
	set_load_weight(p);
	old_prio = p->prio;
	p->prio = effective_prio(p);
	delta = p->prio - old_prio;

	if (on_rq) {
		/*如果以前在队列上，则重新入队列，并增加总的权重*/
		enqueue_task(rq, p, 0);
		inc_load(rq, p);
		/*
		 * 如果进程优先级提升了 或 优先级降低了但是正在被执行，
		 * 则需要抢占目标运行队列上的进程
		 */
		if (delta < 0 || (delta > 0 && task_running(rq, p)))
			resched_task(rq->curr);
	}
out_unlock:
	task_rq_unlock(rq, &flags);
}

getpriority() 和 setpriority()

setpriority() 是对 nice() 的扩展，可以设置一组进程，底层实现都是 set_user_nice()。

getpriority() 返回（一组）进程中最高优先级的 nice 值的相应值，即最小 nice 值。这个系统调用的返回值并不是原始的 nice 值，因为 nice 值是 一个 -20 ~ 19 之间的值，这和系统调用返回负值来指示出错有冲突，所以我们使用 20 减去这个值 得到 1 ~ 40 这个z转换后的返回值。

这两个函数实现涉及了很多内核进程组织的知识，暂时略过这些。

sched_getaffinity() 和 sched_setaffinity()

该组合的系统调用用于修改进程的CPU亲和性，cpumask_t 掩码是一个位图，进程允许在哪些CPU上运行，就置位那个代表CPU编号的位。

sched_getaffinity() 实现相对简单：

long sched_getaffinity(pid_t pid, cpumask_t *mask)
{
	...
	/*将当前的*/
	cpus_and(*mask, p->cpus_allowed, cpu_online_map);
	...
}

sched_setaffinity() 实现较为复杂，我们仅列出核心代码：

long sched_setaffinity(pid_t pid, cpumask_t *mask)
{
	...
	/*获取当前系统可以启动的CPU位图*/
	cpus_allowed = cpuset_cpus_allowed(p);
	/*移除无效位*/
	cpus_and(new_mask, new_mask, cpus_allowed);
 again:
	retval = set_cpus_allowed(p, new_mask);
	if (!retval) {
		/*再次查看，确保位图的有效性，因为系统可以热插拔CPU，修改了有效的系统CPU位图*/
		cpus_allowed = cpuset_cpus_allowed(p);
		if (!cpus_subset(new_mask, cpus_allowed)) {
			new_mask = cpus_allowed;
			goto again;
		}
	}
}

int set_cpus_allowed(struct task_struct *p, cpumask_t new_mask)
{
	struct migration_req req;
	unsigned long flags;
	struct rq *rq;
	int ret = 0;

	rq = task_rq_lock(p, &flags);
	/*与在线 CPU 位图没有交集*/
	if (!cpus_intersects(new_mask, cpu_online_map)) {
		ret = -EINVAL;
		goto out;
	}

	/*替换当前位图*/
	p->cpus_allowed = new_mask;
	/*
	 * 如果修改后 当前进程可执行位图 不包含当前 CPU，则立马迁移
	 */
	if (cpu_isset(task_cpu(p), new_mask))
		goto out;

	/*发起迁移请求*/
	if (migrate_task(p, any_online_cpu(new_mask), &req)) {
		task_rq_unlock(rq, &flags);
		/*唤醒迁移辅助内核线程*/
		wake_up_process(rq->migration_thread);
		/*等待迁移完成*/
		wait_for_completion(&req.done);
		/*一些清理工作*/
		tlb_migrate_finish(p->mm);
		return 0;
	}
out:
	task_rq_unlock(rq, &flags);

	return ret;
}

sched_getscheduler() 和 sched_setscheduler()

获取和设置当前的调度策略，调度策略有如下的类型： SCHED_FIFO、SCHED_RR、SCHED_NORMAL、SCHED_BATCH 和 SCHED_IDLE。分别对应实时调度类、完全公平调度类以及空闲调度类。

sched_getscheduler() 只是简单的从 struct task_struct 中的 policy 字段获取值。

sched_setscheduler() 实现比较复杂，这个函数在改变调度策略的同时，还可以可以设置优先级。先介绍改变的核心属性的实现：

static void
__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)
{
	BUG_ON(p->se.on_rq);

	p->policy = policy;
	switch (p->policy) {
	case SCHED_NORMAL:
	case SCHED_BATCH:
	case SCHED_IDLE:
		/*可以看出来，用户态的进程是不允许使用 idle_sched_class 调度类来调度的*/
		p->sched_class = &fair_sched_class;
		break;
	case SCHED_FIFO:
	case SCHED_RR:
		p->sched_class = &rt_sched_class;
		break;
	}

	/*重置各个优先级属性*/
	p->rt_priority = prio;
	p->normal_prio = normal_prio(p);
	/*防止优先级翻转，如果有当前进程是一个实时互斥量的等待者，则临时提升优先级
	 * 关于优先级翻转，请查看相关方面的文章
	 */
	p->prio = rt_mutex_getprio(p);
	/*重置权重*/
	set_load_weight(p);
}

这个函数之上还有很多工作需要做，比如权限检查、参数校验、进程重新排队等，下面我们仅列出核心的进程调度队列方面的操作。

int sched_setscheduler(struct task_struct *p, int policy,
		       struct sched_param *param)
{
	rq = task_rq_lock(p);
	/*更新时钟，出入队列需要使用新的时钟信息*/
	update_rq_clock(rq);
	on_rq = p->se.on_rq;
	running = task_current(rq, p);
	if (on_rq) {
		/*因为可以设置优先级，并且可能改变调度类，所以需要重新排队，故先出队列*/
		deactivate_task(rq, p, 0);
		if (running)
			/*收集进程的运行时间*/
			p->sched_class->put_prev_task(rq, p);
	}

	/*更新调度类和优先级*/
	oldprio = p->prio;
	__setscheduler(rq, p, policy, param->sched_priority);

	if (on_rq) {
		/*反向的操作，如果以前处于排队状态，那么修改后也应该是排队状态*/
		if (running)
			/*设置启动时间*/
			p->sched_class->set_curr_task(rq);
		/*重新排队*/
		activate_task(rq, p, 0);
		if (running) {
			/*如果设置后，优先级减低，那么应立即让出CPU的使用权*/
			if (p->prio > oldprio)
				resched_task(rq->curr);
		} else {
			/*否则应该检测是否已经太久没有运行，以抢占当前运行进程*/
			check_preempt_curr(rq, p);
		}
	}
	task_rq_unlock(rq);
}

顺便介绍一下 底层一样实现的 sched_getparam() 和 sched_setparam() ，这两个系统调用唯一不同，是不能设置调度策略，仅能设置优先级。

sched_yield()

用户态进程可以通过此系统调用手动让出CPU，起实现很简单，主要就是手动调用一次 调度函数 既可以。

asmlinkage long sys_sched_yield(void)
{
	struct rq *rq = this_rq_lock();
	/*调用调度类 让出CPU 回调*/
	current->sched_class->yield_task(rq);
	_raw_spin_unlock(&rq->lock);
	preempt_enable_no_resched();
	/*手动调度一次*/
	schedule();
	return 0;
}