我，当年啃Linux内核CFS调度的时候，说真的，差点把头发薅秃。第一次看CFS（完全公平调度器）的时候，心里就一个念头：这名字起得也太理想主义了吧？“完全公平”？在这个世界上，哪有什么真正的公平啊。

不过在看完代码之后，倒是也觉得，这帮内核大佬们，至少在技术上，是真心想追求那么一点儿公平的。

提醒一下：各位最好先看看《深入浅出 Linux 内核（进程篇）：进程调度》这篇文章，这样的话可以对进程调度有一个大体的认识。

特别说明：本文内核版本为Linux5.6.4。

进程这东西，说简单也简单、说复杂也复杂，大概分三类：交互式进程、批处理进程还有实时进程。对应这三类进程，Linux内核整了六种调度策略，我当年背这几个宏定义，背了又忘、忘了又背，现在闭着眼都能写出来：

#define SCHED_NORMAL		0
#define SCHED_FIFO		1
#define SCHED_RR		2
#define SCHED_BATCH		3
/* SCHED_ISO: reserved but not implemented yet */
#define SCHED_IDLE		5
#define SCHED_DEADLINE		6

这里面，SCHED_NORMAL和SCHED_BATCH就是咱们最常接触的普通进程，写个接口、跑个脚本，基本都是这俩策略；SCHED_FIFO、SCHED_RR还有SCHED_DEADLINE，是给实时进程用的，比如工业控制里的任务，差一秒都不行；至于SCHED_IDLE，就是CPU没事干的时候才跑的0号进程，相当于CPU的“摸鱼模式”嘛，啥时候没其它进程干活了，它才出来凑数。

绝大多数情况下，你跑的那些程序都是普通进程，归CFS调度器管。这一点，从内核怎么挑下一个要跑的进程就能看出来 —— pick_next_task函数里，有个优化判断，如果所有任务都归fair调度类管，就直接走快速路径。

static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
    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, but only if the @prev task wasn't of a
	 * higher scheduling class, because otherwise those loose the
	 * opportunity to pull in more work from other CPUs.
	 */
    /* likely告诉编译器该分支执行概率大，即系统中都是由CFS调度的进程  */
    if (likely((prev->sched_class == &idle_sched_class ||
            prev->sched_class == &fair_sched_class) &&
            rq->nr_running == rq->cfs.h_nr_running)) {

		p = pick_next_task_fair(rq, prev, rf);
        if (unlikely(p == RETRY_TASK))
            goto restart;

        /* Assumes fair_sched_class->next == idle_sched_class */
        if (!p) {
            put_prev_task(rq, prev);
			p = pick_next_task_idle(rq);
		}

        return p;
	}
	……
	for_each_class(class) {
		p = class->pick_next_task(rq);
        if (p)
            return p;
	}

    /* The idle class should always have a runnable task: */
    BUG();
}

Linux为了搞进程调度，整了好几个核心概念，我当年刚开始记的时候，总把它们弄混，后来干脆弄了个表，才算理清楚 —— 调度类有5个，负责提供调度方法；调度实体有3个，是调度的基本单元，既能调度单个进程，也能调度一组进程；调度策略就是刚才说的6种，按实时和普通进程分；调度算法有4种，跟着调度策略走，啥策略对应啥算法。

这些概念的优先级的关系，我给大家捋了捋，从高到低来，看表格更清楚，当年我就是靠这个表格，才没把优先级搞反：

调度类	调度策略	调度实体	调度算法
stop_sched_class	无	无	无
dl_sched_class	SCHED_DEADLINE	sched_dl_entity	EDF
rt_sched_class	SCHED_RR/SCHED_FIFO	sched_rt_entity	RR/FIFO
fair_sched_class	SCHED_NORMAL/SCHED_BATCH	sched_entity	CFS
idle_sched_class	无

咱们今天聊的CFS调度，其实就是fair_sched_class调度类管的事儿，对应SCHED_NORMAL和SCHED_BATCH两种策略，调度实体就是sched_entity，说穿了，就是普通进程的“管家”。

