Gentoo中文社区

batsom

管理团队

注册时间： 2022-08-03

帖子： 594

个人网站

Gentoo 之 WALT 负载计算

WALT（Window Assisted Load Tracking窗口辅助负载跟踪算法）的核心算法思想是：以时间窗口长度window为单位，跟踪CPU使用情况，用前面N个窗口的CPU使用情况预测当前窗口的CPU需求。窗口默认长度是20ms，walt_ravg_window = (20000000 / TICK_NSEC) * TICK_NSEC，进程负载计算默认是5个历史窗口(#define RAVG_HIST_SIZE_MAX  5)，CPU负载计算只用一个历史窗口。要理解WALT算法需要理解几个概念：WALT时间、cpu_scale、freq_scale。

        WALT时间是什么呢，是进程占用CPU时间吗？想象一下，有两个进程，在一个时间窗口内，A进程在2.6G频率上运行了5ms，B进程在小核500M频率上运行了5ms。如果仅考虑CPU占用时间，那么它们的负载是相同的，这显然与实际情况不符。所以WALT时间，不仅要考虑CPU占用时间，还要考虑所在CPU的运算能力、运行频率。函数scale_exec_time()用于计算WALT时间，参数delta是CPU运行时间，rq是进程所在运行队列（与CPU对应），SCHED_CAPACITY_SHIFT是10。

static u64 scale_exec_time(u64 delta, struct rq *rq)
{
	unsigned long capcurr = capacity_curr_of(cpu_of(rq));
 
	return (delta * capcurr) >> SCHED_CAPACITY_SHIFT;
}
 
unsigned long capacity_curr_of(int cpu)
{
	return cpu_rq(cpu)->cpu_capacity_orig *
	       arch_scale_freq_capacity(NULL, cpu)
	       >> SCHED_CAPACITY_SHIFT;
} 

capacity_curr_of()中cpu_capacity_orig的值最终来源于per_cpu变量cpu_scale。

#define arch_scale_cpu_capacity scale_cpu_capacity
static void update_cpu_capacity(struct sched_domain *sd, int cpu)
{
	unsigned long capacity = arch_scale_cpu_capacity(sd, cpu);
	struct sched_group *sdg = sd->groups;
	struct max_cpu_capacity *mcc;
	unsigned long max_capacity;
	int max_cap_cpu;
	unsigned long flags;
 
	cpu_rq(cpu)->cpu_capacity_orig = capacity;
    ...............................................................
}
unsigned long scale_cpu_capacity(struct sched_domain *sd, int cpu)
{
	return per_cpu(cpu_scale, cpu);
}

capacity_curr_of()中arch_scale_freq_capacity()最终是获取的per_cpu变量freq_scale。

#define arch_scale_freq_capacity cpufreq_scale_freq_capacity
unsigned long cpufreq_scale_freq_capacity(struct sched_domain *sd, int cpu)
{
	return per_cpu(freq_scale, cpu);
}

        上面计算WALT时间的代码，可以简化为如下的运算公式：

         cpu_scale是当前CPU运算能力尺度化。市面上有各种各样的CPU，它们的运算能力各不相同，同一系列的CPU也会迭代升级运算能力，如果以CPU实际运算能力为参数，很难做到算法的统一。内核用CPU运算能力尺度化来解决该问题，定义系统中最高运算能力核的cpu_scale为1024，其它核的cpu_scale为该(CPU运算能力/最大核运算能力)*1024。CPU各个核的cpu_scale都由SOC厂商给出，MTK平台可以cat各cpu目录下cpu_capacity节点查看cpu_scale。

        freq_scale是某CPU当前频率运算能力的瓷都化，系统定义当前核最高频率运行时的freq_scale为1024，其它频率的freq_scale为当前频率运算能力/最高频率运算能力*1024。为什么用频率的运算能力比，而不是频率比呢？是因为有些厂商的CPU是CONFIG_NONLINER_FREQ_CTL类型的，它的运算能力与频率不是正比关系。例如MTK的某些SOC就是这样的芯片，它的运算能力与频率不成正比，只能查表来看某频点运算能力。

综上，我们可以把WALT时间的运算公式做如下表示：

        从上面的公式可以看出，进程只有在最大核的最高频点上运行时，其CPU占用时间才会等于WALT时间，其它情况WALT时间都是CPU占用时间按一定比例缩短的结果。

1.进程负载计算

        进程的task_struct中有一个ravg类型的变量用于保存WALT相关的信息。其中mark_start是上一次统计的时间，sum指进程在当前窗口已经运行的WALT时间，数组sum_history[RAVG_HIST_SIZE_MAX]保存进程在前5个历史窗口期内的WALT时间，demand是由sum_history[]历史数据推算出的值。

struct ravg {
	u64 mark_start;
	u32 sum, demand;
	u32 sum_history[RAVG_HIST_SIZE_MAX];
	u32 curr_window, prev_window;
	u16 active_windows;
};

         在进程切换等情况下，会统计WALT时间，有三种情况。情况一，如果当前时间(wallclock)与上次统计时间(mark_start)在一个时间窗口内，只需要将wallclock - mark_start转换为WALT时间后累加到ravg.sum即可。情况二，如果当前时间(wallclock)与上次统计时间(mark_start)跨了一个窗口，首先计算mark_start到当前窗口起始位置这部分WALT时间，并累加到ravg.sum后调用update_history()，将ravg.sum存入历史窗口。然后计算当前窗口起始时间到现在(wallclock)的这部分WALT时间，并赋值到ravg.sum。情况三，如果当前时间(wallclock)与上次统计时间(mark_start)跨了多个窗口，首先计算mark_start到它下一个窗口起始位置这部分WALT时间，并累加到ravg.sum后调用update_history()，将ravg.sum存入历史窗口。然后计算中间跨过窗口的WALT时间并更新到历史窗口中，最后计算当前窗口起始时间到现在(wallclock)的这部分WALT时间，并赋值到ravg.sum。

//进程切换时更新负载
static void __sched notrace __schedule(bool preempt)
{
	struct task_struct *prev, *next;
	unsigned long *switch_count;
	struct pin_cookie cookie;
	struct rq *rq;
	int cpu;
	u64 wallclock;
    ................................................................
	next = pick_next_task(rq, prev, cookie);
	wallclock = walt_ktime_clock();
	walt_update_task_ravg(prev, rq, PUT_PREV_TASK, wallclock, 0);
	walt_update_task_ravg(next, rq, PICK_NEXT_TASK, wallclock, 0);
	clear_tsk_need_resched(prev);
	clear_preempt_need_resched();
    ................................................................
}
 
void walt_update_task_ravg(struct task_struct *p, struct rq *rq,
	     int event, u64 wallclock, u64 irqtime)
{
	if (walt_disabled || !rq->window_start)
		return;
 
	lockdep_assert_held(&rq->lock);
    //更新窗口起始位置
	update_window_start(rq, wallclock);
 
	if (!p->ravg.mark_start)
		goto done;
    //更新进程负载
	update_task_demand(p, rq, event, wallclock);
	update_cpu_busy_time(p, rq, event, wallclock, irqtime);
 
done:
	trace_walt_update_task_ravg(p, rq, event, wallclock, irqtime);
 
	p->ravg.mark_start = wallclock;
}
 
//更新窗口起始位置
static void update_window_start(struct rq *rq, u64 wallclock)
{
	s64 delta;
	int nr_windows;
 
	delta = wallclock - rq->window_start;
    ..............................................................
	if (delta < walt_ravg_window)
		return;
 
	nr_windows = div64_u64(delta, walt_ravg_window);
	rq->window_start += (u64)nr_windows * (u64)walt_ravg_window;
 
	rq->cum_window_demand = rq->cumulative_runnable_avg;
}
 
static void update_task_demand(struct task_struct *p, struct rq *rq,
	     int event, u64 wallclock)
{
	u64 mark_start = p->ravg.mark_start;
	u64 delta, window_start = rq->window_start;
	int new_window, nr_full_windows;
	u32 window_size = walt_ravg_window;
 
	new_window = mark_start < window_start;
    ................................................................
	//情况一
	if (!new_window) {
		/* The simple case - busy time contained within the existing
		 * window. */
		add_to_task_demand(rq, p, wallclock - mark_start);
		return;
	}
    //情况二、三代码相同，只是情况二nr_full_windows为0
	delta = window_start - mark_start;
	nr_full_windows = div64_u64(delta, window_size);
	window_start -= (u64)nr_full_windows * (u64)window_size;
    //计算mark_start到它下一个窗口起始位置之间的WALT时间
	add_to_task_demand(rq, p, window_start - mark_start);
 
	/* Push new sample(s) into task's demand history */
	update_history(rq, p, p->ravg.sum, 1, event);
	//计算中间跨越窗口的WALT时间
	if (nr_full_windows)
		update_history(rq, p, scale_exec_time(window_size, rq),
			       nr_full_windows, event);
 
	/* Roll window_start back to current to process any remainder
	 * in current window. */
	window_start += (u64)nr_full_windows * (u64)window_size;
 
	/* 计算当前窗口起始时间到现在之间的WALT时间 */
	mark_start = window_start;
	add_to_task_demand(rq, p, wallclock - mark_start);
}

         demand值是在update_history()中更新的，有四种策略可选：WINDOW_STATS_RECENT，用本次更新进来的值；WINDOW_STATS_MAX，用所有历史记录中的最大值；WINDOW_STATS_AVG，用历史记录中的平均值；WINDOW_STATS_MAX_RECENT_AVG，本次更新进来的值与历史平均值中较大的那个。

#define WINDOW_STATS_RECENT		0
#define WINDOW_STATS_MAX		1
#define WINDOW_STATS_MAX_RECENT_AVG	2
#define WINDOW_STATS_AVG		3
#define WINDOW_STATS_INVALID_POLICY	4
 
static void update_history(struct rq *rq, struct task_struct *p,
			 u32 runtime, int samples, int event)
{
	u32 *hist = &p->ravg.sum_history[0];
	int ridx, widx;
	u32 max = 0, avg, demand;
	u64 sum = 0;
 
	/* Ignore windows where task had no activity */
	if (!runtime || is_idle_task(p) || exiting_task(p) || !samples)
			goto done;
 
	/* Push new 'runtime' value onto stack */
	widx = walt_ravg_hist_size - 1;
	ridx = widx - samples;
	for (; ridx >= 0; --widx, --ridx) {
		hist[widx] = hist[ridx];
		sum += hist[widx];
		if (hist[widx] > max)
			max = hist[widx];
	}
 
	for (widx = 0; widx < samples && widx < walt_ravg_hist_size; widx++) {
		hist[widx] = runtime;
		sum += hist[widx];
		if (hist[widx] > max)
			max = hist[widx];
	}
 
	p->ravg.sum = 0;
 
	if (walt_window_stats_policy == WINDOW_STATS_RECENT) {
		demand = runtime;
	} else if (walt_window_stats_policy == WINDOW_STATS_MAX) {
		demand = max;
	} else {
		avg = div64_u64(sum, walt_ravg_hist_size);
		if (walt_window_stats_policy == WINDOW_STATS_AVG)
			demand = avg;
		else
			demand = max(avg, runtime);
	}
    ....................................................................
	if (!task_has_dl_policy(p) || !p->dl.dl_throttled) {
		if (task_on_rq_queued(p))
			fixup_cumulative_runnable_avg(rq, p, demand);
		else if (rq->curr == p)
			fixup_cum_window_demand(rq, demand);
	}
 
	p->ravg.demand = demand;
    ....................................................................
}

        进程负载的计算公式如下，可以看出1024就是满负载时的值，进程满负载必须满足：在整个时间窗口内都处于运行状态，并且所在核是大核，运行频率是大核最高频率。

static inline unsigned long task_util(struct task_struct *p)
{
#ifdef CONFIG_SCHED_WALT
	if (!walt_disabled && (sysctl_sched_use_walt_task_util ||
				p->prio < sched_use_walt_nice)) {
		unsigned long demand = p->ravg.demand;
		return (demand << SCHED_CAPACITY_SHIFT) / walt_ravg_window;
	}
#endif
	return p->se.avg.util_avg;
}

2.CPU负载计算

        CPU负载计算是在update_cpu_busy_time()中完成的，计算方法与进程负载类似。不同的是，CPU负载计算只用了一个历史窗口，就是运行队列中的prev_runnable_sum。

static inline unsigned long cpu_util_freq(int cpu)
{
	unsigned long util = cpu_rq(cpu)->cfs.avg.util_avg;
	unsigned long capacity = capacity_orig_of(cpu);
 
#ifdef CONFIG_SCHED_WALT
	if (!walt_disabled && sysctl_sched_use_walt_cpu_util)
		util = div64_u64(cpu_rq(cpu)->prev_runnable_sum,
				walt_ravg_window >> SCHED_CAPACITY_SHIFT);
#endif
	return (util >= capacity) ? capacity : util;
}