sched: prevent high load weight tasks suppressing balancing
This breaks HT and MC optimizations.. Consider a DP system with each physical processor having two HT logical threads.. if there are two runnable processes running on package-0, with this patch scheduler will never move one of those processes to package-1..
thanks,
suresh
Quoted 101 lines · Peter Williams
Problem:
On systems with more than 2 CPUs it is possible for a single task with a high smpnice load weight to suppress load balancing on other CPUs (to the one that it's running on) if it is the only runnable task on its CPU. E.g. consider a 4-way system (simple SMP system with no HT and cores) scenario where a high priority task (nice-20) is running on P0 and two normal priority tasks running on P1. load balance with smp nice code will never be able to detect an imbalance and hence will never move one of the normal priority tasks on P1 to idle cpus P2 or P3 as P0 will always be identified as the busiest CPU but it has no tasks that can be moved.
Solution:
Make sure that only CPUs with tasks that can be moved get selected as the busiest queue. This involves ensuring that
find_busiest_group()only considers groups that have at least one CPU with more than one task running as candidates for the busiest group and thatfind_busiest_queue()only considers CPUs that have more than one task running as candidates for the busiest run queue.One effect of this is that load balancing will be abandoned earlier in the sequence (i.e. before the double run queue locks are taken prior to calling
move_tasks()rather than inmove_tasks()itself) when there are no tasks that can be moved than would be the case without this patch.Signed-off-by Peter Williams <[email protected]>Peter
PS This doesn't take into account tasks that can't be moved because they are pinned to a particular CPU. At this stage, I don't think that it's worth the effort to make the changes that would enable this.Signature · 7 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce Index: MM-2.6.X/kernel/sched.c ===================================================================kernel/sched.c +11
-8@@ -2115,6 +2115,7 @@ find_busiest_group(struct sched_domain *int local_group;int i;unsigned long sum_nr_running, sum_weighted_load; +unsigned int nr_loaded_cpus =0 ;/* where nr_running > 1 */ local_group =cpu_isset (this_cpu, group->cpumask);@@ -2135,6 +2136,8 @@ find_busiest_group(struct sched_domain * avg_load += load; sum_nr_running += rq->nr_running; +if (rq->nr_running >1 ) + ++nr_loaded_cpus; sum_weighted_load += rq->raw_weighted_load; }@@ -2149,7 +2152,7 @@ find_busiest_group(struct sched_domain * this = group; this_nr_running = sum_nr_running; this_load_per_task = sum_weighted_load; - }else if (avg_load > max_load) { + }else if (avg_load > max_load && nr_loaded_cpus) { max_load = avg_load; busiest = group; busiest_nr_running = sum_nr_running;@@ -2158,7 +2161,7 @@ find_busiest_group(struct sched_domain * group = group->next; }while (group != sd->groups); -if (!busiest || this_load >= max_load || busiest_nr_running <=1 ) +if (!busiest || this_load >= max_load) goto out_balanced; avg_load = (SCHED_LOAD_SCALE * total_load) / total_pwr;@@ -2260,16 +2263,16 @@ out_balanced:static runqueue_t *find_busiest_queue (struct sched_group *group,enum idle_type idle) { -unsigned long load, max_load =0 ; -runqueue_t *busiest =NULL ; +unsigned long max_load =0 ; +runqueue_t *busiest =NULL , *rqi;int i;for_each_cpu_mask (i, group->cpumask) { - load =weighted_cpuload (i); + rqi =cpu_rq (i); -if (load > max_load) { - max_load = load; - busiest =cpu_rq (i); +if (rqi->raw_weighted_load > max_load && rqi->nr_running >1 ) { + max_load = rqi->raw_weighted_load; + busiest = rqi; } }
Quoted 2 lines · Suresh B
This breaks HT and MC optimizations.. Consider a DP system with each
physical processor having two HT logical threads.. if there are two runnable processes running on package-0, with this patch scheduler will never move one of those processes to package-1..
Is this an active_load_balance() issue?
If it is then I suggest that the solution is to fix the active_load_balance() and associated code so that it works with this patch in place.
It would be possible to modify find_busiest_group() and find_busiest_queue() so that they just PREFER the busiest group to have at least one CPU with more than one running task and the busiest queue to have more than one task. However, this would make the code considerably more complex and I'm reluctant to impose that on all architectures just to satisfy HT and MC requirements. Are there configuration macros or other means that I can use to exclude this (proposed) code on systems where it isn't needed i.e. non HT and MC systems or HT and MC systems with only one package.
Personally, I think that the optimal performance of the load balancing code has already been considerably compromised by its unconditionally accommodating the requirements of active_load_balance() (which you have said is now only required by HT and MC systems) and that it might be better if active load balancing was separated out into a separate mechanism that could be excluded from the build on architectures that don't need it. I can't help thinking that this would result in a more efficient active load balancing mechanism as well because the current one is very inefficient.
Peter
PS I don't think that this issue is sufficiently important to prevent the adoption of the smpnice patches while it's being resolved.
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 7 lines · Peter Williams
Quoted 4 lines · Suresh B
This breaks HT and MC optimizations.. Consider a DP system with each physical processor having two HT logical threads.. if there are two runnable processes running on package-0, with this patch scheduler will never move one of those processes to package-1..
Is this an
active_load_balance()issue?
No. find_busiest_group() doesn't find an imbalance in this case..
Quoted 8 lines
If it is then I suggest that the solution is to fix the
active_load_balance()and associated code so that it works with this patch in place.It would be possible to modify
find_busiest_group()andfind_busiest_queue()so that they just PREFER the busiest group to have at least one CPU with more than one running task and the busiest queue to have more than one task. However, this would make the code
Please don't do that... Its not for the complexity I say NO but we are kind of patching the code instead of addressing the root issue..
Quoted 5 lines
considerably more complex and I'm reluctant to impose that on all architectures just to satisfy HT and MC requirements. Are there configuration macros or other means that I can use to exclude this (proposed) code on systems where it isn't needed i.e. non HT and MC systems or HT and MC systems with only one package.
There is no config option to disable that portion of the code. Interaction of this code with mainstream code is very small. Look at the active_load_balance() and how this comes into play with the help of migration thread(which gets activated through load_balance)
Quoted 9 lines
Personally, I think that the optimal performance of the load balancing code has already been considerably compromised by its unconditionally accommodating the requirements of
active_load_balance()(which you have said is now only required by HT and MC systems) and that it might be better if active load balancing was separated out into a separate mechanism that could be excluded from the build on architectures that don't need it. I can't help thinking that this would result in a more efficient active load balancing mechanism as well because the current one is very inefficient.
No. Upto now, this has been encapsulated very generically using cpu_power and thats the reason why adding a sched domain for multi-core was simple.
Quoted 3 lines
Peter
PS I don't think that this issue is sufficiently important to prevent the adoption of the smpnice patches while it's being resolved.
Scheduler is a very critical piece in the kernel. We need to understand and fix all the cases..
thanks,
suresh
Quoted 7 lines · Suresh B
Quoted 4 lines · Peter Williams
Quoted 2 lines · Suresh B
This breaks HT and MC optimizations.. Consider a DP system with each
physical processor having two HT logical threads.. if there are two runnable processes running on package-0, with this patch scheduler will never move one of those processes to package-1..Is this an
active_load_balance()issue?No.
find_busiest_group()doesn't find an imbalance in this case..
But active_load_balance() is the only code that would want to move the only runnable task off a CPU, isn't it? No other load balancing code will try to do this that I can see.
Quoted 5 lines
Quoted 4 lines
If it is then I suggest that the solution is to fix the
active_load_balance()and associated code so that it works with this patch in place.It would be possible to modify
find_busiest_group()andfind_busiest_queue()so that they just PREFER the busiest group to have at least one CPU with more than one running task and the busiest queue to have more than one task. However, this would make the code
Quoted 8 lines
Please don't do that... Its not for the complexity I say NO but we are kind of patching the code instead of addressing the root issue..
Quoted 1 line
considerably more complex and I'm reluctant to impose that on all architectures just to satisfy HT and MC requirements. Are there configuration macros or other means that I can use to exclude this (proposed) code on systems where it isn't needed i.e. non HT and MC systems or HT and MC systems with only one package.
There is no config option to disable that portion of the code. Interaction of this code with mainstream code is very small. Look at the
active_load_balance()and how this comes into play with the help of migrationthread(which gets activated through load_balance)
Yes, I've read that which is why I say (see below) that it's backwards and haphazard.
I'll make a temporary patch that does the PREFER I mentioned above to tide us over until a proper rewrite of the active load balancing functionality can be done. After giving it some more thought I think I can keep the extra complexity fairly small.
Quoted 5 lines
Quoted 2 lines
Personally, I think that the optimal performance of the load balancing code has already been considerably compromised by its unconditionally accommodating the requirements of
active_load_balance()(which you have said is now only required by HT and MC systems) and that it might be better if active load balancing was separated out into a separate mechanism that could be excluded from the build on architectures that don't need it. I can't help thinking that this would result in a more efficient active load balancing mechanism as well because the current one is very inefficient.No. Upto now, this has been encapsulated very generically using
cpu_powerand thats the reason why adding a sched domain for multi-core was simple.
It seems to me that it's being done backwards and haphazardly. As far as I can see the problem that's trying to be solved is there is a package that has two or more CPUs that have exactly one runnable task and there are other packages that have all of their CPUs idle and we want to move one task to each idle package, right?
If any of the CPUs in the package have more than one runnable task then normal load balancing will kick in which is why I say this special code is only required for the case where there's exactly one task for two or more of the CPUs in the package.
So why not write code that (every so many ticks) checks to see if a package meets these criteria and if it does then looks for idle packages (that's packages not groups or queues) and if it finds them initiates active load balancing? Or some variation of that theme.
At the end of scheduler_tick() you could do (every so many ticks):
if rebalance_tick() didn't pull any tasks and this run queue has exactly one runnable task then
if the package that this run queue is in meets the criteria then
set the run queue's active_balance flag and let the
migration thread know that it has work to do.
Properly packaged this code could be excluded from the build on architectures that don't need it.
Quoted 6 lines
Quoted 3 lines
Peter
PS I don't think that this issue is sufficiently important to prevent the adoption of the smpnice patches while it's being resolved.Scheduler is a very critical piece in the kernel. We need to understand and fix all the cases..
Yes, but this particular problem is a very minor especially when compared to the general breakage of "nice" on SMP systems without the smpnice patch.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce