Linux CFS 调度器 (1)：概述

1. 前言

限于作者能力水平，本文可能存在谬误，因此而给读者带来的损失，作者不做任何承诺。

2. CFS 调度器

2.1 概述

CFS，是 Completely Fair Scheduler 的缩写，翻译过来就是 完全公平调度器，由 Ingo Molnar 实现，在 Linux 2.6.23 中合入的新的 “桌面” 进程调度器。

CFS 调度器 80% 的设计可以用一句话来概括：CFS 基本上是在真实硬件上模拟了一个理想、精确的多任务 虚拟 CPU。我们将这个虚拟 CPU 的运行能力定义为 1，假定当前有 nr_running 个任务在虚拟 CPU上运行，则每个任务精准的占用虚拟 CPU 1/nr_running 的运行能力(或 运行时间)。例如有 2 个任务在运行，假定将 虚拟 CPU 的运行能力设定为 100%，那么每个任务占用 虚拟 CPU 50% 的运行能力(或 运行时间)。为了描述方便，在这里先将任务占用的 虚拟 CPU 的运行时间，称作 虚拟运行时间(virtual runtime)，这和后文的 物理 CPU 的 物理运行时间 相对应。

在 CFS 调度器中，并非真的将 物理 CPU 的物理运行能力(或 物理时间)平均分配给所有可运行任务，CFS 仍然要处理任务优先级：即优先级更高的任务，仍然会分配更多 物理 CPU 的物理运行时间 给它们。这看起来似乎和 CFS 调度器的 完全公平调度 宗旨相矛盾，但事实是，CFS 调度器只是尽量保证每个任务占用的 虚拟运行时间(virtual runtime) 一样，而任务占用的 物理运行时间，仍然由任务优先级来体现。正如世界不可能完全公平一样，在 CFS 调度器中，分配给每个任务的 虚拟运行时间(virtual runtime) ，CFS 也只是尽量保证它们一致，不可能达到理想状态的完全一致。

2.2 一些实现细节

在 CFS 调度器中，虚拟运行时间(virtual runtime) 通过每个任务的 p->se.vruntime（以纳秒单位）来表示和跟踪，这样，就可以准确地标记时间戳并测量任务应该获得的预期 CPU 时间。其中，p 指向一个 struct task_struct 结构体。

/* include/linux/sched.h */

struct sched_entity {
	...
	/*
	 * 进程的虚拟运行时间 = 进程的实际运行时间 / 相对权重
	 *
	 * 进程的 实际运行时间 是一段一段的，所以进程的 虚拟运行时间 也是一段一段增长的。
	 *
	 * 进程的 虚拟运行时间 还会在 进程入队时 与 运行队列中的最小虚拟时间 相比较，如
	 * 果更小的话会直接进行增加，并不对应 实际的运行时间。为什么要这么做呢？因为有的
	 * 进程可能会因长时间睡眠，导致其 虚拟运行时间 小于运行队列中所有进程中的 最小虚
	 * 拟运行时间，这样的进程一旦运行起来，会因为其 虚拟运行时间 小，占据 CPU 的时间
	 * 就会长，对其它进程就不公平了。
	 */
	u64				vruntime;
	...
};

struct task_struct {
	...
	const struct sched_class	*sched_class; /* 如果任务使用 CFS 调度，则为 &fair_sched_class */
	struct sched_entity		se; /* CFS 类进程调度参数 */
	...
};

在理想的 虚拟 CPU 上，在任何时刻，所有任务 虚拟运行时间值 p->se.vruntime 都保持相同的值。

CFS 调度器，其任务选择逻辑基于 p->se.vruntime 值：CFS 始终尝试运行具有最小 p->se.vruntime 值的任务（即到目前为止虚拟执行时间(virtual runtime)最小的任务）。CFS 始终尝试在可运行任务之间平均分配 虚拟 CPU时间 ，尽可能接近理想的多任务 虚拟 CPU。

