by Peter Williams

[permalink] [raw]

Subject: Re: [rfc][patch] sched: remove smpnice

Peter Williams wrote:
> Andrew Morton wrote:
>
>> "Siddha, Suresh B" <[email protected]> wrote:
>>
>>> b) On a lightly loaded system, this can result in HT scheduler
>>> optimizations
>>> being disabled in presence of low priority tasks... in this case,
>>> they(low
>>> priority ones) can end up running on the same package, even in the
>>> presence of other idle packages.. Though this is not as serious as
>>> "a" above...
>>>
>
> I think that this issue comes under the heading of "Result of better
> nice enforcement" which is the purpose of the patch :-).

On the assumption that this enforcement is considered to be too
vigorous, I think that it is also amenable to a fix based on a new
biased_load() function by replacing the (*imbalance < SCHED_LOAD_SCALE)
test with (biased_load(*imbalance, busiest) == 0) and (possibly) some
modifications within the if statement's body (most notably replacing the
NICE_TO_BIAS_PRIO(0) expressions with (busiest->prio_bias /
busiest->nr_running) or something similar).

This change would cause no change in functionality in the case where all
tasks are nice==0.

Peter
--
Peter Williams [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce

2006-02-12 01:13:21

Index: MM-2.6.X/kernel/sched.c
===================================================================
--- MM-2.6.X.orig/kernel/sched.c 2006-02-13 10:23:12.000000000 +1100
+++ MM-2.6.X/kernel/sched.c 2006-02-13 11:46:41.000000000 +1100
@@ -2033,9 +2033,11 @@ find_busiest_group(struct sched_domain *
struct sched_group *busiest = NULL, *this = NULL, *group = sd->groups;
unsigned long max_load, avg_load, total_load, this_load, total_pwr;
unsigned long max_pull;
+ unsigned long avg_bias_prio, busiest_prio_bias, busiest_nr_running;
int load_idx;

max_load = this_load = total_load = total_pwr = 0;
+ busiest_prio_bias = busiest_nr_running = 0;
if (idle == NOT_IDLE)
load_idx = sd->busy_idx;
else if (idle == NEWLY_IDLE)
@@ -2047,13 +2049,16 @@ find_busiest_group(struct sched_domain *
unsigned long load;
int local_group;
int i;
+ unsigned long sum_prio_bias, sum_nr_running;

local_group = cpu_isset(this_cpu, group->cpumask);

/* Tally up the load of all CPUs in the group */
- avg_load = 0;
+ sum_prio_bias = sum_nr_running = avg_load = 0;

for_each_cpu_mask(i, group->cpumask) {
+ runqueue_t *rq = cpu_rq(i);
+
if (*sd_idle && !idle_cpu(i))
*sd_idle = 0;

@@ -2064,6 +2069,8 @@ find_busiest_group(struct sched_domain *
load = source_load(i, load_idx);

avg_load += load;
+ sum_prio_bias += rq->prio_bias;
+ sum_nr_running += rq->nr_running;
}

total_load += avg_load;
@@ -2078,6 +2085,8 @@ find_busiest_group(struct sched_domain *
} else if (avg_load > max_load) {
max_load = avg_load;
busiest = group;
+ busiest_prio_bias = sum_prio_bias;
+ busiest_nr_running = sum_nr_running;
}
group = group->next;
} while (group != sd->groups);
@@ -2111,12 +2120,25 @@ find_busiest_group(struct sched_domain *
(avg_load - this_load) * this->cpu_power)
/ SCHED_LOAD_SCALE;

- if (*imbalance < SCHED_LOAD_SCALE) {
+ /* assume that busiest_nr_running > 0 */
+ avg_bias_prio = busiest_prio_bias / busiest_nr_running;
+ /*
+ * Get rid of the scaling factor, rounding down as we divide and
+ * converting to biased load for use by move_tasks()
+ */
+ *imbalance = biased_load(*imbalance);
+ /*
+ * if *imbalance is less than the average runnable task biased prio
+ * there is no gaurantee that any tasks will be moved so we'll have
+ * a think about bumping its value to force at least one task to be
+ * moved
+ */
+ if (*imbalance < avg_bias_prio) {
unsigned long pwr_now = 0, pwr_move = 0;
unsigned long tmp;

- if (max_load - this_load >= SCHED_LOAD_SCALE*2) {
- *imbalance = NICE_TO_BIAS_PRIO(0);
+ if (biased_load(max_load - this_load) >= avg_bias_prio*2) {
+ *imbalance = avg_bias_prio;
return busiest;
}

@@ -2146,18 +2168,19 @@ find_busiest_group(struct sched_domain *
pwr_move /= SCHED_LOAD_SCALE;

/* Move if we gain throughput */
- if (pwr_move <= pwr_now)
- goto out_balanced;
+ if (pwr_move <= pwr_now) {
+ /* or if there's a reasonable chance that *imbalance
+ * is big enough to cause a move
+ */
+ if (*imbalance <= avg_bias_prio / 2)
+ goto out_balanced;
+ else
+ return busiest;
+ }

- *imbalance = NICE_TO_BIAS_PRIO(0);
- return busiest;
+ *imbalance = avg_bias_prio;
}

- /*
- * Get rid of the scaling factor, rounding down as we divide and
- * converting to biased load for use by move_tasks()
- */
- *imbalance = biased_load(*imbalance);
return busiest;

out_balanced:

Attachments:

fix-smpnice-light-load-problem-v2 (3.38 kB)

2006-02-13 14:13:36

by Con Kolivas

[permalink] [raw]

Subject: Re: [rfc][patch] sched: remove smpnice

On Friday 10 February 2006 18:01, Siddha, Suresh B wrote:
> On Tue, Feb 07, 2006 at 03:36:17PM -0800, Andrew Morton wrote:
> > Suresh, Martin, Ingo, Nick and Con: please drop everything, triple-check
> > and test this:
> >
> > From: Peter Williams <[email protected]>
> >
> > This is a modified version of Con Kolivas's patch to add "nice" support
> > to load balancing across physical CPUs on SMP systems.
>
> I have couple of issues with this patch.
>
> a) on a lightly loaded system, this will result in higher priority job
> hopping around from one processor to another processor.. This is because of
> the code in find_busiest_group() which assumes that SCHED_LOAD_SCALE
> represents a unit process load and with nice_to_bias calculations this is
> no longer true(in the presence of non nice-0 tasks)
>
> My testing showed that 178.galgel in SPECfp2000 is down by ~10% when run
> with nice -20 on a 4P(8-way with HT) system compared to a nice-0 run.

While I voted to remove smp nice till this regression is fixed can I just
point out a mildly amusing catch 22 in this. Nice levels are _broken_ on smp
without smp nice, yet it's only by using nice levels that you get this
performance problem. I'm not arguing for changing our decision based on this.

Cheers,
Con

2006-02-14 00:37:29

Peter Williams wrote:
> Siddha, Suresh B wrote:
>
>> On Wed, Feb 15, 2006 at 09:40:32AM +1100, Peter Williams wrote:
>>
>>> Siddha, Suresh B wrote:
>>>
>>>> On a 4P(8-way with HT), if you run a -20 task(a simple infinite loop)
>>>> it hops from one processor to another processor... you can observe it
>>>> using top.
>>>
>>>
>>> How do you get top to display which CPU tasks are running on?
>>
>>
>>
>> In the interactive mode, you can select the "last used cpu" field to
>> display.

Thanks this works and I'm now convinced that there's hopping occurring
but I disagree on the cause (see below).

>> or you can use /proc/pid/stat
>>
>>
>>>> find_busiest_group() thinks there is an imbalance and ultimately the
>>>> idle cpu kicks active load balance on busy cpu, resulting in the
>>>> hopping.
>>>
>>>
>>> I'm still having trouble getting my head around this. A task
>>> shouldn't be moved unless there's at least one other task on its
>>> current CPU, it
>>
>>
>>
>> Because of the highest priority task, weighted load of that cpu
>> will be > SCHED_LOAD_SCALE. Because of this, an idle cpu in
>> find_busiest_group() thinks that there is an imbalance.. This is due to
>> the code near the comment "however we may be ablet to increase total
>> CPU power used by ...". That piece of code assumes that a unit load
>> is represented by SCHED_LOAD_SCALE (which is no longer true with smpnice)
>> and finally results in "pwr_move > pwr_now".. This will make the idle cpu
>> try to pull that process from busiest cpu and the process will
>> ultimately move
>> with the help of active load balance...
>
>
> But as I pointed out, with the code as it is in the recent -mm kernels,
> the amount of biased load (i.e. NICE_TO_BIAS_PRIO(0)) that
> find_busiest_group() sets *imbalance to in these circumstances is too
> small for a task with nice less than zero to be moved i.e. move_tasks()
> will skip it. Or are you just referring to the vanilla kernels?

The upshot of this is that the code near "however we may" etc. never
gets executed. So what must be happening is that *imbalance is greater
than SCHED_LOAD_SCALE so it goes out unchanged (as the fact that the
problem occurs with hard spinners lets try_to_wake_up() off the hook).
But, as I also said in another e-mail, there must be another task with
equal or higher priority than the task (that's doing the hopping) on its
CPU for it to be booted off. I would surmise that the prime candidate
here would be the migration thread for the CPU in question as it's a
real time task and seems to run fairly frequently.

The obvious way to handle this is too NOT move tasks from a run queue
where the migration thread is running unless the number of running tasks
on that CPU is greater than 2. I'll try to come up with a patch that
does this without causing too much complexity.

Peter
--
Peter Williams [email protected]

"Learning, n. The kind of ignorance distinguishing the studious."
-- Ambrose Bierce