“茴”字有几种写法：系统负载是怎样计算的？（二）

/* Code Snippet of select_task_rq_fair() */
...

for_each_domain(cpu, tmp) {
	/*
	 * 简化期间，有意忽略基于 previous CPU 局部性原理的优化
	 * 即只考虑达到 “均衡” 效果。
	 * 如代码所展示，循环退出后 sd 指向顶级的 sched_domain
	 */
	...
	if (tmp->flags & sd_flag)
		sd = tmp;
}
...


else while (sd) {
	struct sched_group *group;
	int weight;
	...

	group = find_idlest_group(sd, p, cpu, sd_flag);
	...

	new_cpu = find_idlest_cpu(group, p, cpu);
	...

	/* Now try balancing at a lower domain level of new_cpu */
	cpu = new_cpu;

	weight = sd->span_weight;
	/* 
	 * cpu 属于 sd，其中 weight 表示 “sd 名下的 CPU 数”（故而下面 for_each_domain
	 * 循环中，要求 “weight <= tmp->span_weight”  其实是要求 sd 是符合要求的、
	 * 包含 cpu 的低层 sched_domain）—— 不然 sd 被再次赋值，
	 * 大循环在 “lower domain level(than sd)” 再迭代
	 */
	sd = NULL;
	for_each_domain(cpu, tmp) {
		if (weight <= tmp->span_weight)
			break;
		if (tmp->flags & sd_flag)
			sd = tmp;
	}
	/* while loop will break here if sd == NULL */
}
...

/*
 * Code Snippet of rebalance_domains(struct rq *rq, enum cpu_idle_type idle):
 * Call Stack：run_rebalance_domains() → rebalance_domains()
 *         or run_rebalance_domains() → nohz_idle_balance() → rebalance_domains()
 */
...

