@

【WALT】update_cpu_busy_time() 代码详解

代码版本：Linux4.9 android-msm-crosshatch-4.9-android12

代码展示

/*
 * Account cpu activity in its busy time counters (rq->curr/prev_runnable_sum)
 */
static void update_cpu_busy_time(struct task_struct *p, struct rq *rq,
				 int event, u64 wallclock, u64 irqtime)
{
	int new_window, full_window = 0;
	int p_is_curr_task = (p == rq->curr);
	u64 mark_start = p->ravg.mark_start;
	u64 window_start = rq->window_start;
	u32 window_size = sched_ravg_window;
	u64 delta;
	u64 *curr_runnable_sum = &rq->curr_runnable_sum;
	u64 *prev_runnable_sum = &rq->prev_runnable_sum;
	u64 *nt_curr_runnable_sum = &rq->nt_curr_runnable_sum;
	u64 *nt_prev_runnable_sum = &rq->nt_prev_runnable_sum;
	bool new_task;
	struct related_thread_group *grp;
	int cpu = rq->cpu;
	u32 old_curr_window = p->ravg.curr_window;

	new_window = mark_start < window_start;
	if (new_window) {
		full_window = (window_start - mark_start) >= window_size;
		if (p->ravg.active_windows < USHRT_MAX)
			p->ravg.active_windows++;
	}

	new_task = is_new_task(p);

	if (!is_idle_task(p) && !exiting_task(p)) {
		if (new_window)
			rollover_task_window(p, full_window);
	}

	if (p_is_curr_task && new_window) {
		rollover_cpu_window(rq, full_window);
		rollover_top_tasks(rq, full_window);
	}

	if (!account_busy_for_cpu_time(rq, p, irqtime, event))
		goto done;

	grp = p->grp;
	if (grp) {
		struct group_cpu_time *cpu_time = &rq->grp_time;

		curr_runnable_sum = &cpu_time->curr_runnable_sum;
		prev_runnable_sum = &cpu_time->prev_runnable_sum;

		nt_curr_runnable_sum = &cpu_time->nt_curr_runnable_sum;
		nt_prev_runnable_sum = &cpu_time->nt_prev_runnable_sum;
	}

	if (!new_window) {
		if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq))
			delta = wallclock - mark_start;
		else
			delta = irqtime;
		delta = scale_exec_time(delta, rq);
		*curr_runnable_sum += delta;
		if (new_task)
			*nt_curr_runnable_sum += delta;

		if (!is_idle_task(p) && !exiting_task(p)) {
			p->ravg.curr_window += delta;
			p->ravg.curr_window_cpu[cpu] += delta;
		}

		goto done;
	}

	if (!p_is_curr_task) {
		if (!full_window) {
			delta = scale_exec_time(window_start - mark_start, rq);
			if (!exiting_task(p)) {
				p->ravg.prev_window += delta;
				p->ravg.prev_window_cpu[cpu] += delta;
			}
		} else {
			delta = scale_exec_time(window_size, rq);
			if (!exiting_task(p)) {
				p->ravg.prev_window = delta;
				p->ravg.prev_window_cpu[cpu] = delta;
			}
		}

		*prev_runnable_sum += delta;
		if (new_task)
			*nt_prev_runnable_sum += delta;

		delta = scale_exec_time(wallclock - window_start, rq);
		*curr_runnable_sum += delta;
		if (new_task)
			*nt_curr_runnable_sum += delta;

		if (!exiting_task(p)) {
			p->ravg.curr_window = delta;
			p->ravg.curr_window_cpu[cpu] = delta;
		}

		goto done;
	}

	if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq)) {
		if (!full_window) {
			delta = scale_exec_time(window_start - mark_start, rq);
			if (!is_idle_task(p) && !exiting_task(p)) {
				p->ravg.prev_window += delta;
				p->ravg.prev_window_cpu[cpu] += delta;
			}
		} else {
			delta = scale_exec_time(window_size, rq);
			if (!is_idle_task(p) && !exiting_task(p)) {
				p->ravg.prev_window = delta;
				p->ravg.prev_window_cpu[cpu] = delta;
			}
		}
		
		*prev_runnable_sum += delta;
		if (new_task)
			*nt_prev_runnable_sum += delta;

		delta = scale_exec_time(wallclock - window_start, rq);
		*curr_runnable_sum += delta;
		if (new_task)
			*nt_curr_runnable_sum += delta;

		if (!is_idle_task(p) && !exiting_task(p)) {
			p->ravg.curr_window = delta;
			p->ravg.curr_window_cpu[cpu] = delta;
		}

		goto done;
	}

	if (irqtime) {
		BUG_ON(!is_idle_task(p));
		mark_start = wallclock - irqtime;

		if (mark_start > window_start) {
			*curr_runnable_sum = scale_exec_time(irqtime, rq);
			return;
		}

		delta = window_start - mark_start;
		if (delta > window_size)
			delta = window_size;
		delta = scale_exec_time(delta, rq);
		*prev_runnable_sum += delta;

		delta = wallclock - window_start;
		rq->curr_runnable_sum = scale_exec_time(delta, rq);

		return;
	}

