Skip to contentSkip to conversation

sched: use runnable avg in load balance

PATCH Superseded Alex Shi 4 participants 44 messages Apr 2, 2013 – Apr 10, 2013

Subsystems (2)

v3 of 8 Superseded Latest is v8 →

lore
Share & tools
lore

Alex Shi

author
#0 lore raw

v3 cover sched: use runnable avg in load balance

This version resolved the aim7 liked benchmark issue by patch 8th. Thanks for MikeG's avg_idle that is a good bursty wakeup indicator.

The first 3 patches were also include in my power aware scheduling patchset.

Morten, you can rebase your patch on this new version that bases on latest Linus tree. :)

a git tree for this patchset:
https://github.com/alexshi/power-scheduling.git runnablelb

Thanks
Alex

[patch v3 1/8] Revert "sched: Introduce temporary FAIR_GROUP_SCHED [patch v3 2/8] sched: set initial value of runnable avg for new [patch v3 3/8] sched: only count runnable avg on cfs_rq's nr_running [patch v3 4/8] sched: update cpu load after task_tick. [patch v3 5/8] sched: compute runnable load avg in cpu_load and [patch v3 6/8] sched: consider runnable load average in move_tasks [patch v3 7/8] sched: consider runnable load average in [patch v3 8/8] sched: use instant load for burst wake up

author
#1 lore raw

PATCH v3 1/8 Revert "sched: Introduce temporary FAIR_GROUP_SCHED dependency for load-tracking"

Remove CONFIG_FAIR_GROUP_SCHED that covers the runnable info, then we can use runnable load variables.

---
 include/linux/sched.h |  7 +------
 kernel/sched/core.c   |  7 +------
 kernel/sched/fair.c   | 13 ++-----------
 kernel/sched/sched.h  |  9 +--------
 4 files changed, 5 insertions(+), 31 deletions(-)
include/linux/sched.h +1 -6
index d35d2b6..5a4cf37 100644
@@ -1160,12 +1160,7 @@ struct sched_entity {
 	struct cfs_rq		*my_q;
 #endif
 
-/*
- * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be
- * removed when useful for applications beyond shares distribution (e.g.
- * load-balance).
- */
-#if defined(CONFIG_SMP) && defined(CONFIG_FAIR_GROUP_SCHED)
+#ifdef CONFIG_SMP
 	/* Per-entity load-tracking */
 	struct sched_avg	avg;
 #endif
kernel/sched/core.c +1 -6
index 7f12624..54eaaa2 100644
@@ -1561,12 +1561,7 @@ static void __sched_fork(struct task_struct *p)
 	p->se.vruntime			= 0;
 	INIT_LIST_HEAD(&p->se.group_node);
 
-/*
- * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be
- * removed when useful for applications beyond shares distribution (e.g.
- * load-balance).
- */
-#if defined(CONFIG_SMP) && defined(CONFIG_FAIR_GROUP_SCHED)
+#ifdef CONFIG_SMP
 	p->se.avg.runnable_avg_period = 0;
 	p->se.avg.runnable_avg_sum = 0;
 #endif
kernel/sched/fair.c +2 -11
index 7a33e59..9c2f726 100644
@@ -1109,8 +1109,7 @@ static inline void update_cfs_shares(struct cfs_rq *cfs_rq)
 }
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
-/* Only depends on SMP, FAIR_GROUP_SCHED may be removed when useful in lb */
-#if defined(CONFIG_SMP) && defined(CONFIG_FAIR_GROUP_SCHED)
+#ifdef CONFIG_SMP
 /*
  * We choose a half-life close to 1 scheduling period.
  * Note: The tables below are dependent on this value.
@@ -3394,12 +3393,6 @@ unlock:
 }
 
 /*
- * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be
- * removed when useful for applications beyond shares distribution (e.g.
- * load-balance).
- */
-#ifdef CONFIG_FAIR_GROUP_SCHED
-/*
  * Called immediately before a task is migrated to a new cpu; task_cpu(p) and
  * cfs_rq_of(p) references at time of call are still valid and identify the
  * previous cpu.  However, the caller only guarantees p->pi_lock is held; no
@@ -3422,7 +3415,6 @@ migrate_task_rq_fair(struct task_struct *p, int next_cpu)
 		atomic64_add(se->avg.load_avg_contrib, &cfs_rq->removed_load);
 	}
 }
-#endif
 #endif /* CONFIG_SMP */
 
 static unsigned long
