Skip to contentSkip to conversation

prefer wakers -v2

PATCH Applied Peter Zijlstra 4 participants 12 messages Jan 14, 2009 – Jan 16, 2009 Scheduler

lore
Share & tools
lore
#1 lore raw

PATCH 1/2 sched: introduce avg_wakeup

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.

---
 include/linux/sched.h |    3 +++
 kernel/sched.c        |   34 ++++++++++++++++++++++++++++------
 kernel/sched_debug.c  |    1 +
 3 files changed, 32 insertions(+), 6 deletions(-)
kernel/sched.c +28 -6
Index: 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;
include/linux/sched.h +3 -0
Index: 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
kernel/sched_debug.c +1 -0
Index: 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;
 
#2 lore raw

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

Helps if I post the patch that builds...

---
Subject: sched: introduce avg_wakeup
From: Peter Zijlstra <[email protected]>
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.

---
 include/linux/sched.h |    3 +++
 kernel/sched.c        |   36 ++++++++++++++++++++++++++++++------
 kernel/sched_debug.c  |    1 +
 3 files changed, 34 insertions(+), 6 deletions(-)
kernel/sched.c +30 -6
Index: 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;
include/linux/sched.h +3 -0
Index: 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
kernel/sched_debug.c +1 -0
Index: 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;
 
maintainer
#3 lore raw

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

Quoted 5 lines · Peter Zijlstra
(quoted diff) +5 -0
+       /*
+        * Only attribute actual wakeups done by this task.
+        */
+       if (!in_interrupt()) {
+               struct sched_entity *se = &current->se;

Review

Quoted 10 lines
(quoted diff) +10 -0
+               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...

kernel/sched.c +1 -1
Index: 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:
maintainer
#4 lore raw

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

Quoted 10 lines · Peter Zijlstra
Quoted 9 lines · Peter Zijlstra
(quoted diff) +9 -0
+       /*
+        * 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;
Quoted 8 lines

Review

Quoted 6 lines
(quoted diff) +6 -0
+               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

---

kernel/sched.c +1 -1
Index: 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:
#5 lore raw

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

In reply to Peter Zijlstra
Quoted 24 lines · Peter Zijlstra
Quoted 5 lines · Peter Zijlstra
(quoted diff) +5 -0
+       /*
+        * Only attribute actual wakeups done by this task.
+        */
+       if (!in_interrupt()) {
+               struct sched_entity *se = &current->se;

Review

Quoted 10 lines
(quoted diff) +10 -0
+               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
===================================================================

kernel/sched.c out_activate: · line 2428

Quoted 6 lines
kernel/sched.c +1 -1
@@ -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

maintainer
#6 lore raw

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

Quoted 2 lines · Ingo Molnar

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

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

---

kernel/sched.c +3 -1
Index: 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:
Applied
#7 lore raw

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

Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Ingo Molnar

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

#8 lore raw

PATCH 2/2 sched: prefer wakers

In reply to Peter Zijlstra

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.

---
 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(-)
kernel/sched_fair.c +53 -6
Index: 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;
 
kernel/sched_features.h +2 -1
Index: 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)
Applied
#9 lore raw
In reply to Peter Zijlstra
Quoted 1 line · Peter Zijlstra

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

#10 lore raw
Quoted 10 lines · Ingo Molnar
Quoted 1 line · Peter Zijlstra

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

#11 lore raw
In reply to Peter Zijlstra
Quoted 1 line · Peter Zijlstra

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