done:
	if (!is_idle_task(p) && !exiting_task(p))
		update_top_tasks(p, rq, old_curr_window, new_window, full_window);
}

代码逻辑

⑴ 更新标志位

WALT 算法中，引入了一个新的概念：窗口（sched_ravg_window）

先介绍几个名词：

• ws：window_start，当前窗口的开始时间
• ms：mark_start，当前任务的开始时间
• wc：wallclock，进入 WALT 算法的时间
• full_windows，如果进入新窗口，则代表旧窗口到当前窗口所经历的完整的窗口个数
• delta：从任务开始到当前时间/新窗口开始时间所经历的时长

和 update_task_demand() 中窗口划分方式相同，但此处只分为两种情况：

1. 仍在旧窗口中（mark_start > window_start）

                   ws   ms  wc
                   |    |   |
                   V    V   V
   |---------------|===============|
   仍在旧窗口会将 new_window 标志位置 0，full_window 标志位仍为 0
   

2. 进入新窗口中（mark_start < window_start）

              ms   ws_tmp                    ws   wc
              |    |                         |    |
              V    V                         V    V
   |---------------|----------|...|----------|===============|
                   |                         |
                   |<---  超过一个窗口时间  --->|
   进入新窗口会将 new_window 标志位置 1
   如果 ms 到 ws 之间的时间超过了一个窗口时间（window_start - mark_start >= window_size），将 full_window 标志位置 1
   如果 p->ravg.active_windows 没有超过 USHRT_MAX（无符号 short int 对象可以存储的最大值 65535），就累加 1
   

   p->ravg.active_windows 用于判断该任务是否是新任务。在 new_task = is_new_task(p); 中：

   static inline bool is_new_task(struct task_struct *p)
   {
   	return p->ravg.active_windows < SCHED_NEW_TASK_WINDOWS;
   }
   

   其中，默认情况下 SCHED_NEW_TASK_WINDOWS = 5，即任务还没翻滚 5 个窗口时都被当作新任务。

⑵ 滚动窗口

在进入新窗口的时候才需要滚动窗口。

1. 如果当前任务不是 idle 任务（pid 为 0 的任务）、或当前任务并没有要出队，滚动任务窗口。

   static void rollover_task_window(struct task_struct *p, bool full_window)
   {
   	u32 *curr_cpu_windows = empty_windows;
   	u32 curr_window;
   	int i;
       
   	/* Rollover the sum */
   	curr_window = 0;
   
   	if (!full_window) {
   		curr_window = p->ravg.curr_window;
   		curr_cpu_windows = p->ravg.curr_window_cpu;
   	}
   
   	p->ravg.prev_window = curr_window;
   	p->ravg.curr_window = 0;
   
   	/* Roll over individual CPU contributions */
   	for (i = 0; i < nr_cpu_ids; i++) {
   		p->ravg.prev_window_cpu[i] = curr_cpu_windows[i];
   		p->ravg.curr_window_cpu[i] = 0;
   	}
   }
   

   主要是更新任务的 prev_window 和 curr_window，并更新 CPU 的 prev_window_cpu 和 curr_window_cpu。

   具体为：将 curr 的执行时间放到 prev 中，并将 curr 的执行时间置 0。