@@ -6114,9 +6106,8 @@ const struct sched_class fair_sched_class = {
 
 #ifdef CONFIG_SMP
 	.select_task_rq		= select_task_rq_fair,
-#ifdef CONFIG_FAIR_GROUP_SCHED
 	.migrate_task_rq	= migrate_task_rq_fair,
-#endif
+
 	.rq_online		= rq_online_fair,
 	.rq_offline		= rq_offline_fair,
 
kernel/sched/sched.h +1 -8
index cc03cfd..7f36024f 100644
@@ -227,12 +227,6 @@ struct cfs_rq {
 #endif
 
 #ifdef CONFIG_SMP
-/*
- * Load-tracking only depends on SMP, FAIR_GROUP_SCHED dependency below may be
- * removed when useful for applications beyond shares distribution (e.g.
- * load-balance).
- */
-#ifdef CONFIG_FAIR_GROUP_SCHED
 	/*
 	 * CFS Load tracking
 	 * Under CFS, load is tracked on a per-entity basis and aggregated up.
@@ -242,8 +236,7 @@ struct cfs_rq {
 	u64 runnable_load_avg, blocked_load_avg;
 	atomic64_t decay_counter, removed_load;
 	u64 last_decay;
-#endif /* CONFIG_FAIR_GROUP_SCHED */
-/* These always depend on CONFIG_FAIR_GROUP_SCHED */
+
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	u32 tg_runnable_contrib;
 	u64 tg_load_contrib;
Signature · 1 line
1.7.12
author
#2 lore raw

PATCH v3 2/8 sched: set initial value of runnable avg for new forked task

In reply to Alex Shi

We need initialize the se.avg.{decay_count, load_avg_contrib} for a new forked task.
Otherwise random values of above variables cause mess when do new task enqueue:
enqueue_task_fair
enqueue_entity
enqueue_entity_load_avg

and make forking balancing imbalance since incorrect load_avg_contrib.

set avg.decay_count = 0, and avg.load_avg_contrib = se->load.weight to resolve such issues.

---
 kernel/sched/core.c | 6 ++++++
 kernel/sched/fair.c | 4 ++++
 2 files changed, 10 insertions(+)
kernel/sched/core.c +6 -0
index 54eaaa2..8843cd3 100644
@@ -1564,6 +1564,7 @@ static void __sched_fork(struct task_struct *p)
 #ifdef CONFIG_SMP
 	p->se.avg.runnable_avg_period = 0;
 	p->se.avg.runnable_avg_sum = 0;
+	p->se.avg.decay_count = 0;
 #endif
 #ifdef CONFIG_SCHEDSTATS
 	memset(&p->se.statistics, 0, sizeof(p->se.statistics));
@@ -1651,6 +1652,11 @@ void sched_fork(struct task_struct *p)
 		p->sched_reset_on_fork = 0;
 	}
 
+	/* New forked task assumed with full utilization */
+#if defined(CONFIG_SMP)
+	p->se.avg.load_avg_contrib = p->se.load.weight;
+#endif
+
 	if (!rt_prio(p->prio))
 		p->sched_class = &fair_sched_class;
 
kernel/sched/fair.c +4 -0
index 9c2f726..2881d42 100644
@@ -1508,6 +1508,10 @@ static inline void enqueue_entity_load_avg(struct cfs_rq *cfs_rq,
 	 * We track migrations using entity decay_count <= 0, on a wake-up
 	 * migration we use a negative decay count to track the remote decays
 	 * accumulated while sleeping.
+	 *
+	 * When enqueue a new forked task, the se->avg.decay_count == 0, so
+	 * we bypass update_entity_load_avg(), use avg.load_avg_contrib initial
+	 * value: se->load.weight.
 	 */
 	if (unlikely(se->avg.decay_count <= 0)) {
 		se->avg.last_runnable_update = rq_of(cfs_rq)->clock_task;
Signature · 1 line
1.7.12
author
#3 lore raw

PATCH v3 3/8 sched: only count runnable avg on cfs_rq's nr_running

In reply to Alex Shi

Old function count the runnable avg on rq's nr_running even there is only rt task in rq. That is incorrect, so correct it to cfs_rq's nr_running.

---
 kernel/sched/fair.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/fair.c +1 -1
index 2881d42..026e959 100644
@@ -2829,7 +2829,7 @@ enqueue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 	}
 
 	if (!se) {
-		update_rq_runnable_avg(rq, rq->nr_running);
+		update_rq_runnable_avg(rq, rq->cfs.nr_running);
 		inc_nr_running(rq);
 	}
 	hrtick_update(rq);
Signature · 1 line
1.7.12
author
#4 lore raw

Re: [patch v3 3/8] sched: only count runnable avg on cfs_rq's nr_running

Quoted 3 lines · Alex Shi

Old function count the runnable avg on rq's nr_running even there is only rt task in rq. That is incorrect, so correct it to cfs_rq's nr_running.

this patch is incorrect and removed in
https://github.com/alexshi/power-scheduling.git runnablelb

author
#5 lore raw

PATCH v3 4/8 sched: update cpu load after task_tick.

In reply to Alex Shi

To get the latest runnable info, we need do this cpuload update after task_tick.

---
 kernel/sched/core.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/sched/core.c +1 -1
index 8843cd3..e3233d3 100644
@@ -2690,8 +2690,8 @@ void scheduler_tick(void)
 
 	raw_spin_lock(&rq->lock);
 	update_rq_clock(rq);
-	update_cpu_load_active(rq);
 	curr->sched_class->task_tick(rq, curr, 0);
+	update_cpu_load_active(rq);
 	raw_spin_unlock(&rq->lock);
 
 	perf_event_task_tick();
Signature · 1 line
1.7.12
author
#6 lore raw

PATCH v3 5/8 sched: compute runnable load avg in cpu_load and cpu_avg_load_per_task

In reply to Alex Shi

They are the base values in load balance, update them with rq runnable load average, then the load balance will consider runnable load avg naturally.

---
 kernel/sched/core.c | 4 ++--
 kernel/sched/fair.c | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)
kernel/sched/core.c +2 -2
index e3233d3..a772de0 100644
@@ -2534,7 +2534,7 @@ static void __update_cpu_load(struct rq *this_rq, unsigned long this_load,
 void update_idle_cpu_load(struct rq *this_rq)
 {
 	unsigned long curr_jiffies = ACCESS_ONCE(jiffies);
-	unsigned long load = this_rq->load.weight;
+	unsigned long load = (unsigned long)this_rq->cfs.runnable_load_avg;
 	unsigned long pending_updates;
 
 	/*
@@ -2584,7 +2584,7 @@ static void update_cpu_load_active(struct rq *this_rq)
 	 * See the mess around update_idle_cpu_load() / update_cpu_load_nohz().
 	 */
 	this_rq->last_load_update_tick = jiffies;
-	__update_cpu_load(this_rq, this_rq->load.weight, 1);
+	__update_cpu_load(this_rq, this_rq->cfs.runnable_load_avg, 1);
 
 	calc_load_account_active(this_rq);
 }
kernel/sched/fair.c +2 -2
index 026e959..1f9026e 100644
@@ -2900,7 +2900,7 @@ static void dequeue_task_fair(struct rq *rq, struct task_struct *p, int flags)
 /* Used instead of source_load when we know the type == 0 */
 static unsigned long weighted_cpuload(const int cpu)
 {
-	return cpu_rq(cpu)->load.weight;
+	return (unsigned long)cpu_rq(cpu)->cfs.runnable_load_avg;
 }
 
 /*
@@ -2947,7 +2947,7 @@ static unsigned long cpu_avg_load_per_task(int cpu)
 	unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
 
 	if (nr_running)
-		return rq->load.weight / nr_running;
+		return (unsigned long)rq->cfs.runnable_load_avg / nr_running;
 
 	return 0;
 }
Signature · 1 line
1.7.12
author
#7 lore raw

PATCH v3 6/8 sched: consider runnable load average in move_tasks

In reply to Alex Shi

Except using runnable load average in background, move_tasks is also the key functions in load balance. We need consider the runnable load average in it in order to the apple to apple load comparison.

---
 kernel/sched/fair.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +10 -1
index 1f9026e..bf4e0d4 100644
@@ -3966,6 +3966,15 @@ static unsigned long task_h_load(struct task_struct *p);
 
 static const unsigned int sched_nr_migrate_break = 32;
 
+static unsigned long task_h_load_avg(struct task_struct *p)
+{
+	u32 period = p->se.avg.runnable_avg_period;
+	if (!period)
+		return 0;
+
+	return task_h_load(p) * p->se.avg.runnable_avg_sum / period;
+}
+
 /*
  * move_tasks tries to move up to imbalance weighted load from busiest to
  * this_rq, as part of a balancing operation within domain "sd".
@@ -4001,7 +4010,7 @@ static int move_tasks(struct lb_env *env)
 		if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
 			goto next;
 
-		load = task_h_load(p);
+		load = task_h_load_avg(p);
 
 		if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
 			goto next;
Signature · 1 line
1.7.12
maintainer
#8 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 14 lines · Alex Shi

Except using runnable load average in background, move_tasks is also the key functions in load balance. We need consider the runnable load average in it in order to the apple to apple load comparison.

---
 kernel/sched/fair.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +0 -0
index 1f9026e..bf4e0d4 100644

kernel/sched/fair.c static unsigned long task_h_load(struct task_struct *p); · line 3975

Quoted 10 lines
kernel/sched/fair.c +7 -0
@@ -3966,6 +3966,15 @@ static unsigned long task_h_load(struct task_struct *p);
 
 static const unsigned int sched_nr_migrate_break = 32;
 
+static unsigned long task_h_load_avg(struct task_struct *p)
+{
+       u32 period = p->se.avg.runnable_avg_period;
+       if (!period)
+               return 0;
+
+       return task_h_load(p) * p->se.avg.runnable_avg_sum / period;

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Vincent

Quoted 17 lines
kernel/sched/fair.c +3 -2
+}
+
 /*
  * move_tasks tries to move up to imbalance weighted load from busiest to
  * this_rq, as part of a balancing operation within domain "sd".
@@ -4001,7 +4010,7 @@ static int move_tasks(struct lb_env *env)
                if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
                        goto next;
 
-               load = task_h_load(p);
+               load = task_h_load_avg(p);
 
                if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
                        goto next;
--

1.7.12

author
#9 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 18 lines · Vincent Guittot
Quoted 17 lines · Alex Shi

Except using runnable load average in background, move_tasks is also the key functions in load balance. We need consider the runnable load average in it in order to the apple to apple load comparison.

---
 kernel/sched/fair.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +0 -0
index 1f9026e..bf4e0d4 100644
@@ -3966,6 +3966,15 @@ static unsigned long task_h_load(struct task_struct *p);
 
 static const unsigned int sched_nr_migrate_break = 32;
 
Quoted 11 lines

kernel/sched/fair.c static unsigned long task_h_load(struct task_struct *p); · line 3975

Quoted 7 lines
kernel/sched/fair.c +7 -0
+static unsigned long task_h_load_avg(struct task_struct *p)
+{
+       u32 period = p->se.avg.runnable_avg_period;
+       if (!period)
+               return 0;
+
+       return task_h_load(p) * p->se.avg.runnable_avg_sum / period;

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Thanks for your question, Vincent!
the runnable_avg_period and runnable_avg_sum, only updated in __update_entity_runnable_avg().
Yes, I didn't see some locks to ensure the coherent of them. but they are updated closely, and it is not big deal even a little incorrect to their value. These data are collected periodically, don't need very very precise at every time.
Am I right? :)

Signature · 1 line
Thanks Alex
maintainer
#10 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 31 lines · Alex Shi
Quoted 18 lines · Vincent Guittot
Quoted 17 lines · Alex Shi

Except using runnable load average in background, move_tasks is also the key functions in load balance. We need consider the runnable load average in it in order to the apple to apple load comparison.

---
 kernel/sched/fair.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +0 -0
index 1f9026e..bf4e0d4 100644
@@ -3966,6 +3966,15 @@ static unsigned long task_h_load(struct task_struct *p);
 
 static const unsigned int sched_nr_migrate_break = 32;
 
Quoted 11 lines

kernel/sched/fair.c static unsigned long task_h_load(struct task_struct *p); · line 3975

Quoted 7 lines
kernel/sched/fair.c +7 -0
+static unsigned long task_h_load_avg(struct task_struct *p)
+{
+       u32 period = p->se.avg.runnable_avg_period;
+       if (!period)
+               return 0;
+
+       return task_h_load(p) * p->se.avg.runnable_avg_sum / period;

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Quoted 8 lines

Thanks for your question, Vincent!
the runnable_avg_period and runnable_avg_sum, only updated in __update_entity_runnable_avg().
Yes, I didn't see some locks to ensure the coherent of them. but they are updated closely, and it is not big deal even a little incorrect to their value. These data are collected periodically, don't need very very precise at every time.
Am I right? :)

The problem mainly appears during starting phase (the 1st 345ms) when runnable_avg_period has not reached the max value yet so you can have avg.runnable_avg_sum greater than avg.runnable_avg_period. In a worst case, runnable_avg_sum could be twice runnable_avg_period

Vincent

Quoted 3 lines

--
Thanks Alex

author
#11 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 12 lines · Vincent Guittot
Quoted 4 lines
Quoted 4 lines
Quoted 3 lines
Quoted 3 lines

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Quoted 8 lines
Quoted 8 lines

Thanks for your question, Vincent!
the runnable_avg_period and runnable_avg_sum, only updated in __update_entity_runnable_avg().
Yes, I didn't see some locks to ensure the coherent of them. but they are updated closely, and it is not big deal even a little incorrect to their value. These data are collected periodically, don't need very very precise at every time.
Am I right? :)

Quoted 4 lines

The problem mainly appears during starting phase (the 1st 345ms) when runnable_avg_period has not reached the max value yet so you can have avg.runnable_avg_sum greater than avg.runnable_avg_period. In a worst case, runnable_avg_sum could be twice runnable_avg_period

Oh, That's a serious problem. Do you catch it in real word or in code? Could you explain more for details?

Signature · 2 lines
Thanks
    Alex
maintainer
#12 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 13 lines · Alex Shi
Quoted 12 lines · Vincent Guittot
Quoted 12 lines
Quoted 12 lines
Quoted 3 lines
Quoted 3 lines

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Thanks for your question, Vincent!
the runnable_avg_period and runnable_avg_sum, only updated in __update_entity_runnable_avg().
Yes, I didn't see some locks to ensure the coherent of them. but they are updated closely, and it is not big deal even a little incorrect to their value. These data are collected periodically, don't need very very precise at every time.
Am I right? :)

Quoted 6 lines
Quoted 4 lines

The problem mainly appears during starting phase (the 1st 345ms) when runnable_avg_period has not reached the max value yet so you can have avg.runnable_avg_sum greater than avg.runnable_avg_period. In a worst case, runnable_avg_sum could be twice runnable_avg_period

Oh, That's a serious problem. Do you catch it in real word or in code?

I haven't trace that shows this issue but nothing prevent an update to occur while you get values so you can have a mix of old and new values.

Quoted 1 line

Could you explain more for details?

Both fields of a new task increase simultaneously but if you get the old value for runnable_avg_period and the new one for runnable_avg_sum, runnable_avg_sum will be greater than runnable_avg_period during this starting phase.

The worst case appears 2ms after the creation of the task, runnable_avg_period and runnable_avg_sum should go from 1024 to 2046. So the task_h_load_avg will be 199% of task_h_load If you have runnable_avg_period with 1024 and runnable_avg_sum with 2046.

A simple solution is to check that runnable_avg_period is always greater or equal to runnable_avg_sum like i have done in my packing small tasks patches

Vincent

Quoted 4 lines

--
Thanks
Alex

author
#13 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 32 lines · Vincent Guittot
Quoted 13 lines · Alex Shi
Quoted 12 lines · Vincent Guittot
Quoted 12 lines
Quoted 12 lines
Quoted 3 lines
Quoted 3 lines

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Thanks for your question, Vincent!
the runnable_avg_period and runnable_avg_sum, only updated in __update_entity_runnable_avg().
Yes, I didn't see some locks to ensure the coherent of them. but they are updated closely, and it is not big deal even a little incorrect to their value. These data are collected periodically, don't need very very precise at every time.
Am I right? :)

Quoted 6 lines
Quoted 4 lines

The problem mainly appears during starting phase (the 1st 345ms) when runnable_avg_period has not reached the max value yet so you can have avg.runnable_avg_sum greater than avg.runnable_avg_period. In a worst case, runnable_avg_sum could be twice runnable_avg_period

Oh, That's a serious problem. Do you catch it in real word or in code?

I haven't trace that shows this issue but nothing prevent an update to occur while you get values so you can have a mix of old and new values.

Quoted 1 line

Could you explain more for details?

Both fields of a new task increase simultaneously but if you get the old value for runnable_avg_period and the new one for runnable_avg_sum, runnable_avg_sum will be greater than runnable_avg_period during this starting phase.

Quoted 4 lines

The worst case appears 2ms after the creation of the task, runnable_avg_period and runnable_avg_sum should go from 1024 to 2046. So the task_h_load_avg will be 199% of task_h_load If you have runnable_avg_period with 1024 and runnable_avg_sum with 2046.

Thanks a lot for info sharing! Vincent.

But I checked the rq->avg and task->se.avg, seems none of them are possible be updated on different CPU at the same time. So my printk didn't catch this with benchmark kbuild and aim7 on my SNB EP box.

Then I find some words in your commit log:
"If a CPU accesses the runnable_avg_sum and runnable_avg_period fields of its buddy CPU while the latter updates it, it can get the new version of a field and the old version of the other one."
So is it possible caused by the buddy cpu's accessing?
Could you like to recheck this without your patch?

Signature · 2 lines
Thanks
    Alex
maintainer
#14 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 38 lines · Alex Shi
Quoted 32 lines · Vincent Guittot
Quoted 13 lines · Alex Shi
Quoted 12 lines · Vincent Guittot
Quoted 12 lines
Quoted 12 lines
Quoted 3 lines
Quoted 3 lines

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Thanks for your question, Vincent!
the runnable_avg_period and runnable_avg_sum, only updated in __update_entity_runnable_avg().
Yes, I didn't see some locks to ensure the coherent of them. but they are updated closely, and it is not big deal even a little incorrect to their value. These data are collected periodically, don't need very very precise at every time.
Am I right? :)

Quoted 6 lines
Quoted 4 lines

The problem mainly appears during starting phase (the 1st 345ms) when runnable_avg_period has not reached the max value yet so you can have avg.runnable_avg_sum greater than avg.runnable_avg_period. In a worst case, runnable_avg_sum could be twice runnable_avg_period

Oh, That's a serious problem. Do you catch it in real word or in code?

I haven't trace that shows this issue but nothing prevent an update to occur while you get values so you can have a mix of old and new values.

Quoted 1 line

Could you explain more for details?

Both fields of a new task increase simultaneously but if you get the old value for runnable_avg_period and the new one for runnable_avg_sum, runnable_avg_sum will be greater than runnable_avg_period during this starting phase.

Quoted 4 lines

The worst case appears 2ms after the creation of the task, runnable_avg_period and runnable_avg_sum should go from 1024 to 2046. So the task_h_load_avg will be 199% of task_h_load If you have runnable_avg_period with 1024 and runnable_avg_sum with 2046.

Quoted 5 lines

Thanks a lot for info sharing! Vincent.

But I checked the rq->avg and task->se.avg, seems none of them are possible be updated on different CPU at the same time. So my printk didn't catch this with benchmark kbuild and aim7 on my SNB EP box.

The problem can happen because reader and writer are accessing the variable asynchronously and on different CPUs

CPUA write runnable_avg_sum
CPUB read runnable_avg_sum
CPUB read runnable_avg_period
CPUA write runnable_avg_period

I agree that the time window, during which this can occur, is short but not impossible

Vincent

Quoted 12 lines

Then I find some words in your commit log:
"If a CPU accesses the runnable_avg_sum and runnable_avg_period fields of its buddy CPU while the latter updates it, it can get the new version of a field and the old version of the other one."
So is it possible caused by the buddy cpu's accessing?
Could you like to recheck this without your patch?

--
Thanks
Alex

author
#15 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 8 lines · Vincent Guittot
Quoted 5 lines
Quoted 5 lines

Thanks a lot for info sharing! Vincent.

But I checked the rq->avg and task->se.avg, seems none of them are possible be updated on different CPU at the same time. So my printk didn't catch this with benchmark kbuild and aim7 on my SNB EP box.

The problem can happen because reader and writer are accessing the variable asynchronously and on different CPUs

Quoted 7 lines

CPUA write runnable_avg_sum
CPUB read runnable_avg_sum
CPUB read runnable_avg_period
CPUA write runnable_avg_period

I agree that the time window, during which this can occur, is short but not impossible

May I didn't say clear. Vincent.

member of rq struct include avg, should be protected by rq->lock when other cpu want to access them. Or be accessed only by local cpu. So they should be no above situation.
And for per task avg, the task is impossible to be on different cpu at the same time. so there are also no above problem.

I thought the problem may exists for middle level entity, but seems task group has each of entity on every cpu. So there is no this problem too.

So, you may better to hold rq->lock when check the buddy cpu info.

Correct me if sth wrong. :)

Signature · 1 line
Thanks Alex
#16 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

In reply to Vincent Guittot
Quoted 18 lines · Vincent Guittot
Quoted 17 lines · Alex Shi

Except using runnable load average in background, move_tasks is also the key functions in load balance. We need consider the runnable load average in it in order to the apple to apple load comparison.

---
 kernel/sched/fair.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +0 -0
index 1f9026e..bf4e0d4 100644
@@ -3966,6 +3966,15 @@ static unsigned long task_h_load(struct task_struct *p);
 
 static const unsigned int sched_nr_migrate_break = 32;
 
Quoted 11 lines

kernel/sched/fair.c static unsigned long task_h_load(struct task_struct *p); · line 3975

Quoted 7 lines
kernel/sched/fair.c +7 -0
+static unsigned long task_h_load_avg(struct task_struct *p)
+{
+       u32 period = p->se.avg.runnable_avg_period;
+       if (!period)
+               return 0;
+
+       return task_h_load(p) * p->se.avg.runnable_avg_sum / period;

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Hi, Vincent

Don't we have the 'rq->lock' to protect it?

move_tasks() was invoked with double locked, for all the se on src and dst rq, no update should happen, isn't it?

Regards,
Michael Wang

Quoted 26 lines

Vincent

Quoted 15 lines
kernel/sched/fair.c +3 -2
+}
+
 /*
  * move_tasks tries to move up to imbalance weighted load from busiest to
  * this_rq, as part of a balancing operation within domain "sd".
@@ -4001,7 +4010,7 @@ static int move_tasks(struct lb_env *env)
                if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
                        goto next;
 
-               load = task_h_load(p);
+               load = task_h_load_avg(p);
 
                if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
                        goto next;
--
Quoted 2 lines

1.7.12

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

maintainer
#17 lore raw

Re: [patch v3 6/8] sched: consider runnable load average in move_tasks

Quoted 31 lines · Michael Wang
Quoted 18 lines · Vincent Guittot
Quoted 17 lines · Alex Shi

Except using runnable load average in background, move_tasks is also the key functions in load balance. We need consider the runnable load average in it in order to the apple to apple load comparison.

---
 kernel/sched/fair.c | 11 ++++++++++-
 1 file changed, 10 insertions(+), 1 deletion(-)
kernel/sched/fair.c +0 -0
index 1f9026e..bf4e0d4 100644
@@ -3966,6 +3966,15 @@ static unsigned long task_h_load(struct task_struct *p);
 
 static const unsigned int sched_nr_migrate_break = 32;
 
Quoted 11 lines

kernel/sched/fair.c static unsigned long task_h_load(struct task_struct *p); · line 3975

Quoted 7 lines
kernel/sched/fair.c +7 -0
+static unsigned long task_h_load_avg(struct task_struct *p)
+{
+       u32 period = p->se.avg.runnable_avg_period;
+       if (!period)
+               return 0;
+
+       return task_h_load(p) * p->se.avg.runnable_avg_sum / period;

How do you ensure that runnable_avg_period and runnable_avg_sum are coherent ? an update of the statistic can occur in the middle of your sequence.

Quoted 6 lines

Hi, Vincent

Don't we have the 'rq->lock' to protect it?

move_tasks() was invoked with double locked, for all the se on src and dst rq, no update should happen, isn't it?

you're right, the double lock protect against concurrent access my remark doesn't apply here

Regards,
Vincent

Quoted 36 lines

Regards,
Michael Wang

Quoted 15 lines

Vincent

Quoted 12 lines
kernel/sched/fair.c +3 -1
+}
+
 /*
  * move_tasks tries to move up to imbalance weighted load from busiest to
  * this_rq, as part of a balancing operation within domain "sd".
@@ -4001,7 +4010,7 @@ static int move_tasks(struct lb_env *env)
                if (throttled_lb_pair(task_group(p), env->src_cpu, env->dst_cpu))
                        goto next;
 
-               load = task_h_load(p);
+               load = task_h_load_avg(p);
 
Quoted 11 lines
Quoted 5 lines
kernel/sched/fair.c +0 -1
                if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
                        goto next;
--

1.7.12

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

author
#18 lore raw

PATCH v3 7/8 sched: consider runnable load average in effective_load

In reply to Alex Shi

effective_load calculates the load change as seen from the root_task_group. It needs to engage the runnable average of changed task.

Thanks for Morten Rasmussen's reminder of this.

---
 kernel/sched/fair.c | 27 ++++++++++++++++++++-------
 1 file changed, 20 insertions(+), 7 deletions(-)
kernel/sched/fair.c +20 -7
index bf4e0d4..fdb88de 100644
@@ -2976,7 +2976,8 @@ static void task_waking_fair(struct task_struct *p)
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 /*
- * effective_load() calculates the load change as seen from the root_task_group
+ * effective_load() calculates the runnable load average change as seen from
+ * the root_task_group
  *
  * Adding load to a group doesn't make a group heavier, but can cause movement
  * of group shares between cpus. Assuming the shares were perfectly aligned one
@@ -3024,6 +3025,9 @@ static void task_waking_fair(struct task_struct *p)
  * Therefore the effective change in loads on CPU 0 would be 5/56 (3/8 - 2/7)
  * times the weight of the group. The effect on CPU 1 would be -4/56 (4/8 -
  * 4/7) times the weight of the group.
+ *
+ * After get effective_load of the load moving, will engaged the sched entity's
+ * runnable avg.
  */
 static long effective_load(struct task_group *tg, int cpu, long wl, long wg)
 {
@@ -3098,6 +3102,7 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	struct task_group *tg;
 	unsigned long weight;
 	int balanced;
+	int runnable_avg;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
@@ -3113,13 +3118,19 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	if (sync) {
 		tg = task_group(current);
 		weight = current->se.load.weight;
+		runnable_avg = current->se.avg.runnable_avg_sum * NICE_0_LOAD
+				/ (current->se.avg.runnable_avg_period + 1);
 
-		this_load += effective_load(tg, this_cpu, -weight, -weight);
-		load += effective_load(tg, prev_cpu, 0, -weight);
+		this_load += effective_load(tg, this_cpu, -weight, -weight)
+				* runnable_avg >> NICE_0_SHIFT;
+		load += effective_load(tg, prev_cpu, 0, -weight)
+				* runnable_avg >> NICE_0_SHIFT;
 	}
 
 	tg = task_group(p);
 	weight = p->se.load.weight;
+	runnable_avg = p->se.avg.runnable_avg_sum * NICE_0_LOAD
+				/ (p->se.avg.runnable_avg_period + 1);
 
 	/*
 	 * In low-load situations, where prev_cpu is idle and this_cpu is idle
@@ -3131,16 +3142,18 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	 * task to be woken on this_cpu.
 	 */
 	if (this_load > 0) {
-		s64 this_eff_load, prev_eff_load;
+		s64 this_eff_load, prev_eff_load, tmp_eff_load;
 
 		this_eff_load = 100;
 		this_eff_load *= power_of(prev_cpu);
-		this_eff_load *= this_load +
-			effective_load(tg, this_cpu, weight, weight);
+		tmp_eff_load = effective_load(tg, this_cpu, weight, weight)
+				* runnable_avg >> NICE_0_SHIFT;
+		this_eff_load *= this_load + tmp_eff_load;
 
 		prev_eff_load = 100 + (sd->imbalance_pct - 100) / 2;
 		prev_eff_load *= power_of(this_cpu);
-		prev_eff_load *= load + effective_load(tg, prev_cpu, 0, weight);
+		prev_eff_load *= load + (effective_load(tg, prev_cpu, 0, weight)
+						* runnable_avg >> NICE_0_SHIFT);
 
 		balanced = this_eff_load <= prev_eff_load;
 	} else
Signature · 1 line
1.7.12
author
#19 lore raw

PATCH v3 8/8 sched: use instant load for burst wake up

In reply to Alex Shi

If many tasks sleep long time, their runnable load are zero. And if they are waked up bursty, too light runnable load causes big imbalance among CPU. So such benchmark, like aim9 drop 5~7%.

With this patch the losing is covered, and even is slight better.

---
 kernel/sched/fair.c | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)
kernel/sched/fair.c +16 -2
index fdb88de..c2f6e4e 100644
@@ -3103,12 +3103,26 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst_prev = 0, burst_this = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst_this = 1;
+	if (cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst_prev = 1;
+
+	/* use instant load on bursty waking up cpu */
+	if (!burst_prev)
+		load = source_load(prev_cpu, idx);
+	else
+		load = cpu_rq(prev_cpu)->load.weight;
+	if (!burst_this)
+		this_load = target_load(this_cpu, idx);
+	else
+		this_load = cpu_rq(this_cpu)->load.weight;
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
Signature · 1 line
1.7.12
#20 lore raw
In reply to Alex Shi

On 04/02/2013 11:23 AM, Alex Shi wrote:
[snip]

Quoted 9 lines

[patch v3 1/8] Revert "sched: Introduce temporary FAIR_GROUP_SCHED [patch v3 2/8] sched: set initial value of runnable avg for new [patch v3 3/8] sched: only count runnable avg on cfs_rq's nr_running [patch v3 4/8] sched: update cpu load after task_tick. [patch v3 5/8] sched: compute runnable load avg in cpu_load and [patch v3 6/8] sched: consider runnable load average in move_tasks [patch v3 7/8] sched: consider runnable load average in [patch v3 8/8] sched: use instant load for burst wake up

I've tested the patch set on 12 cpu X86 box with 3.9.0-rc2, and pgbench show regression on high-end this time.

| db_size | clients |  tps  |   |  tps  |
+---------+---------+-------+   +-------+
| 22 MB   |       1 | 10662 |   | 10446 |
| 22 MB   |       2 | 21483 |   | 20887 |
| 22 MB   |       4 | 42046 |   | 41266 |
| 22 MB   |       8 | 55807 |   | 51987 |
| 22 MB   |      12 | 50768 |   | 50974 |
| 22 MB   |      16 | 49880 |   | 49510 |
| 22 MB   |      24 | 45904 |   | 42398 |
| 22 MB   |      32 | 43420 |   | 40995 |
| 7484 MB |       1 |  7965 |   |  7376 |
| 7484 MB |       2 | 19354 |   | 19149 |
| 7484 MB |       4 | 37552 |   | 37458 |
| 7484 MB |       8 | 48655 |   | 46618 |
| 7484 MB |      12 | 45778 |   | 45756 |
| 7484 MB |      16 | 45659 |   | 44911 |
| 7484 MB |      24 | 42192 |   | 37185 |	-11.87%
| 7484 MB |      32 | 36385 |   | 34447 |
| 15 GB   |       1 |  7677 |   |  7359 |
| 15 GB   |       2 | 19227 |   | 19049 |
| 15 GB   |       4 | 37335 |   | 36947 |
| 15 GB   |       8 | 48130 |   | 46898 |
| 15 GB   |      12 | 45393 |   | 43986 |
| 15 GB   |      16 | 45110 |   | 45719 |
| 15 GB   |      24 | 41415 |   | 36813 |	-11.11%
| 15 GB   |      32 | 35988 |   | 34025 |

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Regards,
Michael Wang

Quoted 6 lines

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

#21 lore raw
Quoted 42 lines · Michael Wang

On 04/02/2013 11:23 AM, Alex Shi wrote:
[snip]

Quoted 9 lines

[patch v3 1/8] Revert "sched: Introduce temporary FAIR_GROUP_SCHED [patch v3 2/8] sched: set initial value of runnable avg for new [patch v3 3/8] sched: only count runnable avg on cfs_rq's nr_running [patch v3 4/8] sched: update cpu load after task_tick. [patch v3 5/8] sched: compute runnable load avg in cpu_load and [patch v3 6/8] sched: consider runnable load average in move_tasks [patch v3 7/8] sched: consider runnable load average in [patch v3 8/8] sched: use instant load for burst wake up

I've tested the patch set on 12 cpu X86 box with 3.9.0-rc2, and pgbench show regression on high-end this time.

| db_size | clients |  tps  |   |  tps  |
+---------+---------+-------+   +-------+
| 22 MB   |       1 | 10662 |   | 10446 |
| 22 MB   |       2 | 21483 |   | 20887 |
| 22 MB   |       4 | 42046 |   | 41266 |
| 22 MB   |       8 | 55807 |   | 51987 |
| 22 MB   |      12 | 50768 |   | 50974 |
| 22 MB   |      16 | 49880 |   | 49510 |
| 22 MB   |      24 | 45904 |   | 42398 |
| 22 MB   |      32 | 43420 |   | 40995 |
| 7484 MB |       1 |  7965 |   |  7376 |
| 7484 MB |       2 | 19354 |   | 19149 |
| 7484 MB |       4 | 37552 |   | 37458 |
| 7484 MB |       8 | 48655 |   | 46618 |
| 7484 MB |      12 | 45778 |   | 45756 |
| 7484 MB |      16 | 45659 |   | 44911 |
| 7484 MB |      24 | 42192 |   | 37185 |	-11.87%
| 7484 MB |      32 | 36385 |   | 34447 |
| 15 GB   |       1 |  7677 |   |  7359 |
| 15 GB   |       2 | 19227 |   | 19049 |
| 15 GB   |       4 | 37335 |   | 36947 |
| 15 GB   |       8 | 48130 |   | 46898 |
| 15 GB   |      12 | 45393 |   | 43986 |
| 15 GB   |      16 | 45110 |   | 45719 |
| 15 GB   |      24 | 41415 |   | 36813 |	-11.11%
| 15 GB   |      32 | 35988 |   | 34025 |
Quoted 2 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

For grins, you could try running the whole thing SCHED_BATCH. (/me sees singing/dancing red herring whenever wake_affine() and pgbench appear in the same sentence;)

-Mike

#22 lore raw

On 04/02/2013 04:34 PM, Mike Galbraith wrote:
[snip]

Quoted 6 lines
Quoted 2 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

For grins, you could try running the whole thing SCHED_BATCH. (/me sees singing/dancing red herring whenever wake_affine() and pgbench appear in the same sentence;)

I saw the patch touched the wake_affine(), just interested on what will happen ;-)

The patch changed the overhead of wake_affine(), and also influence it's result, I used to think the later one may do some help to the pgbench...

Regards,
Michael Wang

Quoted 3 lines

-Mike

author
#23 lore raw
In reply to Michael Wang
Quoted 31 lines · Michael Wang
Quoted 1 line
Quoted 1 line

[patch v3 8/8] sched: use instant load for burst wake up

I've tested the patch set on 12 cpu X86 box with 3.9.0-rc2, and pgbench show regression on high-end this time.

| db_size | clients |  tps  |   |  tps  |
+---------+---------+-------+   +-------+
| 22 MB   |       1 | 10662 |   | 10446 |
| 22 MB   |       2 | 21483 |   | 20887 |
| 22 MB   |       4 | 42046 |   | 41266 |
| 22 MB   |       8 | 55807 |   | 51987 |
| 22 MB   |      12 | 50768 |   | 50974 |
| 22 MB   |      16 | 49880 |   | 49510 |
| 22 MB   |      24 | 45904 |   | 42398 |
| 22 MB   |      32 | 43420 |   | 40995 |
| 7484 MB |       1 |  7965 |   |  7376 |
| 7484 MB |       2 | 19354 |   | 19149 |
| 7484 MB |       4 | 37552 |   | 37458 |
| 7484 MB |       8 | 48655 |   | 46618 |
| 7484 MB |      12 | 45778 |   | 45756 |
| 7484 MB |      16 | 45659 |   | 44911 |
| 7484 MB |      24 | 42192 |   | 37185 |	-11.87%
| 7484 MB |      32 | 36385 |   | 34447 |
| 15 GB   |       1 |  7677 |   |  7359 |
| 15 GB   |       2 | 19227 |   | 19049 |
| 15 GB   |       4 | 37335 |   | 36947 |
| 15 GB   |       8 | 48130 |   | 46898 |
| 15 GB   |      12 | 45393 |   | 43986 |
| 15 GB   |      16 | 45110 |   | 45719 |
| 15 GB   |      24 | 41415 |   | 36813 |	-11.11%
| 15 GB   |      32 | 35988 |   | 34025 |
Quoted 2 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Thanks for testing. Could you like to remove the last patch and test it again? I want to know if the last patch has effect on pgbench.

Signature · 1 line
Thanks Alex
#24 lore raw
Quoted 1 line · Alex Shi

On 04/02/2013 03:23 PM, Michael Wang wrote:

[snip]

Quoted 6 lines
Quoted 3 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Thanks for testing. Could you like to remove the last patch and test it again? I want to know if the last patch has effect on pgbench.

Amazing, without the last one, pgbench show very good improvement, higher than 10ms throttle, lower than 100ms throttle, I need confirm this with a night-through testing.

I will look into those patches in detail later, I think it addressed part of the wake_affine() issue (make the decision more accurately), that's nice ;-)

Regards,
Michael Wang

Quoted 1 line
#25 lore raw
In reply to Alex Shi

On 04/02/2013 04:35 PM, Alex Shi wrote:
[snip]

Quoted 6 lines
Quoted 3 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Thanks for testing. Could you like to remove the last patch and test it again? I want to know if the last patch has effect on pgbench.

Done, here the results of pgbench without the last patch on my box:

| db_size | clients |  tps  |   |  tps  |
+---------+---------+-------+   +-------+
| 22 MB   |       1 | 10662 |   | 10679 |
| 22 MB   |       2 | 21483 |   | 21471 |
| 22 MB   |       4 | 42046 |   | 41957 |
| 22 MB   |       8 | 55807 |   | 55684 |
| 22 MB   |      12 | 50768 |   | 52074 |
| 22 MB   |      16 | 49880 |   | 52879 |
| 22 MB   |      24 | 45904 |   | 53406 |
| 22 MB   |      32 | 43420 |   | 54088 |	+24.57%
| 7484 MB |       1 |  7965 |   |  7725 |
| 7484 MB |       2 | 19354 |   | 19405 |
| 7484 MB |       4 | 37552 |   | 37246 |
| 7484 MB |       8 | 48655 |   | 50613 |
| 7484 MB |      12 | 45778 |   | 47639 |
| 7484 MB |      16 | 45659 |   | 48707 |
| 7484 MB |      24 | 42192 |   | 46469 |
| 7484 MB |      32 | 36385 |   | 46346 |	+27.38%
| 15 GB   |       1 |  7677 |   |  7727 |
| 15 GB   |       2 | 19227 |   | 19199 |
| 15 GB   |       4 | 37335 |   | 37372 |
| 15 GB   |       8 | 48130 |   | 50333 |
| 15 GB   |      12 | 45393 |   | 47590 |
| 15 GB   |      16 | 45110 |   | 48091 |
| 15 GB   |      24 | 41415 |   | 47415 |
| 15 GB   |      32 | 35988 |   | 45749 |	+27.12%

Very nice improvement, I'd like to test it with the wake-affine throttle patch later, let's see what will happen ;-)

Any idea on why the last one caused the regression?

Regards,
Michael Wang

Quoted 1 line
author
#26 lore raw
Quoted 8 lines · Michael Wang
| 15 GB   |      16 | 45110 |   | 48091 |
| 15 GB   |      24 | 41415 |   | 47415 |
| 15 GB   |      32 | 35988 |   | 45749 |	+27.12%

Very nice improvement, I'd like to test it with the wake-affine throttle patch later, let's see what will happen ;-)