一、CFS调度类

聊到CFS，就绕不开它的调度类fair_sched_class，这玩意儿说白了，就是给CFS调度提供各种方法的“工具包”，我当年第一次看它的源码，光记这些方法就头大了好几天 —— 毕竟方法太多，每个方法的作用还不一样，记错一个，理解就全偏了。如下表，大伙不用死记硬背，大概有个印象就行，后续用到的时候再回头查：

方法	描述
enqueue_task_fair	将进程对应的调度实体添加到运行队列红黑树中
dequeue_task_fair	将进程对应的调度实体从运行队列红黑树中删除
yield_task_fair	sched_yield系统调用，将当前进程放入运行队列skip成员中
check_preempt_wakeup	检查当前进程是否可被新进程抢占
__pick_next_task_fair	在调度类中选择下一个要执行的进程
put_prev_task_fair	更新进程vruntime，再将进程放回运行队列，与set_next_task配合使用
set_next_task_fair	将进程放从运行队列删除，并作为当前运行实体，与put_prev_task配合使用
task_tick_fair	scheduler_tick定时器调用，CFS调度算法调用update_curr计算vruntime，可能触发调度
task_fork_fair	do_fork调用，CFS调度算法初始化vruntime

对应的源码大家可以对照着看，我当年就是一边看源码，一边对照表格，才搞懂每个方法的作用，建议大家也这么做，比光看文字管用多了：

/*
 * All the scheduling class methods:
 */
const struct sched_class fair_sched_class = {
	.next			= &idle_sched_class, /* 下一个调度类idle */
	.enqueue_task		= enqueue_task_fair, /* 进程加入运行队列 */
	.dequeue_task		= dequeue_task_fair,/* 进程退出运行队列 */
	.yield_task		= yield_task_fair,/* 进程主动让出CPU，进程退出运行队列后再加入运行队列尾 */
	.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,/* 将进程放回运行队列 */
	.set_next_task          = set_next_task_fair,

#ifdef CONFIG_SMP
	.balance		= balance_fair,
	.select_task_rq		= select_task_rq_fair,/* 返回进程运行队列CPU number */ 
	.migrate_task_rq	= migrate_task_rq_fair,/* 进程迁移到指定CPU，set_task_cpu调用 */

	.rq_online		= rq_online_fair,/* 启动运行队列 */
	.rq_offline		= rq_offline_fair,/* 禁止运行队列 */

	.task_dead		= task_dead_fair,/* 进程切换时前一个进程状态为TASK_DEAD时调用 */
	.set_cpus_allowed	= set_cpus_allowed_common,
#endif

	.task_tick		= task_tick_fair,/*scheduler_tick定时器调用，CFS调度算法调用update_curr计算vruntime*/
	.task_fork		= task_fork_fair,/* do_fork调用，CFS调度算法初始化vruntime */

/* __sched_setscheduler调用check_class_changed，进程切换调度策略时触发切换调度类以及优先级的变化 */
	.prio_changed		= prio_changed_fair,
	.switched_from		= switched_from_fair,
	.switched_to		= switched_to_fair,

/* 系统调用sched_rr_get_interval，返回 round robin time，非RR调度类返回0 */
	.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

#ifdef CONFIG_UCLAMP_TASK
	.uclamp_enabled		= 1,
#endif
}

二、CFS运行队列

内核给每个CPU都分配了一个运行队列rq，也就是this_rq()能拿到的那个，每个rq里都藏着一个CFS运行队列cfs_rq，专门管普通进程的调度。说真的，我当年调试一个CPU占用过高的bug时，就是盯着这个cfs_rq的成员看，看来看去，才发现是nr_running数值异常，导致调度混乱，折腾了整整一个通宵。

cfs_rq里的那些成员，重点记几个就行，比如min_vruntime和tasks_timeline，这俩是CFS的核心，记不住它们，基本就没搞懂CFS：