2. 如果当前任务就是运行队列中正在执行的任务，就滚动 CPU 窗口和 top task 窗口。

   static void rollover_cpu_window(struct rq *rq, bool full_window)
   {
   	u64 curr_sum = rq->curr_runnable_sum;
   	u64 nt_curr_sum = rq->nt_curr_runnable_sum;
   	u64 grp_curr_sum = rq->grp_time.curr_runnable_sum;
   	u64 grp_nt_curr_sum = rq->grp_time.nt_curr_runnable_sum;
   
   	if (unlikely(full_window)) {
   		curr_sum = 0;
   		nt_curr_sum = 0;
   		grp_curr_sum = 0;
   		grp_nt_curr_sum = 0;
   	}
   
   	rq->prev_runnable_sum = curr_sum;
   	rq->nt_prev_runnable_sum = nt_curr_sum;
   	rq->grp_time.prev_runnable_sum = grp_curr_sum;
   	rq->grp_time.nt_prev_runnable_sum = grp_nt_curr_sum;
   
   	rq->curr_runnable_sum = 0;
   	rq->nt_curr_runnable_sum = 0;
   	rq->grp_time.curr_runnable_sum = 0;
   	rq->grp_time.nt_curr_runnable_sum = 0;
   }
   

   翻滚 CPU 窗口时不论任务是否处于 related_thread_group 中（grp），或任务是否是新任务（nt），都一并进行更新操作，具体操作同上。

   static void rollover_top_tasks(struct rq *rq, bool full_window)
   {
   	u8 curr_table = rq->curr_table;
   	u8 prev_table = 1 - curr_table;
   	int curr_top = rq->curr_top;
   
   	clear_top_tasks_table(rq->top_tasks[prev_table]);
   	clear_top_tasks_bitmap(rq->top_tasks_bitmap[prev_table]);
   
   	if (full_window) {
   		curr_top = 0;
   		clear_top_tasks_table(rq->top_tasks[curr_table]);
   		clear_top_tasks_bitmap(
   				rq->top_tasks_bitmap[curr_table]);
   	}
   
   	rq->curr_table = prev_table;
   	rq->prev_top = curr_top;
   	rq->curr_top = 0;
   }
   

   更新 top task 相关信息，点击查看 top task 相关资料。

⑶ 不累加运行时间的条件判断

static int 
account_busy_for_cpu_time(struct rq *rq, struct task_struct *p,
				     u64 irqtime, int event)
{
	if (is_idle_task(p)) {
		if (event == PICK_NEXT_TASK)
			return 0;
		return irqtime || cpu_is_waiting_on_io(rq);
	}

	if (event == TASK_WAKE)
		return 0;

	if (event == PUT_PREV_TASK || event == IRQ_UPDATE)
		return 1;

	if (event == TASK_UPDATE) {	
		if (rq->curr == p)
			return 1;
		return p->on_rq ? SCHED_FREQ_ACCOUNT_WAIT_TIME : 0;
	}

	return SCHED_FREQ_ACCOUNT_WAIT_TIME;
}

和 update_task_demand() 中 account_busy_for_task_demand() 类似，account_busy_for_cpu_time中会判断任务经过的时间是否是 runnable 或 running 时间，返回 1 则是，返回 0 则不是。

1. 任务经过的时间是 runnable 或 running，即返回 1 的情况
   在当前版本内核中，SCHED_ACCOUNT_WAIT_TIME 默认为 1
   • 如果任务是 idle 任务且有中断时间
   • 如果任务是 idle 任务且有 I/O
   • 任务更新且就是运行队列当前任务
   • 任务更新且任务在运行队列中，但不是rq当前任务
   • 其他情况
2. 任务经过的时间不是 runnable 或 running，即返回 0 的情况
   • 如果任务是 idle 任务且要选择最优任务
   • 如果任务是 idle 任务且没有中断和 I/O
   • 任务刚被唤醒
   • 任务中断更新
   • 任务更新且任务不在运行队列中

可以发现，account_busy_for_cpu_time 与 account_busy_for_task_demand() 判断为真或为假的条件并不相同。

如果返回 0，则直接进入 done，跳转 ⑹ 更新 top task。

⑶ 任务处于 grp（相关线程组 related_thread_group）中

相关线程组相关知识可以查看：调度器分支之RTG

rtg 出现的背景，即系统的线程不是孤立的，它们之间存在各种依赖关系。

