prefer wakers -v2
cover prefer wakers -v2
OK, so lets try this again...
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
@@ -1725,6 +1725,9 @@ static void update_avg(u64 *avg, u64 samstatic 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
@@ -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
@@ -397,6 +397,7 @@ void proc_sched_show_task(struct task_stPN (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
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
@@ -1725,6 +1725,9 @@ static void update_avg(u64 *avg, u64 samstatic 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 = ¤t->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
@@ -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
@@ -397,6 +397,7 @@ void proc_sched_show_task(struct task_stPN (se.vruntime);PN (se.sum_exec_runtime);PN (se.avg_overlap); +PN (se.avg_wakeup); nr_switches = p->nvcsw + p->nivcsw;
Peter Zijlstra
maintainerRe: [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 = ¤t->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
@@ -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:
Peter Zijlstra
maintainerRe: [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 = ¤t->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
@@ -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
In reply to Peter ZijlstraQuoted 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 = ¤t->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
Peter Zijlstra
maintainerRe: [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
@@ -2415,14 +2415,16 @@ out_activate:* Only attribute actual wakeups done by this task. */ if (!in_interrupt ()) { +struct sched_entity *se = ¤t->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:
Ingo Molnar
AppliedRe: [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
PATCH 2/2 sched: prefer wakers
In reply to Peter ZijlstraPrefer 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
@@ -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_entitif (vdiff <=0 )return -1 ; - gran =wakeup_gran (curr); + gran =wakeup_gran (curr, se);if (vdiff > gran)return 1 ;
kernel/sched_features.h +2 -1
@@ -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 )
Ingo Molnar
AppliedQuoted 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
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: introduceavg_wakeupMike, what's your review/performance/interactivity verdict?
I saw nothing but good things with it.
-Mike
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