成员	描述
load	运行队列所有调度实体总负载。se入队时update_load_add增加负载；se出队时通过update_load_sub减去负载
nr_running	CFS运行队列调度实体数量，se入队时加1，se出队时减1
h_nr_running	CFS运行队列调度实体数量
idle_h_nr_running	记录idle调度实体数量
min_vruntime	记录 CFS运行队列红黑树中最小的vruntime值，保持单调递增。该值非常重要，在对唤醒进程和fork进程vruntime做补偿时使用
tasks_timeline	CFS运行队列红黑树根，所有调度实体都依据se->vruntime（红黑树的KEY）大小加入到红黑树接受调度
curr	记录CFS运行队列中当前正在运行的se
next	记录CFS运行队列中急需运行的se，wakeup唤醒进程时可能将被唤醒的进程赋值给next。pick_next_entity时会优先选择cfs_rq->next
last	记录CFS运行队列中当前运行的se，与curr不同，curr一定会记录当前运行se，而last只会记录执行wakeup操作的se。pick_next_entity时会次优先选择cfs_rq->last。这样有利于重复利用cache
skip	记录CFS运行队列中跳过运行的se，系统调用sched_yield会将当前实体赋值到cfs_rq->skip。pick_next_entity时如发现选择的se是cfs_rq->skip时，会重新选择se

对应的结构体源码也放这儿，建议大家这个结构体打印出来，贴在显示器旁边，随时看，看多了自然就记住了：

/* CFS-related fields in a runqueue */
struct cfs_rq {
struct load_weight	load; /* CFS运行队列所有调度实体总负载 */
unsigned long		runnable_weight;
unsigned int		nr_running; /* CFS运行队列调度实体数量 */
unsigned int		h_nr_running;   /* SCHED_{NORMAL,BATCH,IDLE} */
unsigned int		idle_h_nr_running; /* SCHED_IDLE */

	u64			exec_clock;
	u64			min_vruntime;/* CFS运行队列红黑树中最小的vruntime值 */
#ifndef CONFIG_64BIT
	u64			min_vruntime_copy;
#endif

struct rb_root_cached	tasks_timeline;/* CFS运行队列红黑树根 */

/*
	 * 'curr' points to currently running entity on this cfs_rq.
	 * It is set to NULL otherwise (i.e when none are currently running).
	 */
struct sched_entity	*curr;/* 记录CFS运行队列中当前正在运行的se */
struct sched_entity	*next;/* 记录CFS运行队列中被wakeup的se */
struct sched_entity	*last;/* 记录CFS运行队列中执行wakeup的se */
struct sched_entity	*skip;/* 记录CFS运行队列需要跳过的se */

#ifdef	CONFIG_SCHED_DEBUG
unsigned int		nr_spread_over;
#endif

#ifdef CONFIG_SMP
/*
	 * CFS load tracking
	 */
struct sched_avg	avg;
#ifndef CONFIG_64BIT
	u64			load_last_update_time_copy;
#endif
struct {
raw_spinlock_t	lock ____cacheline_aligned;
int		nr;
unsigned long	load_avg;
unsigned long	util_avg;
unsigned long	runnable_sum;
	} removed;

#ifdef CONFIG_FAIR_GROUP_SCHED
unsigned long		tg_load_avg_contrib;
long			propagate;
long			prop_runnable_sum;

/*
	 *   h_load = weight * f(tg)
	 *
	 * Where f(tg) is the recursive weight fraction assigned to
	 * this group.
	 */
unsigned long		h_load;
	u64			last_h_load_update;
struct sched_entity	*h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */

#ifdef CONFIG_FAIR_GROUP_SCHED
struct rq		*rq;	/* CPU runqueue to which this cfs_rq is attached */

/*
	 * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
	 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
	 * (like users, containers etc.)
	 *
	 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a CPU.
	 * This list is used during load balance.
	 */
int			on_list;
struct list_head	leaf_cfs_rq_list;
struct task_group	*tg;	/* group that "owns" this runqueue */
	…………
#endif /* CONFIG_FAIR_GROUP_SCHED */
}

三、CFS调度实体

