4.5.1 CFS —— 时间记账

3 分钟阅读次阅读

公平的本质，是让时间在不同权重间流动时，依然保持其相对价值的守恒。

概要：本文详细解析了 Linux 2.6.34.10 版本中 CFS（完全公平调度器）的时间记账机制，重点讲解了 update_curr、calc_delta_fair、calc_delta_mine 等关键函数的作用与实现逻辑，并结合内核补丁讨论了 inv_weight 的计算策略与整数除法取整方法。时间记账是调度器的基础，只有记录了进程运行的时间，才能进行调度决策。

版本

Linux 2.6.34.10

1. 函数解读

1.1 update_curr()

路径：kernel\sched_fair.c

主要功能

计算当前调度实体自上次更新以来的实际运行时间（delta_exec）：
```
delta_exec = (unsigned long)(now - curr->exec_start);
```
累加调度实体的累计运行时间（sum_exec_runtime）：
```
curr->sum_exec_runtime += delta_exec;
```

按权重折算为虚拟运行时间（vruntime）：

delta_exec_weighted = calc_delta_fair(delta_exec, curr);
curr->vruntime += delta_exec_weighted;

调用时机

进程入队/出队时：enqueue_entity、dequeue_entity 都会先调用 update_curr，确保当前进程的运行时间被及时统计。
调度时钟周期到来时：entity_tick（由 task_tick_fair 调用）会调用 update_curr，周期性更新当前进程的运行信息。
进程创建 task_fork_fair、进程切换 put_prev_entity、主动让出 CPU yield_task_fair、抢占检查 check_preempt_wakeup 等调度相关操作时。

函数源码

/*
 * Update the current task's runtime statistics. Skip current tasks that
 * are not in our scheduling class.
 */
static inline void
__update_curr(struct cfs_rq *cfs_rq, struct sched_entity *curr,
	      unsigned long delta_exec)
{
	unsigned long delta_exec_weighted;

	schedstat_set(curr->exec_max, max((u64)delta_exec, curr->exec_max));

	curr->sum_exec_runtime += delta_exec;
	schedstat_add(cfs_rq, exec_clock, delta_exec);
	delta_exec_weighted = calc_delta_fair(delta_exec, curr);

	curr->vruntime += delta_exec_weighted;
	update_min_vruntime(cfs_rq);
}

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;

	if (unlikely(!curr))
		return;

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

	__update_curr(cfs_rq, curr, delta_exec);
	curr->exec_start = now;

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

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

1.2 calc_delta_fair()

将实际运行时间按调度实体权重折算为虚拟运行时间：

/*
 * delta /= w
 */
static inline unsigned long
calc_delta_fair(unsigned long delta, struct sched_entity *se)
{
	if (unlikely(se->load.weight != NICE_0_LOAD))
		delta = calc_delta_mine(delta, NICE_0_LOAD, &se->load);

	return delta;
}

参数注释

delta：实际运行时间（纳秒）
se->load.weight：调度实体的权重（由 nice 值决定）
NICE_0_LOAD：nice=0 时的标准权重

权重越大，虚拟运行时间增量越小，越容易获得更多 CPU 时间。

1.3 calc_delta_mine()

路径：kernel\sched.c 用于按权重折算虚拟运行时间的核心函数。

作用

将实际运行时间 delta_exec 按照调度实体的权重 lw->weight 和基准权重 weight（通常是 NICE_0_LOAD）进行归一化，得到”虚拟运行时间”增量。

#define WMULT_CONST (1UL << 32)

/*
 * delta *= weight / lw
 */
static unsigned long
calc_delta_mine(unsigned long delta_exec, unsigned long weight,
		struct load_weight *lw)
{
	u64 tmp;

	if (!lw->inv_weight) {
		if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
			lw->inv_weight = 1;
		else
			lw->inv_weight = 1 + (WMULT_CONST - lw->weight / 2)
				/ (lw->weight + 1);
	}

	tmp = (u64)delta_exec * weight;

	if (unlikely(tmp > WMULT_CONST))
		tmp = SRR(SRR(tmp, WMULT_SHIFT / 2) * lw->inv_weight,
			WMULT_SHIFT / 2);
	else
		tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);

	return (unsigned long)min(tmp, (u64)(unsigned long)LONG_MAX);
}

算法说明

虚拟运行时间增量 ≈ 实际运行时间 × (基准权重 / 当前权重)
权重越大，虚拟运行时间增量越小，越容易获得更多调度时间

2. calc_delta_mine关键代码解析

2.1 lw->inv_weight 是什么？

它是权重的倒数，用于避免除法运算
计算方式为：inv_weight = WMULT_CONST / weight
使用整数代替浮点数，WMULT_CONST = 2^32，放大倍数

