linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
From: tip-bot for Morten Rasmussen <tipbot@zytor.com>
To: linux-tip-commits@vger.kernel.org
Cc: hpa@zytor.com, tglx@linutronix.de, peterz@infradead.org,
	efault@gmx.de, torvalds@linux-foundation.org,
	morten.rasmussen@arm.com, linux-kernel@vger.kernel.org,
	quentin.perret@arm.com, mingo@kernel.org
Subject: [tip:sched/core] sched/fair: Add over-utilization/tipping point indicator
Date: Tue, 11 Dec 2018 07:37:50 -0800	[thread overview]
Message-ID: <tip-2802bf3cd936fe2c8033a696d375a4d9d3974de4@git.kernel.org> (raw)
In-Reply-To: <20181203095628.11858-13-quentin.perret@arm.com>

Commit-ID:  2802bf3cd936fe2c8033a696d375a4d9d3974de4
Gitweb:     https://git.kernel.org/tip/2802bf3cd936fe2c8033a696d375a4d9d3974de4
Author:     Morten Rasmussen <morten.rasmussen@arm.com>
AuthorDate: Mon, 3 Dec 2018 09:56:25 +0000
Committer:  Ingo Molnar <mingo@kernel.org>
CommitDate: Tue, 11 Dec 2018 15:17:01 +0100

sched/fair: Add over-utilization/tipping point indicator

Energy-aware scheduling is only meant to be active while the system is
_not_ over-utilized. That is, there are spare cycles available to shift
tasks around based on their actual utilization to get a more
energy-efficient task distribution without depriving any tasks. When
above the tipping point task placement is done the traditional way based
on load_avg, spreading the tasks across as many cpus as possible based
on priority scaled load to preserve smp_nice. Below the tipping point we
want to use util_avg instead. We need to define a criteria for when we
make the switch.

The util_avg for each cpu converges towards 100% regardless of how many
additional tasks we may put on it. If we define over-utilized as:

sum_{cpus}(rq.cfs.avg.util_avg) + margin > sum_{cpus}(rq.capacity)

some individual cpus may be over-utilized running multiple tasks even
when the above condition is false. That should be okay as long as we try
to spread the tasks out to avoid per-cpu over-utilization as much as
possible and if all tasks have the _same_ priority. If the latter isn't
true, we have to consider priority to preserve smp_nice.

For example, we could have n_cpus nice=-10 util_avg=55% tasks and
n_cpus/2 nice=0 util_avg=60% tasks. Balancing based on util_avg we are
likely to end up with nice=-10 tasks sharing cpus and nice=0 tasks
getting their own as we 1.5*n_cpus tasks in total and 55%+55% is less
over-utilized than 55%+60% for those cpus that have to be shared. The
system utilization is only 85% of the system capacity, but we are
breaking smp_nice.

To be sure not to break smp_nice, we have defined over-utilization
conservatively as when any cpu in the system is fully utilized at its
highest frequency instead:

cpu_rq(any).cfs.avg.util_avg + margin > cpu_rq(any).capacity

IOW, as soon as one cpu is (nearly) 100% utilized, we switch to load_avg
to factor in priority to preserve smp_nice.

With this definition, we can skip periodic load-balance as no cpu has an
always-running task when the system is not over-utilized. All tasks will
be periodic and we can balance them at wake-up. This conservative
condition does however mean that some scenarios that could benefit from
energy-aware decisions even if one cpu is fully utilized would not get
those benefits.

For systems where some cpus might have reduced capacity on some cpus
(RT-pressure and/or big.LITTLE), we want periodic load-balance checks as
soon a just a single cpu is fully utilized as it might one of those with
reduced capacity and in that case we want to migrate it.

[ peterz: Added a comment explaining why new tasks are not accounted during
          overutilization detection. ]

Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
Signed-off-by: Quentin Perret <quentin.perret@arm.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Mike Galbraith <efault@gmx.de>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: adharmap@codeaurora.org
Cc: chris.redpath@arm.com
Cc: currojerez@riseup.net
Cc: dietmar.eggemann@arm.com
Cc: edubezval@gmail.com
Cc: gregkh@linuxfoundation.org
Cc: javi.merino@kernel.org
Cc: joel@joelfernandes.org
Cc: juri.lelli@redhat.com
Cc: patrick.bellasi@arm.com
Cc: pkondeti@codeaurora.org
Cc: rjw@rjwysocki.net
Cc: skannan@codeaurora.org
Cc: smuckle@google.com
Cc: srinivas.pandruvada@linux.intel.com
Cc: thara.gopinath@linaro.org
Cc: tkjos@google.com
Cc: valentin.schneider@arm.com
Cc: vincent.guittot@linaro.org
Cc: viresh.kumar@linaro.org
Link: https://lkml.kernel.org/r/20181203095628.11858-13-quentin.perret@arm.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
---
 kernel/sched/fair.c  | 59 ++++++++++++++++++++++++++++++++++++++++++++++++++--
 kernel/sched/sched.h |  4 ++++
 2 files changed, 61 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e04f29098ec7..767e7675774b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5082,6 +5082,24 @@ static inline void hrtick_update(struct rq *rq)
 }
 #endif
 
