From: Peter Zijlstra <peterz@infradead.org>
To: Nikhil Rao <ncrao@google.com>
Cc: Ingo Molnar <mingo@elte.hu>, Mike Galbraith <efault@gmx.de>,
linux-kernel@vger.kernel.org,
Venkatesh Pallipadi <venki@google.com>,
Ken Chen <kenchen@google.com>, Paul Turner <pjt@google.com>
Subject: Re: [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing
Date: Mon, 02 Aug 2010 13:39:38 +0200 [thread overview]
Message-ID: <1280749178.1923.114.camel@laptop> (raw)
In-Reply-To: <1280467146-32218-1-git-send-email-ncrao@google.com>
On Thu, 2010-07-29 at 22:19 -0700, Nikhil Rao wrote:
> If folks think this is a good direction and this idea has some merit, then I
> will be more than happy to continue working with the community to improve this
> patchset. If there is another way to fix this problem, then please do tell; I
> would be more than happy to help out.
No its terrible. I've already explained how to solve this on several
occasions (although my google skillz seem to fail me to find the latest
occasion a few months ago).
The thing is that from a fairness point of view 1 nice-0 (weight=1024)
on one CPU and 512 SCHED_IDLE (weight=2) tasks on another CPU and all
other CPUs idle is correct.
It just doesn't seem to be the thing that most people expect.
Special casing things like you've done is utterly the wrong thing to do.
This problem comes in two forms and its name is infeasible weight
distribution. The load-balancer tries to ensure W_k ~= W_l, k,l elem_of
CPUs, where W_k = \Sum_i w_i^k, where w_i^k is the i-th task on CPU k.
The two cases are statically infeasible, and dynamically infeasible.
We say the task-set is statically infeasible if for a task set of n
tasks there is no way to statically distribute them on N <= n CPUs such
that each task gets equal service (assuming the scheduling on each CPU
is fair).
We say the task-set is dynamically infeasible if for the given scenario
there is no way to rotate the tasks to obtain equality.
Lets assume 2 CPUs.
Ex.1: 2 tasks of different weight.
Ex.2: 3 tasks of equal weight.
The first example is both statically and dynamically infeasible as there
is no way to occupy both CPUs such that each task gets the proportional
correct service.
The second example is statically infeasible, but dynamically feasible,
for if we rotate one task, such that we alternate between 2:1 and 1:2 in
equal measures, each task will receive its correct 2/3rd CPU service.
The current load-balancer isn't particularly skilled at either issue.
The proper solution is to 'fix' find_busiest_group() so that it will:
- pick the heaviest cpu with more than 1 task on it
- slowly over-balance things
The first thing will solve your issue.
next prev parent reply other threads:[~2010-08-02 11:39 UTC|newest]
Thread overview: 13+ messages / expand[flat|nested] mbox.gz Atom feed top
2010-07-30 5:19 Nikhil Rao
2010-07-30 5:19 ` [PATCH 1/6] sched: account SCHED_IDLE tasks on rq->idle_nr_running Nikhil Rao
2010-07-30 5:19 ` [PATCH 2/6] sched: add SD_IDLE_LOAD_BALANCE to sched domain flags Nikhil Rao
2010-07-30 5:19 ` [PATCH 3/6] sched: add moving average of time spent servicing SCHED_NORMAL tasks Nikhil Rao
2010-07-30 5:19 ` [PATCH 4/6] sched: add sched_idle_balance argument to lb functions Nikhil Rao
2010-07-30 5:19 ` [PATCH 5/6] sched: add SCHED_IDLE load balancer Nikhil Rao
2010-07-30 5:19 ` [PATCH 6/6] sched: enable SD_IDLE_LOAD_BALANCE on MC, CPU and NUMA (x86) domains Nikhil Rao
2010-07-30 13:32 ` [PATCH 0/6] [RFC] Large weight differential leads to inefficient load balancing Mike Galbraith
2010-07-30 18:59 ` Nikhil Rao
2010-07-30 19:03 ` Paul Turner
2010-08-02 11:39 ` Peter Zijlstra [this message]
2010-08-03 21:28 ` Nikhil Rao
2010-08-04 10:18 ` Peter Zijlstra
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=1280749178.1923.114.camel@laptop \
--to=peterz@infradead.org \
--cc=efault@gmx.de \
--cc=kenchen@google.com \
--cc=linux-kernel@vger.kernel.org \
--cc=mingo@elte.hu \
--cc=ncrao@google.com \
--cc=pjt@google.com \
--cc=venki@google.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
all inboxes | Powered by JetHome®