CFS group scheduler fairness broken starting from 2.6.29-rc1
Bharata B Rao
Acked-by Peter ZijlstraHi,
Group scheduler fainess is broken since 2.6.29-rc1. git bisect led me to this commit:
commit ec4e0e2fe018992d980910db901637c814575914
Author: Ken Chen <[email protected]> Date: Tue Nov 18 22:41:57 2008 -0800
sched: fix inconsistency when redistribute per-cpu tg->cfs_rq shares
Impact: make load-balancing more consistent
In the update_shares() path leading to tg_shares_up(), the calculation of per-cpu cfs_rq shares is rather erratic even under moderate task wake up rate. The problem is that the per-cpu tg->cfs_rq load weight used in the sd_rq_weight aggregation and actual redistribution of the cfs_rq->shares are collected at different time. Under moderate system load, we've seen quite a bit of variation on the cfs_rq->shares and ultimately wildly affects sched_entity's load weight.
This patch caches the result of initial per-cpu load weight when doing the sum calculation, and then pass it down to update_group_shares_cpu() for redistributing per-cpu cfs_rq shares. This allows consistent total cfs_rq shares across all CPUs. It also simplifies the rounding and zero load weight check.
======================================================================
% CPU time division b/n groups
Group 2.6.29-rc1 2.6.29-rc1 w/o the above patch
======================================================================
a with 8 tasks 44 31
b with 5 tasks 32 34
c with 3 tasks 22 34
======================================================================
All groups had equal shares.
Regards,
Bharata.
On Thu, Jul 23, 2009 at 12:57 AM, Bharata BRao<[email protected]> wrote:> Hi,>> Group scheduler fainess is broken since 2.6.29-rc1. git bisect led me> to this commit:>> commit ec4e0e2fe018992d980910db901637c814575914> Author: Ken Chen <[email protected]>> Date: Tue Nov 18 22:41:57 2008 -0800>> sched: fix inconsistency when redistribute per-cpu tg->cfs_rq shares>> Impact: make load-balancing more consistent> ....>> ======================================================================> % CPU time division b/n groups> Group 2.6.29-rc1 2.6.29-rc1 w/o the above patch> ======================================================================> a with 8 tasks 44 31> b with 5 tasks 32 34> c with 3 tasks 22 34> ======================================================================> All groups had equal shares. What value did you use for each task_group's share? For very largevalue of tg->shares, it could be that all of the boost went to one CPUand subsequently causes load-balancer to shuffle tasks around. Do yousee any unexpected task migration?
- Kenÿôèº{.nÇ+‰·Ÿ®‰†+%ŠËÿ±éݶ¥Šwÿº{.nÇ+‰·¥Š{±þG«�éÿŠ{ayºÊ‡Ú™ë,j¢f£¢·hš�ï�êÿ‘êçz_è®(階ŠÝ¢j"�ú¶m§ÿÿ¾«þG«�éÿ¢¸?™¨èÚ&£ø§~�á¶iO•æ¬z·švØ^¶m§ÿÿÃÿ¶ìÿ¢¸?–I¥
Quoted 26 lines · Ken Chen
Quoted 14 lines · Bharata B Rao
Hi,
Group scheduler fainess is broken since 2.6.29-rc1. git bisect led me to this commit:
commit
ec4e0e2fe018992d980910db901637c814575914
Author: Ken Chen <[email protected]>
Date: Tue Nov 18 22:41:57 2008 -0800sched: fix inconsistency when redistribute per-cpu
tg->cfs_rqsharesImpact: make load-balancing more consistent
....Quoted 9 lines
======================================================================
% CPU time division b/n groups
Group 2.6.29-rc1 2.6.29-rc1 w/o the above patch
======================================================================
a with 8 tasks 44 31
b with 5 tasks 32 34
c with 3 tasks 22 34
======================================================================
All groups had equal shares.
Quoted 4 lines
What value did you use for each task_group's share? For very large value of
tg->shares, it could be that all of the boost went to one CPU and subsequently causes load-balancer to shuffle tasks around. Do you see any unexpected task migration?
Used default 1024 for each group.
Without your patch, each of the tasks see around 165 migrations during a 60s run, but with your patch, they see 125 migrations (as per se.nr_migrations). I am using a 8CPU machine here.
Regards,
Bharata.
Quoted 27 lines · Bharata B Rao
Hi,
Group scheduler fainess is broken since 2.6.29-rc1. git bisect led me to this commit:
commit
ec4e0e2fe018992d980910db901637c814575914Author: Ken Chen <[email protected]> Date: Tue Nov 18 22:41:57 2008 -0800sched: fix inconsistency when redistribute per-cpu
tg->cfs_rqsharesImpact: make load-balancing more consistent
In the
update_shares()path leading totg_shares_up(), the calculation of per-cpucfs_rqshares is rather erratic even under moderate task wake up rate. The problem is that the per-cputg->cfs_rqload weight used in thesd_rq_weightaggregation and actual redistribution of thecfs_rq->sharesare collected at different time. Under moderate system load, we've seen quite a bit of variation on thecfs_rq->sharesand ultimately wildly affects sched_entity's load weight.This patch caches the result of initial per-cpu load weight when doing the sum calculation, and then pass it down to
update_group_shares_cpu()for redistributing per-cpucfs_rqshares. This allows consistent totalcfs_rqshares across all CPUs. It also simplifies the rounding and zero load weight check.
Quoted 3 lines
Signed-off-by Ken Chen <[email protected]>Acked-by Peter Zijlstra <[email protected]>Signed-off-by Ingo Molnar <[email protected]>
Right, I think I spotted the bug.
Before this patch we would assign a non-0 share to empty cpu groups in order to avoid starvation cases. But we could not account that non-0 share into the shares sum of the sd on the next run.
With this patch however we do. Which will create a skew which will only be corrected on the top level domain when we reach there.
- tg->cfs_rq[cpu]->shares = boost ? 0 : shares;
Is the logic that went missing.
/me goes frob a patch together.
How does the below work?
--- kernel/sched.c | 28 ++++++++++++++++++++-------- 1 file changed, 20 insertions(+), 8 deletions(-)
kernel/sched.c +20 -8
@@ -1523,13 +1523,18 @@ static void update_group_shares_cpu(struct task_group *tg, int cpu, unsigned long sd_shares, unsigned long sd_rq_weight) { - unsigned long shares; unsigned long rq_weight; +unsigned long shares; +int boost =0 ;if (!tg->se[cpu])return ; rq_weight = tg->cfs_rq[cpu]->rq_weight; +if (!rq_weight) { + boost =1 ; + rq_weight =NICE_0_LOAD ; + }/* * \Sum shares * rq_weight
@@ -1546,8 +1551,7 @@ update_group_shares_cpu(struct task_grouunsigned long flags;spin_lock_irqsave (&rq->lock, flags); - tg->cfs_rq[cpu]->shares = shares; - + tg->cfs_rq[cpu]->shares = boost ?0 : shares;__set_se_shares (tg->se[cpu], shares);spin_unlock_irqrestore (&rq->lock, flags); }
@@ -1560,7 +1564,7 @@ update_group_shares_cpu(struct task_grou*/ static int tg_shares_up (struct task_group *tg,void *data) { -unsigned long weight, rq_weight =0 ; +unsigned long weight, rq_weight =0 , eff_weight =0 ;unsigned long shares =0 ;struct sched_domain *sd = data;int i;
@@ -1572,11 +1576,13 @@ static int tg_shares_up(struct task_grou* run here it will not get delayed by group starvation. */ weight = tg->cfs_rq[i]->load.weight; + tg->cfs_rq[i]->rq_weight = weight; + rq_weight += weight; +if (!weight) weight =NICE_0_LOAD ; - tg->cfs_rq[i]->rq_weight = weight; - rq_weight += weight; + eff_weight += weight; shares += tg->cfs_rq[i]->shares; }
@@ -1586,8 +1592,14 @@ static int tg_shares_up(struct task_grouif (!sd->parent || !(sd->parent->flags &SD_LOAD_BALANCE )) shares = tg->shares; -for_each_cpu (i,sched_domain_span (sd)) -update_group_shares_cpu (tg, i, shares, rq_weight); +for_each_cpu (i,sched_domain_span (sd)) { +unsigned long sd_rq_weight = rq_weight; + +if (!tg->cfs_rq[i]->rq_weight) + sd_rq_weight = eff_weight; + +update_group_shares_cpu (tg, i, shares, sd_rq_weight); + }return 0 ; }
Quoted 41 lines · Peter Zijlstra
Quoted 27 lines · Bharata B Rao
Hi,
Group scheduler fainess is broken since 2.6.29-rc1. git bisect led me to this commit:
commit
ec4e0e2fe018992d980910db901637c814575914Author: Ken Chen <[email protected]> Date: Tue Nov 18 22:41:57 2008 -0800sched: fix inconsistency when redistribute per-cpu
tg->cfs_rqsharesImpact: make load-balancing more consistent
In the
update_shares()path leading totg_shares_up(), the calculation of per-cpucfs_rqshares is rather erratic even under moderate task wake up rate. The problem is that the per-cputg->cfs_rqload weight used in thesd_rq_weightaggregation and actual redistribution of thecfs_rq->sharesare collected at different time. Under moderate system load, we've seen quite a bit of variation on thecfs_rq->sharesand ultimately wildly affects sched_entity's load weight.This patch caches the result of initial per-cpu load weight when doing the sum calculation, and then pass it down to
update_group_shares_cpu()for redistributing per-cpucfs_rqshares. This allows consistent totalcfs_rqshares across all CPUs. It also simplifies the rounding and zero load weight check.Quoted 3 lines
Signed-off-by Ken Chen <[email protected]>Acked-by Peter Zijlstra <[email protected]>Signed-off-by Ingo Molnar <[email protected]>Right, I think I spotted the bug.
Before this patch we would assign a non-0 share to empty cpu groups in order to avoid starvation cases. But we could not account that non-0 share into the shares sum of the sd on the next run.
With this patch however we do. Which will create a skew which will only be corrected on the top level domain when we reach there.
Quoted 7 lines
- tg->cfs_rq[cpu]->shares = boost ? 0 : shares;
Is the logic that went missing.
/me goes frob a patch together.
How does the below work?
Restores the fairness values to that of 2.6.28. IOW, works fine.
Regards,
Bharata.
Quoted 83 lines
Signed-off-by Peter Zijlstra <[email protected]>--- kernel/sched.c | 28 ++++++++++++++++++++-------- 1 file changed, 20 insertions(+), 8 deletions(-)Index:
linux-2.6/kernel/sched.c
===================================================================kernel/sched.c +20
-8@@ -1523,13 +1523,18 @@ static void update_group_shares_cpu(struct task_group *tg, int cpu, unsigned long sd_shares, unsigned long sd_rq_weight) { - unsigned long shares; unsigned long rq_weight; +unsigned long shares; +int boost =0 ;if (!tg->se[cpu])return ; rq_weight = tg->cfs_rq[cpu]->rq_weight; +if (!rq_weight) { + boost =1 ; + rq_weight =NICE_0_LOAD ; + }/* * \Sum shares * rq_weight @@ -1546,8 +1551,7 @@ update_group_shares_cpu(struct task_grouunsigned long flags;spin_lock_irqsave (&rq->lock, flags); - tg->cfs_rq[cpu]->shares = shares; - + tg->cfs_rq[cpu]->shares = boost ?0 : shares;__set_se_shares (tg->se[cpu], shares);spin_unlock_irqrestore (&rq->lock, flags); }@@ -1560,7 +1564,7 @@ update_group_shares_cpu(struct task_grou*/ static int tg_shares_up (struct task_group *tg,void *data) { -unsigned long weight, rq_weight =0 ; +unsigned long weight, rq_weight =0 , eff_weight =0 ;unsigned long shares =0 ;struct sched_domain *sd = data;int i;@@ -1572,11 +1576,13 @@ static int tg_shares_up(struct task_grou* run here it will not get delayed by group starvation. */ weight = tg->cfs_rq[i]->load.weight; + tg->cfs_rq[i]->rq_weight = weight; + rq_weight += weight; +if (!weight) weight =NICE_0_LOAD ; - tg->cfs_rq[i]->rq_weight = weight; - rq_weight += weight; + eff_weight += weight; shares += tg->cfs_rq[i]->shares; }@@ -1586,8 +1592,14 @@ static int tg_shares_up(struct task_grouif (!sd->parent || !(sd->parent->flags &SD_LOAD_BALANCE )) shares = tg->shares; -for_each_cpu (i,sched_domain_span (sd)) -update_group_shares_cpu (tg, i, shares, rq_weight); +for_each_cpu (i,sched_domain_span (sd)) { +unsigned long sd_rq_weight = rq_weight; + +if (!tg->cfs_rq[i]->rq_weight) + sd_rq_weight = eff_weight; + +update_group_shares_cpu (tg, i, shares, sd_rq_weight); + }return 0 ; }
Quoted 3 lines · Bharata B Rao
Quoted 1 line
How does the below work?
Restores the fairness values to that of 2.6.28. IOW, works fine.
That's pretty good for a patch I merely compile tested ;-)
I'll merge this, unless someone (Ken?) can convince me there's something wrong with it ;-)
[tip:sched/core] sched: Fix cgroup smp fairness
In reply to Peter ZijlstraCommit-ID: a5004278f0525dcb9aa43703ef77bf371ea837cd Gitweb: http://git.kernel.org/tip/a5004278f0525dcb9aa43703ef77bf371ea837cd Author: Peter Zijlstra <[email protected]> AuthorDate: Mon, 27 Jul 2009 14:04:49 +0200 Committer: Ingo Molnar <[email protected]> CommitDate: Sun, 2 Aug 2009 14:26:06 +0200
sched: Fix cgroup smp fairness
Commit ec4e0e2fe018992d980910db901637c814575914 ("fix inconsistency when redistribute per-cpu tg->cfs_rq shares") broke cgroup smp fairness.
In order to avoid starvation of newly placed tasks, we never quite set the share of an empty cpu group-task to 0, but instead we set it as if there's a single NICE-0 task present.
If however we actually set this in cfs_rq[cpu]->shares, that means the total shares for that group will be slightly inflated every time we balance, causing the observed unfairness.
Fix this by setting cfs_rq[cpu]->shares to 0 but actually setting the effective weight of the related se to the inflated number.
LKML-Reference: <1248696557.6987.1615.camel@twins>
--- kernel/sched.c | 28 ++++++++++++++++++++-------- 1 files changed, 20 insertions(+), 8 deletions(-)
kernel/sched.c +20 -8
@@ -1523,13 +1523,18 @@ static void update_group_shares_cpu(struct task_group *tg, int cpu, unsigned long sd_shares, unsigned long sd_rq_weight) { - unsigned long shares; unsigned long rq_weight; +unsigned long shares; +int boost =0 ;if (!tg->se[cpu])return ; rq_weight = tg->cfs_rq[cpu]->rq_weight; +if (!rq_weight) { + boost =1 ; + rq_weight =NICE_0_LOAD ; + }/* * \Sum shares * rq_weight
@@ -1546,8 +1551,7 @@ update_group_shares_cpu(struct task_group *tg, int cpu,unsigned long flags;spin_lock_irqsave (&rq->lock, flags); - tg->cfs_rq[cpu]->shares = shares; - + tg->cfs_rq[cpu]->shares = boost ?0 : shares;__set_se_shares (tg->se[cpu], shares);spin_unlock_irqrestore (&rq->lock, flags); }
@@ -1560,7 +1564,7 @@ update_group_shares_cpu(struct task_group *tg, int cpu,*/ static int tg_shares_up (struct task_group *tg,void *data) { -unsigned long weight, rq_weight =0 ; +unsigned long weight, rq_weight =0 , eff_weight =0 ;unsigned long shares =0 ;struct sched_domain *sd = data;int i;
@@ -1572,11 +1576,13 @@ static int tg_shares_up(struct task_group *tg, void *data)* run here it will not get delayed by group starvation. */ weight = tg->cfs_rq[i]->load.weight; + tg->cfs_rq[i]->rq_weight = weight; + rq_weight += weight; +if (!weight) weight =NICE_0_LOAD ; - tg->cfs_rq[i]->rq_weight = weight; - rq_weight += weight; + eff_weight += weight; shares += tg->cfs_rq[i]->shares; }
@@ -1586,8 +1592,14 @@ static int tg_shares_up(struct task_group *tg, void *data)if (!sd->parent || !(sd->parent->flags &SD_LOAD_BALANCE )) shares = tg->shares; -for_each_cpu (i,sched_domain_span (sd)) -update_group_shares_cpu (tg, i, shares, rq_weight); +for_each_cpu (i,sched_domain_span (sd)) { +unsigned long sd_rq_weight = rq_weight; + +if (!tg->cfs_rq[i]->rq_weight) + sd_rq_weight = eff_weight; + +update_group_shares_cpu (tg, i, shares, sd_rq_weight); + }return 0 ; }