[tip:sched/core] sched/fair: Consider misfit tasks when load-balancing
Commit-ID: cad68e552e7774b68ae6a2c5fedb792936098b72
Gitweb: https://git.kernel.org/tip/cad68e552e7774b68ae6a2c5fedb792936098b72
Author: Morten Rasmussen
AuthorDate: Wed, 4 Jul 2018 11:17:42 +0100
Committer: Ingo Molnar
CommitDate: Mon, 10 Sep 2018 11:05:50 +0200
sched/fair: Consider misfit tasks when load-balancing
On asymmetric CPU capacity systems load intensive tasks can end up on
CPUs that don't suit their compute demand. In this scenarios 'misfit'
tasks should be migrated to CPUs with higher compute capacity to ensure
better throughput. group_misfit_task indicates this scenario, but tweaks
to the load-balance code are needed to make the migrations happen.
Misfit balancing only makes sense between a source group of lower
per-CPU capacity and destination group of higher compute capacity.
Otherwise, misfit balancing is ignored. group_misfit_task has lowest
priority so any imbalance due to overload is dealt with first.
The modifications are:
1. Only pick a group containing misfit tasks as the busiest group if the
destination group has higher capacity and has spare capacity.
2. When the busiest group is a 'misfit' group, skip the usual average
load and group capacity checks.
3. Set the imbalance for 'misfit' balancing sufficiently high for a task
to be pulled ignoring average load.
4. Pick the CPU with the highest misfit load as the source CPU.
5. If the misfit task is alone on the source CPU, go for active
balancing.
Signed-off-by: Morten Rasmussen
Signed-off-by: Peter Zijlstra (Intel)
Cc: Linus Torvalds
Cc: Peter Zijlstra
Cc: Thomas Gleixner
Cc: dietmar.eggem...@arm.com
Cc: gaku.inami...@renesas.com
Cc: valentin.schnei...@arm.com
Cc: vincent.guit...@linaro.org
Link:
http://lkml.kernel.org/r/1530699470-29808-5-git-send-email-morten.rasmus...@arm.com
Signed-off-by: Ingo Molnar
---
kernel/sched/fair.c | 51 +--
1 file changed, 49 insertions(+), 2 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fe04315d57b3..24fe39e57bc3 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6890,6 +6890,7 @@ struct lb_env {
unsigned intloop_max;
enum fbq_type fbq_type;
+ enum group_type src_grp_type;
struct list_headtasks;
};
@@ -7873,6 +7874,17 @@ static bool update_sd_pick_busiest(struct lb_env *env,
{
struct sg_lb_stats *busiest = >busiest_stat;
+ /*
+* Don't try to pull misfit tasks we can't help.
+* We can use max_capacity here as reduction in capacity on some
+* CPUs in the group should either be possible to resolve
+* internally or be covered by avg_load imbalance (eventually).
+*/
+ if (sgs->group_type == group_misfit_task &&
+ (!group_smaller_max_cpu_capacity(sg, sds->local) ||
+!group_has_capacity(env, >local_stat)))
+ return false;
+
if (sgs->group_type > busiest->group_type)
return true;
@@ -7895,6 +7907,13 @@ static bool update_sd_pick_busiest(struct lb_env *env,
group_smaller_min_cpu_capacity(sds->local, sg))
return false;
+ /*
+* If we have more than one misfit sg go with the biggest misfit.
+*/
+ if (sgs->group_type == group_misfit_task &&
+ sgs->group_misfit_task_load < busiest->group_misfit_task_load)
+ return false;
+
asym_packing:
/* This is the busiest node in its class. */
if (!(env->sd->flags & SD_ASYM_PACKING))
@@ -8192,8 +8211,9 @@ static inline void calculate_imbalance(struct lb_env
*env, struct sd_lb_stats *s
* factors in sg capacity and sgs with smaller group_type are
* skipped when updating the busiest sg:
*/
- if (busiest->avg_load <= sds->avg_load ||
- local->avg_load >= sds->avg_load) {
+ if (busiest->group_type != group_misfit_task &&
+ (busiest->avg_load <= sds->avg_load ||
+local->avg_load >= sds->avg_load)) {
env->imbalance = 0;
return fix_small_imbalance(env, sds);
}
@@ -8227,6 +8247,12 @@ static inline void calculate_imbalance(struct lb_env
*env, struct sd_lb_stats *s
(sds->avg_load - local->avg_load) * local->group_capacity
) / SCHED_CAPACITY_SCALE;
+ /* Boost imbalance to allow misfit task to be balanced. */
+ if (busiest->group_type == group_misfit_task) {
+ env->imbalance = max_t(long, env->imbalance,
+ busiest->group_misfit_task_load);
+ }
+
/*
* if *imbalance is less than the average load per runnable task
* there is no guarantee that any tasks will be moved so we'll have
@@ -8293,6 +8319,10 @@ static struct sched_group *find_busiest_group(struct
lb_env *env)
busiest->group_no_capacity)
goto force_balance;
+
[tip:sched/core] sched/fair: Consider misfit tasks when load-balancing
Commit-ID: cad68e552e7774b68ae6a2c5fedb792936098b72
Gitweb: https://git.kernel.org/tip/cad68e552e7774b68ae6a2c5fedb792936098b72
Author: Morten Rasmussen
AuthorDate: Wed, 4 Jul 2018 11:17:42 +0100
Committer: Ingo Molnar
CommitDate: Mon, 10 Sep 2018 11:05:50 +0200
sched/fair: Consider misfit tasks when load-balancing
On asymmetric CPU capacity systems load intensive tasks can end up on
CPUs that don't suit their compute demand. In this scenarios 'misfit'
tasks should be migrated to CPUs with higher compute capacity to ensure
better throughput. group_misfit_task indicates this scenario, but tweaks
to the load-balance code are needed to make the migrations happen.
Misfit balancing only makes sense between a source group of lower
per-CPU capacity and destination group of higher compute capacity.
Otherwise, misfit balancing is ignored. group_misfit_task has lowest
priority so any imbalance due to overload is dealt with first.
The modifications are:
1. Only pick a group containing misfit tasks as the busiest group if the
destination group has higher capacity and has spare capacity.
2. When the busiest group is a 'misfit' group, skip the usual average
load and group capacity checks.
3. Set the imbalance for 'misfit' balancing sufficiently high for a task
to be pulled ignoring average load.
4. Pick the CPU with the highest misfit load as the source CPU.
5. If the misfit task is alone on the source CPU, go for active
balancing.
Signed-off-by: Morten Rasmussen
Signed-off-by: Peter Zijlstra (Intel)
Cc: Linus Torvalds
Cc: Peter Zijlstra
Cc: Thomas Gleixner
Cc: dietmar.eggem...@arm.com
Cc: gaku.inami...@renesas.com
Cc: valentin.schnei...@arm.com
Cc: vincent.guit...@linaro.org
Link:
http://lkml.kernel.org/r/1530699470-29808-5-git-send-email-morten.rasmus...@arm.com
Signed-off-by: Ingo Molnar
---
kernel/sched/fair.c | 51 +--
1 file changed, 49 insertions(+), 2 deletions(-)
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index fe04315d57b3..24fe39e57bc3 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6890,6 +6890,7 @@ struct lb_env {
unsigned intloop_max;
enum fbq_type fbq_type;
+ enum group_type src_grp_type;
struct list_headtasks;
};
@@ -7873,6 +7874,17 @@ static bool update_sd_pick_busiest(struct lb_env *env,
{
struct sg_lb_stats *busiest = >busiest_stat;
+ /*
+* Don't try to pull misfit tasks we can't help.
+* We can use max_capacity here as reduction in capacity on some
+* CPUs in the group should either be possible to resolve
+* internally or be covered by avg_load imbalance (eventually).
+*/
+ if (sgs->group_type == group_misfit_task &&
+ (!group_smaller_max_cpu_capacity(sg, sds->local) ||
+!group_has_capacity(env, >local_stat)))
+ return false;
+
if (sgs->group_type > busiest->group_type)
return true;
@@ -7895,6 +7907,13 @@ static bool update_sd_pick_busiest(struct lb_env *env,
group_smaller_min_cpu_capacity(sds->local, sg))
return false;
+ /*
+* If we have more than one misfit sg go with the biggest misfit.
+*/
+ if (sgs->group_type == group_misfit_task &&
+ sgs->group_misfit_task_load < busiest->group_misfit_task_load)
+ return false;
+
asym_packing:
/* This is the busiest node in its class. */
if (!(env->sd->flags & SD_ASYM_PACKING))
@@ -8192,8 +8211,9 @@ static inline void calculate_imbalance(struct lb_env
*env, struct sd_lb_stats *s
* factors in sg capacity and sgs with smaller group_type are
* skipped when updating the busiest sg:
*/
- if (busiest->avg_load <= sds->avg_load ||
- local->avg_load >= sds->avg_load) {
+ if (busiest->group_type != group_misfit_task &&
+ (busiest->avg_load <= sds->avg_load ||
+local->avg_load >= sds->avg_load)) {
env->imbalance = 0;
return fix_small_imbalance(env, sds);
}
@@ -8227,6 +8247,12 @@ static inline void calculate_imbalance(struct lb_env
*env, struct sd_lb_stats *s
(sds->avg_load - local->avg_load) * local->group_capacity
) / SCHED_CAPACITY_SCALE;
+ /* Boost imbalance to allow misfit task to be balanced. */
+ if (busiest->group_type == group_misfit_task) {
+ env->imbalance = max_t(long, env->imbalance,
+ busiest->group_misfit_task_load);
+ }
+
/*
* if *imbalance is less than the average load per runnable task
* there is no guarantee that any tasks will be moved so we'll have
@@ -8293,6 +8319,10 @@ static struct sched_group *find_busiest_group(struct
lb_env *env)
busiest->group_no_capacity)
goto force_balance;
+