RTG 提供一组重要线程的优化调度。可以单独收集和预测 RTG 的负载，并可以设置首选 CPU 集群，让重要线程运行在最佳 CPU 上，内核根据组负载选择合适的 CPU 频率。

RTG希望将组里面的关联线程都放在同一个CPU簇上。通过best_cluster选择一个可以满足组内线程所需算力的CPU簇。

在 update_cpu_busy_time() 中，WALT 针对 grp 组相关线程的负载做了单独的统计，为了方便在做负载聚合调频的时候能够快速的进行计算。如果任务处于 grp 中，就不会将任务执行时间统计进 CPU 的 runnable_sum 中，而是统计进 grp 单独的 runnable_sum 中。

除了 update_cpu_busy_time()，还有 fixup_busy_time() 做任务迁核的修正，transfer_busy_time() 用于任务加入或者退出某个 group 时候的修正。

我们将在文末附上 fixup_busy_time() 和 transfer_busy_time() 的解析，将整个 busytime 路径的负载计算补齐。

⑷ 仍在旧窗口中

如果任务还在旧窗口中，不会进行翻滚（rollover）操作，只进行执行时间的累加操作。

if (!new_window) {
	if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq))
		delta = wallclock - mark_start;
	else
		delta = irqtime;
	delta = scale_exec_time(delta, rq);
	*curr_runnable_sum += delta;
	if (new_task)
		*nt_curr_runnable_sum += delta;

	if (!is_idle_task(p) && !exiting_task(p)) {
		p->ravg.curr_window += delta;
		p->ravg.curr_window_cpu[cpu] += delta;
	}

	goto done;
}

如果任务没有 irq、不是 idle 任务、不在 I/O，delta 就是当前时间减去任务开始时间，繁殖则是 irq 时间。

和 update_task_demand() 一样，delta 也会通过 scale_exec_time() 进行归一化。

在归一化后，会根据任务是否是新任务、是否是 idle 任务或是否要出队来将 delta 累加进 curr_runnable_sum、nt_curr_runnable_sum、curr_window 和 curr_window_cpu[cpu] 中。

更新完后进入 done，跳转 ⑹ 更新 top task。

⑸ 进入新窗口

进入新窗口后，会根据以下三种情况来累加执行时间：

1. if (!p_is_curr_task)
2. if (!irqtime || !is_idle_task(p) || cpu_is_waiting_on_io(rq))
3. if (irqtime)

和 update_task_demand() 不同，update_cpu_busy_time() 只设置当前窗口（curr）和过去窗口（perv）两个窗口。

三种情况中，除了最后一种情况，如果在旧窗口中执行时间未满一个窗口时长，就直接将执行时间累加进 prev 相关数据中；如果执行时间超过一个窗口时长，就直接将一个窗口时长累加进 prev 相关数据中。

然后将新窗口中的执行时间累加进 curr 相关数据中。

更新完后进入 done，跳转 ⑹ 更新 top task。

⑹ 更新 top task

主要更新 top task 相关信息，维护 curr_table/prev_table。

若 p->ravg.curr_window 的值不变，且任务仍在旧窗口中，就不需要更新 top task。点击查看 top task 相关资料。

点击此处回到 WALT 入口函数 update_task_ravg()

点击此处回到【WALT】调度与负载计算

fixup_busy_time()

