Task Throttling V9
Subsystems (3)
PATCH 1/1 Task Throttling V9
Greetings,
Below, please find the latest version of my task throttling attempt.
What the patch addresses:
The current interactivity heuristics are so heavily slanted in favor of tasks which sleep at all, that any task which sleeps for 5% of the time can use 95% cpu forever. Even if this slant were removed, became linear again, any task which sleeps even a tiny bit longer than it runs will eventually attain maximum dynamic priority.
That said, the current heuristics work very well in the general case. When they fail, however, it can get pretty darn ugly. That is the problem space this patch attempts to address, and does pretty well at. It tries to solve the nasty corner cases.
How it works is by no means rocket science, and is described in the comments of the first hunk of sched.c changes.
In addition to the throttling, this simple patch does three things (more?) which may be controversial.
1. It removes the barrier between kernel threads and user tasks wrt the handling of dynamic priority.
2. It changes the meaning of INTERACTIVE_SLEEP() a little.
3. It removes TASK_NONINTERACTIVE from fs/pipe.c
My argument for #1: Either dynamic priority is fully applicable or not at all. If any kernel thread really needs to be exempt from any aspect of dynamic priority, it should be in a different scheduling class.
My argument for #2: The boundary established by TASK_INTERACTIVE() is a portal, and should be treated as such. This patch does not establish the boundary, it only enforces it. It also adds a very modest level of caution to the promotion of tasks beyond the interactive task boundary. One single 10ms sleep will no longer take a pure cpu hog to the very top.
My argument for #3: AnaroK is an mp3 player which uses pipes to communicate with its various components. I can see no that reason it should not receive the same boost as any other task. It is after all a genuine interactive task. Besides, it's no longer necessary.
Oops, there's a #4.
4. It adds knobs to the scheduler.
My argument for #4: These knobs put policy where it belongs. If the user wants a maximum interactive environment, and is willing to accept that this means some starvation comes with the deal, it's his choice. Those who have little to no tolerance for starvation can set both knobs to zero, and be happy. Both can have their cake with whatever icing they are partial to.
There may be a #5, #6... who knows, you tell me ;-)
Comments? Suggestions? Fla^H^H^H (nah... beware what you ask)
-Mike
P.S. Any interactive feel improvement inflicted upon the user by the throttling of hyperactive cpu-hog is absolutely free... as is the strangulation of their favorite mp3 player GL visualization ;-)
Not to be taken as a sign of misguided confidence, I'm just taking blame for this in all of it's ugly-is-in-the-eye-of-the-beholder glory.
include/linux/sched.h renamed from include/linux/sched.h.org +2 -2
@@ -719,14 +719,14 @@unsigned short ioprio;unsigned int btrace_seq; -unsigned long sleep_avg; +unsigned long sleep_avg, last_slice, throttle_stamp;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;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
include/linux/sysctl.h renamed from include/linux/sysctl.h.org +2 -0
@@ -147,6 +147,8 @@KERN_SETUID_DUMPABLE =69 ,/* int: behaviour of dumps for setuid core */ KERN_SPIN_RETRY =70 ,/* int: number of spinlock retries */ KERN_ACPI_VIDEO_FLAGS =71 ,/* int: flags for setting up video after ACPI sleep */ +KERN_SCHED_THROTTLE1 =72 ,/* int: throttling grace period 1 in secs */ + KERN_SCHED_THROTTLE2=73, /* int: throttling grace period 2 in secs */ };
kernel/sched.c renamed from kernel/sched.c.org +307 -26
432 lines not on this page · raw message
kernel/sysctl.c renamed from kernel/sysctl.c.org +27 -6
@@ -69,6 +69,8 @@extern int pid_max_min, pid_max_max;extern int sysctl_drop_caches;extern int percpu_pagelist_fraction; +extern int sched_g1; +extern int sched_g2;#if defined(CONFIG_X86_LOCAL_APIC ) && defined(CONFIG_X86 )int unknown_nmi_panic;
@@ -222,6 +224,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 ,
@@ -664,15 +671,29 @@ .proc_handler = &proc_dointvec, },#endif + { + .ctl_name = KERN_SCHED_THROTTLE1, + .procname = "sched_g1", + .data = &sched_g1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + .strategy = &sysctl_intvec, + .extra1 = &zero, + }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "sched_g2", + .data = &sched_g2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec, + .strategy = &sysctl_intvec, + .extra1 = &zero, + }, { .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 ,
fs/pipe.c renamed from fs/pipe.c.org +1 -5
@@ -39,11 +39,7 @@ {DEFINE_WAIT (wait); -/* -* Pipes are system-local resources, so sleeping on them -* is considered a noninteractive wait: -*/ -prepare_to_wait (PIPE_WAIT (*inode), &wait,TASK_INTERRUPTIBLE |TASK_NONINTERACTIVE ); +prepare_to_wait (PIPE_WAIT (*inode), &wait,TASK_INTERRUPTIBLE );mutex_unlock (PIPE_MUTEX (*inode));schedule ();finish_wait (PIPE_WAIT (*inode), &wait);
PATCH 1/1 Task Throttling V14
Quoted 17 lines · MIke Galbraith
Greetings,
Below, please find the latest version of my task throttling attempt.
What the patch addresses:
The current interactivity heuristics are so heavily slanted in favor of tasks which sleep at all, that any task which sleeps for 5% of the time can use 95% cpu forever. Even if this slant were removed, became linear again, any task which sleeps even a tiny bit longer than it runs will eventually attain maximum dynamic priority.
That said, the current heuristics work very well in the general case. When they fail, however, it can get pretty darn ugly. That is the problem space this patch attempts to address, and does pretty well at. It tries to solve the nasty corner cases.
...
Quoted 1 line
Comments? Suggestions? Fla^H^H^H (nah... beware what you ask)
Not many comments came back, zero actually. Probably because everyone was really busy, not because anyone felt a sudden urge to hug the ole porcelain Buddha after taking a look ;-)
Anyway, below is [imo] a very much nicer version. Functionally, throttling is fairly air tight now, and interactivity is not affected in the least afaikt. The thing works well. So well, that the nasty little fundamental problem, while not whipped, is off in a corner licking it's wounds ;-)
One kinda nifty feature about the way I do the throttling now, is that I don't need to give a sometimes hog like X the keys to the city by defining a huge window of opportunity for it's cpu use, and then trying to figure out if I should throttle it or not when it gets busy. I can leave a _zero_ length window for it, and it is quite happy. It usually has such low cpu usage, that there are plenty of spare cycles that I let it save for a rainy day. There is no free lunch though, they _will_ run out. It's automatic. When the task's savings account is empty, it hits the wall with a big splat. Interactive tasks naturally build a pool of spare cycles, whereas tasks which want excessive cpu can't.
Even if you think that last patch was too ugly to risk looking again, brace yourself, and take a peek at it anyway. There may be a nugget or two be had even if my implementation erm... isn't the most beautiful bit of code you've seen lately. The throttling idea works just fine, and among the low hanging fruit, there's the fact that I don't miss the sleep multiplier I ripped out even a tiny little bit. If anyone actually tries this patch out [recommended] , they'll see what I mean. Try a make -j5 kernel build on a fairly slow nfs mount. That has absolutely nothing to do with the quite functional throttling, it's the result of interactivity logic tweaks I was kinda-sorta-forced to do along the way.
Cheers,
-Mike
fs/pipe.c | 6 include/linux/sched.h | 4 include/linux/sysctl.h | 2 kernel/sched.c | 332 ++++++++++++++++++++++++++++++++++++++++++++----- kernel/sysctl.c | 36 ++++- 5 files changed, 336 insertions(+), 44 deletions(-)
diffstat looks really obese, but it's not as fat as it looks.
include/linux/sched.h renamed from include/linux/sched.h.org +2 -2
@@ -712,14 +712,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;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
include/linux/sysctl.h renamed from include/linux/sysctl.h.org +2 -0
@@ -147,6 +147,8 @@KERN_SETUID_DUMPABLE =69 ,/* int: behaviour of dumps for setuid core */ KERN_SPIN_RETRY =70 ,/* int: number of spinlock retries */ KERN_ACPI_VIDEO_FLAGS =71 ,/* int: flags for setting up video after ACPI sleep */ +KERN_SCHED_THROTTLE1 =72 ,/* int: throttling grace period 1 in secs */ + KERN_SCHED_THROTTLE2=73, /* int: throttling grace period 2 in secs */ };
kernel/sched.c renamed from kernel/sched.c.org +301 -31
440 lines not on this page · raw message
kernel/sysctl.c renamed from kernel/sysctl.c.org +30 -6
@@ -72,6 +72,9 @@extern int pid_max_min, pid_max_max;extern int sysctl_drop_caches;extern int percpu_pagelist_fraction; +extern int sched_g1; +extern int sched_g2; +extern int sched_g2_max;#if defined(CONFIG_X86_LOCAL_APIC ) && defined(CONFIG_X86 )int unknown_nmi_panic;
@@ -225,6 +228,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 ,
@@ -669,15 +677,31 @@ .proc_handler = &proc_dointvec, },#endif + { + .ctl_name = KERN_SCHED_THROTTLE1, + .procname = "sched_g1", + .data = &sched_g1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &sched_g2_max, + }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "sched_g2", + .data = &sched_g2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &sched_g2_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 ,
fs/pipe.c renamed from fs/pipe.c.org +1 -5
@@ -39,11 +39,7 @@ {DEFINE_WAIT (wait); -/* -* Pipes are system-local resources, so sleeping on them -* is considered a noninteractive wait: -*/ -prepare_to_wait (PIPE_WAIT (*inode), &wait,TASK_INTERRUPTIBLE |TASK_NONINTERACTIVE ); +prepare_to_wait (PIPE_WAIT (*inode), &wait,TASK_INTERRUPTIBLE );mutex_unlock (PIPE_MUTEX (*inode));schedule ();finish_wait (PIPE_WAIT (*inode), &wait);
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 3 lines · MIke Galbraith
Not many comments came back, zero actually.
That's because everyone's terribly busy chasing down those final bugs so we get a really great 2.6.16 release (heh, I kill me).
I'm a bit reluctant to add changes like this until we get the smpnice stuff settled down and validated. I guess that means once Ken's run all his performance tests across it.
Of course, if Ken does his testing with just mainline+smpnice then any coupling becomes less of a problem. But I would like to see some feedback from the other sched developers first.
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 9 lines · Andrew Morton
Quoted 2 lines · MIke Galbraith
Not many comments came back, zero actually.
That's because everyone's terribly busy chasing down those final bugs so we get a really great 2.6.16 release (heh, I kill me).
Quoted 7 lines
I'm a bit reluctant to add changes like this until we get the smpnice stuff settled down and validated. I guess that means once Ken's run all his performance tests across it.
Of course, if Ken does his testing with just mainline+smpnice then any coupling becomes less of a problem. But I would like to see some feedback from the other sched developers first.
Personally, I'd rather see PlugSched merged in and this patch be used to create a new scheduler inside PlugSched. But I'm biased :-)
As I see it, the problem that this patch is addressing is caused by the fact that the current scheduler is overly complicated. This patch just makes it more complicated. Some of the schedulers in PlugSched already handle this problem adequately and some of them are simpler than the current scheduler -- the intersection of these two sets is not empty.
So now that it's been acknowledged that the current scheduler has problems, I think that we should be looking at other solutions in addition to just making the current one more complicated.
Peter
PS I agree this should wait until the current scheduler changes in -mm have had a chance to settle down and/or migrate to the vanilla kernel.
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 18 lines · Peter Williams
Quoted 9 lines · Andrew Morton
Quoted 2 lines · MIke Galbraith
Not many comments came back, zero actually.
That's because everyone's terribly busy chasing down those final bugs so we get a really great 2.6.16 release (heh, I kill me).
Quoted 7 lines
I'm a bit reluctant to add changes like this until we get the smpnice stuff settled down and validated. I guess that means once Ken's run all his performance tests across it.
Of course, if Ken does his testing with just mainline+smpnice then any coupling becomes less of a problem. But I would like to see some feedback from the other sched developers first.
Quoted 6 lines
Personally, I'd rather see PlugSched merged in and this patch be used to create a new scheduler inside PlugSched. But I'm biased :-)
As I see it, the problem that this patch is addressing is caused by the fact that the current scheduler is overly complicated. This patch just makes it more complicated.
What's complicated about the scheduler? I see simple/elegant when I look in there. Interaction with the user is complex, but interactive feel is a nebulous thing not restricted to this scheduler.
I really don't think this patch adds complexity, quite the opposite actually. It just does a small bit of tweaking to the scheduler's weak spot, and adds a dirt simple barrier against starvation. IMO, this scheduler is not only quite simple, it's one weakness is generally wonderful for throughput. It's just that it's sometimes a bit _too_ wonderful ;-)
-Mike
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
In reply to Peter WilliamsQuoted 20 lines · Peter Williams
Quoted 9 lines · Andrew Morton
Quoted 2 lines · MIke Galbraith
Not many comments came back, zero actually.
That's because everyone's terribly busy chasing down those final bugs so we get a really great 2.6.16 release (heh, I kill me).
Quoted 7 lines
I'm a bit reluctant to add changes like this until we get the smpnice stuff settled down and validated. I guess that means once Ken's run all his performance tests across it.
Of course, if Ken does his testing with just mainline+smpnice then any coupling becomes less of a problem. But I would like to see some feedback from the other sched developers first.
Quoted 6 lines
Personally, I'd rather see PlugSched merged in and this patch be used to create a new scheduler inside PlugSched. But I'm biased :-)
As I see it, the problem that this patch is addressing is caused by the fact that the current scheduler is overly complicated. This patch just makes it more complicated. Some of the schedulers in PlugSched already handle this problem adequately and some of them are simpler than the current scheduler -- the intersection of these two sets is not empty.
So now that it's been acknowledged that the current scheduler has problems, I think that we should be looking at other solutions in addition to just making the current one more complicated.
I tried this angle years ago and it didn't work :)
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 28 lines · Nick Piggin
Quoted 27 lines · Peter Williams
Quoted 12 lines · Andrew Morton
Quoted 1 line · MIke Galbraith
Not many comments came back, zero actually.
That's because everyone's terribly busy chasing down those final bugs so we
get a really great 2.6.16 release (heh, I kill me).I'm a bit reluctant to add changes like this until we get the smpnice stuff
settled down and validated. I guess that means once Ken's run all his performance tests across it.Quoted 4 lines
Of course, if Ken does his testing with just mainline+smpnice then any coupling becomes less of a problem. But I would like to see some feedback
from the other sched developers first.Personally, I'd rather see PlugSched merged in and this patch be used to create a new scheduler inside PlugSched. But I'm biased :-)
As I see it, the problem that this patch is addressing is caused by the fact that the current scheduler is overly complicated. This patch just makes it more complicated. Some of the schedulers in PlugSched already handle this problem adequately and some of them are simpler than the current scheduler -- the intersection of these two sets is not empty.
Quoted 5 lines
Quoted 3 lines
So now that it's been acknowledged that the current scheduler has problems, I think that we should be looking at other solutions in addition to just making the current one more complicated.
I tried this angle years ago and it didn't work :)
Our "2.6 forever" policy is why we're stuck with this approach. We tried alternative implementations in -mm for a while but like all alternatives they need truckloads more testing to see if they provide a real advantage and don't cause any regressions. This made it impossible to seriously consider any alternatives.
I hacked on and pushed plugsched in an attempt to make it possible to work on an alternative implementation that would make the transition possible in a stable series. This was vetoed by Linus and Ingo and yourself for the reason it dilutes developer effort on the current scheduler. Which leaves us with only continually polishing what is already in place.
None of this is news of course but it helps to set the history for outside observers of this thread.
Cheers,
Con
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 9 lines · Con Kolivas
Quoted 1 line · Nick Piggin
I tried this angle years ago and it didn't work :)
Our "2.6 forever" policy is why we're stuck with this approach. We tried alternative implementations in -mm for a while but like all alternatives they need truckloads more testing to see if they provide a real advantage and don't cause any regressions. This made it impossible to seriously consider any alternatives.
I hacked on and pushed plugsched in an attempt to make it possible to work on an alternative implementation that would make the transition possible in a stable series. This was vetoed by Linus and Ingo and yourself for the reason it dilutes developer effort on the current scheduler. Which leaves us with only continually polishing what is already in place.
Yes. Hence my one-liner.
I still don't think plugsched is that good of an idea for mainline. Not too many people seem to be unhappy with the scheduler we have, so just because this little problem comes up I don't think that means it's time to give up and merge plugsched and 10 other policies.
Signature · 2 lines
SUSE Labs, Novell Inc. Send instant messages to your online friends http://au.messenger.yahoo.com
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 19 lines · Nick Piggin
Quoted 11 lines · Con Kolivas
Quoted 1 line · Nick Piggin
I tried this angle years ago and it didn't work :)
Our "2.6 forever" policy is why we're stuck with this approach. We tried alternative implementations in -mm for a while but like all alternatives they need truckloads more testing to see if they provide a real advantage and don't cause any regressions. This made it impossible to seriously consider any alternatives.
Quoted 6 lines
I hacked on and pushed plugsched in an attempt to make it possible to work on an alternative implementation that would make the transition possible in a stable series. This was vetoed by Linus and Ingo and yourself for the reason it dilutes developer effort on the current scheduler. Which leaves us with only continually polishing what is already in place.
Quoted 6 lines
Yes. Hence my one-liner.
I still don't think plugsched is that good of an idea for mainline. Not too many people seem to be unhappy with the scheduler we have, so just because this little problem comes up I don't think that means it's time to give up and merge plugsched and 10 other policies.
Agreed. The problem is small. Annoying, because it refuses to go away, but it is a small problem.
-Mike
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
In reply to Andrew MortonQuoted 10 lines · Andrew Morton
Quoted 3 lines · MIke Galbraith
Not many comments came back, zero actually.
That's because everyone's terribly busy chasing down those final bugs so we get a really great 2.6.16 release (heh, I kill me).
I'm a bit reluctant to add changes like this until we get the smpnice stuff settled down and validated.
I agree 100% on all counts. If this, or even something like it, is considered, it absolutely does need testing without other flavors in the soup.
-Mike
PATCH 1/1 sched_cleanup-V17 - task throttling patch 1 of 2
Greetings,
Below, please find part 1 of my latest task throttling effort. I've very nearly completely reworked it from top to bottom, and broken it down into separate cleanup and a throttling diffs.
Main things that this diff does:
1. Closes a generic hole in the scheduler design: due to timeslice sample rate of HZ, tasks can and do steal time from each other. Generally this is no big deal, because statistics more or less even things out, but tasks with a high scheduling frequency and a low execution duration can steal considerable time. No longer.
2. Removes overhead from the fast path. There's no need to do division in the fast path, it's cheaper to do it at timeslice refresh time, where it accomplishes the same thing at a fraction of the cost. Trades a subtraction for a division, and removes the obsoleted bits that led to the division.
I have verified that the testcase sent in by David Mosberg ages ago, and which was the prime motivator for going to nanosecond timings in the scheduler in the first place, is not broken by the above changes.
3. Removes the disparity in the handling of dynamic priority for kernel threads verses user-land tasks.
4. Fixes a boot-time buglet where the TSC isn't synchronized yet, resulting in recalc_task_prio() being called with now < p->timestamp. If you place a WARN_ON there, the box won't even boot. With this fix, you'll get one warning, and then all goes fine.
5. Fixes a couple of would-be bugs if anyone ever decided to use TASK_NONINTERACTIVE thing along with TASK_UNINTERRUPTIBLE.
6. Removes sleep_avg multiplier. Back when we had 10s of dynamic range, this was needed to help get interactive tasks up to speed. The 10 time speedup meant that a 1s sleep put us at max priority. Worked great. As we speak however, we have _1_ second of dynamic range, and this gets compressed to 100ms by the multiplier. This is very bad, and to see how bad, just try a very modest parallel kernel compile in a relatively slow NFS mounted filesystem. In heavy testing, I can find no detriment to removing this anachronism.
7. Assorted cleanups to the interactivity logic.
8. Whatever I forgot to mention ;-)
Comments?
-Mike
Signed-off-by Mike Galbraith <[email protected]>
include/linux/sched.h | 3 - kernel/sched.c | 136 +++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
include/linux/sched.h renamed from include/linux/sched.h.org +2 -1
@@ -720,7 +720,8 @@unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice; +unsigned int first_time_slice;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
kernel/sched.c renamed from kernel/sched.c.org +80 -56
271 lines not on this page · raw message
PATCH 1/1 sched_throttle-V17 - task throttling patch 2 of 2
Diff 2 of 2, the throttling itself. Primary changes since the last version is that I no longer dink around with the task's priority directly. Carefully trimming excess sleep_avg at timeslice refresh time works just about as well, and makes the patch look a heck of a lot better.
I've also done away with a division that was in the fast path, and fixed a bug in the 'concession to interactivity' bits in refresh_timeslice() which had it working more by accident than design. With this diff, I can set grace_g0 to zero seconds, and still have a very nice interactive kernel. grace_g2 has to be also set to zero to completely disable interactivity logic.
Comments?
-Mike
include/linux/sched.h | 4 include/linux/sysctl.h | 2 kernel/sched.c | 249 +++++++++++++++++++++++++++++++++++++++++++++---- kernel/sysctl.c | 36 +++++-- 4 files changed, 267 insertions(+), 24 deletions(-)
include/linux/sched.h renamed from include/linux/sched.h.org +2 -2
@@ -713,7 +713,7 @@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;
@@ -721,7 +721,7 @@unsigned long policy;cpumask_t cpus_allowed;int time_slice; -unsigned int first_time_slice; +unsigned int slice_info;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
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 grace period 1 in secs */ + KERN_SCHED_THROTTLE2=74, /* int: throttling grace period 2 in secs */ };
kernel/sched.c renamed from kernel/sched.c.org +233 -16
308 lines not on this page · raw message
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 grace_g1; +extern int grace_g2; +extern int grace_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 = "grace_g1", + .data = &grace_g1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &grace_max, + }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "grace_g2", + .data = &grace_g2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &grace_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 ,
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Mike GalbraithQuoted 44 lines · Mike Galbraith
Greetings,
Below, please find part 1 of my latest task throttling effort. I've very nearly completely reworked it from top to bottom, and broken it down into separate cleanup and a throttling diffs.
Main things that this diff does:
1. Closes a generic hole in the scheduler design: due to timeslice sample rate of HZ, tasks can and do steal time from each other. Generally this is no big deal, because statistics more or less even things out, but tasks with a high scheduling frequency and a low execution duration can steal considerable time. No longer.
2. Removes overhead from the fast path. There's no need to do division in the fast path, it's cheaper to do it at timeslice refresh time, where it accomplishes the same thing at a fraction of the cost. Trades a subtraction for a division, and removes the obsoleted bits that led to the division.
I have verified that the testcase sent in by David Mosberg ages ago, and which was the prime motivator for going to nanosecond timings in the scheduler in the first place, is not broken by the above changes.
3. Removes the disparity in the handling of dynamic priority for kernel threads verses user-land tasks.
4. Fixes a boot-time buglet where the TSC isn't synchronized yet, resulting in
recalc_task_prio()being called with now <p->timestamp. If you place aWARN_ONthere, the box won't even boot. With this fix, you'll get one warning, and then all goes fine.5. Fixes a couple of would-be bugs if anyone ever decided to use
TASK_NONINTERACTIVEthing along withTASK_UNINTERRUPTIBLE.6. Removes
sleep_avgmultiplier. Back when we had 10s of dynamic range, this was needed to help get interactive tasks up to speed. The 10 time speedup meant that a 1s sleep put us at max priority. Worked great. As we speak however, we have _1_ second of dynamic range, and this gets compressed to 100ms by the multiplier. This is very bad, and to see how bad, just try a very modest parallel kernel compile in a relatively slow NFS mounted filesystem. In heavy testing, I can find no detriment to removing this anachronism.
Quoted 5 lines
7. Assorted cleanups to the interactivity logic.
8. Whatever I forgot to mention ;-)
Comments?
If you're going to manage the time slice in nanoseconds why not do it properly? I presume you've held back a bit in case you break something?
If it helps, the smpnice balancing code's use of static_prio_timeslice()
doesn't really care what units it's return value is in as long as DEF_TIMESLICE is in the same units and contains the size of a time slice allocated to a nice==0 non RT task.
Quoted 314 lines
-Mike
Signed-off-by Mike Galbraith <[email protected]>
include/linux/sched.h | 3 - kernel/sched.c | 136 +++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)include/linux/sched.h renamed from include/linux/sched.h.org +2
-1@@ -720,7 +720,8 @@unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice; +unsigned int first_time_slice;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;kernel/sched.c renamed from kernel/sched.c.org +80
-56@@ -99,6 +99,10 @@#define MAX_SLEEP_AVG (DEF_TIMESLICE * MAX_BONUS)#define STARVATION_LIMIT (MAX_SLEEP_AVG)#define NS_MAX_SLEEP_AVG (JIFFIES_TO_NS(MAX_SLEEP_AVG)) +#define NS_MAX_SLEEP_AVG_PCNT (NS_MAX_SLEEP_AVG / 100) +#define PCNT_PER_DYNPRIO (100 / MAX_BONUS) +#define NS_PER_DYNPRIO (PCNT_PER_DYNPRIO * NS_MAX_SLEEP_AVG_PCNT) +#define NS_TICK (JIFFIES_TO_NS(1))/* * If a task is 'interactive' then we reinsert it in the active @@ -153,9 +157,25 @@#define TASK_INTERACTIVE (p) \ ((p)->prio <= (p)->static_prio - DELTA(p)) -#define INTERACTIVE_SLEEP (p) \ - (JIFFIES_TO_NS(MAX_SLEEP_AVG * \ - (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1)) +#define SLEEP_AVG_DIVISOR (p) (1 + CURRENT_BONUS(p)) + +#define INTERACTIVE_SLEEP_AVG (p) \ + (min(JIFFIES_TO_NS(MAX_SLEEP_AVG * (MAX_BONUS / 2 + DELTA(p)) / \ + MAX_BONUS), NS_MAX_SLEEP_AVG)) + +/* +* Returns whether a task has been asleep long enough to be considered idle. +* The metric is whether this quantity of sleep would promote the task more +* than one priority beyond marginally interactive. +*/ +static int task_interactive_idle (task_t *p,unsigned long sleep_time) +{ +unsigned long ceiling = (CURRENT_BONUS (p) +2 ) *NS_PER_DYNPRIO ; + +if (p->sleep_avg + sleep_time < ceiling) +return 0 ; +return p->sleep_avg + sleep_time >=INTERACTIVE_SLEEP_AVG (p); +}#define TASK_PREEMPTS_CURR (p, rq) \ ((p)->prio < (rq)->curr->prio)@@ -182,7 +202,7 @@static inline unsigned int task_timeslice (task_t *p) { -return static_prio_timeslice (p->static_prio); +return JIFFIES_TO_NS (static_prio_timeslice (p->static_prio)); }#define task_hot (p, now, sd) ((long long) ((now) - (p)->last_ran) \@@ -240,6 +260,7 @@unsigned long expired_timestamp;unsigned long long timestamp_last_tick; +unsigned long long timestamp_last_switch;task_t *curr, *idle;struct mm_struct *prev_mm;prio_array_t *active, *expired, arrays[2 ];@@ -777,6 +798,9 @@unsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time; +if (unlikely (now < p->timestamp)) + __sleep_time =0ULL ; +if (unlikely (p->policy ==SCHED_BATCH )) sleep_time =0 ;else {@@ -788,32 +812,32 @@if (likely (sleep_time >0 )) {/* -* User tasks that sleep a long time are categorised as -* idle. They will only have their sleep_avg increased to a +* Tasks that sleep a long time are categorised as idle. +* They will only have their sleep_avg increased to a * level that makes them just interactive priority to stay * active yet prevent them suddenly becoming cpu hogs and * starving other processes. */ -if (p->mm && sleep_time >INTERACTIVE_SLEEP (p)) { -unsigned long ceiling; - - ceiling =JIFFIES_TO_NS (MAX_SLEEP_AVG - -DEF_TIMESLICE ); -if (p->sleep_avg < ceiling) - p->sleep_avg = ceiling; - }else { +if (task_interactive_idle (p, sleep_time)) { +unsigned long ceiling =INTERACTIVE_SLEEP_AVG (p);/* -* The lower the sleep avg a task has the more -* rapidly it will rise with sleep time. This enables -* tasks to rapidly recover to a low latency priority. -* If a task was sleeping with the noninteractive -* label do not apply this non-linear boost +* Promote previously interactive task. */ -if (p->sleep_type !=SLEEP_NONINTERACTIVE || !p->mm) - sleep_time *= - (MAX_BONUS -CURRENT_BONUS (p)) ? :1 ; +if (p->sleep_avg > ceiling) { + ceiling = p->sleep_avg /NS_PER_DYNPRIO ; +if (ceiling <MAX_BONUS ) + ceiling++; + ceiling *=NS_PER_DYNPRIO ; + }else { + ceiling += p->time_slice >>2 ; +if (ceiling >NS_MAX_SLEEP_AVG ) + ceiling =NS_MAX_SLEEP_AVG ; + } +if (p->sleep_avg < ceiling) + p->sleep_avg = ceiling; + }else {/* * This code gives a bonus to interactive tasks. * @@ -1367,7 +1391,8 @@ out_activate:#endif /* CONFIG_SMP */ -if (old_state ==TASK_UNINTERRUPTIBLE ) { + +if (old_state &TASK_UNINTERRUPTIBLE ) { rq->nr_uninterruptible--;/* * Tasks waking from uninterruptible sleep are likely @@ -1461,6 +1486,8 @@*/ local_irq_disable (); p->time_slice = (current->time_slice +1 ) >>1 ; +if (unlikely (p->time_slice <NS_TICK )) + p->time_slice =NS_TICK ;/* * The remainder of the first timeslice might be recovered by * the parent if the child exits early enough. @@ -1468,13 +1495,12 @@ p->first_time_slice =1 ; current->time_slice >>=1 ; p->timestamp =sched_clock (); -if (unlikely (!current->time_slice)) { +if (unlikely (current->time_slice <NS_TICK )) {/* * This case is rare, it happens when the parent has only * a single jiffy left from its timeslice. Taking the * runqueue lock is not a problem. */ - current->time_slice =1 ;scheduler_tick (); }local_irq_enable ();@@ -2586,6 +2612,7 @@ {unsigned long long last =max (p->timestamp, rq->timestamp_last_tick); p->sched_time += now - last; + p->time_slice -= now - last; }/* @@ -2735,8 +2762,8 @@* RR tasks need a special form of timeslice management. * FIFO tasks have no timeslices. */ -if ((p->policy ==SCHED_RR ) && !--p->time_slice) { - p->time_slice =task_timeslice (p); +if ((p->policy ==SCHED_RR ) && p->time_slice <NS_TICK ) { + p->time_slice +=task_timeslice (p); p->first_time_slice =0 ;set_tsk_need_resched (p);@@ -2745,11 +2772,21 @@ } goto out_unlock; } -if (!--p->time_slice) { +if (p->time_slice <NS_TICK ) { +int time_slice =task_timeslice (p); +int run_time = time_slice - p->time_slice;dequeue_task (p, rq->active);set_tsk_need_resched (p); + p->time_slice += time_slice; +/* +* Tasks are charged proportionately less run_time at high +* sleep_avg to delay them losing their interactive status +*/ + run_time /=SLEEP_AVG_DIVISOR (p); + p->sleep_avg -= run_time; +if ((long )p->sleep_avg <0 ) + p->sleep_avg =0 ; p->prio =effective_prio (p); - p->time_slice =task_timeslice (p); p->first_time_slice =0 ;if (!rq->expired_timestamp)@@ -2777,13 +2814,17 @@* This only applies to tasks in the interactive * delta range with at least TIMESLICE_GRANULARITY to requeue. */ -if (TASK_INTERACTIVE (p) && !((task_timeslice (p) - - p->time_slice) %TIMESLICE_GRANULARITY (p)) && - (p->time_slice >=TIMESLICE_GRANULARITY (p)) && - (p->array == rq->active)) { +if (p->array == rq->active) { +unsigned long runtime, period; -requeue_task (p, rq->active); -set_tsk_need_resched (p); + runtime = now - rq->timestamp_last_switch; + period =JIFFIES_TO_NS (TIMESLICE_GRANULARITY (p)); + +if (runtime >= period && p->time_slice >>1 >= period) { +requeue_task (p, rq->active); +set_tsk_need_resched (p); + rq->timestamp_last_switch = now; + } } } out_unlock:@@ -2851,7 +2892,8 @@*/ static inline unsigned long smt_slice (task_t *p,struct sched_domain *sd) { -return p->time_slice * (100 - sd->per_cpu_gain) /100 ; +int time_slice =NS_TO_JIFFIES (p->time_slice) ? :1 ; +return time_slice * (100 - sd->per_cpu_gain) /100 ; }static int dependent_sleeper (int this_cpu,runqueue_t *this_rq)@@ -3014,7 +3056,6 @@prio_array_t *array;struct list_head *queue;unsigned long long now; -unsigned long run_time;int cpu, idx, new_prio;/* @@ -3050,19 +3091,6 @@schedstat_inc (rq, sched_cnt); now =sched_clock (); -if (likely ((long long )(now - prev->timestamp) <NS_MAX_SLEEP_AVG )) { - run_time = now - prev->timestamp; -if (unlikely ((long long )(now - prev->timestamp) <0 )) - run_time =0 ; - }else - run_time =NS_MAX_SLEEP_AVG ; - -/* -* Tasks charged proportionately less run_time at high sleep_avg to -* delay them losing their interactive status -*/ - run_time /= (CURRENT_BONUS (prev) ? :1 ); -spin_lock_irq (&rq->lock);if (unlikely (prev->flags &PF_DEAD ))@@ -3075,7 +3103,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); }@@ -3136,7 +3164,6 @@if (next->sleep_type ==SLEEP_INTERACTIVE ) delta = delta * (ON_RUNQUEUE_WEIGHT *128 /100 ) /128 ; - array = next->array; new_prio =recalc_task_prio (next, next->timestamp + delta);if (unlikely (next->prio != new_prio)) {@@ -3156,14 +3183,11 @@update_cpu_clock (prev, rq, now); - prev->sleep_avg -= run_time; -if ((long )prev->sleep_avg <=0 ) - prev->sleep_avg =0 ; prev->timestamp = prev->last_ran = now;sched_info_switch (prev, next);if (likely (prev != next)) { - next->timestamp = now; + next->timestamp = rq->timestamp_last_switch = now; rq->nr_switches++; rq->curr = next; ++*switch_count;
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 3 lines · Peter Williams
If you're going to manage the time slice in nanoseconds why not do it properly? I presume you've held back a bit in case you break something?
Do you mean the < NS_TICK thing? The spare change doesn't go away.
Quoted 4 lines
If it helps, the smpnice balancing code's use of
static_prio_timeslice()doesn't really care what units it's return value is in as long asDEF_TIMESLICEis in the same units and contains the size of a time slice allocated to a nice==0 non RT task.
Ok, thanks. I wanted to make very certain I couldn't screw it up. Still, it's simpler to just leave it in ticks.
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 8 lines · Mike Galbraith
Quoted 2 lines · Peter Williams
If you're going to manage the time slice in nanoseconds why not do it properly? I presume you've held back a bit in case you break something?
Do you mean the <
NS_TICKthing? The spare change doesn't go away.
Not exactly. I mean "Why calculate time slice in jiffies and convert to nanoseconds? Why not just do the calculation in nanoseconds?"
Quoted 10 lines
Quoted 4 lines
If it helps, the smpnice balancing code's use of
static_prio_timeslice()
doesn't really care what units it's return value is in as long asDEF_TIMESLICEis in the same units and contains the size of a time slice allocated to a nice==0 non RT task.Ok, thanks. I wanted to make very certain I couldn't screw it up. Still, it's simpler to just leave it in ticks.
-Mike
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 9 lines · Peter Williams
Quoted 8 lines · Mike Galbraith
Quoted 3 lines · Peter Williams
If you're going to manage the time slice in nanoseconds why not do it properly? I presume you've held back a bit in case you break something?
Quoted 4 lines
Quoted 1 line
Do you mean the <
NS_TICKthing? The spare change doesn't go away.Not exactly. I mean "Why calculate time slice in jiffies and convert to nanoseconds? Why not just do the calculation in nanoseconds?"
Duh. Good question. Thanks :)
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Peter WilliamsQuoted 9 lines · Peter Williams
Quoted 8 lines · Mike Galbraith
Quoted 3 lines · Peter Williams
If you're going to manage the time slice in nanoseconds why not do it properly? I presume you've held back a bit in case you break something?
Quoted 4 lines
Quoted 1 line
Do you mean the <
NS_TICKthing? The spare change doesn't go away.Not exactly. I mean "Why calculate time slice in jiffies and convert to nanoseconds? Why not just do the calculation in nanoseconds?"
Turns out that my first instinct was right, and there is a good reason not to. It doesn't improve readability nor do anything functional, it only adds clutter. I much prefer the look of plain old ticks, and having nanoseconds only intrude where they're required. I did change NS_TICK to the less obfuscated (1000000000 / HZ), with task_timeslice() returning a more readable ticks * NS_TICK conversion.
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Mike GalbraithQuoted 61 lines · Mike Galbraith
Greetings,
Below, please find part 1 of my latest task throttling effort. I've very nearly completely reworked it from top to bottom, and broken it down into separate cleanup and a throttling diffs.
Main things that this diff does:
1. Closes a generic hole in the scheduler design: due to timeslice sample rate of HZ, tasks can and do steal time from each other. Generally this is no big deal, because statistics more or less even things out, but tasks with a high scheduling frequency and a low execution duration can steal considerable time. No longer.
2. Removes overhead from the fast path. There's no need to do division in the fast path, it's cheaper to do it at timeslice refresh time, where it accomplishes the same thing at a fraction of the cost. Trades a subtraction for a division, and removes the obsoleted bits that led to the division.
I have verified that the testcase sent in by David Mosberg ages ago, and which was the prime motivator for going to nanosecond timings in the scheduler in the first place, is not broken by the above changes.
3. Removes the disparity in the handling of dynamic priority for kernel threads verses user-land tasks.
4. Fixes a boot-time buglet where the TSC isn't synchronized yet, resulting in
recalc_task_prio()being called with now <p->timestamp. If you place aWARN_ONthere, the box won't even boot. With this fix, you'll get one warning, and then all goes fine.5. Fixes a couple of would-be bugs if anyone ever decided to use
TASK_NONINTERACTIVEthing along withTASK_UNINTERRUPTIBLE.6. Removes
sleep_avgmultiplier. Back when we had 10s of dynamic range, this was needed to help get interactive tasks up to speed. The 10 time speedup meant that a 1s sleep put us at max priority. Worked great. As we speak however, we have _1_ second of dynamic range, and this gets compressed to 100ms by the multiplier. This is very bad, and to see how bad, just try a very modest parallel kernel compile in a relatively slow NFS mounted filesystem. In heavy testing, I can find no detriment to removing this anachronism.7. Assorted cleanups to the interactivity logic.
8. Whatever I forgot to mention ;-)
Comments?
-Mike
Signed-off-by Mike Galbraith <[email protected]>
include/linux/sched.h | 3 - kernel/sched.c | 136 +++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
include/linux/sched.h line 723
Quoted 5 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-1@@ -720,7 +720,8 @@unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice;
Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 297 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-0+unsigned int first_time_slice;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;kernel/sched.c renamed from kernel/sched.c.org +80
-56@@ -99,6 +99,10 @@#define MAX_SLEEP_AVG (DEF_TIMESLICE * MAX_BONUS)#define STARVATION_LIMIT (MAX_SLEEP_AVG)#define NS_MAX_SLEEP_AVG (JIFFIES_TO_NS(MAX_SLEEP_AVG)) +#define NS_MAX_SLEEP_AVG_PCNT (NS_MAX_SLEEP_AVG / 100) +#define PCNT_PER_DYNPRIO (100 / MAX_BONUS) +#define NS_PER_DYNPRIO (PCNT_PER_DYNPRIO * NS_MAX_SLEEP_AVG_PCNT) +#define NS_TICK (JIFFIES_TO_NS(1))/* * If a task is 'interactive' then we reinsert it in the active @@ -153,9 +157,25 @@#define TASK_INTERACTIVE (p) \ ((p)->prio <= (p)->static_prio - DELTA(p)) -#define INTERACTIVE_SLEEP (p) \ - (JIFFIES_TO_NS(MAX_SLEEP_AVG * \ - (MAX_BONUS / 2 + DELTA((p)) + 1) / MAX_BONUS - 1)) +#define SLEEP_AVG_DIVISOR (p) (1 + CURRENT_BONUS(p)) + +#define INTERACTIVE_SLEEP_AVG (p) \ + (min(JIFFIES_TO_NS(MAX_SLEEP_AVG * (MAX_BONUS / 2 + DELTA(p)) / \ + MAX_BONUS), NS_MAX_SLEEP_AVG)) + +/* +* Returns whether a task has been asleep long enough to be considered idle. +* The metric is whether this quantity of sleep would promote the task more +* than one priority beyond marginally interactive. +*/ +static int task_interactive_idle (task_t *p,unsigned long sleep_time) +{ +unsigned long ceiling = (CURRENT_BONUS (p) +2 ) *NS_PER_DYNPRIO ; + +if (p->sleep_avg + sleep_time < ceiling) +return 0 ; +return p->sleep_avg + sleep_time >=INTERACTIVE_SLEEP_AVG (p); +}#define TASK_PREEMPTS_CURR (p, rq) \ ((p)->prio < (rq)->curr->prio)@@ -182,7 +202,7 @@static inline unsigned int task_timeslice (task_t *p) { -return static_prio_timeslice (p->static_prio); +return JIFFIES_TO_NS (static_prio_timeslice (p->static_prio)); }#define task_hot (p, now, sd) ((long long) ((now) - (p)->last_ran) \@@ -240,6 +260,7 @@unsigned long expired_timestamp;unsigned long long timestamp_last_tick; +unsigned long long timestamp_last_switch;task_t *curr, *idle;struct mm_struct *prev_mm;prio_array_t *active, *expired, arrays[2 ];@@ -777,6 +798,9 @@unsigned long long __sleep_time = now - p->timestamp;unsigned long sleep_time; +if (unlikely (now < p->timestamp)) + __sleep_time =0ULL ; +if (unlikely (p->policy ==SCHED_BATCH )) sleep_time =0 ;else {@@ -788,32 +812,32 @@if (likely (sleep_time >0 )) {/* -* User tasks that sleep a long time are categorised as -* idle. They will only have their sleep_avg increased to a +* Tasks that sleep a long time are categorised as idle. +* They will only have their sleep_avg increased to a * level that makes them just interactive priority to stay * active yet prevent them suddenly becoming cpu hogs and * starving other processes. */ -if (p->mm && sleep_time >INTERACTIVE_SLEEP (p)) { -unsigned long ceiling; - - ceiling =JIFFIES_TO_NS (MAX_SLEEP_AVG - -DEF_TIMESLICE ); -if (p->sleep_avg < ceiling) - p->sleep_avg = ceiling; - }else { +if (task_interactive_idle (p, sleep_time)) { +unsigned long ceiling =INTERACTIVE_SLEEP_AVG (p);/* -* The lower the sleep avg a task has the more -* rapidly it will rise with sleep time. This enables -* tasks to rapidly recover to a low latency priority. -* If a task was sleeping with the noninteractive -* label do not apply this non-linear boost +* Promote previously interactive task. */ -if (p->sleep_type !=SLEEP_NONINTERACTIVE || !p->mm) - sleep_time *= - (MAX_BONUS -CURRENT_BONUS (p)) ? :1 ; +if (p->sleep_avg > ceiling) { + ceiling = p->sleep_avg /NS_PER_DYNPRIO ; +if (ceiling <MAX_BONUS ) + ceiling++; + ceiling *=NS_PER_DYNPRIO ; + }else { + ceiling += p->time_slice >>2 ; +if (ceiling >NS_MAX_SLEEP_AVG ) + ceiling =NS_MAX_SLEEP_AVG ; + } +if (p->sleep_avg < ceiling) + p->sleep_avg = ceiling; + }else {/* * This code gives a bonus to interactive tasks. * @@ -1367,7 +1391,8 @@ out_activate:#endif /* CONFIG_SMP */ -if (old_state ==TASK_UNINTERRUPTIBLE ) { + +if (old_state &TASK_UNINTERRUPTIBLE ) { rq->nr_uninterruptible--;/* * Tasks waking from uninterruptible sleep are likely @@ -1461,6 +1486,8 @@*/ local_irq_disable (); p->time_slice = (current->time_slice +1 ) >>1 ; +if (unlikely (p->time_slice <NS_TICK )) + p->time_slice =NS_TICK ;/* * The remainder of the first timeslice might be recovered by * the parent if the child exits early enough. @@ -1468,13 +1495,12 @@ p->first_time_slice =1 ; current->time_slice >>=1 ; p->timestamp =sched_clock (); -if (unlikely (!current->time_slice)) { +if (unlikely (current->time_slice <NS_TICK )) {/* * This case is rare, it happens when the parent has only * a single jiffy left from its timeslice. Taking the * runqueue lock is not a problem. */ - current->time_slice =1 ;scheduler_tick (); }local_irq_enable ();@@ -2586,6 +2612,7 @@ {unsigned long long last =max (p->timestamp, rq->timestamp_last_tick); p->sched_time += now - last; + p->time_slice -= now - last; }/* @@ -2735,8 +2762,8 @@* RR tasks need a special form of timeslice management. * FIFO tasks have no timeslices. */ -if ((p->policy ==SCHED_RR ) && !--p->time_slice) { - p->time_slice =task_timeslice (p); +if ((p->policy ==SCHED_RR ) && p->time_slice <NS_TICK ) { + p->time_slice +=task_timeslice (p); p->first_time_slice =0 ;set_tsk_need_resched (p);@@ -2745,11 +2772,21 @@ } goto out_unlock; } -if (!--p->time_slice) { +if (p->time_slice <NS_TICK ) { +int time_slice =task_timeslice (p); +int run_time = time_slice - p->time_slice;dequeue_task (p, rq->active);set_tsk_need_resched (p); + p->time_slice += time_slice; +/* +* Tasks are charged proportionately less run_time at high +* sleep_avg to delay them losing their interactive status +*/ + run_time /=SLEEP_AVG_DIVISOR (p); + p->sleep_avg -= run_time; +if ((long )p->sleep_avg <0 ) + p->sleep_avg =0 ; p->prio =effective_prio (p); - p->time_slice =task_timeslice (p); p->first_time_slice =0 ;if (!rq->expired_timestamp)@@ -2777,13 +2814,17 @@* This only applies to tasks in the interactive * delta range with at least TIMESLICE_GRANULARITY to requeue. */ -if (TASK_INTERACTIVE (p) && !((task_timeslice (p) - - p->time_slice) %TIMESLICE_GRANULARITY (p)) && - (p->time_slice >=TIMESLICE_GRANULARITY (p)) && - (p->array == rq->active)) { +if (p->array == rq->active) { +unsigned long runtime, period; -requeue_task (p, rq->active); -set_tsk_need_resched (p); + runtime = now - rq->timestamp_last_switch; + period =JIFFIES_TO_NS (TIMESLICE_GRANULARITY (p)); + +if (runtime >= period && p->time_slice >>1 >= period) { +requeue_task (p, rq->active); +set_tsk_need_resched (p); + rq->timestamp_last_switch = now; + } } } out_unlock:@@ -2851,7 +2892,8 @@*/ static inline unsigned long smt_slice (task_t *p,struct sched_domain *sd) { -return p->time_slice * (100 - sd->per_cpu_gain) /100 ; +int time_slice =NS_TO_JIFFIES (p->time_slice) ? :1 ; +return time_slice * (100 - sd->per_cpu_gain) /100 ; }static int dependent_sleeper (int this_cpu,runqueue_t *this_rq)@@ -3014,7 +3056,6 @@prio_array_t *array;struct list_head *queue;unsigned long long now; -unsigned long run_time;int cpu, idx, new_prio;/* @@ -3050,19 +3091,6 @@schedstat_inc (rq, sched_cnt); now =sched_clock (); -if (likely ((long long )(now - prev->timestamp) <NS_MAX_SLEEP_AVG )) { - run_time = now - prev->timestamp; -if (unlikely ((long long )(now - prev->timestamp) <0 )) - run_time =0 ; - }else - run_time =NS_MAX_SLEEP_AVG ; - -/* -* Tasks charged proportionately less run_time at high sleep_avg to -* delay them losing their interactive status -*/ - run_time /= (CURRENT_BONUS (prev) ? :1 ); -spin_lock_irq (&rq->lock);if (unlikely (prev->flags &PF_DEAD ))@@ -3075,7 +3103,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); }@@ -3136,7 +3164,6 @@if (next->sleep_type ==SLEEP_INTERACTIVE ) delta = delta * (ON_RUNQUEUE_WEIGHT *128 /100 ) /128 ; - array = next->array; new_prio =recalc_task_prio (next, next->timestamp + delta);if (unlikely (next->prio != new_prio)) {@@ -3156,14 +3183,11 @@update_cpu_clock (prev, rq, now); - prev->sleep_avg -= run_time; -if ((long )prev->sleep_avg <=0 ) - prev->sleep_avg =0 ; prev->timestamp = prev->last_ran = now;sched_info_switch (prev, next);if (likely (prev != next)) { - next->timestamp = now; + next->timestamp = rq->timestamp_last_switch = now; rq->nr_switches++; rq->curr = next; ++*switch_count;
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 8 lines · Peter Williams
Quoted 8 lines
include/linux/sched.h | 3 - kernel/sched.c | 136 +++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)include/linux/sched.h renamed from include/linux/sched.h.org +0
-0@@ -720,7 +720,8 @@
Quoted 7 lines
include/linux/sched.h line 723
Quoted 4 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-1unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Nope, that's a big fat bug.
I need to reconsider the nanosecond tracking a bit anyway. I was too quick on the draw with the granularity change. It doesn't do what the original does, and won't work at all when interrupts become tasks.
To do this properly, I need to maintain separate tick hit count (a.k.a. time_slice;) and run_time. If I had slice_info in the first patch, I could store granularity there and not have to add anything to the task struct, but alas...
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 19 lines · Mike Galbraith
Quoted 10 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@Quoted 7 lines
include/linux/sched.h line 723
Quoted 4 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-1unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 1 line
Nope, that's a big fat bug.
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Cheers,
Con
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 20 lines · Con Kolivas
Quoted 19 lines · Mike Galbraith
Quoted 17 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@include/linux/sched.h line 723
Quoted 4 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-1unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 5 lines
Quoted 1 line
Nope, that's a big fat bug.
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Yup. I just didn't realize that there were 16 bit integers out there.
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 21 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 20 lines · Con Kolivas
Quoted 19 lines · Mike Galbraith
Quoted 17 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@include/linux/sched.h line 723
Quoted 4 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-1unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 7 lines
Quoted 5 lines
Quoted 1 line
Nope, that's a big fat bug.
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
---
~Randy
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 25 lines · Randy.Dunlap
Quoted 24 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 23 lines · Con Kolivas
Quoted 21 lines · Mike Galbraith
Quoted 10 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@Quoted 8 lines
include/linux/sched.h line 723
Quoted 4 lines
include/linux/sched.h renamed from include/linux/sched.h.org +1
-1unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Nope, that's a big fat bug.
Quoted 8 lines
Quoted 6 lines
Quoted 4 lines
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
Alright I made that up, but it might not be one day :P
Cheers,
Con
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 31 lines · On Sat, 4 Mar 2006 16:54:58 +1100 Con Kolivas wrote:
Quoted 30 lines · Randy.Dunlap
Quoted 29 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 27 lines · Con Kolivas
Quoted 20 lines · Mike Galbraith
Quoted 10 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +1
-1unsigned long policy; cpumask_t cpus_allowed; - unsigned int time_slice, first_time_slice; + int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 1 line
Nope, that's a big fat bug.
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
Alright I made that up, but it might not be one day :P
It *was* one day, long ago. Hopefully not in the future, but who knows.
---
~Randy
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Con KolivasQuoted 31 lines · Con Kolivas
Quoted 30 lines · Randy.Dunlap
Quoted 29 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 27 lines · Con Kolivas
Quoted 20 lines · Mike Galbraith
Quoted 10 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +1
-1unsigned long policy; cpumask_t cpus_allowed; - unsigned int time_slice, first_time_slice; + int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 1 line
Nope, that's a big fat bug.
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
Alright I made that up, but it might not be one day :P
Well Fudgecicles. Now you guys have gotten me aaaaall confused. Are there cpus out there (in generic linux land) that have 16 bit integers or not? 16 bit integers existing in a 32 bit cpu OS seems like an alien concept to me, but I'm not a twisted cpu designer... I'll just go with the flow ;-)
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 37 lines · Mike Galbraith
Quoted 36 lines · Con Kolivas
Quoted 34 lines · Randy.Dunlap
Quoted 24 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 23 lines · Con Kolivas
Quoted 21 lines · Mike Galbraith
Quoted 10 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h | 3 - kernel/sched.c | 136+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)
--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@Quoted 8 lines
Review
Quoted 4 lines
(quoted diff) +1
-1unsigned long policy; cpumask_t cpus_allowed; - unsigned int time_slice, first_time_slice; + int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Nope, that's a big fat bug.
Quoted 7 lines
Quoted 4 lines
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
Quoted 7 lines
Quoted 1 line
Alright I made that up, but it might not be one day :P
Well Fudgecicles. Now you guys have gotten me aaaaall confused. Are there cpus out there (in generic linux land) that have 16 bit integers or not? 16 bit integers existing in a 32 bit cpu OS seems like an alien concept to me, but I'm not a twisted cpu designer... I'll just go with the flow ;-)
All supported architectures on linux currently use 32bits for int. That should give you 2.1 seconds in nanoseconds. Sorry my legacy of remembering when ints were 8 bits coloured me.
Cheers,
Con
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
Quoted 10 lines · Con Kolivas
Quoted 5 lines · Mike Galbraith
Well Fudgecicles. Now you guys have gotten me aaaaall confused. Are there cpus out there (in generic linux land) that have 16 bit integers or not? 16 bit integers existing in a 32 bit cpu OS seems like an alien concept to me, but I'm not a twisted cpu designer... I'll just go with the flow ;-)
All supported architectures on linux currently use 32bits for int. That should give you 2.1 seconds in nanoseconds. Sorry my legacy of remembering when ints were 8 bits coloured me.
Well that's a relief. I was getting all kinds of frazzled trying to imagine the kernel not exploding on such a cpu.
-Mike
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Con KolivasQuoted 54 lines · Con Kolivas
Quoted 43 lines · Mike Galbraith
Quoted 41 lines · Con Kolivas
Quoted 38 lines · Randy.Dunlap
Quoted 27 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 25 lines · Con Kolivas
Quoted 22 lines · Mike Galbraith
Quoted 10 lines · Peter Williams
Quoted 10 lines
include/linux/sched.h| 3 -kernel/sched.c| 136
+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@Quoted 8 lines
Review
Quoted 4 lines
unsigned long policy; cpumask_t cpus_allowed;(quoted diff) +1
-1- unsigned int time_slice, first_time_slice; + int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Nope, that's a big fat bug.
Quoted 7 lines
Quoted 4 lines
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
Quoted 7 lines
Quoted 1 line
Alright I made that up, but it might not be one day :P
Well Fudgecicles. Now you guys have gotten me aaaaall confused. Are there cpus out there (in generic linux land) that have 16 bit integers or not? 16 bit integers existing in a 32 bit cpu OS seems like an alien concept to me, but I'm not a twisted cpu designer... I'll just go with the flow ;-)
Quoted 4 lines
All supported architectures on linux currently use 32bits for int. That should give you 2.1 seconds in nanoseconds. Sorry my legacy of remembering when ints were 8 bits coloured me.
Cheers,
Con
The size of int isn't just a function of the architecture it's also a function of the C compiler used. C requires that longs be at least 32 bits but only requires that ints be at least 16 bits. If the architecture supports 16 bit integer operations there's nothing to stop a VALID compiler from make ints only 16 bits. Since everyone uses gcc (at the moment) it's probably not an (urgent) issue but it seems to me that the safe option is to use longs when you want to ensure that you get at least 32 bits.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Mike GalbraithQuoted 42 lines · Mike Galbraith
Quoted 40 lines · Con Kolivas
Quoted 37 lines · Randy.Dunlap
Quoted 25 lines · On Sat, 04 Mar 2006 06:29:47 +0100 Mike Galbraith wrote:
Quoted 23 lines · Con Kolivas
Quoted 21 lines · Mike Galbraith
Quoted 18 lines · Peter Williams
Quoted 12 lines
include/linux/sched.h| 3 -kernel/sched.c| 136
+++++++++++++++++++++++++++++--------------------- 2 files changed, 82 insertions(+), 57 deletions(-)--- linux-2.6.16-rc5-mm2/include/linux/sched.h.org 2006-03-01
15:06:22.000000000 +0100 +++linux-2.6.16-rc5-mm2/include/linux/sched.h2006-03-02
08:33:12.000000000 +0100 @@ -720,7 +720,8 @@unsigned long policy; cpumask_t cpus_allowed;Review
Quoted 2 lines
(quoted diff) +1
-1- unsigned int time_slice, first_time_slice; + int time_slice;Can you guarantee that int is big enough to hold a time slice in nanoseconds on all systems? I think that you'll need more than 16 bits.
Quoted 8 lines
Quoted 6 lines
Quoted 1 line
Nope, that's a big fat bug.
Most ints are 32bit anyway, but even a 32 bit unsigned int overflows with nanoseconds at 4.2 seconds. A signed one at about half that. Our timeslices are never that large, but then int isn't always 32bit either.
Yup. I just didn't realize that there were 16 bit integers out there.
LDD 3rd ed. doesn't know about them either. Same for me.
Quoted 8 lines
Quoted 1 line
Alright I made that up, but it might not be one day :P
Well Fudgecicles. Now you guys have gotten me aaaaall confused. Are there cpus out there (in generic linux land) that have 16 bit integers or not? 16 bit integers existing in a 32 bit cpu OS seems like an alien concept to me, but I'm not a twisted cpu designer... I'll just go with the flow ;-)
I'm not sure which is why I asked. But it seems to be a convention (in the kernel code) to use long or unsigned long when you want to ensure at least 32 bits. This may be a legacy from the days when there were systems with 16 bit integers but it seems (to me) to be alive and well.
Peter
Signature · 4 lines
Peter Williams [email protected] "Learning, n. The kind of ignorance distinguishing the studious." -- Ambrose Bierce
Re: [patch 2.6.16-rc5-mm2] sched_cleanup-V17 - task throttling patch 1 of 2
In reply to Mike GalbraithQuoted 8 lines · Mike Galbraith
I need to reconsider the nanosecond tracking a bit anyway. I was too quick on the draw with the granularity change. It doesn't do what the original does, and won't work at all when interrupts become tasks.
To do this properly, I need to maintain separate tick hit count (a.k.a.
time_slice;) andrun_time. If I hadslice_infoin the first patch, I could store granularity there and not have to add anything to the task struct, but alas...
Ala the below. Leave the ticked timeslice available for those places where nanoseconds are useless, and do precise counting only where that is useful. I need to come up with a better name that slice_ticks, and time_slice is already taken.
-Mike
include/linux/sched.h renamed from include/linux/sched.h.org +2 -1
@@ -720,7 +720,8 @@unsigned long policy;cpumask_t cpus_allowed; -unsigned int time_slice, first_time_slice; +int time_slice; +unsigned int slice_ticks, first_time_slice;#ifdef CONFIG_SCHEDSTATS struct sched_info sched_info;
kernel/sched.c renamed from kernel/sched.c.org +76 -55
261 lines not on this page · raw message
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
In reply to MIke GalbraithQuoted 4 lines · MIke Galbraith
On Fri, 2006-02-17 at 14:45 +0100, MIke Galbraith wrote:
kernel/sched.c renamed from kernel/sched.c.org +3
-0+/* +* Masks for p->slice_info, formerly p->first_time_slice. +* SLICE_FTS: 0x80000000 Task is in it's first ever timeslice.
kernel/sched.c line 219
Quoted 10 lines
kernel/sched.c renamed from kernel/sched.c.org +10
-0+* SLICE_NEW: 0x40000000 Slice refreshed. +* SLICE_SPA: 0x3FFF8000 Spare bits. +* SLICE_LTS: 0x00007F80 Last time slice +* SLICE_AVG: 0x0000007F Task slice_avg stored as percentage. +*/ +#define SLICE_AVG_BITS 7 +#define SLICE_LTS_BITS 10 +#define SLICE_SPA_BITS 13 +#define SLICE_NEW_BITS 1 +#define SLICE_FTS_BITS 1
I count 8 and 15 bits in the documentation of LTS/SPA respectively, not 10 and 13.
kernel/sched.c line 950
Quoted 4 lines
kernel/sched.c renamed from kernel/sched.c.org +1
-0}if (likely (sleep_time >0 )) { +
Extra line
kernel/sysctl.c line 689
Quoted 10 lines
kernel/sysctl.c renamed from kernel/sysctl.c.org +10
-0+ { + .ctl_name = KERN_SCHED_THROTTLE1, + .procname = "sched_g1", + .data = &sched_g1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &sched_g2_max,
sched_g2_max is possibly badly named, as it is used in connection with sched_g1 here.
kernel/sysctl.c line 701
Quoted 12 lines
kernel/sysctl.c renamed from kernel/sysctl.c.org +12
-0+ }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "sched_g2", + .data = &sched_g2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &sched_g2_max, + },
Daniel K.
Re: [patch 2.6.16-rc4-mm1] Task Throttling V14
Quoted 10 lines · Daniel K.
Quoted 9 lines · MIke Galbraith
On Fri, 2006-02-17 at 14:45 +0100, MIke Galbraith wrote:
+/*
+ * Masks forp->slice_info, formerlyp->first_time_slice.+ * SLICE_FTS: 0x80000000 Task is in it's first ever timeslice. + * SLICE_NEW: 0x40000000 Slice refreshed. + * SLICE_SPA: 0x3FFF8000 Spare bits. + * SLICE_LTS: 0x00007F80 Last time slice + * SLICE_AVG: 0x0000007F Task slice_avg stored as percentage.+ */
Quoted 8 lines
kernel/sched.c line 219
Quoted 5 lines
kernel/sched.c renamed from kernel/sched.c.org +5
-0+#define SLICE_AVG_BITS 7 +#define SLICE_LTS_BITS 10 +#define SLICE_SPA_BITS 13 +#define SLICE_NEW_BITS 1 +#define SLICE_FTS_BITS 1I count 8 and 15 bits in the documentation of LTS/SPA respectively, not 10 and 13.
Dang, fixed the stupid bug, but forgot to wipe the evidence ;-) Fixed.
Quoted 7 lines
kernel/sched.c line 950
Quoted 5 lines
kernel/sched.c renamed from kernel/sched.c.org +1
-0}if (likely (sleep_time >0 )) { +Extra line
Fixed.
Quoted 15 lines
kernel/sysctl.c line 689
Quoted 11 lines
kernel/sysctl.c renamed from kernel/sysctl.c.org +10
-0+ { + .ctl_name = KERN_SCHED_THROTTLE1, + .procname = "sched_g1", + .data = &sched_g1, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &sched_g2_max,
sched_g2_maxis possibly badly named, as it is used in connection withsched_g1here.
Quoted 12 lines
kernel/sysctl.c line 701
Quoted 12 lines
kernel/sysctl.c renamed from kernel/sysctl.c.org +12
-0+ }, + { + .ctl_name = KERN_SCHED_THROTTLE2, + .procname = "sched_g2", + .data = &sched_g2, + .maxlen = sizeof (int), + .mode = 0644, + .proc_handler = &proc_dointvec_minmax, + .strategy = &sysctl_intvec, + .extra1 = &zero, + .extra2 = &sched_g2_max, + },
I suppose sched_grace_max would fit better.
Thanks for taking a look.
-Mike