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

Groups > linux.kernel > #1175840 > unrolled thread

Re: [PATCH?] Livelock in pick_next_task_fair() / idle_balance()

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?] Livelock in pick_next_task_fair() / idle_balance() Yuyang Du <yuyang.du@intel.com> - 2015-07-02 11:00 +0200
    Re: [PATCH?] Livelock in pick_next_task_fair() / idle_balance() Morten Rasmussen <morten.rasmussen@arm.com> - 2015-07-03 11:40 +0200
      Re: [PATCH?] Livelock in pick_next_task_fair() / idle_balance() Peter Zijlstra <peterz@infradead.org> - 2015-07-03 18:40 +0200
      Re: [PATCH?] Livelock in pick_next_task_fair() / idle_balance() Rabin Vincent <rabin.vincent@axis.com> - 2015-07-07 13:20 +0200

#1175840 — Re: [PATCH?] Livelock in pick_next_task_fair() / idle_balance()

Hi Mike,

On Thu, Jul 02, 2015 at 10:05:47AM +0200, Mike Galbraith wrote:
> On Thu, 2015-07-02 at 07:25 +0800, Yuyang Du wrote:
> 
> > That being said, it is also obvious to prevent the livelock from happening:
> > idle pulling until the source rq's nr_running is 1, becuase otherwise we
> > just avoid idleness by making another idleness.
> 
> Yeah, but that's just the symptom, not the disease.  Better for the idle
> balance symptom may actually be to only pull one when idle balancing.
> After all, the immediate goal is to find something better to do than
> idle, not to achieve continual perfect (is the enemy of good) balance.
> 
Symptom? :)

You mean "pull one and stop, can't be greedy"? Right, but still need to
assure you don't make another idle CPU (meaning until nr_running == 1), which
is the cure to disease.

I am ok with at most "pull one", but probably we stick to the load_balance()
by pulling an fair amount, assuming load_balance() magically computes the
right imbalance, otherwise you may have to do multiple "pull one"s.

Thanks,
Yuyang
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [next] | [standalone]

#1176442

On Fri, Jul 03, 2015 at 03:37:02AM +0800, Yuyang Du wrote:
> Hi Morten,
> 
> On Thu, Jul 02, 2015 at 12:40:32PM +0100, Morten Rasmussen wrote:
> > detach_tasks() will attempts to pull 62 based on tasks task_h_load() but
> > the task_h_load() sum is only 5 + 10 + 0 and hence detach_tasks() will
> > empty the src_rq.
> > 
> > IOW, since task groups include blocked load in the load_avg_contrib (see
> > __update_group_entity_contrib() and __update_cfs_rq_tg_load_contrib()) the
> > imbalance includes blocked load and hence env->imbalance >=
> > sum(task_h_load(p)) for all tasks p on the rq. Which leads to
> > detach_tasks() emptying the rq completely in the reported scenario where
> > blocked load > runnable load.
> 
> Whenever I want to know the load avg concerning task group, I need to
> walk through the complete codes again, I prefer not to do it this time.
> But it should not be that simply to say "the 118 comes from the blocked load".

But the whole hierarchy of group entities is updated each time we enqueue
or dequeue a task. I don't see how the group entity load_avg_contrib is
not up to date? Why do you need to update it again?

In any case, we have one task in the group hierarchy which has a
load_avg_contrib of 0 and the grand-grand parent group entity has a
load_avg_contrib of 118 and no additional tasks. That load contribution
must be from tasks which are no longer around on the rq? No?

> Anyway, with blocked load, yes, we definitely can't move (or even find) some
> ammount of the imbalance if we only look at the tasks on the queue. But this
> may or may not be a problem.
> 
> Firstly, the question comes to whether we want blocked load anywhere.
> This is just about a "now vs. average" question.

That is what I meant in the paragraph below. It is a scheduling policy
question.

> Secondly, if we stick to average, we just need to treat the blocked load
> consistently, not that group SE has it, but task SE does not, or somewhere
> has it, others not.

I agree that inconsistent use of blocked load will lead us into trouble.
The problem is that none of the load-balance logic was designed for
blocked load. It was written to deal load that is currently on the rq
and slightly biased by average cpu load, not dealing with load
contribution of tasks which we can't migrate at the moment because they
are blocked. The load-balance code has to be updated to deal with
blocked load. We will run into all sorts of issues if we don't and roll
out use of blocked load everywhere.

