泰晓科技 -- 聚焦 Linux - 追本溯源,见微知著!
网站地址:https://tinylab.org

泰晓RISC-V实验箱,转战RISC-V,开箱即用
请稍侯

“茴”字有几种写法:系统负载是怎样计算的?(三)

Chen Jie 创作于 2017/07/23

By Chen Jie of TinyLab.org 2017-07-23 00:00:00

前情回顾

前俩篇从 /proc/loadavg 和负载均衡场景,来体会“负载”是如何定义的。直接把当前计数输出,可能出现这一时刻与下一时刻的巨大波动,换言之,指标很快过期,失去意义。

故而各种负载指标,其实是 最近一段时间的“均值” —— 历史值占“一部分比例”,当前时刻占“一部分比例”。例如,在 /proc/loadavg 中 “0.20 0.18 0.12 1/80 11206”,前三个值是就是最近 1 分钟,5 分钟和 15 分钟的负载均值:

  • 负载 == “采样时,D + R 的任务总数”
  • 采样周期 5s
  • 采样那会 的最近 1 分钟 / 5 分钟 / 10 分钟均值
  • 1 分钟:历史值 * e^(-5/60) + 当前值 * (1.0 - e^(-5/60))
  • 5 分钟:历史值 * e^(-5/300) + 当前值 * (1.0 - e^(-5/300))
  • 15 分钟:历史值 * e^(-5/900) + 当前值 * (1.0 - e^(-5/900))

负载均衡场面比较大,我们躲在 find_busiest_queue() 中,观察对 “busiest” 定义 —— 对于每个 CPU:加权平均负载 / CPU 虚拟算力

  • 加权平均负载,采样周期 1ms:
    • 周期内:累加 “R 状态的任务”时长 * 任务优先级 * CPU 频率缩放系数
    • 多周期平均:a + a1 * q + a2 * q^2 …; // aN 代表距今前 N 个周期,q^32 = 0.5
  • CPU 虚拟算力,固有算力基础上,剔除 RT 开销。剔除方法:
    • 累加 RT 时长 * CPU 频率缩放系数
    • 每 500ms 为一周期
    • 距今 N 周期,则 累加值 >> N (←_← 跨周期边界,跳崖式衰减;一次跨地越多,坠地越快)
    • 计算 RT 时间占比
    • 1.0 - RT 时间占比,是为折扣系数 —— 固有算力上打折,即为虚拟算力

具体细节参见「系统负载是怎样计算的?(一)」以及「系统负载是怎样计算的?(二)」。后篇对加权平均负载的计算函数 __update_load_avg(),留了若干疑问为线索:

  1. 任务们在队列中呆了一段时间,便是负载(当前 CPU 的 TODO list)。计算时,负载已经随 CPU freq 缩放,那不错。但还要据任务的 weight 缩放,weight 定义为何?
  2. 历史的负载值(非本周期),如何随时间衰减?
  3. LOAD_AVG_MAX 的值为何是 47742?

普通任务的 weight 定义

CFS 中,任务 nice 级别,最终换算成了权重(weight)。越“重”,则虚拟时间(vruntime)流逝越慢:

update_curr()
	u64 now = rq_clock_task(rq_of(cfs_rq));
	u64 delta_exec;
	...
	delta_exec = now - curr->exec_start;
	curr->exec_start = now;
	...
	
	// curr->vruntime += delta_exec * NICE_0_LOAD / NICE_OF_THIS_TASK_LOAD;
	curr->vruntime += calc_delta_fair(delta_exec, curr);

例如,32 位系统上,NICE_0_LOAD 为 1024(没错,又是一个 10 位整数模拟小数),NICE_-19_LOAD 为 71755,故而一个 nice=-19 任务,其时间流逝速度为默认情况的 1.427%。

“越重时间流逝越慢”的效应,按照伪科学类比法,就好像相对论重力越强时间流逝越慢:

image

为上图作简单注解,时间间隔是通过周期性重复过程来衡量,例如光的频率。从地球上一点向高空观察者发送一束光,由于逃离重力场光损失能量(频率变慢),故而高空观察者看到了频率红移的光(时间间隔拉长)。即在高空观察者看来,地表的时间流逝慢。