Any idea on why the last one caused the regression?

you can change the burst threshold: sysctl_sched_migration_cost, to see what's happen with different value. create a similar knob and tune it. +
+ if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost)
+ burst_this = 1;
+ if (cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+ burst_prev = 1;
+

BTW, what's the job thread behaviour of pgbench, guess it has lots of wakeup. what's the work and sleep ratio of pgbench?

Signature · 1 line
Thanks Alex
#27 lore raw
Quoted 14 lines · Alex Shi
Quoted 8 lines · Michael Wang
| 15 GB   |      16 | 45110 |   | 48091 |
| 15 GB   |      24 | 41415 |   | 47415 |
| 15 GB   |      32 | 35988 |   | 45749 |	+27.12%

Very nice improvement, I'd like to test it with the wake-affine throttle patch later, let's see what will happen ;-)

Any idea on why the last one caused the regression?

you can change the burst threshold: sysctl_sched_migration_cost, to see what's happen with different value. create a similar knob and tune it.

Review

Quoted 6 lines
(quoted diff) +6 -0
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst_this = 1;
+	if (cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst_prev = 1;
+

This changing the rate of adopt cpu_rq(cpu)->load.weight, correct?

So if rq is busy, cpu_rq(cpu)->load.weight is capable enough to stand for the load status of rq? what's the really idea here?

Quoted 2 lines

BTW, what's the job thread behaviour of pgbench, guess it has lots of wakeup. what's the work and sleep ratio of pgbench?

I won't do the summary unless I reviewed it's code :) what I know is, it's a database benchmark, with several process operating database, see below one for details:

pgbench is a simple program for running benchmark tests on PostgreSQL. It runs the same sequence of SQL commands over and over, possibly in multiple concurrent database sessions, and then calculates the average transaction rate (transactions per second). By default, pgbench tests a scenario that is loosely based on TPC-B, involving five SELECT, UPDATE, and INSERT commands per transaction. However, it is easy to test other cases by writing your own transaction script files.

Regards,
Michael Wang

Quoted 1 line
author
#28 lore raw
Quoted 24 lines · Michael Wang
Quoted 14 lines · Alex Shi
Quoted 8 lines · Michael Wang
| 15 GB   |      16 | 45110 |   | 48091 |
| 15 GB   |      24 | 41415 |   | 47415 |
| 15 GB   |      32 | 35988 |   | 45749 |	+27.12%

Very nice improvement, I'd like to test it with the wake-affine throttle patch later, let's see what will happen ;-)

Any idea on why the last one caused the regression?

you can change the burst threshold: sysctl_sched_migration_cost, to see what's happen with different value. create a similar knob and tune it.

Review

Quoted 6 lines
(quoted diff) +6 -0
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst_this = 1;
+	if (cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst_prev = 1;
+

This changing the rate of adopt cpu_rq(cpu)->load.weight, correct?

Quoted 2 lines

So if rq is busy, cpu_rq(cpu)->load.weight is capable enough to stand for the load status of rq? what's the really idea here?

This patch try to resolved the aim7 liked benchmark regression. If many tasks sleep long time, their runnable load are zero. And then if they are waked up bursty, too light runnable load causes big imbalance in
select_task_rq. So such benchmark, like aim9 drop 5~7%.

this patch try to detect the burst, if so, it use load weight directly not
zero runnable load avg to avoid the imbalance.

but the patch may cause some unfairness if this/prev cpu are not burst at same time. So could like try the following patch?

Quoted 1 line

From 4722a7567dccfb19aa5afbb49982ffb6d65e6ae5 Mon Sep 17 00:00:00 2001

From: Alex Shi <[email protected]>
Date: Tue, 2 Apr 2013 10:27:45 +0800
Subject: [PATCH] sched: use instant load for burst wake up

If many tasks sleep long time, their runnable load are zero. And if they are waked up bursty, too light runnable load causes big imbalance among CPU. So such benchmark, like aim9 drop 5~7%.

With this patch the losing is covered, and even is slight better.

---
 kernel/sched/fair.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
kernel/sched/fair.c +14 -2
index dbaa8ca..25ac437 100644
@@ -3103,12 +3103,24 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
Signature · 1 line
1.7.12
#29 lore raw

On 04/03/2013 12:28 PM, Alex Shi wrote:
[snip]

Quoted 3 lines

but the patch may cause some unfairness if this/prev cpu are not burst at same time. So could like try the following patch?

I will try it later, some doubt below :)