However, before we can rework the load-balance code, we have to agree on
the now vs average balance policy.

Your proposed patch implements a policy somewhere in between. We try to
balance based on average, but we don't allow idle_balance() to empty a
cpu completely. A pure average balance policy would allow a cpu to go
idle even if we could do have tasks waiting on other rqs if the blocked
load indicates that other task will show up shortly one the cpu. A pure
"now" balance would balance based on runnable_load_avg for all entities
including groups ignoring all blocked load, but that goes against the
PELT group balancing design.

I'm not against having a policy that sits somewhere in between, we just
have to agree it is the right policy and clean up the load-balance code
such that the implemented policy is clear.

Morten

>  
> Thanks,
> Yuyang
> 
> > Whether emptying the src_rq is the right thing to do depends on on your
> > point of view. Does balanced load (runnable+blocked) take priority over
> > keeping cpus busy or not? For idle_balance() it seems intuitively
> > correct to not empty the rq and hence you could consider env->imbalance
> > to be too big.
> > 
> > I think we will see more of this kind of problems if we include
> > weighted_cpuload() as well. Parts of the imbalance calculation code is
> > quite old and could use some attention first.
> > 
> > A short term fix could be what Yuyang propose, stop pulling tasks when
> > there is only one left in detach_tasks(). It won't affect active load
> > balance where we may want to migrate the last task as it active load
> > balance doesn't use detach_tasks().
> > 
> > Morten
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1176718

On Fri, Jul 03, 2015 at 10:34:41AM +0100, Morten Rasmussen wrote:
> > > IOW, since task groups include blocked load in the load_avg_contrib (see
> > > __update_group_entity_contrib() and __update_cfs_rq_tg_load_contrib()) the
> > > imbalance includes blocked load and hence env->imbalance >=
> > > sum(task_h_load(p)) for all tasks p on the rq. Which leads to
> > > detach_tasks() emptying the rq completely in the reported scenario where
> > > blocked load > runnable load.

So IIRC we need the blocked load for groups for computing the per-cpu
slices of the total weight, avg works really well for that.

> I'm not against having a policy that sits somewhere in between, we just
> have to agree it is the right policy and clean up the load-balance code
> such that the implemented policy is clear.

Right, for balancing its a tricky question, but mixing them without
intent is, as you say, a bit of a mess.

So clearly blocked load doesn't make sense for (new)idle balancing. OTOH
it does make some sense for the regular periodic balancing, because
there we really do care mostly about the averages, esp. so when we're
overloaded -- but there are issues there too.

Now we can't track them both (or rather we could, but overhead).

I like Yuyang's load tracking rewrite, but it changes exactly this part,
and I'm not sure I understand the full ramifications of that yet.

One way out would be to split the load balancer into 3 distinct regions;

 1) get a task on every CPU, screw everything else.
 2) get each CPU fully utilized, still ignoring 'load'
 3) when everybody is fully utilized, consider load.

If we make find_busiest_foo() select one of these 3, and make
calculate_imbalance() invariant to the metric passed in, and have things
like cpu_load() and task_load() return different, but coherent, numbers
depending on which region we're in, this almost sounds 'simple'.

The devil is in the details, and the balancer is a hairy nest of details
which will make the above non-trivial.

But for 1) we could simply 'balance' on nr_running, for 2) we can
'balance' on runnable_avg and for 3) we'll 'balance' on load_avg (which
will then include blocked load).

Let me go play outside for a bit so that it can sink in what kind of
nonsense my heat addled brain has just sprouted :-)
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

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

#1178371

On Mon, Jul 06, 2015 at 07:36:56PM +0200, Dietmar Eggemann wrote:
> Rabin, could you share the content of your
> /sys/fs/cgroup/cpu/system.slice directory and of /proc/cgroups ?

Here's /proc/cgroups,

# cat /proc/cgroups 
#subsys_name	hierarchy	num_cgroups	enabled
cpu	2	98	1
cpuacct	2	98	1

and the contents of /sys/fs/cgroup/cpu/system.slice are available here:
https://drive.google.com/file/d/0B4tMLbMvJ-l6ZVBvZ09QOE15MU0/view

/Rabin
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web