回到 CFS,nice 到 weight 的对应关系参见 sched_prio_to_weight。另,抢占发生,除了要求候选者的 vruntime 比 current 小以外,还要小出一个阀值,这个阀值计算也与 weight 相关:

  • 对于 Wake up preempt:阀值计算依赖候选者的 weight,候选者“越重”,越容易抢占。
  • 对于 Tick preempt:阀值计算依赖 current 的 weight,current “越重”,越不容易被抢占。

历史负载的衰减(decay_load)

负载值为 val,经历 n 个周期,则衰减为 val * q^n,其中 q^32 ~= 0.5:

static u64 decay_load(u64 val, u64 n)
{
	unsigned int rest_n;
	
	// LOAD_AVG_PERIOD 为 32,即 q^LOAD_AVG_PERIOD ~= 0.5
	// 换言之,每经过 32 个周期右移一位,64 位数则有:
	//   超过 32*63 个周期后,衰减为 0(或确切地说,不足一位)
	if (unlikely(n > LOAD_AVG_PERIOD * 63))
		return 0;
	
	// 转成 32bits
	rest_n = n;
	
	/*
 	 * As q^PERIOD = 1/2, we can combine
 	 *    q^n = 1/2^(n/PERIOD) * q^(n%PERIOD)
 	 * With a look-up table which covers q^n (n<PERIOD)
 	 *
 	 * To achieve constant time decay_load.
 	 */
	if (unlikely(rest_n >= LOAD_AVG_PERIOD)) {
		val >>= rest_n / LOAD_AVG_PERIOD;
		rest_n %= LOAD_AVG_PERIOD;
	}
	
	// val *= q^rest_n,其中 q^rest_n 查表得到,即 runnable_avg_yN_inv[rest_n]
	// 表中值采用 32 位整数模拟小数,故而算完需 “shift right 32”
	val = mul_u64_u32_shr(val, runnable_avg_yN_inv[rest_n], 32);
	return val;
}

来算下神秘的 q 是多少:

# python2 -c "print 0.5 ** (1.0/32)"
# 0.978572062088
#
# python2 -c "print '0x%x' % int(  (0.5 ** (1.0/32)) ** 31 * (1<<32)  )"
# 0x82cd8698, 即 runnable_avg_yN_inv[31] 的值


由于 nohz 存在,历史(持续)负载,可能隔了好几个周期才被统计入,此时面临的是一个等比数列求和:

LOAD = weight * freq_scale * decay
decay = q^0 + q^1 + q^2 + ... q^n

decay 因子计算,对应代码为 __update_load_avg() / __compute_runnable_contrib(n)

static u32 __compute_runnable_contrib(u64 n)
{
	u32 contrib1 = 0;
	u32 contrib2 = 0;
	
	if (likely(n <= LOAD_AVG_PERIOD))
		return runnable_avg_yN_sum[n];
	else if (unlikely(n >= LOAD_AVG_MAX_N))
		return LOAD_AVG_MAX;

	// __accumulated_sum_N32[] 为每隔 32 个周期的、一系列预先计算的、等比求和值
	contrib1 = __accumulated_sum_N32[n/LOAD_AVG_PERIOD];
	
	n %= LOAD_AVG_PERIOD;
	
	contrib1 = decay_load(contrib1, n);
	// runnable_avg_yN_sum[] 为 1-31 个预先计算的、等比求和值
	contrib2 = runnable_avg_yN_sum[n];
	
	return contrib1 + contrib2;
}

其中 LOAD_AVG_MAX 一段持续负载,能产生的“最大 decay 因子”,由无穷递降等比数列求和公式,可得为:

# python -c "print 1/(1 - 0.5 ** (1.0/32))"
# 46.6680463651
	
# 10 位整数模拟小数
# python -c "print 1/(1 - 0.5 ** (1.0/32)) * 1024"
# 47788
	
# 然而 LOAD_AVG_MAX 定义为 47742,注释介绍由 LOAD_AVG_MAX_N(345)个周期所总贡献
# 可是按 345 个周期计算得 47760

上述代码对应 4.11 版本内核,到了 4.12 版 “组织架构调整” —— __update_load_avg() 中的累计过程独立出了新函数 accumulate_sum();其中,“补齐”、“历史(持续)负载”、“本周期” 累计过程塞入 __accumulate_pelt_segments()(仅计算因子)。



Read Related:

Read Latest: