[内核学习]公平调度从CFS到EEVDF

TaterLi

2 周前

先泼盆冷水:fair.c 的文件头注释今天还写着 Completely Fair Scheduling (CFS) Class,调度类还叫 fair_sched_class,策略还叫 SCHED_NORMAL,但 6.6 里面装的东西已经换血了.你要是拿"CFS 就是红黑树挑最左边那个 vruntime 最小的任务"这套讲法去读 6.18 的 pick_eevdf(),会直接对不上号.网上大量资料停在这个阶段,读调度器源码的第一坑就是它.

这篇回答几件事:

vruntime 这套虚拟时钟记账怎么来的,为什么活到了今天
EEVDF 的 eligible 和 virtual deadline 到底在算什么,lag 怎么记怎么还
6.18 的 pick_eevdf 怎么用增广红黑树做到 O(log n),跟 6.6 刚合入时有什么不同
睡眠唤醒的延迟保证怎么来的

先把时间拨回 2007 年.2.6.23,Ingo Molnar 的 CFS 干掉了 O(1) 调度器,核心思想一句话:n 个任务共享一个 CPU,理想是每个拿 1/n,调度器的任务就是缩小现实和理想的差距.

2007 年,2.6.23,Ingo Molnar 的 CFS 干掉了 O(1) 调度器.核心思想一句话:n 个任务共享一个 CPU,理想是每个拿 1/n,调度器的任务就是缩小现实和理想的差距.

为了度量差距,发明了 vruntime.权重来自 nice 值(nice 0 是 1024,每差一级大约 ÷1.25),记账公式:

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);
	return delta;
}

实际时间乘 NICE_0_LOAD 除以自身权重,体重越大虚拟时钟走得越慢.两个任务就算轮流跑,vruntime 始终同步,这就是"虚拟"的含义.这条公式从 2007 活到现在,EEVDF 全盘继承,nice 的语义因此没变.

老 CFS 的选人逻辑:所有可运行任务按 vruntime 排红黑树,每次挑最左.新任务和睡眠唤醒的任务被"放置"到 min_vruntime - sysctl_sched_latency 附近,保证不饿死也不白捡.

那为什么 2023 年(6.6)Peter Zijlstra 又把选人逻辑推倒重来:

延迟没法按需表达.老 CFS 有 sched_latency_ns(目标调度周期)和 sched_min_granularity_ns(最小粒度)两个旋钮,全局拍一个延迟目标."我请求很短,该快点跑完"这种需求表达不出来,只能靠更细粒度间接模拟.
睡眠补偿是补丁式的.唤醒任务拿一段 vruntime 折扣(sleeper bonus),本质上就是"它被亏欠了,该还",但老 CFS 没有系统的账本,还多还少全靠经验公式,还出过著名的 sleeper 公平性漏洞.
理论上有现成的更好答案:EEVDF(Earliest Eligible Virtual Deadline First),1995 年 Stoica 和 Abdel-Wahab 的比例公平调度论文,二十多年前的算法,同时给出公平性和延迟保证.

那新算法长什么样.EEVDF 把每次运行建模成一次请求(request):任务被选中后跑一个 slice,这个 slice 就是一次请求,长度 r.每次从两个条件选人:

EEVDF 把每次运行建模成一次请求(request):任务被选中后跑一个 slice,这个 slice 就是一次请求,长度 r.每次从两个条件选人:

eligible,这个任务被亏欠了,应得的服务没拿够
在 eligible 的任务里,选 virtual deadline 最早的

公平的一半.定义 lag:

lag_i = S - s_i = w_i * (V - v_i)

S 是理想服务,s_i 是实际服务,V 是系统公平点(所有任务 vruntime 的加权平均).lag >= 0 意味着欠它钱,lag < 0 意味着它占便宜了.只有债主才有资格被选,公平性由"每次都从债主里挑"保证,所有 lag 加起来守恒为零.

延迟的一半.虚拟截止期:

vd_i = ve_i + r_i / w_i

两头都被权重缩放:体重大,虚拟时间走得慢,同样物理 slice 在虚拟轴上更短,deadline 更近,更常被选中,这是公平;请求短,r/w 直接小,deadline 近,插队,这是延迟保证.老 CFS 两个全局旋钮想同时调的东西,在这一个公式里统一了,而且 r 是任务自己的属性,想短就短,延迟需求终于有了表达出口.