[snip]

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3122

Quoted 12 lines
kernel/sched/fair.c +12 -0
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;

Ok, my understanding is, we want pull if 'prev_cpu' is burst, and don't want pull if 'this_cpu' is burst, correct?

And we do this by guess the load higher or lower, is that right?

And I think target_load() is capable enough to choose the higher load, if 'cpu_rq(cpu)->load.weight' is really higher, the results will be the same.

So what about this:

	/* prefer higher load if burst */
	load = burst_prev ?
		target_load(prev_cpu, idx) : source_load(prev_cpu, idx);

	this_load = target_load(this_cpu, idx);

Regards,
Michael Wang

Quoted 5 lines
kernel/sched/fair.c +1 -0
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
#30 lore raw
Quoted 27 lines · Michael Wang

On 04/03/2013 12:28 PM, Alex Shi wrote:
[snip]

Quoted 3 lines

but the patch may cause some unfairness if this/prev cpu are not burst at same time. So could like try the following patch?

I will try it later, some doubt below :)

[snip]

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3122

Quoted 12 lines
kernel/sched/fair.c +12 -0
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;

Ok, my understanding is, we want pull if 'prev_cpu' is burst, and don't want pull if 'this_cpu' is burst, correct?

And we do this by guess the load higher or lower, is that right?

