[v3,1/3] sched/fair: add util_est on top of PELT

The util_avg signal computed by PELT is too variable for some use-cases.
For example, a big task waking up after a long sleep period will have its
utilization almost completely decayed. This introduces some latency before
schedutil will be able to pick the best frequency to run a task.

The same issue can affect task placement. Indeed, since the task
utilization is already decayed at wakeup, when the task is enqueued in a
CPU, this can result in a CPU running a big task as being temporarily
represented as being almost empty. This leads to a race condition where
other tasks can be potentially allocated on a CPU which just started to run
a big task which slept for a relatively long period.

Moreover, the PELT utilization of a task can be updated every [ms], thus
making it a continuously changing value for certain longer running
tasks. This means that the instantaneous PELT utilization of a RUNNING
task is not really meaningful to properly support scheduler decisions.

For all these reasons, a more stable signal can do a better job of
representing the expected/estimated utilization of a task/cfs_rq.
Such a signal can be easily created on top of PELT by still using it as
an estimator which produces values to be aggregated on meaningful
events.

This patch adds a simple implementation of util_est, a new signal built on
top of PELT's util_avg where:

    util_est(task) = max(task::util_avg, f(task::util_avg@dequeue_times))

This allows to remember how big a task has been reported by PELT in its
previous activations via the function: f(task::util_avg@dequeue_times).

If a task should change its behavior and it runs even longer in a new
activation, after a certain time its util_est will just track the
original PELT signal (i.e. task::util_avg).

The estimated utilization of cfs_rq is defined only for root ones.
That's because the only sensible consumer of this signal are the
scheduler and schedutil when looking for the overall CPU utilization due
to FAIR tasks.
For this reason, the estimated utilization of a root cfs_rq is simply
defined as:

    util_est(cfs_rq) = max(cfs_rq::util_avg, cfs_rq::util_est_runnable)

where:

    cfs_rq::util_est_runnable = sum(util_est(task))
                                for each RUNNABLE task on that root cfs_rq

It's worth to note that the estimated utilization is tracked only for
objects of interests, specifically:
 - Tasks: to better support tasks placement decisions
 - root cfs_rqs: to better support both tasks placement decisions as
                 well as frequencies selection

Signed-off-by: Patrick Bellasi <patrick.bellasi@arm.com>

Reviewed-by: Dietmar Eggemann <dietmar.eggemann@arm.com>

Cc: Ingo Molnar <mingo@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Cc: Viresh Kumar <viresh.kumar@linaro.org>
Cc: Paul Turner <pjt@google.com>
Cc: Vincent Guittot <vincent.guittot@linaro.org>
Cc: Morten Rasmussen <morten.rasmussen@arm.com>
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: linux-kernel@vger.kernel.org
Cc: linux-pm@vger.kernel.org

---
Changes in 3:
 - rebased on today's tip/sched/core (commit 07881166a892)
 - moved util_est into sched_avg (Peter)
 - use {READ,WRITE}_ONCE() for EWMA updates (Peter)
 - using unsigned int to fit all sched_avg into a single 64B cache line

Changes in v2:
 - rebase on top of v4.15-rc2
 - tested that overhauled PELT code does not affect the util_est
---
 include/linux/sched.h   | 16 ++++++++++
 kernel/sched/debug.c    |  4 +++
 kernel/sched/fair.c     | 82 ++++++++++++++++++++++++++++++++++++++++++++++++-
 kernel/sched/features.h |  5 +++
 kernel/sched/sched.h    |  1 +
 5 files changed, 107 insertions(+), 1 deletion(-)

-- 
2.15.1

On Tue, Jan 23, 2018 at 06:08:45PM +0000, Patrick Bellasi wrote:
> +static inline void util_est_dequeue(struct task_struct *p, int flags)

> +{

> +	struct cfs_rq *cfs_rq = &task_rq(p)->cfs;

> +	unsigned long util_last = task_util(p);

> +	bool sleep = flags & DEQUEUE_SLEEP;

> +	unsigned long ewma;

> +	long util_est = 0;

> +

> +	if (!sched_feat(UTIL_EST))

> +		return;

> +

> +	/*

> +	 * Update root cfs_rq's estimated utilization

> +	 *

> +	 * If *p is the last task then the root cfs_rq's estimated utilization

> +	 * of a CPU is 0 by definition.

> +	 */

> +	if (cfs_rq->nr_running) {

> +		util_est  = READ_ONCE(cfs_rq->util_est_runnable);

> +		util_est -= min_t(long, util_est, task_util_est(p));

> +	}

> +	WRITE_ONCE(cfs_rq->util_est_runnable, util_est);

> +

> +	/*

> +	 * Skip update of task's estimated utilization when the task has not

> +	 * yet completed an activation, e.g. being migrated.

> +	 */

> +	if (!sleep)

> +		return;

> +


Since you only use sleep once, you might as well write it out there.

Also, does GCC lower the task_util() eval to here?

> +        /*

> +         * Skip update of task's estimated utilization when its EWMA is already

> +         * ~1% close to its last activation value.

> +         */

> +        util_est = p->util_est.ewma;

> +        if (abs(util_est - util_last) <= (SCHED_CAPACITY_SCALE / 100))

> +                return;


Aside from that being whitespace challenged, did you also try:

	if ((unsigned)((util_est - util_last) + LIM - 1) < (2 * LIM - 1))

Also, since we only care about the absolute value; we could use:

	util_last - ewma

here (note the above also forgets to use READ_ONCE), and reuse the result:

> +

> +	/*

> +	 * Update Task's estimated utilization

> +	 *

> +	 * When *p completes an activation we can consolidate another sample

> +	 * about the task size. This is done by storing the last PELT value

> +	 * for this task and using this value to load another sample in the

> +	 * exponential weighted moving average:

> +	 *

> +	 *      ewma(t) = w *  task_util(p) + (1 - w) ewma(t-1)

> +	 *              = w *  task_util(p) + ewma(t-1) - w * ewma(t-1)

> +	 *              = w * (task_util(p) + ewma(t-1) / w - ewma(t-1))

> +	 *

> +	 * Where 'w' is the weight of new samples, which is configured to be

> +	 * 0.25, thus making w=1/4

> +	 */

> +	p->se.avg.util_est.last = util_last;

> +	ewma = READ_ONCE(p->se.avg.util_est.ewma);

> +	ewma   = util_last + (ewma << UTIL_EST_WEIGHT_SHIFT) - ewma;


here.

> +	ewma >>= UTIL_EST_WEIGHT_SHIFT;

> +	WRITE_ONCE(p->se.avg.util_est.ewma, ewma);

> +}



So something along these lines:

	ewma = READ_ONCE(p->se.avg.util_est.ewma);
	diff = util_last - ewma;
	if ((unsigned)(diff + LIM - 1) < (2 * LIM - 1))
		return;

	p->se.avg.util_est.last = util_last;
	ewma = (diff + (ewma << EWMA_SHIFT)) >> EWMA_SHIFT;
	WRITE_ONCE(p->se.avg.util_est.ewma, ewma);

Make sense?