sched: START_NICE feature (temporarily niced forks) (v4)
RFC PATCH 1/1 sched: START_NICE feature (temporarily niced forks) (v4)
This patch tweaks the fair vruntime calculation of both the parent and the child after a fork to double vruntime increment speed, but this is only applied to their first slice after the fork. The goal of this scheme is that their respective vruntime will increment faster in the first slice after the fork, so a workload doing many forks (e.g. make -j10) will have a limited impact on latency-sensitive workloads.
This is an alternative to START_DEBIT which does not have the downside of moving newly forked threads to the end of the runqueue.
Changelog since v3:
- Take Peter Zijlstra's comments into account.
- Move timeout check and penality reset to __update_curr().
Changelog since v2:
- Apply vruntime penality even the first time the exec time has moved across the timeout.
Changelog since v1:
- Moving away from modifying the task weight from within the scheduler, as it is
error-prone: modifying the weight of a queued task leads to cpu weight errors. For the moment, just tweak calc_delta_fair vruntime calculation. Eventually we could revisit the weight modification approach if we decide that it's worth the more intrusive changes. I redid the START_NICE benchmark, which did not change much: it is still appealing.
Latency benchmark:
* wakeup-latency.c (SIGEV_THREAD) with make -j10 on UP 2.0GHz
Kernel used: mainline 2.6.35.2 with smaller min_granularity and check_preempt vruntime vs runtime comparison patches applied.
- START_DEBIT (vanilla setting)
maximum latency: 26409.0 µs
average latency: 6762.1 µs
missed timer events: 0
- NO_START_DEBIT, NO_START_NICE
maximum latency: 10001.8 µs
average latency: 1618.7 µs
missed timer events: 0
- START_NICE
maximum latency: 8351.2 µs
average latency: 1597.7 µs
missed timer events: 0
On the Xorg interactivity aspect, I notice a major improvement with START_NICE compared to the two other settings. I just came up with a very simple repeatable low-tech test that takes into account both input and video update responsiveness:
Start make -j10 in a gnome-terminal
In another gnome-terminal, start pressing the space bar, holding it. Use the cursor speed (my cursor is a full rectangle) as latency indicator. With low latency, its speed should be constant, no stopping and no sudden acceleration.
--- include/linux/sched.h | 2 + kernel/sched.c | 2 + kernel/sched_debug.c | 11 +++++--- kernel/sched_fair.c | 65 ++++++++++++++++++++++++++++++++++++++++++------ kernel/sched_features.h | 6 ++++ 5 files changed, 75 insertions(+), 11 deletions(-)
kernel/sched_features.h +6 -0
@@ -12,6 +12,12 @@ SCHED_FEAT(GENTLE_FAIR_SLEEPERS, 1)SCHED_FEAT (START_DEBIT ,1 )/* +* After a fork, ensure both the parent and the child get niced for their +* following slice. + */ +SCHED_FEAT (START_NICE ,0 ) + +/* * Should wakeups try to preempt running tasks. */SCHED_FEAT (WAKEUP_PREEMPT ,1 )
include/linux/sched.h +2 -0
@@ -1132,6 +1132,8 @@ struct sched_entity {u64 prev_sum_exec_runtime;u64 nr_migrations; +u64 fork_nice_timeout; +unsigned int fork_nice_penality;#ifdef CONFIG_SCHEDSTATS struct sched_statistics statistics;
kernel/sched.c +2 -0
@@ -2421,6 +2421,8 @@ static void __sched_fork(struct task_str p->se.sum_exec_runtime =0 ; p->se.prev_sum_exec_runtime =0 ; p->se.nr_migrations =0 ; + p->se.fork_nice_timeout =0 ; + p->se.fork_nice_penality =0 ;#ifdef CONFIG_SCHEDSTATS memset (&p->se.statistics,0 ,sizeof (p->se.statistics));
kernel/sched_fair.c +57 -8
114 lines not on this page · raw message
kernel/sched_debug.c +8 -3
@@ -120,6 +120,10 @@ print_task(struct seq_file *m, struct rq SEQ_printf(m, " %s", path); }#endif + +SEQ_printf (m," %d" , p->se.fork_nice_penality); +SEQ_printf (m," %9Ld.%06ld" ,SPLIT_NS (p->se.fork_nice_timeout)); +SEQ_printf (m,"\n" ); }
@@ -131,9 +135,10 @@ static void print_rq(struct seq_file *m,SEQ_printf (m,"\nrunnable tasks:\n" " task PID tree-key switches prio" -" exec-runtime sum-exec sum-sleep\n" -"------------------------------------------------------" -"----------------------------------------------------\n" ); +" exec-runtime sum-exec sum-sleep nice-pen" +" nice-pen-timeout\n" +"---------------------------------------------------------------" +"---------------------------------------------------------------\n" );read_lock_irqsave (&tasklist_lock, flags);
Signature · 4 lines
Mathieu Desnoyers Operating System Efficiency R&D Consultant EfficiOS Inc. http://www.efficios.com
Quoted 2 lines · Mathieu Desnoyers
Kernel used: mainline 2.6.35.2 with smaller
min_granularityandcheck_preemptvruntime vs runtime comparison patches applied.
My test kernel is fresh baked v2.6.36-rc5.
Quoted 5 lines
-
START_DEBIT(vanilla setting)maximum latency: 26409.0 µs
average latency: 6762.1 µs
missed timer events: 0
Mine are much worse, as I have 0bf377bb reverted to keep my base test numbers relevant while tinkering. These are fresh though.
maximum latency: 69261.1 µs 130058.0 µs 106636.9 µs
average latency: 9169.6 µs 9456.4 µs 9281.7 µs
missed timer events: 0 0 0
pert vs make -j3, 30 sec sample time
pert/s: 70 >6963.47us: 857 min: 0.06 max:60738.53 avg:10738.03 sum/s:754884us overhead:75.49% pert/s: 70 >10471.13us: 847 min: 0.12 max:73405.91 avg:10674.23 sum/s:753245us overhead:75.31% pert/s: 72 >12703.37us: 790 min: 0.11 max:55287.48 avg:10299.53 sum/s:749463us overhead:74.84% pert/s: 71 >14825.31us: 740 min: 0.11 max:57264.25 avg:10581.39 sum/s:751984us overhead:75.20%
Quoted 5 lines
-
NO_START_DEBIT,NO_START_NICEmaximum latency: 10001.8 µs
average latency: 1618.7 µs
missed timer events: 0
maximum latency: 19948.5 µs 19215.4 µs 19526.3 µs average latency: 5000.1 µs 4712.2 µs 5005.5 µs missed timer events: 0 0 0
pert vs make -j3, 30 sec sample time
pert/s: 61 >8928.57us: 743 min: 0.15 max:78659.33 avg:12895.03 sum/s:787026us overhead:78.64% pert/s: 62 >12853.44us: 700 min: 0.12 max:83828.68 avg:12525.78 sum/s:778686us overhead:77.84% pert/s: 61 >15566.82us: 675 min: 0.11 max:67289.16 avg:12685.47 sum/s:781002us overhead:78.07% pert/s: 61 >18254.31us: 690 min: 1.40 max:72051.21 avg:12832.17 sum/s:782762us overhead:78.27%
Quoted 5 lines
-
START_NICEmaximum latency: 8351.2 µs
average latency: 1597.7 µs
missed timer events: 0
maximum latency: 34004.7 µs 34712.5 µs 46956.6 µs
average latency: 7886.9 µs 8099.8 µs 8060.3 µs
missed timer events: 0 0 0
pert vs make -j3, 30 sec sample time
pert/s: 104 >5610.69us: 1036 min: 0.05 max:56740.62 avg:6047.66 sum/s:628957us overhead:62.90% pert/s: 104 >8617.90us: 884 min: 0.15 max:65410.85 avg:5954.64 sum/s:623253us overhead:62.25% pert/s: 116 >11005.35us: 837 min: 0.14 max:60020.97 avg:4963.97 sum/s:577641us overhead:57.76% pert/s: 99 >13632.91us: 863 min: 0.14 max:68019.67 avg:6542.21 sum/s:648987us overhead:64.86%
V4 seems to have lost some effectiveness wrt new thread latency, and tilted the fairness scaled considerably further in the 100% hog's favor.
kernel/sched_fair.c static u64 sched_slice(struct cfs_rq *cf · line 490
Quoted 9 lines
kernel/sched_fair.c +2
-0@@ -481,6 +483,8 @@ static u64 sched_slice(struct cfs_rq *cf load = &lw; } slice =calc_delta_mine (slice, se->load.weight, load); +if (se->fork_nice_penality) + slice <<= se->fork_nice_penality; }return slice; }
Hm. Parent/child can exec longer (?), but also sit in the penalty box longer, so pay through the nose. That doesn't look right. Why mess with slice? Neither effect seems logical.
Since this is mostly about reducing latencies for the non-fork competition, maybe a kinder gentler START_DEBIT would work. Let the child inherit parent's vruntime, charge a fraction of the vruntime equalizer bill _after_ it execs, until the bill has been paid, or whatnot.
(I've tried a few things, and my bit-bucket runneth over, so this idea probably sucks rocks too;)
-Mike
Quoted 5 lines · Mike Galbraith
Since this is mostly about reducing latencies for the non-fork competition, maybe a kinder gentler
START_DEBITwould work. Let the child inherit parent's vruntime, charge a fraction of the vruntime equalizer bill _after_ it execs, until the bill has been paid, or whatnot.
One thing that comes to mind is that a lot of this problem is generated, or rather exacerbated by, sleeper fairness. For example, take vfork:
parent goes to sleep after passing the baton to the child. When the child exits, the parent wakes, gets credit for sleeping while it was really running in drag, may preempt as a result, and is free to repeat the procedure, gaining an edge. START_DEBIT prevents that.
In the naked vfork/exec case, the parent _should_ resume at the relative vruntime of the child, without further sleeper vruntime adjustment, but that wouldn't help fix plain fork/clone which can do the same, nor would it help kbuild's vfork->exec->clone[s]->parallel_stuff->exit unless you add a lot of complexity...
(...heh, to end up with something remarkably similar to cgroup container per process. Nope, don't want to re-invent the process scheduler to fix a task scheduler corner case. That's the core though, same old divide and conquer problem we've always had. We have a process scheduler available these days though. Back to our task scheduler problem...)
Perhaps take that vslice penalty, apply it to parent and child, and if present, deduct sleep time from their debt, and only credit sleep time if there's anything left over? In any case, seems to me that sleep time has to be included in the equation while the penalty is in effect.
Guess I'll try that, see what happens.
(but that will likely negate much of the benefit for your testcase, where parent and child sleep)
-Mike
Quoted 6 lines · Mike Galbraith
Perhaps take that vslice penalty, apply it to parent and child, and if present, deduct sleep time from their debt, and only credit sleep time if there's anything left over? In any case, seems to me that sleep time has to be included in the equation while the penalty is in effect.
Guess I'll try that, see what happens.
Nothing good. Several flavors thereof.
Quoted 2 lines
(but that will likely negate much of the benefit for your testcase, where parent and child sleep)
(yup, it did)
BTTODB.
-Mike
Hi Mathieu,
include/linux/sched.h struct sched_entity { · line 1136
Quoted 2 lines · Mathieu Desnoyers
include/linux/sched.h +2
-0+u64 fork_nice_timeout; +unsigned int fork_nice_penality;
A pedantic nit from an editor-type: penalty doesn't have an 'i', so you probably want 'fork_nice_penalty'.
jake
Signature · 1 line
Jake Edge - [email protected] - http://www.lwn.net