Quoted 8 lines

And I think target_load() is capable enough to choose the higher load, if 'cpu_rq(cpu)->load.weight' is really higher, the results will be the same.

So what about this:

	/* prefer higher load if burst */
	load = burst_prev ?

And this check could also be:

	load = burst_prev && !burst_this ?

if we don't prefer the pull when this_cpu also bursted.

Regards,
Michael Wang

Quoted 13 lines
		target_load(prev_cpu, idx) : source_load(prev_cpu, idx);

	this_load = target_load(this_cpu, idx);

Regards,
Michael Wang

Quoted 5 lines
kernel/sched/fair.c +1 -0
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
author
#31 lore raw
In reply to Michael Wang
Quoted 9 lines · Michael Wang

On 04/03/2013 12:28 PM, Alex Shi wrote:
[snip]

Quoted 3 lines

but the patch may cause some unfairness if this/prev cpu are not burst at same time. So could like try the following patch?

I will try it later, some doubt below :)

[snip]

Quoted 15 lines

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3122

Quoted 12 lines
kernel/sched/fair.c +12 -0
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;

Ok, my understanding is, we want pull if 'prev_cpu' is burst, and don't want pull if 'this_cpu' is burst, correct?

Nope, as my thought, a burst cpu doesn't mean it has heavy load than others, so we still need to compare their load on the same condition.

Quoted 2 lines

And we do this by guess the load higher or lower, is that right?

ditto.

Quoted 5 lines

And I think target_load() is capable enough to choose the higher load, if 'cpu_rq(cpu)->load.weight' is really higher, the results will be the same.

Quoted 7 lines

So what about this:

	/* prefer higher load if burst */
	load = burst_prev ?
		target_load(prev_cpu, idx) : source_load(prev_cpu, idx);

	this_load = target_load(this_cpu, idx);

here, the idx is zero, so source_load and target load is same.

Quoted 10 lines

Regards,
Michael Wang

Quoted 5 lines
kernel/sched/fair.c +1 -0
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
Signature · 1 line
Thanks Alex
#32 lore raw
In reply to Alex Shi
Quoted 3 lines · Alex Shi
Quoted 2 lines · Michael Wang
Quoted 1 line · Alex Shi

On 04/03/2013 10:46 AM, Michael Wang wrote:

[snip]

Quoted 7 lines

From 4722a7567dccfb19aa5afbb49982ffb6d65e6ae5 Mon Sep 17 00:00:00 2001
From: Alex Shi <[email protected]>
Date: Tue, 2 Apr 2013 10:27:45 +0800
Subject: [PATCH] sched: use instant load for burst wake up

Quoted 5 lines

If many tasks sleep long time, their runnable load are zero. And if they are waked up bursty, too light runnable load causes big imbalance among CPU. So such benchmark, like aim9 drop 5~7%.

With this patch the losing is covered, and even is slight better.

A fast test show the improvement disappear and the regression back again...after applied this one as the 8th patch, it doesn't works.

Regards,
Michael Wang

Quoted 38 lines
---
 kernel/sched/fair.c | 16 ++++++++++++++--
 1 file changed, 14 insertions(+), 2 deletions(-)
kernel/sched/fair.c +14 -2
index dbaa8ca..25ac437 100644
@@ -3103,12 +3103,24 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
author
#33 lore raw
Quoted 8 lines · Michael Wang
Quoted 6 lines
Quoted 6 lines

If many tasks sleep long time, their runnable load are zero. And if they are waked up bursty, too light runnable load causes big imbalance among CPU. So such benchmark, like aim9 drop 5~7%.

With this patch the losing is covered, and even is slight better.

A fast test show the improvement disappear and the regression back again...after applied this one as the 8th patch, it doesn't works.

It always is good for on benchmark and bad for another. :)

the following patch include the renamed knob, and you can tune it under /proc/sys/kernel/... to see detailed impact degree.

Quoted 1 line

From e540b31b99c887d5a0c5338f7b1f224972b98932 Mon Sep 17 00:00:00 2001

From: Alex Shi <[email protected]>
Date: Tue, 2 Apr 2013 10:27:45 +0800
Subject: [PATCH] sched: use instant load for burst wake up

If many tasks sleep long time, their runnable load are zero. And if they are waked up bursty, too light runnable load causes big imbalance among CPU. So such benchmark, like aim9 drop 5~7%.

rq->avg_idle is 'to used to accommodate bursty loads in a dirt simple dirt cheap manner' -- Mike Galbraith.

With this cheap and smart bursty indicator, we can find the wake up burst, and just use nr_running as instant utilization only.

The 'sysctl_sched_burst_threshold' used for wakeup burst.

With this patch the losing is covered, and even is slight better.

---
 include/linux/sched/sysctl.h |  1 +
 kernel/sched/fair.c          | 17 +++++++++++++++--
 kernel/sysctl.c              |  7 +++++++
 3 files changed, 23 insertions(+), 2 deletions(-)
include/linux/sched/sysctl.h +1 -0
index bf8086b..a3c3d43 100644
@@ -53,6 +53,7 @@ extern unsigned int sysctl_numa_balancing_settle_count;
 
 #ifdef CONFIG_SCHED_DEBUG
 extern unsigned int sysctl_sched_migration_cost;
+extern unsigned int sysctl_sched_burst_threshold;
 extern unsigned int sysctl_sched_nr_migrate;
 extern unsigned int sysctl_sched_time_avg;
 extern unsigned int sysctl_timer_migration;
