大家好,我是蟹老板~

我,当年啃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)

往期文章推荐

图解 TCP/IP协议,看图秒懂

图解 C/C++ 多线程,看图秒懂

爆肝整理!嵌入式开发必知10种调试手段

【图解】SSH(安全外壳协议)工作原理

五、调度权重

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

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

关于调度权重,有几点我得跟大家说清楚,这些都是当年我踩过坑才记住的。普通进程的优先级是通过nice值确定的,默认优先级120,nice值范围-20到19,对应40个优先级等级,nice值越高,优先级越低,权重也越低,反之亦然。

还有个小规律,nice值每增加1,进程能拿到的CPU时间,就比nice为0的时候少10%;nice值每减少1,就多10%。内核为了计算方便,把nice为0时的权重定为1024,其他nice值对应的权重,不用实时计算,直接查表就行,也就是内核里的全局变量sched_prio_to_weight。

这个数组里,相邻两个值大概是1.25倍的关系,比如nice为0是1024,nice为1就是820,820大概是1024的0.8倍,刚好对应10%的减少,是不是很巧妙?另外,内核还有个sched_prio_to_wmult数组,存的是2^32除以sched_prio_to_weight的值,提前算好,就是为了提高计算效率,不用每次都做除法——毕竟内核里的计算,能省一点是一点。

给大家举个直观的例子,进程A和B,创建时nice值都是0,权重都是1024,那它俩各占50%的CPU时间,也就是1024/(1024+1024)=50%。如果把B的nice值改成1,那B的权重就变成820,此时A占55%左右,B占45%,刚好少了10%,是不是很准?

这两个数组的源码如下,大家看一眼就行,不用死记硬背,知道有这么个东西就行:

/*
 * Nice levels are multiplicative, with a gentle 10% change for every
 * nice level changed. I.e. when a CPU-bound task goes from nice 0 to
 * nice 1, it will get ~10% less CPU time than another CPU-bound task
 * that remained on nice 0.
 *
 * The "10% effect" is relative and cumulative: from _any_ nice level,
 * if you go up 1 level, it's -10% CPU usage, if you go down 1 level
 * it's +10% CPU usage. (to achieve that we use a multiplier of 1.25.
 * If a task goes up by ~10% and another task goes down by ~10% then
 * the relative distance between them is ~25%.)
 */
const int sched_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 sched_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:
 */
const u32 sched_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,
};

这两个数组的关系,其实就是sched_prio_to_wmult[i] = 2^32 / sched_prio_to_weight[i],内核提前算好,就是为了避免除法运算,提高效率。内核里还有个set_load_weight函数,专门用来设置调度实体的load,也就是p->se.load:

static void set_load_weight(struct task_struct *p, bool update_load)
{
int prio = p->static_prio - MAX_RT_PRIO;
struct load_weight *load = &p->se.load;


/*
	 * SCHED_IDLE tasks get minimal weight:
	 */
if (task_has_idle_policy(p)) {
		load->weight = scale_load(WEIGHT_IDLEPRIO);
		load->inv_weight = WMULT_IDLEPRIO;
		p->se.runnable_weight = load->weight;
return;
	}


/*
	 * SCHED_OTHER tasks have to update their load when changing their
	 * weight
	 */
if (update_load && p->sched_class == &fair_sched_class) {
		reweight_task(p, prio);
	} else {
		load->weight = scale_load(sched_prio_to_weight[prio]);
		load->inv_weight = sched_prio_to_wmult[prio];
		p->se.runnable_weight = load->weight;
	}
}

六、虚拟运行时间的计算

为啥内核要搞个sched_prio_to_wmult数组?

这就得说到CFS调度器的核心——虚拟运行时间的计算了。CFS没有用传统的时间片调度,而是靠权重计算虚拟运行时间,来实现“完全公平”,这也是它叫“完全公平调度器”的原因。

简单说,每个进程的虚拟运行时间,是相对于nice为0时的权重比例值。nice值小的进程,权重大,虚拟运行时间比真实运行时间慢,这样就能拿到更多的CPU运行时间——毕竟,权重高,说明进程更重要,理应多占用CPU嘛。

