Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1630301 > unrolled thread

Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-25 10:40 +0200
    Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Tejun Heo <tj@kernel.org> - 2017-04-25 20:20 +0200
      Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-26 19:00 +0200
        Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Tejun Heo <tj@kernel.org> - 2017-04-27 00:50 +0200
          Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Vincent Guittot <vincent.guittot@linaro.org> - 2017-04-27 09:10 +0200
        Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Peter Zijlstra <peterz@infradead.org> - 2017-05-01 16:20 +0200
          Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Peter Zijlstra <peterz@infradead.org> - 2017-05-01 17:00 +0200
          Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Tejun Heo <tj@kernel.org> - 2017-05-02 00:00 +0200
            Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Peter Zijlstra <peterz@infradead.org> - 2017-05-02 10:20 +0200
              Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Peter Zijlstra <peterz@infradead.org> - 2017-05-02 10:40 +0200
                Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Tejun Heo <tj@kernel.org> - 2017-05-02 22:10 +0200
                  Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq  to its sched_entity Peter Zijlstra <peterz@infradead.org> - 2017-05-03 11:20 +0200

#1630301 — Re: [PATCH 1/2] sched/fair: Fix how load gets propagated from cfs_rq to its sched_entity

Hi Tejun

On 24 April 2017 at 22:14, Tejun Heo <tj@kernel.org> wrote:
> 09a43ace1f98 ("sched/fair: Propagate load during synchronous
> attach/detach") added immediate load propagation from cfs_rq to its
> sched_entity then to the parent cfs_rq; however, what gets propagated
> doesn't seem to make sense.
>
> It repeats the tg_weight calculation done in calc_cfs_shares() but
> only uses it to compensate for shares being out of date.  After that,
> it sets the sched_entity's load_avg to the load_avg of the
> corresponding cfs_rq.
>
> This doesn't make sense as the cfs_rq's load_avg is some fraction of
> its total weight, which the sched_entity's weight has nothing to with.
> For example, if the cfs_rq has a single constant load 1 task the
> cfs_rq's load_avg would be around 1.  If that cfs_rq is the only
> active sched_entity in the parent cfs_rq which has the maximum weight,
> the sched_entity's load should be around the maximum weight but
> update_tg_cfs_load() ends up overriding it to 1.

not sure to catch your example:
a task TA with a load_avg = 1 is the only task in a task group GB so
the cfs_rq load_avg = 1 too and the group_entity of this cfs_rq has
got a weight of 1024 (I use 10bits format for readability) which is
the total share of task group GB

Are you saying that the group_entity load_avg should be around 1024 and not 1 ?

I would say it depends of TA weight. I assume that TA weight is the
default value (1024) as you don't specify any value in your example

If TA directly runs at parent level, its sched_entity would have a
load_avg of 1 so why the group entity load_avg should be 1024 ? it
will just temporally show the cfs_rq more loaded than it is really and
at the end the group entity load_avg will go back to 1

>
> At the parent's level, the absolute value of load_avg inside a child
> cfs_rq doesn't mean anything.  Only the ratio against its weight is
> meaningful.
>
> This patch changes update_tg_cfs_load() to normalize the
> runnable_load_avg of the cfs_rq and then scale it to the matching
> sched_entity's freshly calculated shares for propagation.  Use of
> runnable_load_avg instead of load_avg is intentional and keeps the
> parent's runnable_load_avg true to the sum of scaled loads of all
> tasks queued under it which is critical for the correction operation
> of load balancer.  The next patch will depend on it.
>
> Signed-off-by: Tejun Heo <tj@kernel.org>
> Cc: Vincent Guittot <vincent.guittot@linaro.org>
> Cc: Ingo Molnar <mingo@redhat.com>
> Cc: Peter Zijlstra <peterz@infradead.org>
> Cc: Mike Galbraith <efault@gmx.de>
> Cc: Paul Turner <pjt@google.com>
> ---
>  kernel/sched/fair.c |   46 +++++++++++++++++++---------------------------
>  1 file changed, 19 insertions(+), 27 deletions(-)
>
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -3078,37 +3078,29 @@ static inline void
>  update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
>  {
>         struct cfs_rq *gcfs_rq = group_cfs_rq(se);
> -       long delta, load = gcfs_rq->avg.load_avg;
> +       long load = 0, delta;
>
>         /*
> -        * If the load of group cfs_rq is null, the load of the
> -        * sched_entity will also be null so we can skip the formula
> +        * A cfs_rq's load avg contribution to the parent should be scaled
> +        * to the sched_entity's weight.  Use freshly calculated shares
> +        * instead of @se->load.weight as the latter may not reflect
> +        * changes from the current scheduling operation.
> +        *
> +        * Note that the propagation source is runnable_load_avg instead of
> +        * load_avg.  This keeps every cfs_rq's runnable_load_avg true to
> +        * the sum of the scaled loads of all tasks queued under it, which
> +        * is important for the correct operation of the load balancer.
> +        *
> +        * This can make the sched_entity's load_avg jumpier but that
> +        * correctly reflects what would happen without cgroups if each
> +        * task's load is scaled across nesting - the load is being
> +        * averaged at the task and each cfs_rq.
>          */
> -       if (load) {
> -               long tg_load;
> +       if (gcfs_rq->load.weight) {
> +               long shares = calc_cfs_shares(gcfs_rq, gcfs_rq->tg);
>
> -               /* Get tg's load and ensure tg_load > 0 */
> -               tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
> -
> -               /* Ensure tg_load >= load and updated with current load*/
> -               tg_load -= gcfs_rq->tg_load_avg_contrib;
> -               tg_load += load;
> -
> -               /*
> -                * We need to compute a correction term in the case that the
> -                * task group is consuming more CPU than a task of equal
> -                * weight. A task with a weight equals to tg->shares will have
> -                * a load less or equal to scale_load_down(tg->shares).
> -                * Similarly, the sched_entities that represent the task group
> -                * at parent level, can't have a load higher than
> -                * scale_load_down(tg->shares). And the Sum of sched_entities'
> -                * load must be <= scale_load_down(tg->shares).
> -                */
> -               if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
> -                       /* scale gcfs_rq's load into tg's shares*/
> -                       load *= scale_load_down(gcfs_rq->tg->shares);
> -                       load /= tg_load;
> -               }
> +               load = min(gcfs_rq->runnable_load_avg *
> +                          shares / gcfs_rq->load.weight, shares);
>         }
>
>         delta = load - se->avg.load_avg;

[toc] | [next] | [standalone]

#1630860

Hello,

On Tue, Apr 25, 2017 at 10:35:53AM +0200, Vincent Guittot wrote:
> not sure to catch your example:
> a task TA with a load_avg = 1 is the only task in a task group GB so
> the cfs_rq load_avg = 1 too and the group_entity of this cfs_rq has
> got a weight of 1024 (I use 10bits format for readability) which is
> the total share of task group GB

The group_entity (the sched_entity corresponding to the cfs_rq) should
behave as if it's a task which has the weight of 1024.

> Are you saying that the group_entity load_avg should be around 1024 and not 1 ?

Yes.

> I would say it depends of TA weight. I assume that TA weight is the
> default value (1024) as you don't specify any value in your example

Please consider the following configuration, where GA is a group
entity, and TA and TB are tasks.

	ROOT - GA (weight 1024) - TA (weight 1)
	     \ GB (weight 1   ) - TB (weight 1)

Let's say both TA and TB are running full-tilt.  Now let's take out GA
and GB.

	ROOT - TA1 (weight 1024)
	     \ TB1 (weight 1   )

GA should behave the same as TA1 and GB TB1.  GA's load should match
TA1's, and GA's load when seen from ROOT's cfs_rq has nothing to do
with how much total absolute weight it has inside it.

	ROOT - GA2 (weight 1024) - TA2 (weight 1   )
	     \ GB2 (weight 1   ) - TB2 (weight 1024)

If TA2 and TB2 are constantly running, GA2 and GB2's in ROOT's cfs_rq
should match GA and GB's, respectively.

> If TA directly runs at parent level, its sched_entity would have a
> load_avg of 1 so why the group entity load_avg should be 1024 ? it

Because then the hierarchical weight configuration doesn't mean
anything.

> will just temporally show the cfs_rq more loaded than it is really and
> at the end the group entity load_avg will go back to 1

It's not temporary.  The weight of a group is its shares, which is its
load fraction of the configured weight of the group.  Assuming UP, if
you configure a group to the weight of 1024 and have any task running
full-tilt in it, the group will converge to the load of 1024.  The
problem is that the propagation logic is currently doing something
completely different and temporarily push down the load whenever it
triggers.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1631605

Le Tuesday 25 Apr 2017 à 11:12:19 (-0700), Tejun Heo a écrit :
> Hello,
> 
> On Tue, Apr 25, 2017 at 10:35:53AM +0200, Vincent Guittot wrote:
> > not sure to catch your example:
> > a task TA with a load_avg = 1 is the only task in a task group GB so
> > the cfs_rq load_avg = 1 too and the group_entity of this cfs_rq has
> > got a weight of 1024 (I use 10bits format for readability) which is
> > the total share of task group GB
> 
> The group_entity (the sched_entity corresponding to the cfs_rq) should
> behave as if it's a task which has the weight of 1024.
> 
> > Are you saying that the group_entity load_avg should be around 1024 and not 1 ?
> 
> Yes.
> 
> > I would say it depends of TA weight. I assume that TA weight is the
> > default value (1024) as you don't specify any value in your example
> 
> Please consider the following configuration, where GA is a group
> entity, and TA and TB are tasks.
> 
> 	ROOT - GA (weight 1024) - TA (weight 1)
> 	     \ GB (weight 1   ) - TB (weight 1)
> 
> Let's say both TA and TB are running full-tilt.  Now let's take out GA
> and GB.
> 
> 	ROOT - TA1 (weight 1024)
> 	     \ TB1 (weight 1   )
> 
> GA should behave the same as TA1 and GB TB1.  GA's load should match
> TA1's, and GA's load when seen from ROOT's cfs_rq has nothing to do
> with how much total absolute weight it has inside it.
> 
> 	ROOT - GA2 (weight 1024) - TA2 (weight 1   )
> 	     \ GB2 (weight 1   ) - TB2 (weight 1024)
> 
> If TA2 and TB2 are constantly running, GA2 and GB2's in ROOT's cfs_rq
> should match GA and GB's, respectively.

Yes I agree

> 
> > If TA directly runs at parent level, its sched_entity would have a
> > load_avg of 1 so why the group entity load_avg should be 1024 ? it
> 
> Because then the hierarchical weight configuration doesn't mean
> anything.
> 
> > will just temporally show the cfs_rq more loaded than it is really and
> > at the end the group entity load_avg will go back to 1
> 
> It's not temporary.  The weight of a group is its shares, which is its
> load fraction of the configured weight of the group.  Assuming UP, if
> you configure a group to the weight of 1024 and have any task running
> full-tilt in it, the group will converge to the load of 1024.  The
> problem is that the propagation logic is currently doing something
> completely different and temporarily push down the load whenever it
> triggers.

Ok, I see your point and agree that there is an issue when propagating
load_avg of a task group which has tasks with lower weight than the share
but your proposal has got issue because it uses runnable_load_avg instead
of load_avg and this makes propagation of loadavg_avg incorrect, something
like below which keeps using load_avg solve the problem

+	if (gcfs_rq->load.weight) {
+		long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
+
+		load = min(gcfs_rq->avg.load_avg *
+			   shares / scale_load_down(gcfs_rq->load.weight), shares);

I have run schbench with the change above on v4.11-rc8 and latency are ok

Thanks
Vincent
>
> 
> Thanks.
> 
> -- 
> tejun

[toc] | [prev] | [next] | [standalone]

#1631778

Hello,

On Wed, Apr 26, 2017 at 06:51:23PM +0200, Vincent Guittot wrote:
> > It's not temporary.  The weight of a group is its shares, which is its
> > load fraction of the configured weight of the group.  Assuming UP, if
> > you configure a group to the weight of 1024 and have any task running
> > full-tilt in it, the group will converge to the load of 1024.  The
> > problem is that the propagation logic is currently doing something
> > completely different and temporarily push down the load whenever it
> > triggers.
> 
> Ok, I see your point and agree that there is an issue when propagating
> load_avg of a task group which has tasks with lower weight than the share
> but your proposal has got issue because it uses runnable_load_avg instead
> of load_avg and this makes propagation of loadavg_avg incorrect, something
> like below which keeps using load_avg solve the problem
> 
> +	if (gcfs_rq->load.weight) {
> +		long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
> +
> +		load = min(gcfs_rq->avg.load_avg *
> +			   shares / scale_load_down(gcfs_rq->load.weight), shares);
> 
> I have run schbench with the change above on v4.11-rc8 and latency are ok

Hmm... so, I'll test this but this wouldn't solve the problem of
root's runnable_load_avg being out of sync with the approximate sum of
all task loads, which is the cause of the latencies that I'm seeing.

Are you saying that with the above change, you're not seeing the
higher latency issue that you reported in the other reply?

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1631915

On 27 April 2017 at 00:40, Tejun Heo <tj@kernel.org> wrote:
> Hello,
>
> On Wed, Apr 26, 2017 at 06:51:23PM +0200, Vincent Guittot wrote:
>> > It's not temporary.  The weight of a group is its shares, which is its
>> > load fraction of the configured weight of the group.  Assuming UP, if
>> > you configure a group to the weight of 1024 and have any task running
>> > full-tilt in it, the group will converge to the load of 1024.  The
>> > problem is that the propagation logic is currently doing something
>> > completely different and temporarily push down the load whenever it
>> > triggers.
>>
>> Ok, I see your point and agree that there is an issue when propagating
>> load_avg of a task group which has tasks with lower weight than the share
>> but your proposal has got issue because it uses runnable_load_avg instead
>> of load_avg and this makes propagation of loadavg_avg incorrect, something
>> like below which keeps using load_avg solve the problem
>>
>> +     if (gcfs_rq->load.weight) {
>> +             long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
>> +
>> +             load = min(gcfs_rq->avg.load_avg *
>> +                        shares / scale_load_down(gcfs_rq->load.weight), shares);
>>
>> I have run schbench with the change above on v4.11-rc8 and latency are ok
>
> Hmm... so, I'll test this but this wouldn't solve the problem of
> root's runnable_load_avg being out of sync with the approximate sum of
> all task loads, which is the cause of the latencies that I'm seeing.
>
> Are you saying that with the above change, you're not seeing the
> higher latency issue that you reported in the other reply?

yes I don't have any latency regression like v4.11-rc8 with the above
change that uses load_avg but fix the propagation for of a task with a
lower weight than task group share.

>
> Thanks.
>
> --
> tejun

[toc] | [prev] | [next] | [standalone]

#1633683

Hi,

sorry for being late to the party, trying to catch-up..

On Wed, Apr 26, 2017 at 06:51:23PM +0200, Vincent Guittot wrote:
> Ok, I see your point and agree that there is an issue when propagating
> load_avg of a task group which has tasks with lower weight than the share
> but your proposal has got issue because it uses runnable_load_avg instead
> of load_avg and this makes propagation of loadavg_avg incorrect, something
> like below which keeps using load_avg solve the problem
> 
> +	if (gcfs_rq->load.weight) {
> +		long shares = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg));
> +
> +		load = min(gcfs_rq->avg.load_avg *
> +			   shares / scale_load_down(gcfs_rq->load.weight), shares);
> 


So this here does:

  ( tg->load_avg = \Sum cfs_rq->load_avg )

  load      = cfs_rq->load.weight

  tg_weight = tg->load_avg - cfs_rq->contrib + load


           tg->shares * load
  shares = -----------------
               tg_weight


                        cfs_rq->load_avg
  avg_shares = shares * ----------------
                              load

	       tg->shares * cfs_rq->load_avg
             = -----------------------------
                      tg_weight


  ( se->load.weight = shares )

  se->load_avg = min(shares, avg_shares);


So where shares (and se->load.weight) are an upper bound (due to using
cfs_rq->load.weight, see calc_cfs_shares), avg_shares is supposedly a
more accurate representation based on our PELT averages.

This looks OK; and I agree with Vincent that we should use
cfs_rq->avg.load_avg, not cfs_rq->runnable_load_avg, since tg->load_avg
is a sum of the former, not the latter.

Also, arguably calculating the above avg_shares directly (using the
second equation) might be more precise; but I doubt it makes much of a
difference, however since we do min(), we should at least clamp against
MIN_SHARES again.

Furthermore, it appears to me we want a different tg_weight value for
the avg_shares, something like:

  tg_weight = tg->load_avg - cfs_rq->contrib + cfs_rq->avg.load_avg

To better match with the numerator's units, otherwise it will have a
tendency to push avg_shares down further than it needs to be.


(All assuming it actually works of course.. compile tested only)

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2634,7 +2634,9 @@ account_entity_dequeue(struct cfs_rq *cf
 # ifdef CONFIG_SMP
 static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
+
+	tg_shares = READ_ONCE(tg->shares);
 
 	/*
 	 * This really should be: cfs_rq->avg.load_avg, but instead we use
@@ -2665,12 +2667,7 @@ static long calc_cfs_shares(struct cfs_r
 	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
 	 * instead of 0.
 	 */
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
-	if (shares > tg->shares)
-		shares = tg->shares;
-
-	return shares;
+	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
 # else /* CONFIG_SMP */
 static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
@@ -3075,37 +3072,69 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
+	long load = 0, delta;
 
 	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
+	 * If there is load in our group cfs_rq (@gcfs_rq), then update its
+	 * corresponding group se (@se) load value to reflect any change in
+	 * weights.
+	 *
+	 * Also see effective_load(), where we do something similar.
+	 *
+	 *   ( tg->load_avg = \Sum cfs_rq->load_avg )
+	 *   
+	 *   tg_weight = tg->load_avg - cfs_rq->contrib
+	 *   
+	 *   
+	 *            tg->shares * cfs_rq->weight
+	 *   shares = ---------------------------
+	 *            tg_weight  + cfs_rq->weight
+	 *   
+	 *   
+	 *		  tg->shares * cfs_rq->load_avg
+	 *   avg_shares = -----------------------------
+	 *                tg_weight  + cfs_rq->load_avg
+	 *   
+	 *   
+	 *   ( se->load.weight = shares )
+	 *   
+	 *   se->load_avg = min(shares, avg_shares);
+	 *
+	 * Where @shares is an upper bound to @avg_shares, see the comments
+	 * in calc_cfs_shares().
 	 */
-	if (load) {
-		long tg_load;
-
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
+	if (gcfs_rq->load.weight) {
+		long tg_weight1, tg_weight2, tg_shares, shares, avg_shares;
+		struct task_group *tg = gcfs_rq->tg;
 
 		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
+		 * This open-codes calc_cfs_shares(), in order to ensure
+		 * we use consistent values for @shares and @avg_shares,
+		 * as well as make sure we clip the result properly.
 		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
+
+		tg_shares = READ_ONCE(tg->shares);
+
+		load = scale_load_down(gcfs_rq->load.weight);
+
+		tg_weight1 = atomic_long_read(&tg->load_avg);
+		tg_weight2 = (tg_weight1 -= cfs_rq->tg_load_avg_contrib);
+		tg_weight1 += load;
+
+		shares = tg_shares * load;
+		if (tg_weight1)
+			shares /= tg_weight1;
+
+
+		load = READ_ONCE(gcfs_rq->avg.load_avg);
+
+		tg_weight2 += load;
+
+		avg_shares = tg_shares * load;
+		if (tg_weight2)
+			avg_shares /= tg_weight2;
+
+		load = clamp_t(long, min(shares, avg_shares), MIN_SHARES, tg_shares);
 	}
 
 	delta = load - se->avg.load_avg;

[toc] | [prev] | [next] | [standalone]

#1633696

On Mon, May 01, 2017 at 04:17:33PM +0200, Peter Zijlstra wrote:

> So this here does:
> 
>   ( tg->load_avg = \Sum cfs_rq->load_avg )
> 
>   load      = cfs_rq->load.weight
> 
>   tg_weight = tg->load_avg - cfs_rq->contrib + load
> 
> 
>            tg->shares * load
>   shares = -----------------
>                tg_weight
> 
> 
>                         cfs_rq->load_avg
>   avg_shares = shares * ----------------
>                               load
> 
> 	       tg->shares * cfs_rq->load_avg
>              = -----------------------------
>                       tg_weight
> 
> 
>   ( se->load.weight = shares )
> 
>   se->load_avg = min(shares, avg_shares);

I wonder though; do we really need the min() ? Can't we simply use
avg_shares all the time?

[toc] | [prev] | [next] | [standalone]

#1633981

Hello, Peter.

On Mon, May 01, 2017 at 04:17:33PM +0200, Peter Zijlstra wrote:
> So this here does:
> 
>   ( tg->load_avg = \Sum cfs_rq->load_avg )
> 
>   load      = cfs_rq->load.weight
> 
>   tg_weight = tg->load_avg - cfs_rq->contrib + load
> 
> 
>            tg->shares * load
>   shares = -----------------
>                tg_weight
> 
> 
>                         cfs_rq->load_avg
>   avg_shares = shares * ----------------
>                               load
> 
> 	       tg->shares * cfs_rq->load_avg
>              = -----------------------------
>                       tg_weight
> 
> 
>   ( se->load.weight = shares )
> 
>   se->load_avg = min(shares, avg_shares);
> 
> 
> So where shares (and se->load.weight) are an upper bound (due to using
> cfs_rq->load.weight, see calc_cfs_shares), avg_shares is supposedly a
> more accurate representation based on our PELT averages.
> 
> This looks OK; and I agree with Vincent that we should use
> cfs_rq->avg.load_avg, not cfs_rq->runnable_load_avg, since tg->load_avg
> is a sum of the former, not the latter.

With this, we end up using a different metric for picking the busiest
queue depending on whether there are nested cfs_rq's or not.  The
root's runnable_load_avg ends up including blocked load avgs queued
behind nested cfs_rq's because we lose the resolution across threads
across nesting.

> Also, arguably calculating the above avg_shares directly (using the
> second equation) might be more precise; but I doubt it makes much of a
> difference, however since we do min(), we should at least clamp against
> MIN_SHARES again.
> 
> Furthermore, it appears to me we want a different tg_weight value for
> the avg_shares, something like:
> 
>   tg_weight = tg->load_avg - cfs_rq->contrib + cfs_rq->avg.load_avg
> 
> To better match with the numerator's units, otherwise it will have a
> tendency to push avg_shares down further than it needs to be.
> 
> 
> (All assuming it actually works of course.. compile tested only)

So, if changing gcfs_rq se->load_avg.avg to match the gcfs_rq's
runnable_load_avg is icky, and I can see why that would be, we can
simply introduce a separate channel of propagation so that
runnable_load_avg gets propagated independently from se->load_avg
propagation, so that for all every cfs_rq, its runnable_load_avg is
the sum of all active load_avgs queued on itself and its descendents,
which is the number we want for load balancing anyway.  I'll try to
spin a patch which does that.

I still wonder what gcfs_rq se->load_avg.avg is good for tho?  It's
nice to keep the value in line but is it actually used anywhere?  The
parent cfs_rq's values are independently calculated and, AFAICS, the
only time the value is used is to propagate into the parent's
runnable_load_sum, which has to use a different value, as explained
above.

Thanks.

-- 
tejun

[toc] | [prev] | [next] | [standalone]

#1634233

On Mon, May 01, 2017 at 05:56:04PM -0400, Tejun Heo wrote:

> I still wonder what gcfs_rq se->load_avg.avg is good for tho?  It's
> nice to keep the value in line but is it actually used anywhere?

Its used to manage its parent's cfs_rq sums boundary conditions. When we
enqueue the group se to the parent group, we do:

  enqueue_entity()
    enqueue_entity_load_avg()
      // update runnable
      // add se.avg to cfs_rq.avg if 'migrated'

Now obviously group se's never actually migrate between CPUs, but they
still pass through that code. I think the 'migrate' condition also
triggers for new entities for example, they 'migrate' into the system.

Similar for dequeue, that should trigger when groups entities
get destroyed, they 'migrate' out of the system.

But I get what you're saying. They're not overly useful as such.

> So, if changing gcfs_rq se->load_avg.avg to match the gcfs_rq's
> runnable_load_avg is icky, and I can see why that would be, we can
> simply introduce a separate channel of propagation ...

Can you have a play with something like the below? I suspect
'shares_runnable' might work for you here.

Its still 'icky', but not more so than calc_cfs_shares() was to begin
with. When many CPUs are involved the global sum (tg_shares) is still
dominated by avg_load and the division will have a downward bias, but
given the purpose that might not be too bad.

---
 kernel/sched/fair.c | 62 +++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 44 insertions(+), 18 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index a903276fcb62..7d1fb5f421bc 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2630,26 +2630,56 @@ static inline void account_numa_dequeue(struct rq *rq, struct task_struct *p)
 	cfs_rq->nr_running--;
 }
 
+enum shares_type {
+	shares_runnable,
+	shares_avg,
+	shares_weight,
+};
+
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
-static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
+static long
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
 
-	/*
-	 * This really should be: cfs_rq->avg.load_avg, but instead we use
-	 * cfs_rq->load.weight, which is its upper bound. This helps ramp up
-	 * the shares for small weight interactive tasks.
-	 */
-	load = scale_load_down(cfs_rq->load.weight);
+	tg_shares = READ_ONCE(tg->shares);
+
+	switch (shares_type) {
+	case shares_runnable:
+		/*
+		 * Instead of the correct cfs_rq->avg.load_avg we use
+		 * cfs_rq->runnable_load_avg, which does not include the
+		 * blocked load.
+		 */
+		load = cfs_rq->runnable_load_avg;
+		break;
+
+	case shares_avg:
+		load = cfs_rq->avg.load_avg;
+		break;
+
+	case shares_weight:
+		/*
+		 * Instead of the correct cfs_rq->avg.load_avg we use
+		 * cfs_rq->load.weight, which is its upper bound. This helps
+		 * ramp up the shares for small weight interactive tasks.
+		 */
+		load = scale_load_down(cfs_rq->load.weight);
+		break;
+	}
 
 	tg_weight = atomic_long_read(&tg->load_avg);
 
-	/* Ensure tg_weight >= load */
+	/*
+	 * This ensures the sum is up-to-date for this CPU, in case of the other
+	 * two approximations it biases the sum towards their value and in case
+	 * of (near) UP ensures the division ends up <= 1.
+	 */
 	tg_weight -= cfs_rq->tg_load_avg_contrib;
 	tg_weight += load;
 
-	shares = (tg->shares * load);
+	shares = (tg_shares * load);
 	if (tg_weight)
 		shares /= tg_weight;
 
@@ -2665,15 +2695,11 @@ static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
 	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
 	 * instead of 0.
 	 */
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
-	if (shares > tg->shares)
-		shares = tg->shares;
-
-	return shares;
+	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
 # else /* CONFIG_SMP */
-static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
+static inline long
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
 {
 	return tg->shares;
 }
@@ -2715,7 +2741,7 @@ static void update_cfs_shares(struct sched_entity *se)
 	if (likely(se->load.weight == tg->shares))
 		return;
 #endif
-	shares = calc_cfs_shares(cfs_rq, tg);
+	shares = calc_cfs_shares(cfs_rq, tg, shares_weight);
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }

[toc] | [prev] | [next] | [standalone]

#1634244

On Tue, May 02, 2017 at 10:19:05AM +0200, Peter Zijlstra wrote:
> Can you have a play with something like the below? I suspect
> 'shares_runnable' might work for you here.

> ---
>  kernel/sched/fair.c | 62 +++++++++++++++++++++++++++++++++++++----------------
>  1 file changed, 44 insertions(+), 18 deletions(-)

So something like so on top I suppose...

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -3101,38 +3101,7 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = gcfs_rq->avg.load_avg;
-
-	/*
-	 * If the load of group cfs_rq is null, the load of the
-	 * sched_entity will also be null so we can skip the formula
-	 */
-	if (load) {
-		long tg_load;
-
-		/* Get tg's load and ensure tg_load > 0 */
-		tg_load = atomic_long_read(&gcfs_rq->tg->load_avg) + 1;
-
-		/* Ensure tg_load >= load and updated with current load*/
-		tg_load -= gcfs_rq->tg_load_avg_contrib;
-		tg_load += load;
-
-		/*
-		 * We need to compute a correction term in the case that the
-		 * task group is consuming more CPU than a task of equal
-		 * weight. A task with a weight equals to tg->shares will have
-		 * a load less or equal to scale_load_down(tg->shares).
-		 * Similarly, the sched_entities that represent the task group
-		 * at parent level, can't have a load higher than
-		 * scale_load_down(tg->shares). And the Sum of sched_entities'
-		 * load must be <= scale_load_down(tg->shares).
-		 */
-		if (tg_load > scale_load_down(gcfs_rq->tg->shares)) {
-			/* scale gcfs_rq's load into tg's shares*/
-			load *= scale_load_down(gcfs_rq->tg->shares);
-			load /= tg_load;
-		}
-	}
+	long delta, load = calc_cfs_shares(gcfs_rq, gcfs_rq->tg, shares_runnable);
 
 	delta = load - se->avg.load_avg;
 

[toc] | [prev] | [next] | [standalone]

#1634598

Hello, Peter.

Your changes need the following fix patch.  With the fix and
"sched/fair: Always propagate runnable_load_avg" applied, it seems to
work fine.  The propagated number is a bit different but I don't see
noticeable difference in behavior and the new number seems to better
represent what we need.

Thanks.
---
 kernel/sched/fair.c |    7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)

--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -2645,7 +2645,8 @@ enum shares_type {
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
 static long
-calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg,
+		enum shares_type shares_type)
 {
 	long tg_weight, tg_shares, load, shares;
 
@@ -2705,7 +2706,7 @@ calc_cfs_shares(struct cfs_rq *cfs_rq, s
 }
 # else /* CONFIG_SMP */
 static inline long
-calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type)
+calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, enum shares_type shares_type)
 {
 	return tg->shares;
 }
@@ -3104,7 +3105,7 @@ static inline void
 update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	struct cfs_rq *gcfs_rq = group_cfs_rq(se);
-	long delta, load = calc_cfs_shares(gcfs_rq, gcfs_rq->tg, shares_runnable);
+	long delta, load = scale_load_down(calc_cfs_shares(gcfs_rq, gcfs_rq->tg, shares_runnable));
 
 	delta = load - se->avg.load_avg;
 

[toc] | [prev] | [next] | [standalone]

#1634827

On Tue, May 02, 2017 at 04:00:28PM -0400, Tejun Heo wrote:
> Hello, Peter.
> 
> Your changes need the following fix patch.

D'0h, so much for not running my patches through a compiler ;-)

> With the fix and
> "sched/fair: Always propagate runnable_load_avg" applied, it seems to
> work fine.  The propagated number is a bit different but I don't see
> noticeable difference in behavior and the new number seems to better
> represent what we need.

Right. Let me stare at that always propagate thing a bit. My instant
worry is overhead, but yeah, we need something to make this work.

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web