+#ifdef CONFIG_SMP
+static inline unsigned long cpu_util(int cpu);
+static unsigned long capacity_of(int cpu);
+
+static inline bool cpu_overutilized(int cpu)
+{
+	return (capacity_of(cpu) * 1024) < (cpu_util(cpu) * capacity_margin);
+}
+
+static inline void update_overutilized_status(struct rq *rq)
+{
+	if (!READ_ONCE(rq->rd->overutilized) && cpu_overutilized(rq->cpu))
+		WRITE_ONCE(rq->rd->overutilized, SG_OVERUTILIZED);
+}
+#else
+static inline void update_overutilized_status(struct rq *rq) { }
+#endif
+
 /*
  * The enqueue_task method is called before nr_running is
  * increased. Here we update the fair scheduling stats and
@@ -5139,8 +5157,26 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 		update_cfs_group(se);
 	}
 
-	if (!se)
+	if (!se) {
 		add_nr_running(rq, 1);
+		/*
+		 * Since new tasks are assigned an initial util_avg equal to
+		 * half of the spare capacity of their CPU, tiny tasks have the
+		 * ability to cross the overutilized threshold, which will
+		 * result in the load balancer ruining all the task placement
+		 * done by EAS. As a way to mitigate that effect, do not account
+		 * for the first enqueue operation of new tasks during the
+		 * overutilized flag detection.
+		 *
+		 * A better way of solving this problem would be to wait for
+		 * the PELT signals of tasks to converge before taking them
+		 * into account, but that is not straightforward to implement,
+		 * and the following generally works well enough in practice.
+		 */
+		if (flags & ENQUEUE_WAKEUP)
+			update_overutilized_status(rq);
+
+	}
 
 	hrtick_update(rq);
 }
@@ -7940,6 +7976,9 @@ static inline void update_sg_lb_stats(struct lb_env *env,
 		if (nr_running > 1)
 			*sg_status |= SG_OVERLOAD;
 
+		if (cpu_overutilized(i))
+			*sg_status |= SG_OVERUTILIZED;
+
 #ifdef CONFIG_NUMA_BALANCING
 		sgs->nr_numa_running += rq->nr_numa_running;
 		sgs->nr_preferred_running += rq->nr_preferred_running;
@@ -8170,8 +8209,15 @@ next_group:
 		env->fbq_type = fbq_classify_group(&sds->busiest_stat);
 
 	if (!env->sd->parent) {
+		struct root_domain *rd = env->dst_rq->rd;
+
 		/* update overload indicator if we are at root domain */
-		WRITE_ONCE(env->dst_rq->rd->overload, sg_status & SG_OVERLOAD);
+		WRITE_ONCE(rd->overload, sg_status & SG_OVERLOAD);
+
+		/* Update over-utilization (tipping point, U >= 0) indicator */
+		WRITE_ONCE(rd->overutilized, sg_status & SG_OVERUTILIZED);
+	} else if (sg_status & SG_OVERUTILIZED) {
+		WRITE_ONCE(env->dst_rq->rd->overutilized, SG_OVERUTILIZED);
 	}
 }
 
@@ -8398,6 +8444,14 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
 	 * this level.
 	 */
 	update_sd_lb_stats(env, &sds);
+
+	if (static_branch_unlikely(&sched_energy_present)) {
+		struct root_domain *rd = env->dst_rq->rd;
+
+		if (rcu_dereference(rd->pd) && !READ_ONCE(rd->overutilized))
+			goto out_balanced;
+	}
+
 	local = &sds.local_stat;
 	busiest = &sds.busiest_stat;
 
@@ -9798,6 +9852,7 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 		task_tick_numa(rq, curr);
 
 	update_misfit_status(curr, rq);
+	update_overutilized_status(task_rq(curr));
 }
 
 /*
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index d4d984846924..0ba08924e017 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -718,6 +718,7 @@ struct perf_domain {
 
 /* Scheduling group status flags */
 #define SG_OVERLOAD		0x1 /* More than one runnable task on a CPU. */
