[PATCH 0/2] prefer wakers -v2

[PATCH 0/2] prefer wakers -v2

[Peter Zijlstra]

OK, so lets try this again...
-- 

[PATCH 1/2] sched: introduce avg_wakeup

[Peter Zijlstra]

[-- Attachment #1: wakeup-preempt-stats.patch --]
[-- Type: text/plain, Size: 3268 bytes --]

Introduce a new avg_wakeup statistic.

avg_wakeup is a measure of how frequently a task wakes up other tasks, it
represents the average time between wakeups, with a limit of avg_runtime
for when it doesn't wake up anybody.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Mike Galbraith <efault@gmx.de>
---
 include/linux/sched.h |    3 +++
 kernel/sched.c        |   34 ++++++++++++++++++++++++++++------
 kernel/sched_debug.c  |    1 +
 3 files changed, 32 insertions(+), 6 deletions(-)

Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -1725,6 +1725,9 @@ static void update_avg(u64 *avg, u64 sam
 
 static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)
 {
+	if (wakeup)
+		p->se.start_runtime = p->se.sum_exec_runtime;
+
 	sched_info_queued(p);
 	p->sched_class->enqueue_task(rq, p, wakeup);
 	p->se.on_rq = 1;
@@ -1732,10 +1735,15 @@ static void enqueue_task(struct rq *rq, 
 
 static void dequeue_task(struct rq *rq, struct task_struct *p, int sleep)
 {
-	if (sleep && p->se.last_wakeup) {
-		update_avg(&p->se.avg_overlap,
-			   p->se.sum_exec_runtime - p->se.last_wakeup);
-		p->se.last_wakeup = 0;
+	if (sleep) {
+		if (p->se.last_wakeup) {
+			update_avg(&p->se.avg_overlap,
+				p->se.sum_exec_runtime - p->se.last_wakeup);
+			p->se.last_wakeup = 0;
+		} else {
+			update_avg(&p->se.avg_wakeup,
+				sysctl_sched_wakeup_granularity);
+		}
 	}
 
 	sched_info_dequeued(p);
@@ -2403,6 +2411,20 @@ out_activate:
 	activate_task(rq, p, 1);
 	success = 1;
 
+	/*
+	 * Only attribute actual wakeups done by this task.
+	 */
+	if (!in_interrupt()) {
+		u64 sample = se->sum_exec_runtime;
+		if (se->last_wakeup)
+			sample -= se->last_wakeup;
+		else
+			sample -= se->start_runtime;
+		update_avg(&se->avg_wakeup, sample);
+
+		current->se.last_wakeup = current->se.sum_exec_runtime;
+	}
+
 out_running:
 	trace_sched_wakeup(rq, p, success);
 	check_preempt_curr(rq, p, sync);
@@ -2413,8 +2435,6 @@ out_running:
 		p->sched_class->task_wake_up(rq, p);
 #endif
 out:
-	current->se.last_wakeup = current->se.sum_exec_runtime;
-
 	task_rq_unlock(rq, &flags);
 
 	return success;
@@ -2445,6 +2465,8 @@ static void __sched_fork(struct task_str
 	p->se.nr_migrations		= 0;
 	p->se.last_wakeup		= 0;
 	p->se.avg_overlap		= 0;
+	p->se.start_runtime		= 0;
+	p->se.avg_wakeup		= sysctl_sched_wakeup_granularity;
 
 #ifdef CONFIG_SCHEDSTATS
 	p->se.wait_start		= 0;
Index: linux-2.6/include/linux/sched.h
===================================================================
--- linux-2.6.orig/include/linux/sched.h
+++ linux-2.6/include/linux/sched.h
@@ -1035,6 +1035,9 @@ struct sched_entity {
 	u64			last_wakeup;
 	u64			avg_overlap;
 
+	u64			start_runtime;
+	u64			avg_wakeup;
+
 	u64			nr_migrations;
 
 #ifdef CONFIG_SCHEDSTATS
Index: linux-2.6/kernel/sched_debug.c
===================================================================
--- linux-2.6.orig/kernel/sched_debug.c
+++ linux-2.6/kernel/sched_debug.c
@@ -397,6 +397,7 @@ void proc_sched_show_task(struct task_st
 	PN(se.vruntime);
 	PN(se.sum_exec_runtime);
 	PN(se.avg_overlap);
+	PN(se.avg_wakeup);
 
 	nr_switches = p->nvcsw + p->nivcsw;
 

-- 

Re: [PATCH 1/2] sched: introduce avg_wakeup

[Peter Zijlstra]

Helps if I post the patch that builds...

---
Subject: sched: introduce avg_wakeup
From: Peter Zijlstra <a.p.zijlstra@chello.nl>
Date: Tue Dec 09 11:08:21 CET 2008

Introduce a new avg_wakeup statistic.

avg_wakeup is a measure of how frequently a task wakes up other tasks, it
represents the average time between wakeups, with a limit of avg_runtime
for when it doesn't wake up anybody.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Mike Galbraith <efault@gmx.de>
---
 include/linux/sched.h |    3 +++
 kernel/sched.c        |   36 ++++++++++++++++++++++++++++++------
 kernel/sched_debug.c  |    1 +
 3 files changed, 34 insertions(+), 6 deletions(-)

Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -1725,6 +1725,9 @@ static void update_avg(u64 *avg, u64 sam
 
 static void enqueue_task(struct rq *rq, struct task_struct *p, int wakeup)
 {
+	if (wakeup)
+		p->se.start_runtime = p->se.sum_exec_runtime;
+
 	sched_info_queued(p);
 	p->sched_class->enqueue_task(rq, p, wakeup);
 	p->se.on_rq = 1;
@@ -1732,10 +1735,15 @@ static void enqueue_task(struct rq *rq, 
 
 static void dequeue_task(struct rq *rq, struct task_struct *p, int sleep)
 {
-	if (sleep && p->se.last_wakeup) {
-		update_avg(&p->se.avg_overlap,
-			   p->se.sum_exec_runtime - p->se.last_wakeup);
-		p->se.last_wakeup = 0;
+	if (sleep) {
+		if (p->se.last_wakeup) {
+			update_avg(&p->se.avg_overlap,
+				p->se.sum_exec_runtime - p->se.last_wakeup);
+			p->se.last_wakeup = 0;
+		} else {
+			update_avg(&p->se.avg_wakeup,
+				sysctl_sched_wakeup_granularity);
+		}
 	}
 
 	sched_info_dequeued(p);
@@ -2403,6 +2411,22 @@ out_activate:
 	activate_task(rq, p, 1);
 	success = 1;
 
+	/*
+	 * Only attribute actual wakeups done by this task.
+	 */
+	if (!in_interrupt()) {
+		struct sched_entity *se = &current->se;
+		u64 sample = se->sum_exec_runtime;
+
+		if (se->last_wakeup)
+			sample -= se->last_wakeup;
+		else
+			sample -= se->start_runtime;
+		update_avg(&se->avg_wakeup, sample);
+
+		current->se.last_wakeup = current->se.sum_exec_runtime;
+	}
+
 out_running:
 	trace_sched_wakeup(rq, p, success);
 	check_preempt_curr(rq, p, sync);
@@ -2413,8 +2437,6 @@ out_running:
 		p->sched_class->task_wake_up(rq, p);
 #endif
 out:
-	current->se.last_wakeup = current->se.sum_exec_runtime;
-
 	task_rq_unlock(rq, &flags);
 
 	return success;
@@ -2445,6 +2467,8 @@ static void __sched_fork(struct task_str
 	p->se.nr_migrations		= 0;
 	p->se.last_wakeup		= 0;
 	p->se.avg_overlap		= 0;
+	p->se.start_runtime		= 0;
+	p->se.avg_wakeup		= sysctl_sched_wakeup_granularity;
 
 #ifdef CONFIG_SCHEDSTATS
 	p->se.wait_start		= 0;
Index: linux-2.6/include/linux/sched.h
===================================================================
--- linux-2.6.orig/include/linux/sched.h
+++ linux-2.6/include/linux/sched.h
@@ -1035,6 +1035,9 @@ struct sched_entity {
 	u64			last_wakeup;
 	u64			avg_overlap;
 
+	u64			start_runtime;
+	u64			avg_wakeup;
+
 	u64			nr_migrations;
 
 #ifdef CONFIG_SCHEDSTATS
Index: linux-2.6/kernel/sched_debug.c
===================================================================
--- linux-2.6.orig/kernel/sched_debug.c
+++ linux-2.6/kernel/sched_debug.c
@@ -397,6 +397,7 @@ void proc_sched_show_task(struct task_st
 	PN(se.vruntime);
 	PN(se.sum_exec_runtime);
 	PN(se.avg_overlap);
+	PN(se.avg_wakeup);
 
 	nr_switches = p->nvcsw + p->nivcsw;
 

Re: [PATCH 1/2] sched: introduce avg_wakeup

[Peter Zijlstra]

On Wed, 2009-01-14 at 12:59 +0100, Peter Zijlstra wrote:
> +       /*
> +        * Only attribute actual wakeups done by this task.
> +        */
> +       if (!in_interrupt()) {
> +               struct sched_entity *se = &current->se;
> +               u64 sample = se->sum_exec_runtime;
> +
> +               if (se->last_wakeup)
> +                       sample -= se->last_wakeup;
> +               else
> +                       sample -= se->start_runtime;
> +               update_avg(&se->avg_wakeup, sample);
> +
> +               current->se.last_wakeup = current->se.sum_exec_runtime;
> +       }

time for lunch apparently...

Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -2424,7 +2424,7 @@ out_activate:
 			sample -= se->start_runtime;
 		update_avg(&se->avg_wakeup, sample);
 
-		current->se.last_wakeup = current->se.sum_exec_runtime;
+		se.last_wakeup = se.sum_exec_runtime;
 	}
 
 out_running:

Re: [PATCH 1/2] sched: introduce avg_wakeup

[Peter Zijlstra]

On Wed, 2009-01-14 at 13:03 +0100, Peter Zijlstra wrote:
> On Wed, 2009-01-14 at 12:59 +0100, Peter Zijlstra wrote:
> > +       /*
> > +        * Only attribute actual wakeups done by this task.
> > +        */
> > +       if (!in_interrupt()) {
> > +               struct sched_entity *se = &current->se;
> > +               u64 sample = se->sum_exec_runtime;
> > +
> > +               if (se->last_wakeup)
> > +                       sample -= se->last_wakeup;
> > +               else
> > +                       sample -= se->start_runtime;
> > +               update_avg(&se->avg_wakeup, sample);
> > +
> > +               current->se.last_wakeup = current->se.sum_exec_runtime;
> > +       }
> 
> time for lunch apparently...

D'oh

---
Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -2424,7 +2424,7 @@ out_activate:
 			sample -= se->start_runtime;
 		update_avg(&se->avg_wakeup, sample);
 
-		current->se.last_wakeup = current->se.sum_exec_runtime;
+		se->last_wakeup = se->sum_exec_runtime;
 	}
 
 out_running:

Re: [PATCH 1/2] sched: introduce avg_wakeup

[Ingo Molnar]

* Peter Zijlstra <peterz@infradead.org> wrote:

> On Wed, 2009-01-14 at 12:59 +0100, Peter Zijlstra wrote:
> > +       /*
> > +        * Only attribute actual wakeups done by this task.
> > +        */
> > +       if (!in_interrupt()) {
> > +               struct sched_entity *se = &current->se;
> > +               u64 sample = se->sum_exec_runtime;
> > +
> > +               if (se->last_wakeup)
> > +                       sample -= se->last_wakeup;
> > +               else
> > +                       sample -= se->start_runtime;
> > +               update_avg(&se->avg_wakeup, sample);
> > +
> > +               current->se.last_wakeup = current->se.sum_exec_runtime;
> > +       }
> 
> time for lunch apparently...
> 
> Index: linux-2.6/kernel/sched.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched.c
> +++ linux-2.6/kernel/sched.c
> @@ -2424,7 +2424,7 @@ out_activate:
>  			sample -= se->start_runtime;
>  		update_avg(&se->avg_wakeup, sample);
>  
> -		current->se.last_wakeup = current->se.sum_exec_runtime;
> +		se.last_wakeup = se.sum_exec_runtime;
>  	}

mind sending a delta against the first submission? Whenever you are done 
with the lunch stuff ;-)

	Ingo

Re: [PATCH 1/2] sched: introduce avg_wakeup

[Peter Zijlstra]

On Wed, 2009-01-14 at 13:05 +0100, Ingo Molnar wrote:

> mind sending a delta against the first submission? Whenever you are done 
> with the lunch stuff ;-)

Compile fix and cleanup, actually compile tested too :-)

---
Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -2415,14 +2415,16 @@ out_activate:
 	 * Only attribute actual wakeups done by this task.
 	 */
 	if (!in_interrupt()) {
+		struct sched_entity *se = &current->se;
 		u64 sample = se->sum_exec_runtime;
+
 		if (se->last_wakeup)
 			sample -= se->last_wakeup;
 		else
 			sample -= se->start_runtime;
 		update_avg(&se->avg_wakeup, sample);
 
-		current->se.last_wakeup = current->se.sum_exec_runtime;
+		se->last_wakeup = se->sum_exec_runtime;
 	}
 
 out_running:

Re: [PATCH 1/2] sched: introduce avg_wakeup

[Ingo Molnar]

* Peter Zijlstra <peterz@infradead.org> wrote:

> On Wed, 2009-01-14 at 13:05 +0100, Ingo Molnar wrote:
> 
> > mind sending a delta against the first submission? Whenever you are done 
> > with the lunch stuff ;-)
> 
> Compile fix and cleanup, actually compile tested too :-)

applied, thanks Peter!

	Ingo

[PATCH 2/2] sched: prefer wakers

[Peter Zijlstra]

[-- Attachment #1: wakeup-preempt-fiddle.patch --]
[-- Type: text/plain, Size: 4586 bytes --]

Prefer tasks that wake other tasks to preempt quickly. This improves
performance because more work is available sooner.

The workload that prompted this patch was a kernel build over NFS4 (for some
curious and not understood reason we had to revert commit:
18de9735300756e3ca9c361ef58409d8561dfe0d to make any progress at all)

Without this patch a make -j8 bzImage (of x86-64 defconfig) would take
3m30-ish, with this patch we're down to 2m50-ish.

psql-sysbench/mysql-sysbench show a slight improvement in peak performance as
well, tbench and vmark seemed to not care.

It is possible to improve upon the build time (to 2m20-ish) but that seriously
destroys other benchmarks (just shows that there's more room for tinkering).

Much thanks to Mike who put in a lot of effort to benchmark things and proved
a worthy opponent with a competing patch.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Mike Galbraith <efault@gmx.de>
---
 include/linux/sched.h   |    3 ++
 kernel/sched.c          |   34 ++++++++++++++++++++++-----
 kernel/sched_debug.c    |    1 
 kernel/sched_fair.c     |   59 +++++++++++++++++++++++++++++++++++++++++++-----
 kernel/sched_features.h |    3 +-
 5 files changed, 87 insertions(+), 13 deletions(-)

Index: linux-2.6/kernel/sched_fair.c
===================================================================
--- linux-2.6.orig/kernel/sched_fair.c
+++ linux-2.6/kernel/sched_fair.c
@@ -1295,16 +1295,63 @@ out:
 }
 #endif /* CONFIG_SMP */
 
-static unsigned long wakeup_gran(struct sched_entity *se)
+/*
+ * Adaptive granularity
+ *
+ * se->avg_wakeup gives the average time a task runs until it does a wakeup,
+ * with the limit of wakeup_gran -- when it never does a wakeup.
+ *
+ * So the smaller avg_wakeup is the faster we want this task to preempt,
+ * but we don't want to treat the preemptee unfairly and therefore allow it
+ * to run for at least the amount of time we'd like to run.
+ *
+ * NOTE: we use 2*avg_wakeup to increase the probability of actually doing one
+ *
+ * NOTE: we use *nr_running to scale with load, this nicely matches the
+ *       degrading latency on load.
+ */
+static unsigned long
+adaptive_gran(struct sched_entity *curr, struct sched_entity *se)
+{
+	u64 this_run = curr->sum_exec_runtime - curr->prev_sum_exec_runtime;
+	u64 expected_wakeup = 2*se->avg_wakeup * cfs_rq_of(se)->nr_running;
+	u64 gran = 0;
+
+	if (this_run < expected_wakeup)
+		gran = expected_wakeup - this_run;
+
+	return min_t(s64, gran, sysctl_sched_wakeup_granularity);
+}
+
+static unsigned long
+wakeup_gran(struct sched_entity *curr, struct sched_entity *se)
 {
 	unsigned long gran = sysctl_sched_wakeup_granularity;
 
+	if (cfs_rq_of(curr)->curr && sched_feat(ADAPTIVE_GRAN))
+		gran = adaptive_gran(curr, se);
+
 	/*
-	 * More easily preempt - nice tasks, while not making it harder for
-	 * + nice tasks.
+	 * Since its curr running now, convert the gran from real-time
+	 * to virtual-time in his units.
 	 */
-	if (!sched_feat(ASYM_GRAN) || se->load.weight > NICE_0_LOAD)
-		gran = calc_delta_fair(sysctl_sched_wakeup_granularity, se);
+	if (sched_feat(ASYM_GRAN)) {
+		/*
+		 * By using 'se' instead of 'curr' we penalize light tasks, so
+		 * they get preempted easier. That is, if 'se' < 'curr' then
+		 * the resulting gran will be larger, therefore penalizing the
+		 * lighter, if otoh 'se' > 'curr' then the resulting gran will
+		 * be smaller, again penalizing the lighter task.
+		 *
+		 * This is especially important for buddies when the leftmost
+		 * task is higher priority than the buddy.
+		 */
+		if (unlikely(se->load.weight != NICE_0_LOAD))
+			gran = calc_delta_fair(gran, se);
+	} else {
+		if (unlikely(curr->load.weight != NICE_0_LOAD))
+			gran = calc_delta_fair(gran, curr);
+	}
 
 	return gran;
 }
@@ -1331,7 +1378,7 @@ wakeup_preempt_entity(struct sched_entit
 	if (vdiff <= 0)
 		return -1;
 
-	gran = wakeup_gran(curr);
+	gran = wakeup_gran(curr, se);
 	if (vdiff > gran)
 		return 1;
 
Index: linux-2.6/kernel/sched_features.h
===================================================================
--- linux-2.6.orig/kernel/sched_features.h
+++ linux-2.6/kernel/sched_features.h
@@ -1,5 +1,5 @@
 SCHED_FEAT(NEW_FAIR_SLEEPERS, 1)
-SCHED_FEAT(NORMALIZED_SLEEPER, 1)
+SCHED_FEAT(NORMALIZED_SLEEPER, 0)
 SCHED_FEAT(WAKEUP_PREEMPT, 1)
 SCHED_FEAT(START_DEBIT, 1)
 SCHED_FEAT(AFFINE_WAKEUPS, 1)
@@ -13,4 +13,5 @@ SCHED_FEAT(LB_WAKEUP_UPDATE, 1)
 SCHED_FEAT(ASYM_EFF_LOAD, 1)
 SCHED_FEAT(WAKEUP_OVERLAP, 0)
 SCHED_FEAT(LAST_BUDDY, 1)
+SCHED_FEAT(ADAPTIVE_GRAN, 1)
 SCHED_FEAT(OWNER_SPIN, 1)

-- 

Re: [PATCH 0/2] prefer wakers -v2

[Ingo Molnar]

* Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:

> OK, so lets try this again...

applied them to tip/sched/core:

 c4cddec: sched: prefer wakers
 6a70714: sched: introduce avg_wakeup

Mike, what's your review/performance/interactivity verdict?

	Ingo

Re: [PATCH 0/2] prefer wakers -v2

[Mike Galbraith]

On Wed, 2009-01-14 at 12:47 +0100, Ingo Molnar wrote:
> * Peter Zijlstra <a.p.zijlstra@chello.nl> wrote:
> 
> > OK, so lets try this again...
> 
> applied them to tip/sched/core:
> 
>  c4cddec: sched: prefer wakers
>  6a70714: sched: introduce avg_wakeup
> 
> Mike, what's your review/performance/interactivity verdict?

I saw nothing but good things with it.

	-Mike

Re: [PATCH 0/2] prefer wakers -v2

[Mike Galbraith]

On Wed, 2009-01-14 at 12:39 +0100, Peter Zijlstra wrote:
> OK, so lets try this again...

I took tip out for a little test-drive.  Mysql/pgsql+oltp showed no
effect vs 29.git beyond noise level, but cache hot make -j8 kbuild times
in an nfs4 mount show marked improvement.

2.6.29.git
real    6m29.291s
user    10m20.355s
sys     2m1.288s

2.6.29.tip
real    4m30.160s
user    10m26.115s
sys     2m3.088s

Wire saturates at ~4m, so there's still some room for improvement.

On the interactivity front, tip feels snappier, particularly when IO is
going on.  One place that this is quite noticeable is reading lkml with
evolution while building a new kernel.  I generally keep thread count
low when using evolution because IO makes it sluggish when deleting and
moving on to the next message.  With tip, the evolution experience is
much improved.

	-Mike