CFS 设计的其余部分大部分都脱离了这个非常简单的概念，有一些其它附加修饰，如任务的 nice 值，各种识别睡眠任务的算法等等。

2.3 运行队列：红黑树

CFS 不同于以往的调度器，它不使用运行队列以往的旧数据结构，而是使用按时间排序的 红黑树(rbtree) 来构建未来任务执行的时间线，而它之前 O(1) 调度器使用位图进行任务调度管理。

CFS 还维护 rq->cfs.min_vruntime 值，该值是一个单调递增值，用于跟踪运行队列中所有任务中的最小 vruntime。该值用于尽可能将新激活的调度实体(struct sched_entity，即任务)放置在红黑树的左侧。由于该值一直使用 min_vruntime 单调递增累加，所以也可用来跟踪系统完成的工作总量。

/* kernel/sched/sched.h */

/* CFS-related fields in a runqueue */
struct cfs_rq {
	...
	u64 min_vruntime; /* CFS 调度算法 运行队列中 进程 的 最小 虚拟运行时间 */
	...
};

/*
 * This is the main, per-CPU runqueue data structure.
 *
 * Locking rule: those places that want to lock multiple runqueues
 * (such as the load balancing or the thread migration code), lock
 * acquire operations must be ordered by ascending &runqueue.
 */
struct rq {
	...
	struct cfs_rq cfs;
	...
};

DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues); /* 每 CPU 的运行队列 */

运行队列的权重通过 rq->cfs.load 值进行统计，该值是运行队列上排队的任务权重的总和：

/* kernel/sched/sched.h */

/* CFS-related fields in a runqueue */
struct cfs_rq {
	/*
	 * 运行队列的权重, 等于其上所有进程的权重之和。
	 * 进程在入队出队时，也会相应地从运行队列中加上减去其自身的权重。
	 */
	struct load_weight load;
	...
};

CFS 维护一个按时间排序的 红黑树(rbtree)，即所有可运行的任务都按 p->se.vruntime 键排序，然后CFS 从这棵树中挑选最左边(即 p->se.vruntime 最小)的任务执行。随着时间往后推移，执行的任务越来越多地被放入树中，执行时间更少的任务逐渐往红黑树左边移动，执行时间更多的任务往红黑树右边移动，如此循环往复。

2.4 一些特征

CFS 使用纳秒级精度，对任务的虚拟运行时间的统计，它不依赖于 jiffies 或 HZ 值。因此，CFS 调度器没有像以前的调度器那样的时间片概念，也没有任何启发式方法。不使用启发式方法这一点，这使得 CFS 不容易受到针对启发式调度的攻击。

CFS 对任务 nice 值 和 SCHED_BATCH 策略任务 的处理比以往的调度器更优。

CFS 对 SMP 架构下的负载均衡代码进行了清理，使得负载均衡逻辑更加简单。

2.5 调度策略

CFS 实现了 3 种调度策略：

• SCHED_NORMAL，以往也叫 SCHED_OTHER：用于常规任务。
• SCHED_BATCH：适用于没有用户交互行为的后台进程，用户对该类进程的响应时间要求不高，但对吞吐量要求较高，因此调度器会在完成所有 SCHED_NORMAL 的任务之后让该类任务不受打扰地跑上一段时间，这样能够最大限度地利用缓存。
• SCHED_IDLE：这类调度策略被用于系统中优先级最低的任务，只有在没有任何其他任务可运行时，调度器才会将运行该类任务。

2.6 调度器类别

Linux 同时支持多种类型调度器类别，CFS 调度只是其中的一种，实现在文件 sched/fair.c 中。而像其它的调度类别如实现 SCHED_FIFO 和 SCHED_RR 调度策略的实时调度器，实现在文件 sched/rt.c 中。

调度类是通过 struct sched_class 结构体实现的，该结构体包含一些列回调，在发生特定事件时被调用。struct sched_class 结构体内容如下：

