throttling tree patches
Subsystems (2)
PATCH 1/1 throttling tree patches
Greetings,
I've broken down my throttling tree into 6 patches, which I'll send as replies to this start-point.
Patch 1/6
Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.
kernel/sched.c renamed from kernel/sched.c.org +14 -4
@@ -805,6 +805,16 @@unsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time; +/* +* On SMP systems, a task can go to sleep on one CPU and +* wake up on another. When this happens, the timestamp +* is rounded to the nearest tick, which can lead to now +* being less than p->timestamp for short sleeps. Ignore +* these, they're insignificant. +*/ +if (unlikely (now < p->timestamp)) + __sleep_time =0ULL ; +if (batch_task (p)) sleep_time =0 ;else {
@@ -871,20 +881,20 @@*/ static void activate_task (task_t *p,runqueue_t *rq,int local) { -unsigned long long now; +unsigned long long now, comp; - now =sched_clock (); + now = comp =sched_clock ();#ifdef CONFIG_SMP if (!local) {/* Compensate for drifting sched_clock */ runqueue_t *this_rq =this_rq (); - now = (now - this_rq->timestamp_last_tick) + comp = (now - this_rq->timestamp_last_tick) + rq->timestamp_last_tick; }#endif if (!rt_task (p)) - p->prio =recalc_task_prio (p, now); + p->prio =recalc_task_prio (p, comp);/* * This checks to make sure it's not an uninterruptible task
patch 2/6
This patch just fixes a bug waiting for a place to happen. If anyone ever decides to use TASK_NONINTERACTIVE along with TASK_UNINTERRUPTIBLE, bad things will happen.
kernel/sched.c renamed from kernel/sched.c-1.timewarp +2 -2
@@ -1418,7 +1418,7 @@ out_activate:#endif /* CONFIG_SMP */ -if (old_state ==TASK_UNINTERRUPTIBLE ) { +if (old_state &TASK_UNINTERRUPTIBLE ) { rq->nr_uninterruptible--;/* * Tasks on involuntary sleep don't earn
@@ -3125,7 +3125,7 @@ unlikely(signal_pending(prev)))) prev->state = TASK_RUNNING; else { -if (prev->state ==TASK_UNINTERRUPTIBLE ) +if (prev->state &TASK_UNINTERRUPTIBLE ) rq->nr_uninterruptible++;deactivate_task (prev, rq); }
patch 3/6
This patch does various interactivity cleanups.
1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.
2. Removes the priority barrier for IO.
3. Treats TASK_INTERACTIVE as a transition point that all tasks must stop at prior to being promoted further.
4. Moves division out of the fast path and into scheduler_tick(). While doing so, tightens timeslice accounting, since it's free, and is the flip-side of the reason for having nanosecond sched_clock().
include/linux/sched.h renamed from include/linux/sched.h.org +1 -0
@@ -741,6 +741,7 @@unsigned long policy;cpumask_t cpus_allowed;unsigned int time_slice, first_time_slice; +long slice_time_ns;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
kernel/sched.c renamed from kernel/sched.c-2.uninterruptible +80 -53
239 lines not on this page · raw message
patch 4/6
This patch implements the throttling.
Throttling is done via computing a slice_avg, which is the upper limit of what a task's sleep_avg may be and be sane. When a task begins to consume more CPU than it's sleep_avg indicates it should, the task will be throttled. A task which conforms to expectations can save credit for later use, which allows interactive tasks to do a burst of activity without being throttled. When their reserve is exhausted however, that's the end of high ussage at high priority.
include/linux/sched.h renamed from include/linux/sched.h.org +2 -2
@@ -733,14 +733,14 @@unsigned short ioprio;unsigned int btrace_seq; -unsigned long sleep_avg; +unsigned long sleep_avg, last_slice, throttle;unsigned long long timestamp, last_ran;unsigned long long sched_time;/* sched_clock time spent running */ enum sleep_type sleep_type;unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +unsigned int time_slice, slice_info;long slice_time_ns;#ifdef CONFIG_SCHEDSTATS
kernel/sched.c renamed from kernel/sched.c-3.interactivity +243 -22
340 lines not on this page · raw message
patch 5/6
This patch tightens timeslice accounting the rest of the way, such that a task which has received more than it's slice due to missing with the timer interrupt will have the excess deducted from their next slice.
kernel/sched.c renamed from kernel/sched.c-4.throttle +18 -3
@@ -2924,13 +2924,28 @@unsigned int slice =last_slice (p);unsigned int slice_avg, cpu, idle;long run_time =-1 * p->slice_time_ns; +long slice_time_ns =task_timeslice_ns (p);int w =MAX_BONUS , delta, bonus;/* -* Update time_slice. +* Update time_slice. Account for unused fragment, +* or excess time received due to missed tick. */ - p->slice_time_ns =task_timeslice_ns (p); - p->time_slice =task_timeslice (p); + p->slice_time_ns += slice_time_ns; +/* +* Not common, but this does happen on SMP systems. +* Timeslice theft of this magnitude has never been +* observed in the wild, so assume that this is BS, +* and give the poor task it's full slice. Theory: +* mostly idle task migrates between CPUs numerous +* times during it's slice, timestamp rounding leads +* to wildly inaccurate calculation. Rounding has +* maximum effect on those who stretch their slice, +* but is also fairly meaningless, so ignore it. +*/ +if (unlikely (p->slice_time_ns <NS_TICK )) + p->slice_time_ns = slice_time_ns; + p->time_slice =NS_TO_JIFFIES (p->slice_time_ns);set_last_slice (p, p->time_slice);/*
patch 6/6
This patch exports throttling tuning knobs to userland. Should be useful for testing, and in easily discarded should my throttling stuff make it into mm, and survive the experience.
include/linux/sysctl.h renamed from include/linux/sysctl.h.org +2 -0
@@ -148,6 +148,8 @@KERN_SPIN_RETRY =70 ,/* int: number of spinlock retries */ KERN_ACPI_VIDEO_FLAGS =71 ,/* int: flags for setting up video after ACPI sleep */ KERN_IA64_UNALIGNED =72 ,/* int: ia64 unaligned userland trap enable */ +KERN_SCHED_THROTTLE1 =73 ,/* int: throttling credit period 1 in secs */ + KERN_SCHED_THROTTLE2=74, /* int: throttling credit period 2 in secs */ };
kernel/sysctl.c renamed from kernel/sysctl.c.org +30 -6
@@ -73,6 +73,9 @@extern int pid_max_min, pid_max_max;extern int sysctl_drop_caches;extern int percpu_pagelist_fraction; +extern int credit_c1; +extern int credit_c2; +extern int credit_max;#if defined(CONFIG_X86_LOCAL_APIC ) && defined(CONFIG_X86 )int unknown_nmi_panic;
@@ -230,6 +233,11 @@ { .ctl_name = 0 } }; +/* Constants for minimum and maximum testing in vm_table and +* kern_table. We use these as one-element integer vectors. */ +static int zero; +static int one_hundred =100 ; +static ctl_table kern_table[] = { { .ctl_name =KERN_OSTYPE ,
@@ -684,15 +692,31 @@ .proc_handler = &proc_dointvec, },#endif + { + .ctl_name = KERN_SCHED_THROTTLE1, + .procname = "credit_c1", + .data = &credit_c1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &credit_max, + }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "credit_c2", + .data = &credit_c2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &credit_max, + }, { .ctl_name = 0 } }; -/* Constants for minimum and maximum testing in vm_table. -We use these as one-element integer vectors. */ -static int zero; -static int one_hundred =100 ; - -static ctl_table vm_table[] = { { .ctl_name =VM_OVERCOMMIT_MEMORY ,
kernel/sched.c renamed from kernel/sched.c-5.slice_accounting +5 -4
@@ -220,11 +220,12 @@* credit that fits in 32 bits jiffies is 42949 seconds. */ -#define CREDIT_C1 10 -#define CREDIT_C2 14400 +int credit_c1 =10 ; +int credit_c2 =14400 ; +int credit_max =42949 ; -#define C1 (CREDIT_C1 * MAX_BONUS * HZ) -#define C2 (CREDIT_C2 * MAX_BONUS * HZ + C1) +#define C1 (credit_c1 * MAX_BONUS * HZ) +#define C2 (credit_c2 * MAX_BONUS * HZ + C1)#define C3 (MAX_BONUS * C2)#define credit_exhausted (p, credit) \
Quoted 7 lines · Mike Galbraith
patch 6/6
This patch exports throttling tuning knobs to userland. Should be useful for testing, and in easily discarded should my throttling stuff make it into mm, and survive the experience.
Signed-off-by Mike Galbraith <[email protected]>
Ok.
Cheers,
Con
Quoted 7 lines · Mike Galbraith
patch 5/6
This patch tightens timeslice accounting the rest of the way, such that a task which has received more than it's slice due to missing with the timer interrupt will have the excess deducted from their next slice.
Signed-off-by Mike Galbraith <[email protected]>
Looks ok.
Cheers,
Con
Quoted 11 lines · Mike Galbraith
patch 4/6
This patch implements the throttling.
Throttling is done via computing a
slice_avg, which is the upper limit of what a task'ssleep_avgmay be and be sane. When a task begins to consume more CPU than it'ssleep_avgindicates it should, the task will be throttled. A task which conforms to expectations can save credit for later use, which allows interactive tasks to do a burst of activity without being throttled. When their reserve is exhausted however, that's the end of high ussage at high priority.
Looks ok. The description of credit still sounds cryptic.
kernel/sched.c line 228
Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c-3.interactivity +3
-0+#define C1 (CREDIT_C1 * MAX_BONUS * HZ) +#define C2 (CREDIT_C2 * MAX_BONUS * HZ + C1) +#define C3 (MAX_BONUS * C2)
Macro names that short are asking for trouble...
...
else looks good. After we've cleaned out all the sched patches from -mm it would be nice to get this work in. The values of C1 and particularly C2 _sound_ large but may well be appropriate since you've been hard at work on this. I'll have to have a play for myself (if I ever find spare cycles on my miniscule selection of hardware) with them when they hit -mm.
Cheers,
Con
Quoted 1 line · Mike Galbraith
This patch does various interactivity cleanups.
I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.
Quoted 2 lines
1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.
This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb. Most kernel threads do sleep for extended periods and will always end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.
Quoted 1 line
2. Removes the priority barrier for IO.
Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.
Quoted 2 lines
3. Treats
TASK_INTERACTIVEas a transition point that all tasks must stop at prior to being promoted further.
Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.
Quoted 3 lines
4. Moves division out of the fast path and into
scheduler_tick(). While doing so, tightens timeslice accounting, since it's free, and is the flip-side of the reason for having nanosecondsched_clock().
Seems fine.
Cheers,
Con
Quoted 5 lines · Con Kolivas
Quoted 1 line · Mike Galbraith
This patch does various interactivity cleanups.
I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.
They're all part of the same thing, they're just cleanup.
Quoted 6 lines
Quoted 2 lines
1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.
This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb.
Kernel threads don't make the transition, they're sitting there with a fully loaded sleep_avg. You stop on the way up, sure, but once there, a long sleep doesn't truncate you. Try it.
Quoted 4 lines
Most kernel threads do sleep for extended periods and will always
end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.
No, they won't. Furthermore, any kernel thread which cannot tolerate dynamic priority semantics should not use them, they should be RT.
Quoted 5 lines
Quoted 1 line
2. Removes the priority barrier for IO.
Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.
This barrier is artificial, and has been demonstrated to be harmful to some loads. Being practical, if this is demonstrated to still cause trouble, I'll happily re-introduce it with a follow-up patch.
Quoted 5 lines
Quoted 2 lines
3. Treats
TASK_INTERACTIVEas a transition point that all tasks must stop at prior to being promoted further.Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.
Quite the opposite, it makes perfect sense. Taking the long sleeper to the artificial barrier of prio 16 as stock does is the very reason that thud totally destroys the interactive experience. I'd love to remove this barrier too, and have 'purity', but OTOH, the interactive border _is_ a transition point where the scheduler changes behavior. This is a transition point in fact, so treating it as such is indeed correct.
-Mike
Quoted 8 lines · Mike Galbraith
Quoted 5 lines · Con Kolivas
Quoted 1 line · Mike Galbraith
This patch does various interactivity cleanups.
I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.
They're all part of the same thing, they're just cleanup.
Cleanup? Something that changes behaviour is not cleanup.
Quoted 11 lines
Quoted 7 lines
Quoted 3 lines
1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.
This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb.
Kernel threads don't make the transition, they're sitting there with a fully loaded
sleep_avg. You stop on the way up, sure, but once there, a long sleep doesn't truncate you. Try it.
Threads like kswapd do not have a fully loaded sleep_avg.
Quoted 7 lines
Quoted 4 lines
Most kernel threads do sleep for extended periods and will always
end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.No, they won't. Furthermore, any kernel thread which cannot tolerate dynamic priority semantics should not use them, they should be RT.
Very few kernel threads should require RT just to work as you just said, yet you'll make it harder for them with your changed dynamic priority semantics. We already know they are not going to be misbehaving userspace tasks and they deserve simpler semantics than the full interactivity estimator gives.
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
2. Removes the priority barrier for IO.
Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.
This barrier is artificial, and has been demonstrated to be harmful to some loads.
Which?
Quoted 2 lines
Being practical, if this is demonstrated to still cause trouble, I'll happily re-introduce it with a follow-up patch.
Trouble occurs months afterwards this hits mainline since you'll get almost noone testing it in -mm. It was put there because it hurt interactivity and you're removing it because you don't like that we have to put a special case there?
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines
3. Treats
TASK_INTERACTIVEas a transition point that all tasks must stop at prior to being promoted further.Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.
Quoted 6 lines
Quite the opposite, it makes perfect sense. Taking the long sleeper to the artificial barrier of prio 16 as stock does is the very reason that thud totally destroys the interactive experience. I'd love to remove this barrier too, and have 'purity', but OTOH, the interactive border _is_ a transition point where the scheduler changes behavior. This is a transition point in fact, so treating it as such is indeed correct.
And what does it actually achieve making this change is my question?
I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.
Cheers,
Con
Quoted 11 lines · Con Kolivas
Quoted 8 lines · Mike Galbraith
Quoted 5 lines · Con Kolivas
Quoted 1 line · Mike Galbraith
This patch does various interactivity cleanups.
I have trouble with this patch. By your own admission this patch does 4 different things which one patch shouldn't.
They're all part of the same thing, they're just cleanup.
Cleanup? Something that changes behaviour is not cleanup.
A semantic cleanup remains a cleanup.
Quoted 7 lines
Quoted 7 lines
Quoted 6 lines
Quoted 2 lines
1. Removes the barrier between kernel threads and user tasks wrt dynamic priority handling.
This is a bad idea. Subjecting a priority ceiling to kernel threads because they spend a long time idle is not the same as a user task that may be an idle bomb.
Quoted 5 lines
Quoted 3 lines
Kernel threads don't make the transition, they're sitting there with a fully loaded
sleep_avg. You stop on the way up, sure, but once there, a long sleep doesn't truncate you. Try it.Threads like kswapd do not have a fully loaded
sleep_avg.
Huh? I've yet to see kswapd non-interactive. If I do, I'll have grounds to party, because the box would otherwise have been a doorstop.
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
Most kernel threads do sleep for extended periods and will always
end up hitting this ceiling. That could lead to some difficult to understand latencies in scheduling of kernel threads, even if they are nice -5 because they'll expire very easily.
Quoted 7 lines
Quoted 2 lines
No, they won't. Furthermore, any kernel thread which cannot tolerate dynamic priority semantics should not use them, they should be RT.
Very few kernel threads should require RT just to work as you just said, yet you'll make it harder for them with your changed dynamic priority semantics. We already know they are not going to be misbehaving userspace tasks and they deserve simpler semantics than the full interactivity estimator gives.
They don't need to be treated special, and it is flat wrong to do so. Try the patch set and you'll see that they continue to work just fine.
Consider this: why should 10 copies of knfsd have any more right than 10 copies of apache to utterly monopolize my cpu? Fact is, there is no difference. Both are acting on behalf other user tasks. The fact that one is a kernel thread means nothing.
Quoted 10 lines
Quoted 8 lines
Quoted 5 lines
Quoted 1 line
2. Removes the priority barrier for IO.
Bad again. This caused the biggest detriment on interbench numbers and is by far the most palpable interactivity killer in linux. I/O hurts us lots and this change will be very noticeable.
This barrier is artificial, and has been demonstrated to be harmful to some loads.
Which?
Remember the demonstration of dd being starved?
Quoted 7 lines
Quoted 2 lines
Being practical, if this is demonstrated to still cause trouble, I'll happily re-introduce it with a follow-up patch.
Trouble occurs months afterwards this hits mainline since you'll get almost noone testing it in -mm. It was put there because it hurt interactivity and you're removing it because you don't like that we have to put a special case there?
Throttling changes this. Believe it or not, I didn't just run around with a machete looking for things to chop to ribbons.
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Quoted 2 lines
3. Treats
TASK_INTERACTIVEas a transition point that all tasks must stop at prior to being promoted further.Why? Makes no sense. You end up getting hiccups in the rise of priority of tasks instead of it happening smoothly with sleep.
Quoted 8 lines
Quoted 6 lines
Quite the opposite, it makes perfect sense. Taking the long sleeper to the artificial barrier of prio 16 as stock does is the very reason that thud totally destroys the interactive experience. I'd love to remove this barrier too, and have 'purity', but OTOH, the interactive border _is_ a transition point where the scheduler changes behavior. This is a transition point in fact, so treating it as such is indeed correct.
And what does it actually achieve making this change is my question?
It achieves precisely what the comment you placed there some odd years ago says it should achieve. Thud is a pure cpu hog that sleeps for a while to charge it's battery for an intentional attack. It was written specifically to demonstrate the problem with allowing a long sleep to rocket you to the top of the world as stock code does. Try running the stock kernel with irman2 and thud running, then you'll certainly understand what this change achieves.
Quoted 2 lines
I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.
Why should it degenerate? You express your concerns, I answer them. You don't have to agree with me, and I don't have to agree with you. That's no reason for the discussion to degenerate.
-Mike
Quoted 7 lines · Mike Galbraith
Quoted 2 lines · Con Kolivas
I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.
Why should it degenerate? You express your concerns, I answer them. You don't have to agree with me, and I don't have to agree with you. That's no reason for the discussion to degenerate.
By degenerate I mean get stuck in an endless loop. I don't have the energy for cyclical discussions where no conclusive endpoint can ever be reached. That is the nature of what we're discussing. Everything is some sort of compromise and you're moving one set of compromises for another which means this can be debated forever without a right or wrong.
The merits of throttling seem obvious with a sliding scale between interactivity and fairness. These other changes, to me, do not. On the interactivity side I only have interbench for hard data, and it is showing me regressions consistent with my concerns from these other "cleanups". You'll trade some other advantage for these and we'll repeat the discussion all over again. Rinse and repeat.
Cheers,
Con
Quoted 15 lines · Con Kolivas
Quoted 7 lines · Mike Galbraith
Quoted 2 lines · Con Kolivas
I feel this discussion may degenerate beyond this point. Should we say to agree to disagree at this point? I don't like these changes.
Why should it degenerate? You express your concerns, I answer them. You don't have to agree with me, and I don't have to agree with you. That's no reason for the discussion to degenerate.
By degenerate I mean get stuck in an endless loop. I don't have the energy for cyclical discussions where no conclusive endpoint can ever be reached. That is the nature of what we're discussing. Everything is some sort of compromise and you're moving one set of compromises for another which means this can be debated forever without a right or wrong.
Quoted 6 lines
The merits of throttling seem obvious with a sliding scale between interactivity and fairness. These other changes, to me, do not. On the interactivity side I only have interbench for hard data, and it is showing me regressions consistent with my concerns from these other "cleanups". You'll trade some other advantage for these and we'll repeat the discussion all over again. Rinse and repeat.
So be it. We shall agree to disagree.
I'll close with this. I'm not basing any of my changes on a benchmark, I'm basing them on real life applications and exploits written by people who were experiencing problems with their real life applications. It is my carefully considered opinion that those changes which you so strongly oppose are important.
-Mike
Con Kolivas
Acked-byQuoted 7 lines · Mike Galbraith
patch 2/6
This patch just fixes a bug waiting for a place to happen. If anyone ever decides to use
TASK_NONINTERACTIVEalong withTASK_UNINTERRUPTIBLE, bad things will happen.Signed-off-by Mike Galbraith <[email protected]>
Quoted 1 line · Mike Galbraith
Greetings,
/me waves
Quoted 2 lines
Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.
Looks good. Actually now < p->timestamp is not going to only happen on SMP. Once every I don't know how often the sched_clock seems to return a value that appears to have been in the past (I believe Peter has instrumented this).
kernel/sched.c line 816
Quoted 3 lines
Signed-off-by Mike Galbraith <[email protected]>kernel/sched.c renamed from kernel/sched.c.org +1
-0+ __sleep_time =0ULL ;
I don't think the ULL is necessary.
Quoted 8 lines
kernel/sched.c renamed from kernel/sched.c.org +2
-2-unsigned long long now; +unsigned long long now, comp; - now =sched_clock (); + now = comp =sched_clock ();#ifdef CONFIG_SMP if (!local) {/* Compensate for drifting sched_clock */
kernel/sched.c line 897
Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +2
-2runqueue_t *this_rq =this_rq (); - now = (now - this_rq->timestamp_last_tick) + comp = (now - this_rq->timestamp_last_tick) + rq->timestamp_last_tick; }#endif if (!rt_task (p)) - p->prio =recalc_task_prio (p, now); + p->prio =recalc_task_prio (p, comp);
Seems wasteful of a very expensive (on 32bit) unsigned long long on uniprocessor builds.
Cheers,
Con
Quoted 9 lines · Con Kolivas
Quoted 1 line · Mike Galbraith
Greetings,
/me waves
Quoted 2 lines
Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.
Looks good. Actually now <
p->timestampis not going to only happen on SMP. Once every I don't know how often thesched_clockseems to return a value that appears to have been in the past (I believe Peter has instrumented this).
I haven't bothered to check if it still occurs for quite a long while. I just check for time deltas being negative and if they are negative I make them zero and move on. As far as I can remember I only ever saw this when measuring "delay" (i.e. time on the run queue waiting to get on to a CPU which can be quite short :-) when the systems not heavily loaded) as other time intervals that I measure (i.e. time on CPU and sleep time) are generally long enough for the error in the delta not being big enough to make the value negative.
Quoted 22 lines
kernel/sched.c line 816
Quoted 4 lines
Signed-off-by Mike Galbraith <[email protected]>kernel/sched.c renamed from kernel/sched.c.org +1
-0+ __sleep_time =0ULL ;I don't think the ULL is necessary.
Quoted 15 lines
kernel/sched.c renamed from kernel/sched.c.org +3
-3-unsigned long long now; +unsigned long long now, comp; - now =sched_clock (); + now = comp =sched_clock ();#ifdef CONFIG_SMP if (!local) {/* Compensate for drifting sched_clock */ runqueue_t *this_rq =this_rq (); - now = (now - this_rq->timestamp_last_tick) + comp = (now - this_rq->timestamp_last_tick) + rq->timestamp_last_tick; }#endif
Quoted 5 lines
kernel/sched.c line 897
Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c.org +1
-1if (!rt_task (p)) - p->prio =recalc_task_prio (p, now); + p->prio =recalc_task_prio (p, comp);Seems wasteful of a very expensive (on 32bit) unsigned long long on uniprocessor builds.
Unsigned long long is necessary in order to avoid overflow when dealing with nano seconds but (if you reorganized the expressions and made the desired precedence explicit) you could probably use something smaller for the difference between the two timestamp_lats_tick values. More importantly, I think that the original code which used the computed "now" was correct as otherwise the task's timestamp will not have the correct time for its CPU.
Of course, this all hinges on the differences between the run queues' timestamp_last_tick fields being a true measure of the time drift between them. I've never been wholly convinced of that but as long as any error is much smaller than the drift it's probably worth doing.
Peter
PS I think that some inline functions to handle timestamp adjustment wouldn't hurt.
PPS I'm not sure that the timstamp adjustment in __migrate_task() is completely valid as the timestamp will be modified in activate_task() using the wrong clock. I need to study this more to see if I convince myself one way or the other.
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 9 lines · Peter Williams
Quoted 6 lines · Con Kolivas
kernel/sched.c line 897
Quoted 3 lines
kernel/sched.c renamed from kernel/sched.c.org +1
-1if (!rt_task (p)) - p->prio =recalc_task_prio (p, now); + p->prio =recalc_task_prio (p, comp);Seems wasteful of a very expensive (on 32bit) unsigned long long on uniprocessor builds.
Quoted 7 lines
Unsigned long long is necessary in order to avoid overflow when dealing with nano seconds but (if you reorganized the expressions and made the desired precedence explicit) you could probably use something smaller for the difference between the two
timestamp_lats_tickvalues. More importantly, I think that the original code which used the computed "now" was correct as otherwise the task's timestamp will not have the correct time for its CPU.
I can live with it either way. On my SMT box, the rounding is much worse than the actual drift, that's microseconds, but the rounding turns it into milliseconds.
Quoted 4 lines
Of course, this all hinges on the differences between the run queues'
timestamp_last_tickfields being a true measure of the time drift between them. I've never been wholly convinced of that but as long as any error is much smaller than the drift it's probably worth doing.
On a real SMP, this adjusting of timestamps probably helps (dunno, no have), on my box it's doomed to do more harm than good. To me, the only thing that really matters is ignoring the bogus transition.
-Mike
PATCH 1/1 ignore timewarps
Greetings,
The patch below is a correction to patch 1 of my throttling tree series.
The only thing that really matters is that timewarps are ignored, whatever the cause. This patch does that, and only that.
-Mike
kernel/sched.c renamed from kernel/sched.c.org +9 -0
@@ -805,6 +805,15 @@unsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time; +/* +* On SMP systems, a task can go to sleep on one CPU +* and wake up on another. When this happens, now can +* end up being less than p->timestamp for short sleeps. +* Ignore these, they're insignificant. +*/ +if (unlikely (now < p->timestamp)) + __sleep_time =0 ; +if (batch_task (p)) sleep_time =0 ;else {
Quoted 15 lines · Mike Galbraith
Greetings,
I've broken down my throttling tree into 6 patches, which I'll send as replies to this start-point.
Patch 1/6
Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.
Signed-off-by Mike Galbraith <[email protected]>
kernel/sched.c line 811
Quoted 7 lines
kernel/sched.c renamed from kernel/sched.c.org +4
-0@@ -805,6 +805,16 @@unsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time; +/* +* On SMP systems, a task can go to sleep on one CPU and +* wake up on another. When this happens, the timestamp +* is rounded to the nearest tick,
Is this true? There's no rounding that I can see. An attempt is made to adjust the timestamp for the drift between time as seen from the two CPUs but there's no deliberate rounding involved. Of course, that's not to say that the adjustment is accurate as I'm not convinced that the difference between the run queues' timestamp_last_tick is a always totally accurate measure of the drift in their clocks (due to possible races -- I may be wrong).
Of course, that doesn't mean that this chunk of code isn't required just that the comment is misleading.
Quoted 25 lines
which can lead to now
kernel/sched.c renamed from kernel/sched.c.org +9
-3+* being less than p->timestamp for short sleeps. Ignore +* these, they're insignificant. +*/ +if (unlikely (now < p->timestamp)) + __sleep_time =0ULL ; +if (batch_task (p)) sleep_time =0 ;else {@@ -871,20 +881,20 @@*/ static void activate_task (task_t *p,runqueue_t *rq,int local) { -unsigned long long now; +unsigned long long now, comp; - now =sched_clock (); + now = comp =sched_clock ();#ifdef CONFIG_SMP if (!local) {/* Compensate for drifting sched_clock */ runqueue_t *this_rq =this_rq (); - now = (now - this_rq->timestamp_last_tick) + comp = (now - this_rq->timestamp_last_tick)
kernel/sched.c line 900
Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +1
-1+ rq->timestamp_last_tick; }#endif if (!rt_task (p)) - p->prio =recalc_task_prio (p, now); + p->prio =recalc_task_prio (p, comp);/* * This checks to make sure it's not an uninterruptible task
I think that this will end up with p->timestamp being set with a time appropriate to the current task's CPU rather than its own.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Quoted 19 lines · Peter Williams
Quoted 18 lines · Mike Galbraith
Greetings,
I've broken down my throttling tree into 6 patches, which I'll send as replies to this start-point.
Patch 1/6
Ignore timewarps caused by SMP timestamp rounding. Also, don't stamp a task with a computed timestamp, stamp with the already called clock.
Signed-off-by Mike Galbraith <[email protected]>kernel/sched.c renamed from kernel/sched.c.org +0
-0@@ -805,6 +805,16 @@unsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time;
Quoted 6 lines
kernel/sched.c
Quoted 4 lines
kernel/sched.c renamed from kernel/sched.c.org +4
-0+/* +* On SMP systems, a task can go to sleep on one CPU and +* wake up on another. When this happens, the timestamp +* is rounded to the nearest tick, Is this true? There's no rounding that I can see.
Instrumenting it looked the same as rounding down, putting now in the past was the result.
Quoted 2 lines
Of course, that doesn't mean that this chunk of code isn't required just that the comment is misleading.
I'm not attached to the comment.
-Mike