理论说完,看 6.18 里具体长什么样.

先看公平点 V 的维护.公平点是所有在队任务的加权平均:

公平点是所有在队任务的加权平均:

V = Σ(v_i * w_i) / W

6.18 用 cfs_rq 的三个字段做增量维护:sum_w_vruntime,sum_weight,zero_vruntime.任务进出队加减自己的贡献,查询时除一下.entity_key 里把 vruntime 换算成相对 zero_vruntime 的差值再做乘加,因为 vruntime 是一路增长的大数,直接乘权重会溢出,相对化之后都是小量."锚点+相对量"是后面版本重写过的,老版本用近似传播,现在是精确账本.

再看 lag,entity_lag 干的事:

static s64 entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 avruntime)
{
	u64 max_slice = cfs_rq_max_slice(cfs_rq) + TICK_NSEC;
	s64 vlag, limit;

	vlag = avruntime - se->vruntime;
	limit = calc_delta_fair(max_slice, se);

	return clamp(vlag, -limit, limit);
}

lag 用虚拟量表示(vlag),出队时存进 se->vlag.clamp 的边界来自 EEVDF 理论:-r_max < lag < max(r_max, q),再叠一个 TICK_NSEC,因为记账精度就到 tick 级,不 clamp 的话一次进出队能把 V 拽得乱跳.

eligible 的判断有个小心思:

static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
{
	...
	return avg >= vruntime_op(vruntime, "-", cfs_rq->zero_vruntime) * load;
}

lag >= 0 等价于 V >= v_i,但 V 要除法,有精度损失,这里把不等式两边同乘 W 变成纯整数乘法比较,注释专门写了"用 avg_vruntime() > se->vruntime 判断是不精确的".这种把除法题改写成乘法题的小心思调度器里到处都是,看代码要留神.

deadline 和 slice 的关系在 update_deadline 里:

static bool update_deadline(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
	if (vruntime_cmp(se->vruntime, "<", se->deadline))
		return false;

	if (!se->custom_slice)
		se->slice = sysctl_sched_base_slice;

	/* EEVDF: vd_i = ve_i + r_i / w_i */
	se->deadline = se->vruntime + calc_delta_fair(se->slice, se);
	...
	return true;
}

跑满当前请求就发起新请求,顺手判断要不要 NEED_RESCHED.注意 se->slice 是物理时间,默认不随权重缩放,随权重缩放的是虚拟距离 calc_delta_fair(slice, se).想自定义有口子:__setparam_fair 读 sched_setattr 的 sched_runtime,clamp 在 0.1ms 到 100ms,标记 custom_slice.

下面是唤醒延迟的核心,place_entity,出队时存 lag,入队时还:

唤醒延迟的核心,出队时存 lag,入队时还:

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
{
	u64 vslice, vruntime = avg_vruntime(cfs_rq);
	s64 lag = 0;

	if (!se->custom_slice)
		se->slice = sysctl_sched_base_slice;
	vslice = calc_delta_fair(se->slice, se);

	if (sched_feat(PLACE_LAG) && cfs_rq->nr_queued && se->vlag) {
		lag = se->vlag;
		/* 乘 (W+w)/W 补偿自稀释, 推导见原注释 */
		lag = div_s64(lag * (load + se->weight), load);
	}

	se->vruntime = vruntime - lag;

	if (sched_feat(PLACE_DEADLINE_INITIAL) && (flags & ENQUEUE_INITIAL))
		vslice /= 2;	/* 新任务给半个 slice 的 deadline */

	se->deadline = se->vruntime + vslice;
}

两个细节.lag 保值要放大:V 是加权平均,直接把带正 lag 的任务塞回去,它会被自己的权重稀释,亏欠凭空蒸发,源码注释用十几行推导出补偿系数 (W+w)/W,入队前先膨胀,剩下的才等于当初欠的.新任务给半个 slice:老成员平均都跑到一半了,新人按整 slice 算 deadline 就是插队,给一半正好混进人流.

账本有了,看怎么选人.数据结构还是红黑树,但排序键变成了 deadline(老 CFS 是 vruntime),每个节点还维护子树聚合(include/linux/sched.h 的 sched_entity):