2.2 inv_weight 特殊处理

if (BITS_PER_LONG > 32 && unlikely(lw->weight >= WMULT_CONST))
	lw->inv_weight = 1;

当系统为 64 位，且权重大于等于放大倍数时，直接设为 1
原因：避免 WMULT_CONST / weight 为 0，导致后续乘法结果为 0

2.3 四舍五入的整数除法

lw->inv_weight = 1 + (WMULT_CONST - lw->weight / 2) / (lw->weight + 1);

这里使用了四舍五入的整数除法。

一般的整数除法是向下取整，即 x / y 会丢弃小数部分。为了实现更接近实际值的四舍五入效果，常用的方法是：

(x + y/2) / y

这种方法的原理是：

若余数 r < y/2，则 (r + y/2) / y = 0，结果保持为原商 q（即“舍”）；
若余数 r ≥ y/2，则 (r + y/2) / y = 1，结果为 q + 1（即“入”）。

1.1 数学推导

假设：

x = q * y + r   （其中 0 ≤ r < y）

则：

x + y/2 = q * y + r + y/2 = y * (q + 0.5) + r

除以 y：

(x + y/2) / y = q + 0.5 + r/y

若 r ≥ y/2，则结果大于等于 q + 1，整数除法结果为 q + 1；
若 r < y/2，则结果小于 q + 1，整数除法结果为 q。

因此，(x + y/2) / y 实现了标准的四舍五入。

2. Linux 内核补丁中的算法变形分析

参考：Re: [PATCH] sched: fix inv_weight calc

2.1 背景

Gregory Haskins 在邮件中指出，当前的 sched-devel 分支中存在一个调度器负载不均衡的问题，特别是在未启用 CONFIG_FAIR_GROUP_SCHED 时。多任务负载会集中在一个 CPU 上，其他 CPU 空闲。

通过 bisect 定位到如下提交：

commit 1b9552e878a5db3388eba8660e8d8400020a07e9
Author: Peter Zijlstra
Subject: sched: higher granularity load on 64bit systems

该提交中，有一处对 inv_weight 计算的修改：

原公式：

inv_weight = (WMULT_CONST - weight / 2) / (weight + 1)

修改后：

inv_weight = 1 + (WMULT_CONST - weight / 2) / (weight + 1)

2.2 设计意图与问题

Peter 的解释是：
由于 WMULT_CONST 处于整数上限，直接加上 y/2（即 weight/2）可能会导致溢出，因此采用 - weight/2 的方式，再额外加 1 来补偿误差。

这类似于将标准算法 (x + y/2)/y 转换为 (x - y/2)/y + 1。

Gregory 起初认为这个 +1 是问题根源，尝试移除后发现调度依然不平衡，说明问题更为复杂。

3. 算法示例分析

通过几个简单例子来观察 (x - y/2)/y + 1 与标准四舍五入的差异：

示例 1：

x = 5, y = 2
标准计算：       (5 + 1)/2 = 6/2 = 3
变形算法：       (5 - 1)/2 + 1 = 4/2 + 1 = 2 + 1 = 3 ✅

结果一致，正确。

示例 2：

x = 7, y = 3
实际值：7/3 ≈ 2.333...
正确的四舍五入应为 2
变形算法仍为： (7 - 1)/3 + 1 = 6/3 + 1 = 3 ❌

此处结果不正确，说明该算法在某些情况下会偏离预期的四舍五入。

2.4 SRR 宏定义解释

#define SRR(x, y) (((x) + (1UL << ((y) - 1))) >> (y))
#define WMULT_SHIFT 32

含义：右移 y 位之前先加上 2^(y-1)，实现四舍五入，与上文的四舍五入算法一致
目的：将乘法结果从 64 位缩小至正常范围

示例展开

tmp = SRR(tmp * lw->inv_weight, WMULT_SHIFT);

此处是将乘法后的结果缩小 2^32 倍，恢复单位

2.5 防止溢出的双重 SRR

if (unlikely(tmp > WMULT_CONST))
	tmp = SRR(SRR(tmp, WMULT_SHIFT / 2) * lw->inv_weight,
		WMULT_SHIFT / 2);

当中间值过大时，先右移 16 位再乘，再右移 16 位
目的是防止在乘以 inv_weight 时发生 64 位溢出

3. 总结

update_curr() 是 CFS 时间记账的核心函数，负责更新当前调度实体的运行时间
calc_delta_fair() 和 calc_delta_mine() 实现了权重归一化，使 CFS 实现“公平”调度

复制链接复制短链接 QQ空间微博

吴思含(Witheart)