/* kernel/sched/sched.h */

struct sched_class {
	const struct sched_class *next;

	/*
	 * 将进程 @p 放入运行队列 @rq 。
	 * 在任务进入可运行状态时调用。
	 * 它将调度实体（任务）放入红黑树中，并递增 nr_running 变量。
	 */
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
	/*
	 * 将进程 @p 移出运行队列 @rq 。
	 * 当任务不再可运行时，将调用此函数以将相应的调度实体移出红黑树，并递减 
	 * nr_running 变量。
	 */
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
	/*
	 * 当前进程主动让出 CPU , 即移出运行队列，但 其状态依然是 runnable ，
	 * 然后将另一进程加入运行队列。
	 * 可通过系统调用 sys_sched_yield() 触发。
	 */
	void (*yield_task) (struct rq *rq);
	/* 当前进程主动让出 cpu 给进程组内进程 @p */
	bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

	/*
	 * 被唤醒进程的抢占逻辑：检查 @p 是否会抢占 @rq 中当前正在运行的进程. 
	 * 通常情况下是在 @p 进入 runnable 态时，检查 @p 是否会抢占当前正在运
	 * 行的进程。
     */
	void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);

	/*
	 * It is the responsibility of the pick_next_task() method that will
	 * return the next task to call put_prev_task() on the @prev task or
	 * something equivalent.
	 *
	 * May return RETRY_TASK when it finds a higher prio class has runnable
	 * tasks.
	 */
	/* 
	 * 挑选下一可执行进程, 且以 @prev 为参数, 调用 put_prev_task() . 
	 *
	 * 通常返回挑选的下一可执行进程, 但当发现更高优先级调度类别有可运行进程时, 
	 * 返回 RETRY_TASK .
	 */ 
	struct task_struct * (*pick_next_task) (struct rq *rq,
						struct task_struct *prev,
						struct rq_flags *rf);
	void (*put_prev_task) (struct rq *rq, struct task_struct *p);

#ifdef CONFIG_SMP
	/*
	 * 为进程 @p 选择运行队列。
	 * 当系统调用 fork() + exec() 创建一个新的进程时，在 SMP 系统中
	 * 选择一个合理的 runqueue 来将该进程入队。Scheduler 此时需要考
	 * 虑 负载均衡 问题。
	 */
	int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
	void (*migrate_task_rq)(struct task_struct *p);

	void (*task_woken) (struct rq *this_rq, struct task_struct *task);

	/* 设置进程的 cpu affinity */
	void (*set_cpus_allowed)(struct task_struct *p, 
				 const struct cpumask *newmask);

	void (*rq_online)(struct rq *rq); /* cpu online */
	void (*rq_offline)(struct rq *rq); /* cpu offline */
#endif

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

	/*
	 * The switched_from() call is allowed to drop rq->lock, therefore we
	 * cannot assume the switched_from/switched_to pair is serliazed by
	 * rq->lock. They are however serialized by p->pi_lock.
	 */
	void (*switched_from) (struct rq *this_rq, struct task_struct *task); /* @task 从 当前调度类别 切换到 其他调度类别 */
	void (*switched_to) (struct rq *this_rq, struct task_struct *task); /* @task 从 其他调度类别 切换到 当前调度类别 */
	void (*prio_changed) (struct rq *this_rq, struct task_struct *task, /* 优先级变更时的抢占逻辑 */
			     int oldprio);

	/* 获取分配给进程 @task 的时间片 (sys_sched_rr_get_interval()) */
	unsigned int (*get_rr_interval) (struct rq *rq, 
					 struct task_struct *task);

	/* 更新当前进程运行时间统计信息 */
	void (*update_curr) (struct rq *rq);

#define TASK_SET_GROUP  0
#define TASK_MOVE_GROUP	1

#ifdef CONFIG_FAIR_GROUP_SCHED
	void (*task_change_group) (struct task_struct *p, int type);
