From: Morten Rasmussen <morten.rasmussen@arm.com>
To: peterz@infradead.org, mingo@redhat.com
Cc: dietmar.eggemann@arm.com, yuyang.du@intel.com,
vincent.guittot@linaro.org, mgalbraith@suse.de,
linux-kernel@vger.kernel.org,
Morten Rasmussen <morten.rasmussen@arm.com>
Subject: [PATCH v2 08/13] sched/fair: Compute task/cpu utilization at wake-up more correctly
Date: Wed, 22 Jun 2016 18:03:19 +0100 [thread overview]
Message-ID: <1466615004-3503-9-git-send-email-morten.rasmussen@arm.com> (raw)
In-Reply-To: <1466615004-3503-1-git-send-email-morten.rasmussen@arm.com>
At task wake-up load-tracking isn't updated until the task is enqueued.
The task's own view of its utilization contribution may therefore not be
aligned with its contribution to the cfs_rq load-tracking which may have
been updated in the meantime. Basically, the task's own utilization
hasn't yet accounted for the sleep decay, while the cfs_rq may have
(partially). Estimating the cfs_rq utilization in case the task is
migrated at wake-up as task_rq(p)->cfs.avg.util_avg - p->se.avg.util_avg
is therefore incorrect as the two load-tracking signals aren't time
synchronized (different last update).
To solve this problem, this patch introduces task_util_wake() which
computes the decayed task utilization based on the last update of the
previous cpu's last load-tracking update. It is done without having to
take the rq lock, similar to how it is done in remove_entity_load_avg().
cc: Ingo Molnar <mingo@redhat.com>
cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Morten Rasmussen <morten.rasmussen@arm.com>
---
kernel/sched/fair.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 69 insertions(+)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index dba02c7b57b3..2874aeb08fb4 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5271,6 +5271,75 @@ static inline int task_util(struct task_struct *p)
return p->se.avg.util_avg;
}
+/*
+ * task_util_wake: Returns an updated estimate of the utilization contribution
+ * of a waking task. At wake-up the task blocked utilization contribution
+ * (cfs_rq->avg) may have decayed while the utilization tracking of the task
+ * (se->avg) hasn't yet.
+ * Note that this estimate isn't perfectly accurate as the 1ms boundaries used
+ * for updating util_avg in __update_load_avg() are not considered here. This
+ * results in an error of up to 1ms utilization decay/accumulation which leads
+ * to an absolute util_avg error margin of 1024*1024/LOAD_AVG_MAX ~= 22
+ * (for LOAD_AVG_MAX = 47742).
+ */
+static inline int task_util_wake(struct task_struct *p)
+{
+ struct cfs_rq *prev_cfs_rq = &task_rq(p)->cfs;
+ struct sched_avg *psa = &p->se.avg;
+ u64 cfs_rq_last_update, p_last_update, delta;
+ u32 util_decayed;
+
+ p_last_update = psa->last_update_time;
+
+ /*
+ * Task on rq (exec()) should be load-tracking aligned already.
+ * New tasks have no history and should use the init value.
+ */
+ if (p->se.on_rq || !p_last_update)
+ return task_util(p);
+
+ cfs_rq_last_update = cfs_rq_last_update_time(prev_cfs_rq);
+ delta = cfs_rq_last_update - p_last_update;
+
+ if ((s64)delta <= 0)
+ return task_util(p);
+
+ delta >>= 20;
+
+ if (!delta)
+ return task_util(p);
+
+ util_decayed = decay_load((u64)psa->util_sum, delta);
+ util_decayed /= LOAD_AVG_MAX;
+
+ /*
+ * psa->util_avg can be slightly out of date as it is only updated
+ * when a 1ms boundary is crossed.
+ * See 'decayed' in __update_load_avg()
+ */
+ util_decayed = min_t(unsigned long, util_decayed, task_util(p));
+
+ return util_decayed;
+}
+
+/*
+ * cpu_util_wake: Compute cpu utilization with any contributions from
+ * the waking task p removed.
+ */
+static int cpu_util_wake(int cpu, struct task_struct *p)
+{
+ unsigned long util, capacity;
+
+ /* Task has no contribution or is new */
+ if (cpu != task_cpu(p) || !p->se.avg.last_update_time)
+ return cpu_util(cpu);
+
+ capacity = capacity_orig_of(cpu);
+ util = max_t(long, cpu_rq(cpu)->cfs.avg.util_avg - task_util_wake(p), 0);
+
+ return (util >= capacity) ? capacity : util;
+}
+
static int wake_cap(struct task_struct *p, int cpu, int prev_cpu)
{
long min_cap, max_cap;
--
1.9.1
next prev parent reply other threads:[~2016-06-22 17:05 UTC|newest]
Thread overview: 64+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-06-22 17:03 [PATCH v2 00/13] sched: Clean-ups and asymmetric cpu capacity support Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 01/13] sched: Fix power to capacity renaming in comment Morten Rasmussen
2016-08-10 18:03 ` [tip:sched/core] sched/core: " tip-bot for Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 02/13] sched/fair: Consistent use of prev_cpu in wakeup path Morten Rasmussen
2016-06-22 18:04 ` Rik van Riel
2016-06-23 9:56 ` Morten Rasmussen
2016-06-23 12:24 ` Rik van Riel
2016-08-10 18:03 ` [tip:sched/core] sched/fair: Make the use of prev_cpu consistent in the " tip-bot for Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 03/13] sched/fair: Optimize find_idlest_cpu() when there is no choice Morten Rasmussen
2016-07-13 12:20 ` Vincent Guittot
2016-08-10 18:03 ` [tip:sched/core] " tip-bot for Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 04/13] sched: Introduce SD_ASYM_CPUCAPACITY sched_domain topology flag Morten Rasmussen
2016-07-11 9:55 ` Peter Zijlstra
2016-07-11 10:42 ` Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 05/13] sched: Enable SD_BALANCE_WAKE for asymmetric capacity systems Morten Rasmussen
2016-07-11 10:04 ` Peter Zijlstra
2016-07-11 10:37 ` Morten Rasmussen
2016-07-11 11:04 ` Morten Rasmussen
2016-07-11 11:24 ` Peter Zijlstra
2016-07-12 14:26 ` Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 06/13] sched: Store maximum per-cpu capacity in root domain Morten Rasmussen
2016-07-11 10:18 ` Peter Zijlstra
2016-07-11 16:16 ` Dietmar Eggemann
2016-07-12 11:42 ` Peter Zijlstra
2016-07-13 11:18 ` Dietmar Eggemann
2016-07-13 12:40 ` Vincent Guittot
2016-07-13 13:48 ` Dietmar Eggemann
2016-07-13 16:37 ` Morten Rasmussen
2016-07-14 13:25 ` Vincent Guittot
2016-07-14 15:15 ` Morten Rasmussen
2016-07-15 11:46 ` Morten Rasmussen
2016-07-15 13:39 ` Vincent Guittot
2016-07-15 16:02 ` Morten Rasmussen
2016-07-18 12:48 ` Vincent Guittot
2016-07-18 15:11 ` Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 07/13] sched/fair: Let asymmetric cpu configurations balance at wake-up Morten Rasmussen
2016-07-11 11:13 ` Peter Zijlstra
2016-07-11 12:32 ` Morten Rasmussen
2016-07-13 12:56 ` Vincent Guittot
2016-07-13 16:14 ` Morten Rasmussen
2016-07-14 13:45 ` Vincent Guittot
2016-07-15 8:37 ` Morten Rasmussen
2016-06-22 17:03 ` Morten Rasmussen [this message]
2016-06-22 17:03 ` [PATCH v2 09/13] sched/fair: Consider spare capacity in find_idlest_group() Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 10/13] sched: Add per-cpu max capacity to sched_group_capacity Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 11/13] sched/fair: Avoid pulling tasks from non-overloaded higher capacity groups Morten Rasmussen
2016-06-23 21:20 ` Sai Gurrappadi
2016-06-30 7:49 ` Morten Rasmussen
2016-07-14 16:39 ` Sai Gurrappadi
2016-07-15 8:39 ` Morten Rasmussen
2016-07-12 12:59 ` Peter Zijlstra
2016-07-12 14:34 ` Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 12/13] arm: Set SD_ASYM_CPUCAPACITY for big.LITTLE platforms Morten Rasmussen
2016-06-22 17:03 ` [PATCH v2 13/13] arm: Update arch_scale_cpu_capacity() to reflect change to define Morten Rasmussen
2016-06-28 10:20 ` [PATCH v2 00/13] sched: Clean-ups and asymmetric cpu capacity support Koan-Sin Tan
2016-06-30 7:53 ` Morten Rasmussen
2016-07-08 7:35 ` KEITA KOBAYASHI
2016-07-08 8:18 ` Morten Rasmussen
2016-07-11 8:33 ` Morten Rasmussen
2016-07-11 12:44 ` Vincent Guittot
2016-07-12 13:25 ` Peter Zijlstra
2016-07-12 14:39 ` Morten Rasmussen
2016-07-13 12:06 ` Vincent Guittot
2016-07-13 15:54 ` Morten Rasmussen
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=1466615004-3503-9-git-send-email-morten.rasmussen@arm.com \
--to=morten.rasmussen@arm.com \
--cc=dietmar.eggemann@arm.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mgalbraith@suse.de \
--cc=mingo@redhat.com \
--cc=peterz@infradead.org \
--cc=vincent.guittot@linaro.org \
--cc=yuyang.du@intel.com \
/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
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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).