虚拟运行时间的计算公式是:vruntime = delta_exec * (NICE_0_LOAD / weight),其中delta_exec是实际运行时间,NICE_0_LOAD是nice为0时的权重1024,weight是当前进程的权重。

但你想啊,内核里做除法多费时间,所以内核就把公式改了一下,变成vruntime = delta_exec * (NICE_0_LOAD * inv_weight) / 2^32,而inv_weight就是sched_prio_to_wmult数组里的值,也就是2^32 / weight。这么一改,除法就变成了乘法和位移运算,效率一下子就提上来了,是不是很聪明?

最终的公式就是:vruntime = delta_exec * (NICE_0_LOAD * sched_prio_to_wmult[i]) >> 32,内核就是这么实现的:

static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
	u64 fact = scale_load_down(weight);/* weight=NICE_0_LOAD */
int shift = WMULT_SHIFT;


	__update_inv_weight(lw);


if (unlikely(fact >> 32)) {
while (fact >> 32) {
			fact >>= 1;
			shift--;
		}
	}


/* fact=NICE_0_LOAD*inv_weight */
	fact = mul_u32_u32(fact, lw->inv_weight);


while (fact >> 32) {
		fact >>= 1;
		shift--;
	}


/* delta_exec*=fact >> 32 */
return mul_u64_u32_shr(delta_exec, fact, shift);
}


static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = __calc_delta(delta, NICE_0_LOAD, &se->load);


/* 如果调度实体权重为NICE_0_LOAD,则其虚拟运行时间等于实际运行时间 */
return delta;
}

很明显,当nice值为0时,进程的权重就是NICE_0_LOAD,这时候虚拟运行时间就等于实际运行时间,不用做额外计算,内核直接返回delta就行,省了不少事。

七、虚拟运行时间的更新

虚拟运行时间不是一成不变的,进程一直在运行,它的vruntime就得一直更新,这个更新工作,就是由update_curr函数完成的。我当年调试的时候,就是通过打印这个函数里的delta_exec和vruntime,才找到进程调度异常的原因,这个函数可是个“调试神器”。

update_curr的工作流程其实很简单,首先它的入参是当前进程的CFS运行队列cfs_rq;然后用rq_clock_task获取当前运行队列的clock_task值,这个值是由update_rq_clock_task更新的;接着计算delta_exec,也就是上次调用update_curr到现在的时间差;再调用calc_delta_fair计算vruntime的增量;最后调用update_min_vruntime更新cfs_rq->min_vruntime,这个值是CFS运行队列里最小的vruntime,特别重要。

/*
 * Update the current task's runtime statistics.
 */
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr; /* 当前进程调度实体 */
	u64 now = rq_clock_task(rq_of(cfs_rq)); /* 运行队列clock_task值 */
	u64 delta_exec;


if (unlikely(!curr))
return;


/* delta_exec计算该进程上次调用update_curr到现在的时间差 */
	delta_exec = now - curr->exec_start;
if (unlikely((s64)delta_exec <= 0))
return;


/* curr->exec_start记录本次调用的时间 */
	curr->exec_start = now;


	schedstat_set(curr->statistics.exec_max,
		      max(delta_exec, curr->statistics.exec_max));
/* curr->sum_exec_runtime记录进程占用CPU的总时间 */
	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq->exec_clock, delta_exec);


/* 利用delta_exec实际运行时间的增量计算vruntime增量 */
	curr->vruntime += calc_delta_fair(delta_exec, curr);
/* 更新cfs_rq->min_vruntime */
	update_min_vruntime(cfs_rq);


if (entity_is_task(curr)) {
struct task_struct *curtask = task_of(curr);


		trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
		cgroup_account_cputime(curtask, delta_exec);
		account_group_exec_runtime(curtask, delta_exec);
	}


	account_cfs_rq_runtime(cfs_rq, delta_exec);
}

update_min_vruntime更新cfs_rq->min_vruntime的原则很简单,就是记录运行队列里最小的虚拟运行时间,而且这个值是单调递增的,不会倒退——毕竟,时间哪能倒流呢?