#endif
};

CFS 调度器类别定义如下：

/*
 * All the scheduling class methods:
 */
const struct sched_class fair_sched_class = {
	.next			= &idle_sched_class,
	.enqueue_task		= enqueue_task_fair,
	.dequeue_task		= dequeue_task_fair,
	.yield_task		= yield_task_fair,
	.yield_to_task		= yield_to_task_fair,

	.check_preempt_curr	= check_preempt_wakeup,

	.pick_next_task		= pick_next_task_fair,
	.put_prev_task		= put_prev_task_fair,

#ifdef CONFIG_SMP
	.select_task_rq		= select_task_rq_fair,
	.migrate_task_rq	= migrate_task_rq_fair,

	.rq_online		= rq_online_fair,
	.rq_offline		= rq_offline_fair,

	.task_dead		= task_dead_fair,
	.set_cpus_allowed	= set_cpus_allowed_common,
#endif

	.set_curr_task          = set_curr_task_fair,
	.task_tick		= task_tick_fair, /* cfs 类定时器周期调度接口: scheduler_tick() -> task_tick_fair() */
	.task_fork		= task_fork_fair, /* 子进程创建时, 更新其虚拟时间 */

	.prio_changed		= prio_changed_fair,
	.switched_from		= switched_from_fair,
	.switched_to		= switched_to_fair,

	.get_rr_interval	= get_rr_interval_fair,

	.update_curr		= update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
	.task_change_group	= task_change_group_fair,
#endif
};

2.7 扩展：组调度

通常，CFS 调度器对单个任务进行操作，并努力为每个任务提供公平的 CPU 时间。有时，可能需要对任务进行分组，并为每个此类任务组提供公平的 CPU 时间。例如，可能需要首先为系统上的每个用户提供公平的 CPU 时间，然后再为属于用户的每个任务提供公平的 CPU 时间。

CONFIG_CGROUP_SCHED 配置涵盖的功能，试图实现这一目标：它允许对任务进行分组，并在这些组之间公平地分配 CPU 时间。

CONFIG_RT_GROUP_SCHED 允许对实时任务（即使用 SCHED_FIFO 和 SCHED_RR 调度策略的任务）进行分组。

CONFIG_FAIR_GROUP_SCHED 允许对 CFS 任务（即使用 SCHED_NORMAL 和SCHED_BATCH 调度策略的任务）进行分组。

开启了 CONFIG_FAIR_GROUP_SCHED 后，将为使用 cgroups 伪文件系统创建的每个组创建一个 cpu.shares 文件。请参阅以下示例步骤，以创建任务组并使用 cgroups 伪文件系统 修改 CPU 份额：

# mount -t tmpfs cgroup_root /sys/fs/cgroup
# mkdir /sys/fs/cgroup/cpu
# mount -t cgroup -ocpu none /sys/fs/cgroup/cpu
# cd /sys/fs/cgroup/cpu

# mkdir multimedia      # create "multimedia" group of tasks
# mkdir browser         # create "browser" group of tasks

# #Configure the multimedia group to receive twice the CPU bandwidth
# #that of browser group

# echo 2048 > multimedia/cpu.shares
# echo 1024 > browser/cpu.shares

# firefox &     # Launch firefox and move it to "browser" group
# echo <firefox_pid> > browser/tasks

# #Launch gmplayer (or your favourite movie player)
# echo <movie_player_pid> > multimedia/tasks

以上这一系列操作，分别为 多媒体程序 和 浏览器程序 创建了两个任务分组，并指定了它们各自的 CPU 配额。

注意，以上这些配置项都依赖于 CONFIG_CGROUPS，并允许管理员使用 cgroup 伪文件系统创建任务组。更多 cgroups 功能，读者可查阅相关资料。

3. 参考资料

[1] CFS Scheduler
[2] Completely Fair Scheduler
[3] 2.2.3 核心概念 - 调度策略