for_each_domain(cpu, sd) {
	...

	interval = get_sd_balance_interval(sd, idle != CPU_IDLE);
	...

	if (time_after_eq(jiffies, sd->last_balance + interval)) {
		if (load_balance(cpu, rq, sd, idle, &continue_balancing)) {
			...

/*
 * Code Snippet of idle_balance(struct rq *this_rq, struct rq_flags *rf)
 */
...
for_each_domain(this_cpu, sd) {
	...
	if (sd->flags & SD_BALANCE_NEWIDLE) {
		t0 = sched_clock_cpu(this_cpu);

		pulled_task = load_balance(this_cpu, this_rq,
					   sd, CPU_NEWLY_IDLE,
					   &continue_balancing);
		...

/*
 * Code Snippet of load_balance(int this_cpu, struct rq *this_rq,
 *                              struct sched_domain *sd, enum cpu_idle_type idle,
 *                              int *continue_balancing):
 */
...
struct sched_group *group;
struct rq *busiest;

struct lb_env env = {
	.sd		= sd,
	.dst_cpu	= this_cpu,
	.dst_rq		= this_rq,
	.dst_grpmask    = sched_group_cpus(sd->groups),
	.idle		= idle,
	.loop_break	= sched_nr_migrate_break,
	.cpus		= cpus,
	.fbq_type	= all,
	.tasks		= LIST_HEAD_INIT(env.tasks),
};

if (!should_we_balance(&env)) {
	*continue_balancing = 0;
	goto out_balanced;
}

group = find_busiest_group(&env);
if (!group) {
	schedstat_inc(sd->lb_nobusyg[idle]);
	goto out_balanced;
}

busiest = find_busiest_queue(&env, group);
if (!busiest) {
	schedstat_inc(sd->lb_nobusyq[idle]);
	goto out_balanced;
}

...

env.src_cpu = busiest->cpu;
env.src_rq = busiest;

ld_moved = 0;
if (busiest->nr_running > 1) {
	...

	/*
	 * cur_ld_moved - load moved in current iteration
	 * ld_moved     - cumulative load moved across iterations
	 */
	cur_ld_moved = detach_tasks(&env);

	...

	if (cur_ld_moved) {
		attach_tasks(&env);
		ld_moved += cur_ld_moved;
	}

	...

/* 
 * Code Snippet of find_busiest_queue(struct lb_env *env,
 *                                    struct sched_group *group)
 */
struct rq *busiest = NULL, *rq;
unsigned long busiest_load = 0, busiest_capacity = 1;
int i;

for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
	unsigned long capacity, wl;
	...

	rq = cpu_rq(i);

	...

	capacity = capacity_of(i);

	wl = weighted_cpuload(i);

	...

	/*
	 * For the load comparisons with the other cpu's, consider
	 * the weighted_cpuload() scaled with the cpu capacity, so
	 * that the load can be moved away from the cpu that is
	 * potentially running at a lower capacity.
	 *
	 * Thus we're looking for max(wl_i / capacity_i), crosswise
	 * multiplication to rid ourselves of the division works out
	 * to: wl_i * capacity_j > wl_j * capacity_i;  where j is
	 * our previous maximum.
	 */
	if (wl * busiest_capacity > busiest_load * capacity) {
		busiest_load = wl;
		busiest_capacity = capacity;
		busiest = rq;
	}
}

/* se 为入列 / 出列的 sched_entity */

struct sched_avg *sa = &se->avg;

/* 入列 */
cfs_rq->runnable_load_avg += sa->load_avg;
cfs_rq->runnable_load_sum += sa->load_sum;

/* 出列 */
cfs_rq->runnable_load_avg =
	max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
cfs_rq->runnable_load_sum =
	max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);

/*
 * Code Snippet of __update_load_avg()
 * 简化期间，只关注 cfs_rq->runnable_load_avg 相关，且“多功能”复用的分支被移除
 */

scale_freq = arch_scale_freq_capacity(NULL, cpu);

delta_w = sa->period_contrib;  /* 前次记录的，本周期已经过的时间 */
if (delta + delta_w >= 1024) { /* 超过一个周期，进行统计 */
	decayed = 1;

	sa->period_contrib = 0;

	/* ❶ 补齐 */
	delta_w = 1024 - delta_w;
	scaled_delta_w = cap_scale(delta_w, scale_freq);
	sa->load_sum += weight * scaled_delta_w;
	             // ^^^^^^ Question 1
	cfs_rq->runnable_load_sum += weight * scaled_delta_w;

	delta -= delta_w;

	/* ❷ 衰减 */
	periods = delta / 1024;
	delta %= 1024;

	/* 已计入的历史负载，经历 N 周期后，进行相应衰减 */
	sa->load_sum = decay_load(sa->load_sum, periods + 1);
	            // ^^^^^^^^^^ Question 2
	cfs_rq->runnable_load_sum =
			decay_load(cfs_rq->runnable_load_sum, periods + 1);

	/* 尚未计入的历史（持续）负载，在 1...N 周期的各衰减求和，再计入 */
	contrib = __compute_runnable_contrib(periods);
	       // ^^^^^^^^^^^^^^^^^^^^^^^^^^ Question 3
	contrib = cap_scale(contrib, scale_freq);
	sa->load_sum += weight * contrib;
	cfs_rq->runnable_load_sum += weight * contrib;
}

/* ❸ 累加 */
scaled_delta = cap_scale(delta, scale_freq);
sa->load_sum += weight * scaled_delta;
cfs_rq->runnable_load_sum += weight * scaled_delta;

sa->period_contrib += delta;

/* 完成统计，更新均值 */
if (decayed) {
	sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX);
	                                  // ^^^^^^^^^^^^ Question 4
	cfs_rq->runnable_load_avg =
			div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX);
}

/* ❶ Code Snippet of update_cpu_capacity() */
unsigned long capacity = arch_scale_cpu_capacity(sd, cpu);

cpu_rq(cpu)->cpu_capacity_orig = capacity;

capacity *= scale_rt_capacity(cpu);
capacity >>= SCHED_CAPACITY_SHIFT; /* 模拟浮点乘法，保留 10 位精度 */

/* ❷ Code Snippet of scale_rt_capacity() */
age_stamp = READ_ONCE(rq->age_stamp);
avg = READ_ONCE(rq->rt_avg);
delta = __rq_clock_broken(rq) - age_stamp;

if (unlikely(delta < 0))
	delta = 0;

total = sched_avg_period() + delta;

used = div_u64(avg, total);

if (likely(used < SCHED_CAPACITY_SCALE))
	return SCHED_CAPACITY_SCALE - used;

return 1;

/* 
 * ❸ Code Snippet of sched_rt_avg_update() 
 *
 * - 调用时机：tick 落在 RT 任务时
 */
rq->rt_avg += rt_delta * arch_scale_freq_capacity(NULL, cpu_of(rq));
sched_avg_update(rq);

/* 
 * ❹ Code Snippet of sched_avg_update()
 *
 * - sched_avg_period() 返回 sysctl_sched_time_avg 的一半
 * - sysctl_sched_time_avg 即 /proc/sys/kernel/sched_time_avg_ms，默认为 1s
 */
s64 period = sched_avg_period();

while ((s64)(rq_clock(rq) - rq->age_stamp) > period) {
	/*
	 * Inline assembly required to prevent the compiler
	 * optimising this loop into a divmod call.
	 * See __iter_div_u64_rem() for another example of this.
	 */
	asm("" : "+rm" (rq->age_stamp));
	rq->age_stamp += period;
	rq->rt_avg /= 2;
}