它工作流程也不复杂,先把vruntime赋值为上次记录的min_vruntime;如果curr调度实体在运行队列里,就把vruntime更新为curr的vruntime;然后,如果红黑树有最左节点(也就是vruntime最小的调度实体),就比较这个节点的vruntime和当前的vruntime,取最小值;最后,把cfs_rq->min_vruntime更新为这个最小值和原来的min_vruntime中的最大值,确保它不会倒退。

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr; /* 当前进程调度实体 */
struct rb_node *leftmost = rb_first_cached(&cfs_rq->tasks_timeline);/* CFS运行队列红黑树最左子节点 */
/* vruntime赋值为上次记录的min_vruntime值 */
	u64 vruntime = cfs_rq->min_vruntime;


if (curr) {
if (curr->on_rq)
			vruntime = curr->vruntime;/* curr实体在运行队列中,则更新vruntime值 */
else
			curr = NULL;
	}


if (leftmost) { /* non-empty tree */
struct sched_entity *se;
/* 获取CFS运行队列红黑树最左节点调度实体 */
		se = rb_entry(leftmost, struct sched_entity, run_node);


if (!curr)
/* 若当前调度实体为空,则vruntime为CFS运行队列红黑树最左节点调度实体的vruntime */
			vruntime = se->vruntime;
else
/* 若当前调度实体不为空,则vruntime为CFS运行队列红黑树最左节点调度实体的vruntime和当前vruntime值中的最小值 */
			vruntime = min_vruntime(vruntime, se->vruntime);
	}


/* ensure we never gain time by being placed backwards. */
/* cfs_rq->min_vruntime是vruntime和cfs_rq->min_vruntime中的最大值 */
	cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
#ifndef CONFIG_64BIT
smp_wmb();
	cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
#endif
}

那vruntime什么时候会被更新呢?

其实内核里有很多地方会调用update_curr,我给大家举几个常见的:进程创建时,do_fork会调用sched_fork,再调用task_fork_fair,最后调用update_curr;内核有个定时器任务scheduler_tick,会定时调用调度类的task_tick方法,对于CFS来说,就是task_tick_fair,这个方法会调用entity_tick,进而调用update_curr,这个是周期性的更新;还有,调度实体加入CFS运行队列时,enqueue_task_fair也会调用update_curr。

八、虚拟运行时间的使用和分配

说了这么多,vruntime到底是怎么用的呢?

其实很简单,它有两个核心作用:一是判断进程是否需要被抢占,二是作为红黑树的key,决定进程的调度顺序。

先说说抢占的判断。进程一直在运行,vruntime也一直在增加,当它的vruntime超过一定额度后,内核就会设置进程thread_info里的TIF_NEED_RESCHED标志,触发延时调度schedule,这样就能让其他进程有机会运行,实现公平。

vruntime越小的进程,在红黑树里就越靠左,pick_next_task的时候就优先被选中。

内核的定时器scheduler_tick会周期性地调用task_tick_fair,然后走到check_preempt_tick:

static void check_preempt_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    ideal_runtime = sched_slice(cfs_rq, curr);  // 理论该跑多久
    delta_exec = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;


    // 如果实际跑的时间超过理论时间,就触发调度
    if (delta_exec > ideal_runtime) {
        resched_curr(rq_of(cfs_rq));
        return;
    }


    // 跑到这儿,说明还没超时,但得看看有没有vruntime更小的进程在排队
    se = __pick_first_entity(cfs_rq);
    delta = curr->vruntime - se->vruntime;
    if (delta > ideal_runtime)
        resched_curr(rq_of(cfs_rq));
}

说白了就是:你跑够了理论时间,或者有比你更“饿”的进程在等着,就得让位。

九、新进程和刚醒来的进程,怎么处理vruntime?

你想想啊,一个进程睡了很久刚被唤醒,或者一个新创建的进程,它们的vruntime可能早就过时了。如果直接用旧的vruntime,那它就会获得“报复性”的CPU占用——因为它的vruntime太小了,红黑树里排在最左边。

所以内核会做点手脚:

  • 唤醒的进程:入队时vruntime加上cfs_rq->min_vruntime,再减掉sched_latency/2作为补偿
  • 新创建的进程:vruntime设为父进程的值,加上一个调度周期的虚拟时间作为“惩罚”,再减掉min_vruntime