数据结构还是红黑树,但排序键变成了 deadline(老 CFS 是 vruntime),每个节点还维护子树聚合(include/linux/sched.h 的 sched_entity):

struct sched_entity {
	struct load_weight	load;
	struct rb_node		run_node;
	u64			deadline;
	u64			min_vruntime;	// 本子树最小 vruntime
	u64			min_slice;
	u64			max_slice;
	...
	s64			vlag;
	u64			vprot;		// slice 保护线
	u64			slice;
};

min_vruntime 由 RB_DECLARE_CALLBACKS_MULTI 在树旋转时自动维护,效果是这棵树同时是 vruntime 小顶堆.选人逻辑(fair.c 的 pick_eevdf):

	/* 最左 = 全局 deadline 最早,它 eligible 就直接赢 */
	if (se && entity_eligible(cfs_rq, se)) {
		best = se;
		goto found;
	}

	/* 堆搜索:左子树里有 eligible 就往左走(左边 deadline 都更早) */
	while (node) {
		struct rb_node *left = node->rb_left;

		if (left && vruntime_eligible(cfs_rq,
					__node_2_se(left)->min_vruntime)) {
			node = left;
			continue;
		}
		se = __node_2_se(node);
		if (entity_eligible(cfs_rq, se)) {
			best = se;
			break;
		}
		node = node->rb_right;
	}

剪枝依据:左子树的 min_vruntime 是该子树里最欠债的任务,连它都不 eligible,整棵左子树都没戏,直接跳右边.整体 O(log n).值得一提的是,EEVDF 6.6 刚合入时的选人是对着树逐节点扫,最坏 O(n),后来几个版本持续打磨才长成现在这样,这也是读调度器要认准版本的又一个理由.

正在跑的任务有保护期.current 不会一过 deadline 就被扒下来,set_protect_slice 给它设了 vprot:RUN_TO_PARITY 开着时保护到"队列里最短的 slice"用完(跑到平价),关掉时至少保一个 base_slice 的量子,防止高频切换把吞吐磨没.update_curr 在 deadline 过期且失去保护时才 resched_curr_lazy.

slice 从哪调:老 CFS 的 sched_latency_ns/sched_min_granularity_ns 在 6.6 就删了,如今 /proc/sys/kernel 里公平调度就剩个带宽控制类旋钮,粒度相关的全在 debugfs:

cat /sys/kernel/debug/sched/base_slice_ns
cat /sys/kernel/debug/sched/features

base_slice 默认 0.7ms,会被 tunable_scaling(默认 LOG)按 CPU 数放大:实际值 = 0.7ms × (1 + ilog2(cpus)).当年短暂出现过的 latency_nice 也删干净了(全树 grep 不到),表达延迟需求的正统途径就是 custom_slice.

最后看睡眠唤醒,这是 EEVDF 最漂亮的部分.一个任务睡了一小时,醒来时它是谁?在 EEVDF 里它是大债主:

一个任务睡了一小时,醒来时它是谁?在 EEVDF 里它是大债主:应得服务分文未动,lag 深深为正,deadline 按 place_entity 重新算,大概率比跑了很久的老任务更近,于是 eligible 加 deadline 最早,马上被选.延迟保证不用任何特判,是 lag 语义的自然结果.对比老 CFS 的 vruntime 折扣补丁,这是系统性方案.

唤醒抢占的判断在 check_preempt_wakeup_fair,6.18 的版本骨架:

	/* 醒来的人 slice 更短,保护期照抢 */
	if (sched_feat(PREEMPT_SHORT) && (pse->slice < se->slice)) {
		preempt_action = PREEMPT_WAKEUP_SHORT;
		goto pick;
	}
...
pick:
	nse = pick_next_entity(rq, cfs_rq, preempt_action != PREEMPT_WAKEUP_SHORT);
	/* 让 pick_eevdf 重选,选出来是醒来的任务就抢 */
	if (nse == pse)
		goto preempt;

这套设计很 EEVDF:不自己发明抢占判据,把要不要抢扔回给 pick_eevdf 重选一遍,选出来是谁就是谁.PREEMPT_SHORT 是唯一例外通道,短 slice 任务连 current 的保护期都能踩,因为让它先跑完对总延迟更优,slice 就是延迟的语言.