每个进程的描述符task_struct里，都藏着一个sched_entity成员，这就是调度实体 —— 说穿了，CFS调度的不是进程本身，而是这个调度实体。它可以是一个进程，也可以是一个调度组，当年我就是没搞懂这一点，误以为CFS直接调度进程，绕了好大一圈弯路。

struct sched_entity {
    /* For load-balancing: */
    struct load_weight		load; /* 调度权重 */
    unsigned long			runnable_weight;
    struct rb_node			run_node;/* 调度实体在cfs_rq红黑树的节点 */
    struct list_head		group_node;
    unsigned int			on_rq;/* 调度实体是否在调度队列中接受调度 */

	u64				exec_start;
	u64				sum_exec_runtime;/* 当前累计运行实际时间 */
	u64				vruntime;/* 虚拟运行时间 */
	u64				prev_sum_exec_runtime;/* 上次累计运行实际时间 */

	u64				nr_migrations;

    struct sched_statistics		statistics;

#ifdef CONFIG_FAIR_GROUP_SCHED
    int				depth;
    struct sched_entity		*parent;
    /* rq on which this entity is (to be) queued: */
    struct cfs_rq			*cfs_rq;
    /* rq "owned" by this entity/group: */
    struct cfs_rq			*my_q;
#endif

#ifdef CONFIG_SMP
    /*
	 * Per entity load average tracking.
	 *
	 * Put into separate cache line so it does not
	 * collide with read-mostly values above.
	 */
    struct sched_avg		avg;/* 进程负载 */
#endif
}

四、调度优先级

聊完调度实体，就得说说调度优先级了，这是影响进程抢占的关键。task_struct里有几个相关的成员，我给大家重点说下。

int				prio;                    /* 动态优先级 */
int				static_prio;             /* 静态优先级 */
int				normal_prio;             /* 普通优先级 */
unsigned int			rt_priority;     /* 实时优先级 */

内核用0到139表示进程优先级，记住了，数值越低，优先级越高，别搞反了！

其中，0到99是给实时进程用的，100到139是给普通进程用的。MAX_RT_PRIO宏是最大实时进程优先级，数值是100；DEFAULT_PRIO宏是默认普通进程优先级，数值是120，也就是说，咱们新建一个普通进程，默认优先级就是120，也可以用nice系统调用来改。

说到nice，大家可得注意，它的取值范围是-20到19，负值会让进程优先级变高，正值会让优先级变低，别搞反了哦。实时进程的优先级范围是0到MAX_PRIO-1，也就是0到99，普通进程是MAX_RT_PRIO到MAX_PRIO-1，也就是100到139，这些数值，记不住没关系，用到的时候查源码就行，源码里写得明明白白：

#define MAX_NICE	19
#define MIN_NICE	-20
#define NICE_WIDTH	(MAX_NICE - MIN_NICE + 1)

/*
 * Priority of a process goes from 0..MAX_PRIO-1, valid RT
 * priority is 0..MAX_RT_PRIO-1, and SCHED_NORMAL/SCHED_BATCH
 * tasks are in the range MAX_RT_PRIO..MAX_PRIO-1. Priority
 * values are inverted: lower p->prio value means higher priority.
 *
 * The MAX_USER_RT_PRIO value allows the actual maximum
 * RT priority to be separate from the value exported to
 * user-space.  This allows kernel threads to set their
 * priority to a value higher than any user task. Note:
 * MAX_RT_PRIO must not be smaller than MAX_USER_RT_PRIO.
 */

#define MAX_USER_RT_PRIO	100
#define MAX_RT_PRIO		MAX_USER_RT_PRIO

#define MAX_PRIO		(MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO		(MAX_RT_PRIO + NICE_WIDTH / 2)

五、调度权重

调度实体里有个load成员，也就是struct load_weight load，这就是调度权重，它可是CFS实现“公平”的关键——毕竟，优先级最终都会转换成权重，权重越高，进程能拿到的CPU时间就越多。

struct load_weight {
    unsigned long			weight; /* 调度实体的权重 */
	u32				inv_weight; /* 调度实体的权重的中间计算值 */
};

更多内容请看下回。