Improve load balancing when tasks have large weight differential
cover Improve load balancing when tasks have large weight differential
Hi all,
I have attached a series of patches that improve load balancing when there is a
large weight differential between tasks. These patches are based off the
feedback Peter Zijlstra gave in an earlier post (see http://thread.gmane.org/gmane.linux.kernel/1015966).
They can be applied to v2.6.36-rc5 or -tip without conflicts.
Tested with the following setup.
- Test machine is a 16 cpu box (quad-socket, quad-core).
- Baseline is v2.6.36-rc5 kernel
We spawn 16 SCHED_IDLE soaker threads and one SCHED_NORMAL task. On the baseline kernel, the machine has ~18% idle time. With these patches applied on top of baseline, idle time drops to 0%.
v2.6.36-rc5
04:58:46 PM CPU %user %nice %sys %iowait %irq %soft %steal %idle intr/s 04:58:47 PM all 81.47 0.00 0.25 0.00 0.00 0.00 0.00 18.28 13796.00 04:58:48 PM all 81.20 0.00 0.25 0.00 0.00 0.00 0.00 18.55 13816.00 04:58:49 PM all 80.93 0.19 0.25 0.00 0.00 0.06 0.00 18.57 13965.00 04:58:50 PM all 81.40 0.00 0.25 0.00 0.00 0.00 0.00 18.35 13837.37 04:58:51 PM all 81.19 0.00 0.31 0.00 0.00 0.00 0.00 18.50 13592.08 04:58:52 PM all 81.25 0.00 0.25 0.00 0.00 0.00 0.00 18.50 13721.00 04:58:53 PM all 81.19 0.00 0.25 0.00 0.00 0.00 0.00 18.56 13764.00 04:58:54 PM all 81.25 0.00 0.25 0.00 0.00 0.00 0.00 18.50 13841.41 04:58:55 PM all 80.30 0.00 1.19 0.00 0.00 0.00 0.00 18.51 14989.11 04:58:56 PM all 80.77 0.00 0.50 0.00 0.00 0.00 0.00 18.73 13964.65 Average: all 81.09 0.02 0.37 0.00 0.00 0.01 0.00 18.51 13929.53
v2.6.36-rc5 + patches
05:00:06 PM CPU %user %nice %sys %iowait %irq %soft %steal %idle intr/s 05:00:07 PM all 99.94 0.00 0.06 0.00 0.00 0.00 0.00 0.00 16364.00 05:00:08 PM all 99.81 0.06 0.12 0.00 0.00 0.00 0.00 0.00 16348.00 05:00:09 PM all 99.94 0.00 0.06 0.00 0.00 0.00 0.00 0.00 16330.00 05:00:10 PM all 99.94 0.00 0.06 0.00 0.00 0.00 0.00 0.00 16317.00 05:00:11 PM all 99.88 0.06 0.06 0.00 0.00 0.00 0.00 0.00 16327.00 05:00:12 PM all 99.94 0.00 0.06 0.00 0.00 0.00 0.00 0.00 16323.00 05:00:13 PM all 99.88 0.00 0.12 0.00 0.00 0.00 0.00 0.00 16323.00 05:00:14 PM all 99.94 0.00 0.06 0.00 0.00 0.00 0.00 0.00 16321.00 05:00:15 PM all 99.63 0.06 0.25 0.00 0.00 0.06 0.00 0.00 16354.00 05:00:16 PM all 99.62 0.00 0.38 0.00 0.00 0.00 0.00 0.00 19059.60 Average: all 99.85 0.02 0.13 0.00 0.00 0.01 0.00 0.00 16604.20
Comments, feedback welcome.
-Thanks,
Nikhil
Nikhil Rao (3):
sched: set group_imb only a task can be pulled from the busiest cpu
sched: drop group_capacity to 1 only if remote group has no running
tasks
sched: do not consider SCHED_IDLE tasks to be cache hot
kernel/sched.c | 3 +++ kernel/sched_fair.c | 12 ++++++++---- 2 files changed, 11 insertions(+), 4 deletions(-)
PATCH 1/3 sched: set group_imb only a task can be pulled from the busiest cpu
When cycling through sched groups to determine the busiest group, set group_imb only if the busiest cpu has more than 1 runnable task. This patch fixes the case where two cpus in a group have one runnable task each, but there is a large weight differential between these two tasks. The load balancer is unable to migrate any task from this group, and hence do not consider this group to be imbalanced.
--- kernel/sched_fair.c | 10 +++++++--- 1 files changed, 7 insertions(+), 3 deletions(-)
kernel/sched_fair.c +7 -3
@@ -2378,7 +2378,7 @@ static inline void update_sg_lb_stats(struct sched_domain *sd, int local_group, const struct cpumask *cpus, int *balance, struct sg_lb_stats *sgs) { - unsigned long load, max_cpu_load, min_cpu_load; + unsigned long load, max_cpu_load, min_cpu_load, max_nr_running;int i;unsigned int balance_cpu =-1 , first_idle_cpu =0 ;unsigned long avg_load_per_task =0 ;
@@ -2389,6 +2389,7 @@ static inline void update_sg_lb_stats(struct sched_domain *sd,/* Tally up the load of all CPUs in the group */ max_cpu_load =0 ; min_cpu_load = ~0UL ; + max_nr_running =0 ;for_each_cpu_and (i,sched_group_cpus (group), cpus) {struct rq *rq =cpu_rq (i);
@@ -2406,8 +2407,10 @@ static inline void update_sg_lb_stats(struct sched_domain *sd, load =target_load (i, load_idx); }else { load =source_load (i, load_idx); -if (load > max_cpu_load) +if (load > max_cpu_load) { max_cpu_load = load; + max_nr_running = rq->nr_running; + }if (min_cpu_load > load) min_cpu_load = load; }
@@ -2447,7 +2450,8 @@ static inline void update_sg_lb_stats(struct sched_domain *sd,if (sgs->sum_nr_running) avg_load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running; -if ((max_cpu_load - min_cpu_load) >2 *avg_load_per_task) +if ((max_cpu_load - min_cpu_load) >2 *avg_load_per_task && + max_nr_running >1 ) sgs->group_imb =1 ; sgs->group_capacity =
Signature · 1 line
1.7.1
PATCH 2/3 sched: drop group_capacity to 1 only if remote group has no running tasks
In reply to Nikhil RaoWhen SD_PREFER_SIBLING is set on a sched domain, drop group_capacity to 1 only if the remote sched group has no running tasks. This addresses the case where you have two tasks on one socket and the other socket is idle, in which case you drop the capacity to 1. If the remote group has >=1 running task, then there is no difference from a cache-sharing perspective.
--- kernel/sched_fair.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)
kernel/sched_fair.c +1 -1
@@ -2548,7 +2548,7 @@ static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,* first, lower the sg capacity to one so that we'll try * and move all the excess tasks away. */ -if (prefer_sibling) +if (prefer_sibling && !sgs.sum_nr_running) sgs.group_capacity =min (sgs.group_capacity,1UL );if (local_group) {
Signature · 1 line
1.7.1
Re: [PATCH 2/3] sched: drop group_capacity to 1 only if remote group has no running tasks
Quoted 16 lines · Nikhil Rao
When
SD_PREFER_SIBLINGis set on a sched domain, dropgroup_capacityto 1 only if the remote sched group has no running tasks. This addresses the case where you have two tasks on one socket and the other socket is idle, in which case you drop the capacity to 1. If the remote group has >=1 running task, then there is no difference from a cache-sharing perspective.Signed-off-by Nikhil Rao <[email protected]>--- kernel/sched_fair.c | 2 +- 1 files changed, 1 insertions(+), 1 deletions(-)kernel/sched_fair.c +0
-0
kernel/sched_fair.c static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu, · line 2554
Quoted 8 lines
kernel/sched_fair.c +1
-1@@ -2548,7 +2548,7 @@ static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,* first, lower the sg capacity to one so that we'll try * and move all the excess tasks away. */ -if (prefer_sibling) +if (prefer_sibling && !sgs.sum_nr_running) sgs.group_capacity =min (sgs.group_capacity,1UL );if (local_group) {
Nikhil, Doesn't this break the case of:
two sockets with dual-core and HT. Four tasks currently scheduled as:
three on socket-0 (two threads on core-0 running two tasks and 1 thread on core-1 running one task). One on socket-1 (one thread on core-0 running a task, with other core-1 idle)
We would like to move the task from core-0 socket-0 to core-1 socket-1, while we are load balancing at the socket level (it might be smp or numa level depending on system).
thanks,
suresh
Re: [PATCH 2/3] sched: drop group_capacity to 1 only if remote group has no running tasks
Hi Suresh,
Sorry for the delayed reply.
Quoted 33 lines · Suresh Siddha
Quoted 16 lines · Nikhil Rao
When
SD_PREFER_SIBLINGis set on a sched domain, dropgroup_capacityto 1 only if the remote sched group has no running tasks. This addresses the case where you have two tasks on one socket and the other socket is idle, in which case you drop the capacity to 1. If the remote group has >=1 running task, then there is no difference from a cache-sharing perspective.Signed-off-by Nikhil Rao <[email protected]>---
kernel/sched_fair.c | 2 +-1 files changed, 1 insertions(+), 1 deletions(-)kernel/sched_fair.c +0
-0kernel/sched_fair.c static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu, · line 2554
Quoted 8 lines
kernel/sched_fair.c +1
-1@@ -2548,7 +2548,7 @@ static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,* first, lower the sg capacity to one so that we'll try * and move all the excess tasks away. */ - if (prefer_sibling) + if (prefer_sibling && !sgs.sum_nr_running) sgs.group_capacity = min(sgs.group_capacity, 1UL); if (local_group) {Nikhil, Doesn't this break the case of:
two sockets with dual-core and HT. Four tasks currently scheduled as:
three on socket-0 (two threads on core-0 running two tasks and 1 thread on core-1 running one task). One on socket-1 (one thread on core-0 running a task, with other core-1 idle)
Quoted 7 lines
We would like to move the task from core-0 socket-0 to core-1 socket-1, while we are load balancing at the socket level (it might be smp or numa level depending on system).
thanks,
suresh
Thanks for raising this issue. Yes, when you have a quad-core, dual-socket machine, the additional check will prevent group_capacity from dropping down to 1. In this situation, we want to decrease group_capacity if the local group has extra capacity (i.e. this_nr_running < this_group_weight) [credit goes to Venki for this insight]. This also works when you have a niced task, which is what this patch was trying to fix. I have attached a modified version of the patch below. Does this look OK?
-Thanks,
Nikhil
---
kernel/sched_fair.c +1 -0
@@ -2030,6 +2030,7 @@ struct sd_lb_stats {unsigned long this_load;unsigned long this_load_per_task;unsigned long this_nr_running; +unsigned long this_group_capacity;/* Statistics of the busiest group */ unsigned long max_load;
@@ -2548,7 +2549,8 @@ static inline void update_sd_lb_stats(struct
sched_domain *sd, int this_cpu,
* first, lower the sg capacity to one so that we'll try
* and move all the excess tasks away.
*/
- if (prefer_sibling)
+ if (prefer_sibling && !local_group &&
+ sds->this_nr_running < sds->this_group_capacity)
sgs.group_capacity = min(sgs.group_capacity, 1UL);
if (local_group) {
@@ -2556,6 +2558,7 @@ static inline void update_sd_lb_stats(struct
sched_domain *sd, int this_cpu,
sds->this = sg;
sds->this_nr_running = sgs.sum_nr_running;
sds->this_load_per_task = sgs.sum_weighted_load;
+ sds->this_group_capacity = sgs.group_capacity;
} else if (update_sd_pick_busiest(sd, sds, sg, &sgs,
this_cpu)) {
sds->max_load = sgs.avg_load;
sds->busiest = sg;PATCH 3/3 sched: do not consider SCHED_IDLE tasks to be cache hot
In reply to Nikhil RaoThis patch adds a check in task_hot to return if the task has SCHED_IDLE policy. SCHED_IDLE tasks have very low weight, and when run with regular weight tasks, are typically scheduled many milliseconds apart. There is no benefit from considering SCHED_IDLE tasks cache hot for load balancing.
--- kernel/sched.c | 3 +++ 1 files changed, 3 insertions(+), 0 deletions(-)
kernel/sched.c +3 -0
@@ -2003,6 +2003,9 @@ task_hot(struct task_struct *p, u64 now, struct sched_domain *sd)if (p->sched_class != &fair_sched_class)return 0 ; +if (p->policy ==SCHED_IDLE ) +return 0 ; +/* * Buddy candidates are cache hot: */
Signature · 1 line
1.7.1
Quoted 7 lines · Nikhil Rao
Hi all,
I have attached a series of patches that improve load balancing when there is a
large weight differential between tasks. These patches are based off the
feedback Peter Zijlstra gave in an earlier post (see http://thread.gmane.org/gmane.linux.kernel/1015966).
They can be applied to v2.6.36-rc5 or -tip without conflicts.
Quoted 7 lines
Tested with the following setup.
- Test machine is a 16 cpu box (quad-socket, quad-core).
- Baseline is v2.6.36-rc5 kernelWe spawn 16
SCHED_IDLEsoaker threads and oneSCHED_NORMALtask. On the baseline kernel, the machine has ~18% idle time. With these patches applied on top of baseline, idle time drops to 0%.
Hm. I can get it stuck with one core idle on ym little quad.
top - 15:53:22 up 11 min, 17 users, load average: 5.05, 4.40, 2.51
Tasks: 270 total, 7 running, 263 sleeping, 0 stopped, 0 zombie
Cpu(s): 75.3%us, 0.0%sy, 0.0%ni, 24.7%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ P COMMAND 7455 root 5 -15 7996 340 256 R 100 0.0 0:59.93 1 pert 7421 root 20 0 7996 340 256 R 50 0.0 4:20.01 3 pert 7422 root 20 0 7996 340 256 R 50 0.0 3:45.81 2 pert 7423 root 20 0 7996 340 256 R 50 0.0 4:09.45 2 pert 7424 root 20 0 7996 344 256 R 50 0.0 4:12.75 3 pert
Quoted 22 lines · Mike Galbraith
Quoted 7 lines · Nikhil Rao
Hi all,
I have attached a series of patches that improve load balancing when there is a
large weight differential between tasks. These patches are based off the
feedback Peter Zijlstra gave in an earlier post (see http://thread.gmane.org/gmane.linux.kernel/1015966).
They can be applied to v2.6.36-rc5 or -tip without conflicts.Quoted 7 lines
Tested with the following setup.
- Test machine is a 16 cpu box (quad-socket, quad-core).
- Baseline is v2.6.36-rc5 kernelWe spawn 16
SCHED_IDLEsoaker threads and oneSCHED_NORMALtask. On the baseline kernel, the machine has ~18% idle time. With these patches applied on top of baseline, idle time drops to 0%.Hm. I can get it stuck with one core idle on ym little quad.
top - 15:53:22 up 11 min, 17 users, load average: 5.05, 4.40, 2.51
Tasks: 270 total, 7 running, 263 sleeping, 0 stopped, 0 zombie Cpu(s): 75.3%us, 0.0%sy, 0.0%ni, 24.7%id, 0.0%wa, 0.0%hi, 0.0%si, 0.0%st
Quoted 8 lines
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ P COMMAND 7455 root 5 -15 7996 340 256 R 100 0.0 0:59.93 1 pert 7421 root 20 0 7996 340 256 R 50 0.0 4:20.01 3 pert 7422 root 20 0 7996 340 256 R 50 0.0 3:45.81 2 pert 7423 root 20 0 7996 340 256 R 50 0.0 4:09.45 2 pert 7424 root 20 0 7996 344 256 R 50 0.0 4:12.75 3 pert
Mike,
Thanks for running this. I've not been able to reproduce what you are seeing on the few test machines that I have (different combinations of MC, CPU and NODE domains). Can you please give me more info about your setup?
-Thanks,
Nikhil
Quoted 4 lines · Nikhil Rao
Thanks for running this. I've not been able to reproduce what you are seeing on the few test machines that I have (different combinations of MC, CPU and NODE domains). Can you please give me more info about your setup?
It's a plain-jane Q6600 box, so has only MC and CPU domains.
It doesn't necessarily _instantly_ "stick", can take a couple tries, or a little time.
-Mike
Quoted 11 lines · Mike Galbraith
Quoted 4 lines · Nikhil Rao
Thanks for running this. I've not been able to reproduce what you are seeing on the few test machines that I have (different combinations of MC, CPU and NODE domains). Can you please give me more info about your setup?
It's a plain-jane Q6600 box, so has only MC and CPU domains.
It doesn't necessarily _instantly_ "stick", can take a couple tries, or a little time.
The closest I have is a quad-core dual-socket machine (MC, CPU domains). And I'm having trouble reproducing it on that machine as well :-( I ran 5 soaker threads (one of them niced to -15) for a few hours and didn't see the problem. Can you please give me some trace data & schedstats to work with?
Looking at the patch/code, I suspect active migration on the CPU scheduling domain pushes the nice 0 task (running on the same socket as the nice -15 task) to the other socket. This leaves you with an idle core on the nice -15 socket, and with soaker threads there is no way to come back to a 100% utilized state. One possible explanation is the group capacity for a sched group in the CPU sched domain is rounded to 1 (instead of 2). I have a patch below that throws a hammer at the problem and uses group weight instead of group capacity (this is experimental, will refine it if it works). Can you please see if that solves the problem?
kernel/sched_fair.c +1 -0
@@ -2057,6 +2057,7 @@ struct sg_lb_stats {unsigned long sum_nr_running;/* Nr tasks running in the group */ unsigned long sum_weighted_load;/* Weighted load of group's tasks */ unsigned long group_capacity; +unsigned long group_weight;int group_imb;/* Is there an imbalance in the group ? */ };
@@ -2458,6 +2459,8 @@ static inline void update_sg_lb_stats(struct
sched_domain *sd,
DIV_ROUND_CLOSEST(group->cpu_power, SCHED_LOAD_SCALE);
if (!sgs->group_capacity)
sgs->group_capacity = fix_small_capacity(sd, group);+
+ sgs->group_weight = cpumask_weight(sched_group_cpus(group));
}
/**
@@ -2480,6 +2483,9 @@ static bool update_sd_pick_busiest(struct sched_domain *sd,
if (sgs->avg_load <= sds->max_load)
return false;+ if (sgs->sum_nr_running <= sgs->group_weight)
+ return false;
+
if (sgs->sum_nr_running > sgs->group_capacity)
return true;Sorry for the late reply. (fired up your patchlet bright and early so it didn't rot in my inbox any longer;)
Quoted 10 lines · Nikhil Rao
Quoted 9 lines · Mike Galbraith
Quoted 4 lines · Nikhil Rao
Thanks for running this. I've not been able to reproduce what you are seeing on the few test machines that I have (different combinations of MC, CPU and NODE domains). Can you please give me more info about your setup?
It's a plain-jane Q6600 box, so has only MC and CPU domains.
Quoted 8 lines
Quoted 2 lines
It doesn't necessarily _instantly_ "stick", can take a couple tries, or a little time.
The closest I have is a quad-core dual-socket machine (MC, CPU domains). And I'm having trouble reproducing it on that machine as well :-( I ran 5 soaker threads (one of them niced to -15) for a few hours and didn't see the problem. Can you please give me some trace data & schedstats to work with?
Booting with isolcpus or offlining the excess should help.
Quoted 10 lines
Looking at the patch/code, I suspect active migration on the CPU scheduling domain pushes the nice 0 task (running on the same socket as the nice -15 task) to the other socket. This leaves you with an idle core on the nice -15 socket, and with soaker threads there is no way to come back to a 100% utilized state. One possible explanation is the group capacity for a sched group in the CPU sched domain is rounded to 1 (instead of 2). I have a patch below that throws a hammer at the problem and uses group weight instead of group capacity (this is experimental, will refine it if it works). Can you please see if that solves the problem?
Nope, didn't help. I'll poke at it, but am squabbling elsewhere atm.
-Mike
Quoted 9 lines · Mike Galbraith
Quoted 5 lines · Nikhil Rao
The closest I have is a quad-core dual-socket machine (MC, CPU domains). And I'm having trouble reproducing it on that machine as well :-( I ran 5 soaker threads (one of them niced to -15) for a few hours and didn't see the problem. Can you please give me some trace data & schedstats to work with?
Booting with isolcpus or offlining the excess should help.
Sorry for the late reply. Booting with isolcpus did the trick, thanks.
... and now to dig into why this is happening.
-Thanks,
Nikhil
Quoted 16 lines
Quoted 10 lines
Looking at the patch/code, I suspect active migration on the CPU scheduling domain pushes the nice 0 task (running on the same socket as the nice -15 task) to the other socket. This leaves you with an idle core on the nice -15 socket, and with soaker threads there is no way to come back to a 100% utilized state. One possible explanation is the group capacity for a sched group in the CPU sched domain is rounded to 1 (instead of 2). I have a patch below that throws a hammer at the problem and uses group weight instead of group capacity (this is experimental, will refine it if it works). Can you please see if that solves the problem?
Nope, didn't help. I'll poke at it, but am squabbling elsewhere atm.
-Mike
Quoted 8 lines · Nikhil Rao
Quoted 7 lines · Mike Galbraith
Quoted 5 lines · Nikhil Rao
The closest I have is a quad-core dual-socket machine (MC, CPU domains). And I'm having trouble reproducing it on that machine as well :-( I ran 5 soaker threads (one of them niced to -15) for a few hours and didn't see the problem. Can you please give me some trace data & schedstats to work with?
Quoted 6 lines
Quoted 2 lines
Booting with isolcpus or offlining the excess should help.
Sorry for the late reply. Booting with isolcpus did the trick, thanks.
... and now to dig into why this is happening.
I was poking it (again) yesterday, and it's kind of annoying. I can't call this behavior black/white broken. It's freeing up a cache for a very high priority task, which is kinda nice, but SMP nice is costing 25% of my box's processor power in this case too. Hrmph.
-Mike
Quoted 12 lines · Mike Galbraith
Quoted 11 lines · Nikhil Rao
Quoted 9 lines · Mike Galbraith
Quoted 5 lines · Nikhil Rao
The closest I have is a quad-core dual-socket machine (MC, CPU domains). And I'm having trouble reproducing it on that machine as well :-( I ran 5 soaker threads (one of them niced to -15) for a few hours and didn't see the problem. Can you please give me some trace data & schedstats to work with?
Booting with isolcpus or offlining the excess should help.
Quoted 9 lines
Quoted 3 lines
Sorry for the late reply. Booting with isolcpus did the trick, thanks.
... and now to dig into why this is happening.
I was poking it (again) yesterday, and it's kind of annoying. I can't call this behavior black/white broken. It's freeing up a cache for a very high priority task, which is kinda nice, but SMP nice is costing 25% of my box's processor power in this case too. Hrmph.
I agree that freeing up the cache for the high priority task is a nice side-effect of weight-based balancing. However, with sufficient number of low weight tasks on the system, or with a small nudge to affinity masks, the niced task will end up sharing cache with low weight tasks. In that sense, I think this is a tad bit more black than white :-) It would be nice to make the load balancer more cache aware, but that's for a different RFC. :-)
Further, once a sched group reaches a certain "bad state", where the niced task is the only task in a sched group with more than 1 cpu, it does not recover from that state easily. This leads to the sub-optimal utilization situation that we have been chasing down. In this situation, even though the sched group has capacity, it does not pull tasks because sds.this_load >> sds.max_load, and f_b_g() returns NULL.
A sched group reaches this state because either (i). a niced task is pulled into an empty sched group, or (ii). all other tasks in the sched group are pulled away from the group. The patches in this patchset try to prevent the latter, i.e. prevent low weight tasks from being pulled away from the sched group. However, there are still many ways to end up in the bad state. From empirical evidence, it seems to happen more probability on a machine with fewer cpus. I have verified that with the appropriate test setup, this also happens on the quad-socket, quad-core machines as well (i.e. set affinity of the normal tasks to socket-0 and niced task to socket-1, and then reset affinities).
I have attached a patch that tackles the problem in different way. Instead of preventing the sched group from entering the bad state, it shortcuts the checks in fbg if the group has extra capacity, where extra capacity is defined as group_capacity > nr_running. The patch exposes a sched feature called PREFER_UTILIZATION (disabled by default). When this is enabled, f_b_g shortcuts the checks if the local group has capacity. This actually works quite well. I tested this on a quad-core dual-socket (with isolcpus) and waited for the machine to enter the bad state. On flipping the sched feature, utilization immediately shoots up to 100% (of non-isolated cores). I have some data below.
This is very experimental and has not been tested beyond this case and some basic load balance tests. If you see a better way to do this please let me know.
w/ PREFER_UTILIZATION disabled
Cpu(s): 34.3% us, 0.2% sy, 0.0% ni, 65.1% id, 0.4% wa, 0.0% hi, 0.0% si Mem: 16463308k total, 996368k used, 15466940k free, 12304k buffers Swap: 0k total, 0k used, 0k free, 756244k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 7651 root 5 -15 5876 84 0 R 98 0.0 37:35.97 lat 7652 root 20 0 5876 84 0 R 49 0.0 19:49.02 lat 7654 root 20 0 5876 84 0 R 49 0.0 20:48.93 lat 7655 root 20 0 5876 84 0 R 49 0.0 19:25.74 lat 7653 root 20 0 5876 84 0 R 47 0.0 20:02.16 lat
w/ PREFER_UTILIZATION enabled
Cpu(s): 52.3% us, 0.0% sy, 0.0% ni, 47.6% id, 0.0% wa, 0.0% hi, 0.0% si Mem: 16463308k total, 1002852k used, 15460456k free, 12304k buffers Swap: 0k total, 0k used, 0k free, 756312k cached
PID USER PR NI VIRT RES SHR S %CPU %MEM TIME+ COMMAND 7651 root 5 -15 5876 84 0 R 100 0.0 38:12.37 lat 7655 root 20 0 5876 84 0 R 99 0.0 19:49.99 lat 7652 root 20 0 5876 84 0 R 80 0.0 20:09.80 lat 7653 root 20 0 5876 84 0 R 60 0.0 20:22.13 lat 7654 root 20 0 5876 84 0 R 58 0.0 21:07.88 lat
---
kernel/sched_fair.c +3 -0
@@ -2030,12 +2030,14 @@ struct sd_lb_stats {unsigned long this_load;unsigned long this_load_per_task;unsigned long this_nr_running; +unsigned long this_has_capacity;/* Statistics of the busiest group */ unsigned long max_load;unsigned long busiest_load_per_task;unsigned long busiest_nr_running;unsigned long busiest_group_capacity; +unsigned long busiest_has_capacity;int group_imb;/* Is there imbalance in this sd */ #if defined(CONFIG_SCHED_MC ) || defined(CONFIG_SCHED_SMT )
@@ -2058,6 +2060,7 @@ struct sg_lb_stats {unsigned long sum_weighted_load;/* Weighted load of group's tasks */ unsigned long group_capacity;int group_imb;/* Is there an imbalance in the group ? */ +int group_has_capacity;/* Is there extra capacity in the group? */ };/**
@@ -2458,6 +2461,9 @@ static inline void update_sg_lb_stats(struct
sched_domain *sd,
DIV_ROUND_CLOSEST(group->cpu_power, SCHED_LOAD_SCALE);
if (!sgs->group_capacity)
sgs->group_capacity = fix_small_capacity(sd, group);
+
+ if (sgs->group_capacity > sgs->sum_nr_running)
+ sgs->group_has_capacity = 1;
}
/**
@@ -2556,12 +2562,14 @@ static inline void update_sd_lb_stats(struct sched_domain *sd, int this_cpu,
sds->this = sg;
sds->this_nr_running = sgs.sum_nr_running; sds->this_load_per_task = sgs.sum_weighted_load;
+ sds->this_has_capacity = sgs.group_has_capacity;
} else if (update_sd_pick_busiest(sd, sds, sg, &sgs, this_cpu)) {
sds->max_load = sgs.avg_load;
sds->busiest = sg;
sds->busiest_nr_running = sgs.sum_nr_running; sds->busiest_group_capacity = sgs.group_capacity; sds->busiest_load_per_task = sgs.sum_weighted_load;
+ sds->busiest_has_capacity = sgs.group_has_capacity;
sds->group_imb = sgs.group_imb;
}
@@ -2820,6 +2828,10 @@ find_busiest_group(struct sched_domain *sd, int this_cpu,
if (!sds.busiest || sds.busiest_nr_running == 0)
goto out_balanced;
+ if (sched_feat(PREFER_UTILIZATION) &&
+ sds.this_has_capacity && !sds.busiest_has_capacity)
+ goto force_balance;
+
if (sds.this_load >= sds.max_load)
goto out_balanced;
@@ -2831,6 +2843,7 @@ find_busiest_group(struct sched_domain *sd, int this_cpu,
if (100 * sds.max_load <= sd->imbalance_pct * sds.this_load)
goto out_balanced;
+force_balance:
/* Looks like there is an imbalance. Compute it */ calculate_imbalance(&sds, this_cpu, imbalance); return sds.busiest;
kernel/sched_features.h +6 -0
@@ -61,3 +61,9 @@ SCHED_FEAT(ASYM_EFF_LOAD, 1)* release the lock. Decreases scheduling overhead. */ SCHED_FEAT (OWNER_SPIN ,1 ) + +/* +* Prefer utilization over fairness when balancing tasks with large weight +* differential. + */ +SCHED_FEAT (PREFER_UTILIZATION ,0 )
Quoted 7 lines · Nikhil Rao
I have attached a patch that tackles the problem in different way. Instead of preventing the sched group from entering the bad state, it shortcuts the checks in fbg if the group has extra capacity, where extra capacity is defined as
group_capacity>nr_running. The patch exposes a sched feature calledPREFER_UTILIZATION(disabled by default). When this is enabled,f_b_gshortcuts the checks if the local group has capacity. This actually works quite well.
Yeah, it does seem to work well.
I don't like the sched feature much though, a domain flag seems more appropriate. I bent your patch up a bit to correct utilization woes during NEWIDLE balancing instead.. still seems to work fine.
--- kernel/sched_fair.c | 30 +++++++++++++++++++++++++++--- 1 file changed, 27 insertions(+), 3 deletions(-)
kernel/sched_fair.c +27 -3
@@ -1764,6 +1764,10 @@ static void pull_task(struct rq *src_rq,set_task_cpu (p, this_cpu);activate_task (this_rq, p,0 );check_preempt_curr (this_rq, p,0 ); + +/* re-arm NEWIDLE balancing when moving tasks */ + src_rq->avg_idle = this_rq->avg_idle =2 *sysctl_sched_migration_cost; + this_rq->idle_stamp =0 ; }/*
@@ -2030,12 +2034,14 @@ struct sd_lb_stats {unsigned long this_load;unsigned long this_load_per_task;unsigned long this_nr_running; +unsigned long this_has_capacity;/* Statistics of the busiest group */ unsigned long max_load;unsigned long busiest_load_per_task;unsigned long busiest_nr_running;unsigned long busiest_group_capacity; +unsigned long busiest_has_capacity;int group_imb;/* Is there imbalance in this sd */ #if defined(CONFIG_SCHED_MC ) || defined(CONFIG_SCHED_SMT )
@@ -2058,6 +2064,7 @@ struct sg_lb_stats {unsigned long sum_weighted_load;/* Weighted load of group's tasks */ unsigned long group_capacity;int group_imb;/* Is there an imbalance in the group ? */ +int group_has_capacity;/* Is there extra capacity in the group? */ };/**
@@ -2454,6 +2461,9 @@ static inline void update_sg_lb_stats(stDIV_ROUND_CLOSEST (group->cpu_power,SCHED_LOAD_SCALE );if (!sgs->group_capacity) sgs->group_capacity =fix_small_capacity (sd, group); + +if (sgs->group_capacity > sgs->sum_nr_running) + sgs->group_has_capacity =1 ; }/**
@@ -2552,12 +2562,14 @@ static inline void update_sd_lb_stats(st sds->this = sg; sds->this_nr_running = sgs.sum_nr_running; sds->this_load_per_task = sgs.sum_weighted_load; + sds->this_has_capacity = sgs.group_has_capacity; }else if (update_sd_pick_busiest (sd, sds, sg, &sgs, this_cpu)) { sds->max_load = sgs.avg_load; sds->busiest = sg; sds->busiest_nr_running = sgs.sum_nr_running; sds->busiest_group_capacity = sgs.group_capacity; sds->busiest_load_per_task = sgs.sum_weighted_load; + sds->busiest_has_capacity = sgs.group_has_capacity; sds->group_imb = sgs.group_imb; }
@@ -2754,6 +2766,15 @@ static inline void calculate_imbalance(sreturn fix_small_imbalance (sds, this_cpu, imbalance); } + +bool check_utilization (struct sd_lb_stats *sds) +{ +if (!sds->this_has_capacity || sds->busiest_has_capacity) +return false; + +return true; +} +/******* find_busiest_group() helpers end here *********************/ /**
@@ -2816,6 +2837,10 @@ find_busiest_group(struct sched_domain *if (!sds.busiest || sds.busiest_nr_running ==0 ) goto out_balanced; +/* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */ +if (idle ==CPU_NEWLY_IDLE &&check_utilization (&sds)) + goto force_balance; +if (sds.this_load >= sds.max_load) goto out_balanced;
@@ -2827,6 +2852,7 @@ find_busiest_group(struct sched_domain *if (100 * sds.max_load <= sd->imbalance_pct * sds.this_load) goto out_balanced; +force_balance:/* Looks like there is an imbalance. Compute it */ calculate_imbalance (&sds, this_cpu, imbalance);return sds.busiest;
@@ -3153,10 +3179,8 @@ static void idle_balance(int this_cpu, s interval =msecs_to_jiffies (sd->balance_interval);if (time_after (next_balance, sd->last_balance + interval)) next_balance = sd->last_balance + interval; -if (pulled_task) { - this_rq->idle_stamp =0 ; +if (pulled_task)break ; - } }raw_spin_lock (&this_rq->lock);