DELAY_DEQUEUE(6.10 引入)解决另一个烦人问题:任务要睡但它不欠债,出队再入队的账面抖动毫无意义,于是先赖在队列里标 sched_delayed,等真正失去资格或下次被 pick 再真正出队.配合它的 PLACE_REL_DEADLINE:短暂离开队列(比如迁移)时 deadline 存成相对值,V 停走期间不吃亏.

上板.RK3399,6 核,6.18.56,两把尺子一起量.

上板.RK3399,6 核,6.18.56.先看旋钮:

# cat /sys/kernel/debug/sched/base_slice_ns
2100000

正好是 0.7ms × (1 + ilog2(6)) = 2.1ms,和源码推的一致.

然后做个实验:两个死循环 hog 绑在同一个 A72 大核上,一个 nice 0 一个 nice 1,跑 5 秒,量两个东西:各自拿到的真实 CPU 时间,和各自 vruntime 的增量.

nice 0 (w=1024): cpu 279 ticks, vruntime +2790.4 ms
nice 1 (w=820):  cpu 224 ticks, vruntime +2796.2 ms
cpu 份额比 = 1.246 (理论 1024/820 = 1.249)

(tick 是 USER_HZ=100,一个 10ms;vruntime 从 /proc/PID/sched 读,单位毫秒)

这组数字把公平调度的本质演示得明明白白:真实 CPU 份额按权重分,279:224 = 1.246,和理论权重比 1.249 对上;但两人的 vruntime 增量几乎一样,2790.4 对 2796.2,误差 0.2%.这正是设计目标:vruntime 是公平的账本,所有任务同速往前走,谁也没占谁便宜.权重决定的不是"谁的时钟走得快",而是"同样的时钟刻度,你要用多少真实 CPU 来换".nice 1 的任务每换 1ms 的 vruntime 要付出的真实时间多 25%,这就是虚拟时钟.

顺带一说,我一开始预期的是"vruntime 增速比也是 1.25",拿到数据才发现想岔了,单跑满速的两个任务才有那个比值,共享一个核的稳态就是同速前进.又一次,实测教育人.

/proc/PID/sched 还有一堆好东西(CONFIG_SCHED_DEBUG):

se.exec_start                                :       2409080.784559
se.vruntime                                  :           929.443551
se.sum_exec_runtime                          :           308.122378
se.nr_migrations                             :                    1
nr_switches                                  :                   46
nr_voluntary_switches                        :                    1
nr_involuntary_switches                      :                    45
se.load.weight                               :               343040

这是一个 nice 5 的 hog:46 次切换里 45 次是被动的(时间片/抢占),主动让出只有 1 次,死循环任务的标准画像.se.load.weight 显示 343040,是权重表里 nice 5 的 335 乘上 1024 的内部表示,别被吓到.

再配合 sched:sched_switch tracepoint(这块板没编 FUNCTION_TRACER,available_tracers 只有 nop,但 tracepoint 是好的),echo 1 > events/sched/sched_switch/enable 就能看到两个 hog 在 CPU4 上的切换节奏和 slice 长度,和 2.1ms 的 base_slice 对得上.

最后留几个容易忽略的细节:

文件名,类名,策略名全是历史遗留的 fair/CFS,算法是 EEVDF.vruntime 还在用,但"挑 vruntime 最小"的时代结束了,树的排序键是 deadline.
slice 是物理等长的,不等长的是虚拟 deadline 距离.重任务不是"跑更久的块",是"更频繁的块".
vruntime 是 u64,比较全靠 vruntime_cmp 宏转 (s64)(a-b),那个用 __builtin_strcmp 选操作符的宏写法很怪,但编译期就能查错,合理.
update_curr 开头注释提到 rq->donor,那是实验性的 PROXY_EXEC(CONFIG_SCHED_PROXY_EXEC,默认关),默认编译下 donor 就是 curr,知道有这回事就行.
SCHED_BATCH 和 SCHED_IDLE 不参与唤醒抢占(normal_policy 检查),交互延迟优化只给 SCHED_NORMAL.
base_slice 会按 CPU 数缩放,做单核/多核对比实验先 cat 一眼基准,别拿 0.7ms 硬算.我这板 6 核就是 2.1ms.