From: Quentin Perret <quentin.perret@arm.com> To: peterz@infradead.org, rjw@rjwysocki.net, linux-kernel@vger.kernel.org, linux-pm@vger.kernel.org Cc: gregkh@linuxfoundation.org, mingo@redhat.com, dietmar.eggemann@arm.com, morten.rasmussen@arm.com, chris.redpath@arm.com, patrick.bellasi@arm.com, valentin.schneider@arm.com, vincent.guittot@linaro.org, thara.gopinath@linaro.org, viresh.kumar@linaro.org, tkjos@google.com, joel@joelfernandes.org, smuckle@google.com, adharmap@codeaurora.org, skannan@codeaurora.org, pkondeti@codeaurora.org, juri.lelli@redhat.com, edubezval@gmail.com, srinivas.pandruvada@linux.intel.com, currojerez@riseup.net, javi.merino@kernel.org, quentin.perret@arm.com Subject: [PATCH v10 12/15] sched: Add over-utilization/tipping point indicator Date: Mon, 3 Dec 2018 09:56:25 +0000 [thread overview] Message-ID: <20181203095628.11858-13-quentin.perret@arm.com> (raw) In-Reply-To: <20181203095628.11858-1-quentin.perret@arm.com> From: Morten Rasmussen <morten.rasmussen@arm.com> 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. cc: Ingo Molnar <mingo@redhat.com> cc: Peter Zijlstra <peterz@infradead.org> Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com> [ Added a comment explaining why new tasks are not accounted during overutilization detection ] Signed-off-by: Quentin Perret <quentin.perret@arm.com> --- 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 e21f37129395..c3b2dad72c9c 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 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd 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 4c1e4b73f40d..28d9209554dc 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -717,6 +717,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 @@ -740,6 +741,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). -- 2.19.2
next prev parent reply other threads:[~2018-12-03 9:57 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 ` Quentin Perret [this message] 2018-12-11 15:37 ` [tip:sched/core] sched/fair: Add over-utilization/tipping point indicator tip-bot for Morten Rasmussen 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=20181203095628.11858-13-quentin.perret@arm.com \ --to=quentin.perret@arm.com \ --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=linux-kernel@vger.kernel.org \ --cc=linux-pm@vger.kernel.org \ --cc=mingo@redhat.com \ --cc=morten.rasmussen@arm.com \ --cc=patrick.bellasi@arm.com \ --cc=peterz@infradead.org \ --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 \ --subject='Re: [PATCH v10 12/15] sched: 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).