static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;


    if (initial)  // fork出来的
        vruntime += sched_vslice(cfs_rq, se);
    else          // 唤醒的
        vruntime -= sysctl_sched_latency / 2;


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

为啥要这么折腾?就是为了防止“睡美人”现象——一个睡了很久的进程醒来后疯狂抢占CPU,把其他进程饿死。

十、CFS入队:把进程塞进红黑树

enqueue_task_fair负责入队,核心是__enqueue_entity:

static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    struct rb_node **link = &cfs_rq->tasks_timeline.rb_root.rb_node;
    bool leftmost = true;


    while (*link) {
        parent = *link;
        entry = rb_entry(parent, struct sched_entity, run_node);


        if (entity_before(se, entry)) {
            link = &parent->rb_left;
        } else {
            link = &parent->rb_right;
            leftmost = false;  // 往右走就不可能是最左节点了
        }
    }


    rb_link_node(&se->run_node, parent, link);
    rb_insert_color_cached(&se->run_node, &cfs_rq->tasks_timeline, leftmost);
}

你看,就是标准的红黑树插入——以vruntime为key,小的在左,大的在右。

十一、CFS出队:从红黑树里删掉

dequeue_entity负责出队,简单粗暴:

static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}

就是调用红黑树的删除函数罢了。

十二、CFS选择下一个进程

这是最能体现CFS“公平”的地方了。pick_next_task_fair的核心三板斧:

第一步:put_prev_task —— 把当前进程放回队列

static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
{
    if (prev->on_rq) {
        update_curr(cfs_rq);
        __enqueue_entity(cfs_rq, prev);  // 放回红黑树
    }
    cfs_rq->curr = NULL;
}

第二步:pick_next_entity —— 从队列里挑一个

优先顺序:next > last > 红黑树最左节点,但要跳过skip标记的进程。

static struct sched_entity * pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
{
    struct sched_entity *left = __pick_first_entity(cfs_rq);
    struct sched_entity *se = left;


    if (cfs_rq->skip == se) {
        // 重选,避开skip
    }


    if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
        se = cfs_rq->last;


    if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
        se = cfs_rq->next;


    clear_buddies(cfs_rq, se);
    return se;
}

第三步:set_next_entity —— 让选中的进程上岗

static void set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    if (se->on_rq) {
        __dequeue_entity(cfs_rq, se);  // 从红黑树移除
    }


    cfs_rq->curr = se;
    se->prev_sum_exec_runtime = se->sum_exec_runtime;  // 记录开始时间
}

十三、进程唤醒

wake_up_process或者wake_up_new_task调用时,会检查新进程能不能抢占当前进程:

static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
    if (wakeup_preempt_entity(se, pse) == 1) {
        set_next_buddy(pse);
        goto preempt;
    }
    return;


preempt:
    resched_curr(rq);  // 触发调度
    if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
        set_last_buddy(se);  // 记录last,方便下次优先选择
}

wakeup_preempt_entity干了什么?就是比较两个实体的vruntime,如果差距大于调度唤醒粒度(默认1ms换算成虚拟时间),就允许抢占。


说实话,CFS的设计挺巧妙的——用vruntime这把标尺衡量公平,用红黑树高效组织进程,还照顾到sleep进程和fork进程的特殊情况。但公平这事儿啊,永远都是相对的。就像咱们现实生活里,哪有什么绝对的公平?只不过是在各方利益之间,找到一个能被大多数人接受的平衡点罢了。

内核也是这样,在各种进程之间来回权衡,最终给出一个“看起来还算公平”的调度方案。

好了,这篇文章就到这儿吧。如果你在实际开发中遇到过因为调度导致的问题,欢迎来交流——我写过的Bug,可能比你想象的要多得多。

Logo

openEuler 是由开放原子开源基金会孵化的全场景开源操作系统项目,面向数字基础设施四大核心场景(服务器、云计算、边缘计算、嵌入式),全面支持 ARM、x86、RISC-V、loongArch、PowerPC、SW-64 等多样性计算架构

更多推荐