kernel/sched/fair.c +15 -2
index dbaa8ca..f41ca67 100644
@@ -91,6 +91,7 @@ unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
 
 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
+const_debug unsigned int sysctl_sched_burst_threshold = 1000000UL;
 
 /*
  * The exponential sliding  window over which load is averaged for shares
@@ -3103,12 +3104,24 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
kernel/sysctl.c +7 -0
index afc1dc6..1f23457 100644
@@ -327,6 +327,13 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 	{
+		.procname	= "sched_burst_threshold_ns",
+		.data		= &sysctl_sched_burst_threshold,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
 		.procname	= "sched_nr_migrate",
 		.data		= &sysctl_sched_nr_migrate,
 		.maxlen		= sizeof(unsigned int),
Signature · 5 lines
1.7.12


-- 
Thanks Alex
#34 lore raw
Quoted 11 lines · Alex Shi
Quoted 8 lines · Michael Wang
Quoted 6 lines
Quoted 6 lines

If many tasks sleep long time, their runnable load are zero. And if they are waked up bursty, too light runnable load causes big imbalance among CPU. So such benchmark, like aim9 drop 5~7%.

With this patch the losing is covered, and even is slight better.

A fast test show the improvement disappear and the regression back again...after applied this one as the 8th patch, it doesn't works.

It always is good for on benchmark and bad for another. :)

That's right :)

Quoted 3 lines

the following patch include the renamed knob, and you can tune it under /proc/sys/kernel/... to see detailed impact degree.

Could I make the conclusion that the improvement on pgbench was caused by the new weighted_cpuload()?

The burst branch seems to just adopt the load in old world, if reduce the rate to enter that branch could regain the benefit, then I could confirm my supposition.

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3114

Quoted 3 lines
kernel/sched/fair.c +2 -0
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)

It should be 'sysctl_sched_burst_threshold' here, isn't it? anyway, I will take a try with different rate.

Regards,
Michael Wang

Quoted 32 lines
kernel/sched/fair.c +10 -0
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
kernel/sysctl.c +7 -0
index afc1dc6..1f23457 100644
@@ -327,6 +327,13 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 	{
+		.procname	= "sched_burst_threshold_ns",
+		.data		= &sysctl_sched_burst_threshold,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
 		.procname	= "sched_nr_migrate",
 		.data		= &sysctl_sched_nr_migrate,
 		.maxlen		= sizeof(unsigned int),
author
#35 lore raw
Quoted 4 lines · Michael Wang
Quoted 2 lines
Quoted 2 lines

the following patch include the renamed knob, and you can tune it under /proc/sys/kernel/... to see detailed impact degree.

Could I make the conclusion that the improvement on pgbench was caused by the new weighted_cpuload()?

guess too.

Quoted 10 lines

The burst branch seems to just adopt the load in old world, if reduce the rate to enter that branch could regain the benefit, then I could confirm my supposition.

Quoted 3 lines

kernel/sched/fair.c static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync) · line 3114

Quoted 3 lines
kernel/sched/fair.c +2 -0
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_migration_cost ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_migration_cost)

It should be 'sysctl_sched_burst_threshold' here, isn't it? anyway, I will take a try with different rate.

Ops, sth wrong in my git operation.

Signature · 1 line
Thanks Alex
author
#36 lore raw
In reply to Michael Wang
Quoted 7 lines · Michael Wang
| 15 GB   |      12 | 45393 |   | 43986 |
| 15 GB   |      16 | 45110 |   | 45719 |
| 15 GB   |      24 | 41415 |   | 36813 |	-11.11%
| 15 GB   |      32 | 35988 |   | 34025 |

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Michael:
I changed the threshold to 0.1ms it has same effect on aim7. So could you try the following on pgbench?

include/linux/sched/sysctl.h +1 -0
index bf8086b..a3c3d43 100644
@@ -53,6 +53,7 @@ extern unsigned int sysctl_numa_balancing_settle_count;
 
 #ifdef CONFIG_SCHED_DEBUG
 extern unsigned int sysctl_sched_migration_cost;
+extern unsigned int sysctl_sched_burst_threshold;
 extern unsigned int sysctl_sched_nr_migrate;
 extern unsigned int sysctl_sched_time_avg;
 extern unsigned int sysctl_timer_migration;
kernel/sched/fair.c +15 -2
index dbaa8ca..dd5a324 100644
@@ -91,6 +91,7 @@ unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
 
 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
+const_debug unsigned int sysctl_sched_burst_threshold = 100000UL;
 
 /*
  * The exponential sliding  window over which load is averaged for shares
@@ -3103,12 +3104,24 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_burst_threshold ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_burst_threshold)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
kernel/sysctl.c +7 -0
index afc1dc6..1f23457 100644
@@ -327,6 +327,13 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 	{
+		.procname	= "sched_burst_threshold_ns",
+		.data		= &sysctl_sched_burst_threshold,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
 		.procname	= "sched_nr_migrate",
 		.data		= &sysctl_sched_nr_migrate,
 		.maxlen		= sizeof(unsigned int),
Signature · 1 line
Thanks Alex
#37 lore raw
Quoted 6 lines · Alex Shi
Quoted 5 lines · Michael Wang
| 15 GB   |      12 | 45393 |   | 43986 |
| 15 GB   |      16 | 45110 |   | 45719 |
| 15 GB   |      24 | 41415 |   | 36813 |	-11.11%
| 15 GB   |      32 | 35988 |   | 34025 |
Quoted 6 lines
Quoted 2 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Michael:
I changed the threshold to 0.1ms it has same effect on aim7. So could you try the following on pgbench?

Hi, Alex

I've done some rough test and the change point should in 60000~120000, I'm currently running a auto test with value 500000, 250000, 120000, 60000, 30000, 15000, 6000, 3000, 1500, it will take some time to finish the test, and we will gain detail info for analysis.

BTW, you know we have festival in China, so the report may be delayed, forgive me on that ;-)

Regards,
Michael Wang

Quoted 72 lines
include/linux/sched/sysctl.h +1 -0
index bf8086b..a3c3d43 100644
@@ -53,6 +53,7 @@ extern unsigned int sysctl_numa_balancing_settle_count;
 
 #ifdef CONFIG_SCHED_DEBUG
 extern unsigned int sysctl_sched_migration_cost;
+extern unsigned int sysctl_sched_burst_threshold;
 extern unsigned int sysctl_sched_nr_migrate;
 extern unsigned int sysctl_sched_time_avg;
 extern unsigned int sysctl_timer_migration;
kernel/sched/fair.c +15 -2
index dbaa8ca..dd5a324 100644
@@ -91,6 +91,7 @@ unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
 
 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
+const_debug unsigned int sysctl_sched_burst_threshold = 100000UL;
 
 /*
  * The exponential sliding  window over which load is averaged for shares
@@ -3103,12 +3104,24 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_burst_threshold ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_burst_threshold)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
kernel/sysctl.c +7 -0
index afc1dc6..1f23457 100644
@@ -327,6 +327,13 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 	{
+		.procname	= "sched_burst_threshold_ns",
+		.data		= &sysctl_sched_burst_threshold,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
 		.procname	= "sched_nr_migrate",
 		.data		= &sysctl_sched_nr_migrate,
 		.maxlen		= sizeof(unsigned int),
author
#38 lore raw
Quoted 7 lines · Michael Wang
Quoted 4 lines
Quoted 4 lines

Michael:
I changed the threshold to 0.1ms it has same effect on aim7. So could you try the following on pgbench?

Hi, Alex

I've done some rough test and the change point should in 60000~120000,

Sounds good.

Quoted 3 lines

I'm currently running a auto test with value 500000, 250000, 120000, 60000, 30000, 15000, 6000, 3000, 1500, it will take some time to finish the test, and we will gain detail info for analysis.

Thanks

Quoted 3 lines

BTW, you know we have festival in China, so the report may be delayed, forgive me on that ;-)

That's all right. I locate in China too. :)

Signature · 2 lines
Thanks
    Alex
#39 lore raw
In reply to Alex Shi
Quoted 6 lines · Alex Shi
Quoted 5 lines · Michael Wang
| 15 GB   |      12 | 45393 |   | 43986 |
| 15 GB   |      16 | 45110 |   | 45719 |
| 15 GB   |      24 | 41415 |   | 36813 |	-11.11%
| 15 GB   |      32 | 35988 |   | 34025 |
Quoted 6 lines
Quoted 2 lines

The reason may caused by wake_affine()'s higher overhead, and pgbench is really sensitive to this stuff...

Michael:
I changed the threshold to 0.1ms it has same effect on aim7. So could you try the following on pgbench?

Here the results of different threshold, too many data so I just list 22 MB 32 clients item:

threshold(us) tps

base 43420
500 40694
250 40591
120 41468 -4.50%
60 47785 +10.05%
30 51389
15 52844
6 54539
3 52674
1.5 52885

Since 120~60us seems to be the inflection, I made more test in this range:

threshold(us) tps
base 43420
110 41772
100 42246
90 43471 0%
80 44920
70 46341

According to these data, 90us == 90000 is the inflection point on my box for 22 MB 32 clients item, other test items show different float, so 80~90us is the conclusion.

Now the concern is how to deal with this issue, the results may changed on different deployment, static value is not acceptable, so we need another new knob here?

I'm not sure whether you have take a look at the wake-affine throttle patch I sent weeks ago, it's purpose is throttle the wake-affine to not work too frequently.

And since the aim problem is caused by the imbalance which is the side-effect of frequently succeed wake-affine, may be the throttle patch could help to address that issue too, if it is, then we only need to add one new knob.

BTW, the benefit your patch set bring is not conflict with wake-affine throttle patch, which means with your patch set, the 1ms throttle will also show 25% improvement now (used to be <5%), and it also increase the maximum benefit from 40% to 45% on my box ;-)

Regards,
Michael Wang

Quoted 72 lines
include/linux/sched/sysctl.h +1 -0
index bf8086b..a3c3d43 100644
@@ -53,6 +53,7 @@ extern unsigned int sysctl_numa_balancing_settle_count;
 
 #ifdef CONFIG_SCHED_DEBUG
 extern unsigned int sysctl_sched_migration_cost;
+extern unsigned int sysctl_sched_burst_threshold;
 extern unsigned int sysctl_sched_nr_migrate;
 extern unsigned int sysctl_sched_time_avg;
 extern unsigned int sysctl_timer_migration;
kernel/sched/fair.c +15 -2
index dbaa8ca..dd5a324 100644
@@ -91,6 +91,7 @@ unsigned int sysctl_sched_wakeup_granularity = 1000000UL;
 unsigned int normalized_sysctl_sched_wakeup_granularity = 1000000UL;
 
 const_debug unsigned int sysctl_sched_migration_cost = 500000UL;
+const_debug unsigned int sysctl_sched_burst_threshold = 100000UL;
 
 /*
  * The exponential sliding  window over which load is averaged for shares
@@ -3103,12 +3104,24 @@ static int wake_affine(struct sched_domain *sd, struct task_struct *p, int sync)
 	unsigned long weight;
 	int balanced;
 	int runnable_avg;
+	int burst = 0;
 
 	idx	  = sd->wake_idx;
 	this_cpu  = smp_processor_id();
 	prev_cpu  = task_cpu(p);
-	load	  = source_load(prev_cpu, idx);
-	this_load = target_load(this_cpu, idx);
+
+	if (cpu_rq(this_cpu)->avg_idle < sysctl_sched_burst_threshold ||
+		cpu_rq(prev_cpu)->avg_idle < sysctl_sched_burst_threshold)
+		burst= 1;
+
+	/* use instant load for bursty waking up */
+	if (!burst) {
+		load = source_load(prev_cpu, idx);
+		this_load = target_load(this_cpu, idx);
+	} else {
+		load = cpu_rq(prev_cpu)->load.weight;
+		this_load = cpu_rq(this_cpu)->load.weight;
+	}
 
 	/*
 	 * If sync wakeup then subtract the (maximum possible)
kernel/sysctl.c +7 -0
index afc1dc6..1f23457 100644
@@ -327,6 +327,13 @@ static struct ctl_table kern_table[] = {
 		.proc_handler	= proc_dointvec,
 	},
 	{
+		.procname	= "sched_burst_threshold_ns",
+		.data		= &sysctl_sched_burst_threshold,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= proc_dointvec,
+	},
+	{
 		.procname	= "sched_nr_migrate",
 		.data		= &sysctl_sched_nr_migrate,
 		.maxlen		= sizeof(unsigned int),
author
#40 lore raw
Quoted 4 lines

According to these data, 90us == 90000 is the inflection point on my box for 22 MB 32 clients item, other test items show different float, so 80~90us is the conclusion.

Thanks a lot for the testing!

Quoted 8 lines

Now the concern is how to deal with this issue, the results may changed on different deployment, static value is not acceptable, so we need another new knob here?

I'm not sure whether you have take a look at the wake-affine throttle patch I sent weeks ago, it's purpose is throttle the wake-affine to not work too frequently.

Yes. In the patch your directly set the target cpu to this_cpu when no wake_affine. Maybe this is the key points, not the wake_affine cost give the improvement. Basically I agree with this. but if so, it is a bit blind. but, but, The interesting point is the blind target cpu setting has the best performance in our current testing. :)

Quoted 5 lines

And since the aim problem is caused by the imbalance which is the side-effect of frequently succeed wake-affine, may be the throttle patch could help to address that issue too, if it is, then we only need to add one new knob.

As to the aim7 problem, I need apologise to you all!
The aim7 regression exist with the patch v2 that base on 3.8 kernel, not with this v3 version base on 3.9.

After the lock-stealing RW sem patch introduced in 3.9 kernel, the aim7 has recovered the cpu task imbalance, So on balanced 3.9 kernel, this v3 version won't bring extra imbalance on aim7. no clear regression on aim7, no extra imbalance on aim7.

So, I referenced a old testing result without double confirming, tried to resolve a disappeared problem. I am sorry and applogize to you all.

And this burst patch doesn't need on 3.9 kernel. Patch 1,2,4,5,6,7 are enough and valid.

Signature · 1 line
Thanks Alex
#41 lore raw
Quoted 15 lines · Alex Shi
Quoted 4 lines

According to these data, 90us == 90000 is the inflection point on my box for 22 MB 32 clients item, other test items show different float, so 80~90us is the conclusion.

Thanks a lot for the testing!

Quoted 8 lines

Now the concern is how to deal with this issue, the results may changed on different deployment, static value is not acceptable, so we need another new knob here?

I'm not sure whether you have take a look at the wake-affine throttle patch I sent weeks ago, it's purpose is throttle the wake-affine to not work too frequently.

Quoted 5 lines

Yes. In the patch your directly set the target cpu to this_cpu when no wake_affine. Maybe this is the key points, not the wake_affine cost give the improvement. Basically I agree with this. but if so, it is a bit blind. but, but, The interesting point is the blind target cpu setting has the best performance in our current testing. :)

IMHO, the wake-affine stuff is blindly at all, so actually this throttle knob should be added at the first time along with the stuff, what we need to do now is just add that missed knob.

I do believe when first time the wake-affine stuff was added, there is no regression, but since the world changed, the regression start to be accumulated and become so big, we could not ignore it now.

The throttle idea is just try to provide a way to stop the blind judgement, easy and efficient :)

Quoted 11 lines
Quoted 6 lines

And since the aim problem is caused by the imbalance which is the side-effect of frequently succeed wake-affine, may be the throttle patch could help to address that issue too, if it is, then we only need to add one new knob.

As to the aim7 problem, I need apologise to you all!
The aim7 regression exist with the patch v2 that base on 3.8 kernel, not with this v3 version base on 3.9.

Quoted 7 lines

After the lock-stealing RW sem patch introduced in 3.9 kernel, the aim7 has recovered the cpu task imbalance, So on balanced 3.9 kernel, this v3 version won't bring extra imbalance on aim7. no clear regression on aim7, no extra imbalance on aim7.

So, I referenced a old testing result without double confirming, tried to resolve a disappeared problem. I am sorry and applogize to you all.

That's all right, and it's good to know we could ignore the last patch, I really like the benefit 1~7 bring, combined with the throttle idea, pgbench was satisfied a lot ;-)

Regards,
Michael Wang

Quoted 4 lines

And this burst patch doesn't need on 3.9 kernel. Patch 1,2,4,5,6,7 are enough and valid.

author
#42 lore raw
In reply to Alex Shi
Quoted 10 lines · Alex Shi

This version resolved the aim7 liked benchmark issue by patch 8th. Thanks for MikeG's avg_idle that is a good bursty wakeup indicator.

The first 3 patches were also include in my power aware scheduling patchset.

Morten, you can rebase your patch on this new version that bases on latest Linus tree. :)

a git tree for this patchset:
https://github.com/alexshi/power-scheduling.git runnablelb

I removed the 3rd and 8th patches, left 1,2,4,5,6,7. and updated them in above git tree.

I tested the kbuild, specjbb2005, aim9, fileio-cfq, hackbench and dbench. on my NHM EP and 2 sockets SNB EP box. hackbench increased 3~5% on both machines. kbuild has suspicious 2% increase. others has no clear change.

Any more comments or concern about this patch?

Quoted 13 lines

Thanks
Alex

[patch v3 1/8] Revert "sched: Introduce temporary FAIR_GROUP_SCHED [patch v3 2/8] sched: set initial value of runnable avg for new [patch v3 3/8] sched: only count runnable avg on cfs_rq's nr_running [patch v3 4/8] sched: update cpu load after task_tick. [patch v3 5/8] sched: compute runnable load avg in cpu_load and [patch v3 6/8] sched: consider runnable load average in move_tasks [patch v3 7/8] sched: consider runnable load average in [patch v3 8/8] sched: use instant load for burst wake up

Signature · 1 line
Thanks Alex
author
#43 lore raw
Quoted 11 lines · Alex Shi
Quoted 10 lines · Alex Shi
Quoted 10 lines

This version resolved the aim7 liked benchmark issue by patch 8th. Thanks for MikeG's avg_idle that is a good bursty wakeup indicator.

The first 3 patches were also include in my power aware scheduling patchset.

Morten, you can rebase your patch on this new version that bases on latest Linus tree. :)

a git tree for this patchset:
https://github.com/alexshi/power-scheduling.git runnablelb

Quoted 7 lines

I removed the 3rd and 8th patches, left 1,2,4,5,6,7. and updated them in above git tree.

I tested the kbuild, specjbb2005, aim9, fileio-cfq, hackbench and dbench. on my NHM EP and 2 sockets SNB EP box. hackbench increased 3~5% on both machines. kbuild has suspicious 2% increase. others has no clear change.

This patchset has tested by ARM guys and Michael. None of regression found.

Peter, could you like to give some comments?

Signature · 2 lines
Thanks
    Alex