+#define SG_OVERUTILIZED		0x2 /* One or more CPUs are over-utilized. */
 
 /*
  * We add the notion of a root-domain which will be used to define per-domain
@@ -741,6 +742,9 @@ struct root_domain {
 	 */
 	int			overload;
 
+	/* Indicate one or more cpus over-utilized (tipping point) */
+	int			overutilized;
+
 	/*
 	 * The bit corresponding to a CPU gets set here if such CPU has more
 	 * than one runnable -deadline task (as it is below for RT tasks).

  reply	other threads:[~2018-12-11 15:38 UTC|newest]

Thread overview: 45+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2018-12-03  9:56 [PATCH v10 00/15] Energy Aware Scheduling Quentin Perret
2018-12-03  9:56 ` [PATCH v10 01/15] sched: Relocate arch_scale_cpu_capacity Quentin Perret
2018-12-11 15:32   ` [tip:sched/core] sched/topology: Relocate arch_scale_cpu_capacity() to the internal header tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 02/15] sched/cpufreq: Prepare schedutil for Energy Aware Scheduling Quentin Perret
2018-12-11 12:01   ` Rafael J. Wysocki
2018-12-11 12:17     ` Quentin Perret
2018-12-11 12:22       ` Rafael J. Wysocki
2018-12-11 12:24         ` Quentin Perret
2018-12-11 15:33   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 03/15] PM: Introduce an Energy Model management framework Quentin Perret
2018-12-11 15:33   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 04/15] PM / EM: Expose the Energy Model in sysfs Quentin Perret
2018-12-11 14:18   ` Ingo Molnar
2018-12-11 15:04     ` Quentin Perret
2018-12-03  9:56 ` [PATCH v10 05/15] sched/topology: Reference the Energy Model of CPUs when available Quentin Perret
2018-12-11 15:34   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 06/15] sched/topology: Lowest CPU asymmetry sched_domain level pointer Quentin Perret
2018-12-11 15:34   ` [tip:sched/core] sched/topology: Add lowest " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 07/15] sched/topology: Disable EAS on inappropriate platforms Quentin Perret
2018-12-11 15:35   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 08/15] sched/topology: Make Energy Aware Scheduling depend on schedutil Quentin Perret
2018-12-11 15:36   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 09/15] sched: Introduce sched_energy_present static key Quentin Perret
2018-12-11 15:36   ` [tip:sched/core] sched/toplogy: Introduce the 'sched_energy_present' " tip-bot for Quentin Perret
2018-12-13 13:56     ` Quentin Perret
2018-12-03  9:56 ` [PATCH v10 10/15] sched: Introduce a sysctl for Energy Aware Scheduling Quentin Perret
2018-12-11 14:15   ` Ingo Molnar
2018-12-11 14:49     ` Quentin Perret
2018-12-13 14:03       ` Peter Zijlstra
2019-01-21 11:35   ` [tip:sched/core] sched/topology: " tip-bot for Quentin Perret
2019-01-21 13:51   ` tip-bot for Quentin Perret
2019-01-27 11:34   ` tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 11/15] sched/fair: Clean-up update_sg_lb_stats parameters Quentin Perret
2018-12-11 15:37   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 12/15] sched: Add over-utilization/tipping point indicator Quentin Perret
2018-12-11 15:37   ` tip-bot for Morten Rasmussen [this message]
2018-12-03  9:56 ` [PATCH v10 13/15] sched/fair: Introduce an energy estimation helper function Quentin Perret
2018-12-11 15:38   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 14/15] sched/fair: Select an energy-efficient CPU on task wake-up Quentin Perret
2018-12-11 15:39   ` [tip:sched/core] " tip-bot for Quentin Perret
2018-12-03  9:56 ` [PATCH v10 15/15] OPTIONAL: cpufreq: dt: Register an Energy Model Quentin Perret
2019-01-08 20:38   ` Matthias Kaehlcke
2019-01-09 10:57     ` Quentin Perret
2019-01-09 18:14       ` Matthias Kaehlcke
2019-01-10  9:08         ` Quentin Perret

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=tip-2802bf3cd936fe2c8033a696d375a4d9d3974de4@git.kernel.org \
    --to=tipbot@zytor.com \
    --cc=efault@gmx.de \
    --cc=hpa@zytor.com \
    --cc=linux-kernel@vger.kernel.org \
    --cc=linux-tip-commits@vger.kernel.org \
    --cc=mingo@kernel.org \
    --cc=morten.rasmussen@arm.com \
    --cc=peterz@infradead.org \
    --cc=quentin.perret@arm.com \
    --cc=tglx@linutronix.de \
    --cc=torvalds@linux-foundation.org \
    --subject='Re: [tip:sched/core] sched/fair: Add over-utilization/tipping point indicator' \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).