void fixup_busy_time(struct task_struct *p, int new_cpu)
{
	struct rq *src_rq = task_rq(p);
	struct rq *dest_rq = cpu_rq(new_cpu);
	u64 wallclock;
	u64 *src_curr_runnable_sum, *dst_curr_runnable_sum;
	u64 *src_prev_runnable_sum, *dst_prev_runnable_sum;
	u64 *src_nt_curr_runnable_sum, *dst_nt_curr_runnable_sum;
	u64 *src_nt_prev_runnable_sum, *dst_nt_prev_runnable_sum;
	bool new_task;
	struct related_thread_group *grp;

	if (!p->on_rq && p->state != TASK_WAKING)
		return;

	if (exiting_task(p)) {
		clear_ed_task(p, src_rq);
		return;
	}

	if (p->state == TASK_WAKING)
		double_rq_lock(src_rq, dest_rq);

	if (sched_disable_window_stats)
		goto done;

	wallclock = ktime_get_ns();

	update_task_ravg(task_rq(p)->curr, task_rq(p),
			 TASK_UPDATE,
			 wallclock, 0);
	update_task_ravg(dest_rq->curr, dest_rq,
			 TASK_UPDATE, wallclock, 0);

	update_task_ravg(p, task_rq(p), TASK_MIGRATE,
			 wallclock, 0);

	update_task_cpu_cycles(p, new_cpu, wallclock);

	/*
	 * When a task is migrating during the wakeup, adjust
	 * the task's contribution towards cumulative window
	 * demand.
	 * 译：当任务在唤醒期间迁移时，调整任务对累积窗口需求的贡献。
	 */
	if (p->state == TASK_WAKING && p->last_sleep_ts >=
				       src_rq->window_start) {
		walt_fixup_cum_window_demand(src_rq, -(s64)p->ravg.demand);
		walt_fixup_cum_window_demand(dest_rq, p->ravg.demand);
	}

	new_task = is_new_task(p);
	/* Protected by rq_lock */
	grp = p->grp;

	/*
	 * For frequency aggregation, we continue to do migration fixups
	 * even for intra cluster migrations. This is because, the aggregated
	 * load has to reported on a single CPU regardless.
	 */
	if (grp) {
		struct group_cpu_time *cpu_time;

		cpu_time = &src_rq->grp_time;
		src_curr_runnable_sum = &cpu_time->curr_runnable_sum;
		src_prev_runnable_sum = &cpu_time->prev_runnable_sum;
		src_nt_curr_runnable_sum = &cpu_time->nt_curr_runnable_sum;
		src_nt_prev_runnable_sum = &cpu_time->nt_prev_runnable_sum;

		cpu_time = &dest_rq->grp_time;
		dst_curr_runnable_sum = &cpu_time->curr_runnable_sum;
		dst_prev_runnable_sum = &cpu_time->prev_runnable_sum;
		dst_nt_curr_runnable_sum = &cpu_time->nt_curr_runnable_sum;
		dst_nt_prev_runnable_sum = &cpu_time->nt_prev_runnable_sum;

		if (p->ravg.curr_window) {
			*src_curr_runnable_sum -= p->ravg.curr_window;
			*dst_curr_runnable_sum += p->ravg.curr_window;
			if (new_task) {
				*src_nt_curr_runnable_sum -=
							p->ravg.curr_window;
				*dst_nt_curr_runnable_sum +=
							p->ravg.curr_window;
			}
		}

		if (p->ravg.prev_window) {
			*src_prev_runnable_sum -= p->ravg.prev_window;
			*dst_prev_runnable_sum += p->ravg.prev_window;
			if (new_task) {
				*src_nt_prev_runnable_sum -=
							p->ravg.prev_window;
				*dst_nt_prev_runnable_sum +=
							p->ravg.prev_window;
			}
		}
	} else {
		inter_cluster_migration_fixup(p, new_cpu,
						task_cpu(p), new_task);
	}

	migrate_top_tasks(p, src_rq, dest_rq);

	if (!same_freq_domain(new_cpu, task_cpu(p))) {
		src_rq->notif_pending = true;
		dest_rq->notif_pending = true;
		irq_work_queue(&walt_migration_irq_work);
	}

	if (p == src_rq->ed_task) {
		src_rq->ed_task = NULL;
		dest_rq->ed_task = p;
	}

done:
	if (p->state == TASK_WAKING)
		double_rq_unlock(src_rq, dest_rq);
}

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 用jacoco统计JAVA项目测试代码覆盖率
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• GDB调试之源代码查看与管理(六)
• 写代码时如何合理的画图表达逻辑结构
• 十行python代码实现文件去重，去除重复文件的脚本
• [代码随想录] 第四天
• idea 中java代码修改后运行代码不生效
• 一行代码创建网页（html）
• 如何在SAP GUI中快速执行新的事务代码

update_cpu_busy_time 路径 busytime 代码 updateupdate_cpu_busy_time路径busytime代码 update_cpu_busy_time busytime update_history history代码update update_task_demand代码update demand update_task_cpu_cycles代码update cycles update_window_start代码update window walt update_task_ravg入口 代码 路径 代码lived2电脑 车位 路径 代码matlab