CFS scheduler, -v8
in [Kernel]
|
Prev: Bug in current -git tree causing dbus and gnome to chew up cpu time
Next: Introduce O_CLOEXEC (take >2)
From: William Lee Irwin III on 3 May 2007 16:00 On Thu, 2007-05-03 at 08:53 -0700, William Lee Irwin III wrote: >> Tong Li's Trio scheduler does a bit of this, though it doesn't seem to >> have the mindshare cfs seems to have acquired. >> The hyperlink seems to have broken, though: >> http://www.cs.duke.edu/~tongli/linux/linux-2.6.19.2-trio.patch On Thu, May 03, 2007 at 11:44:27AM -0700, Li, Tong N wrote: > Yeah, I just fixed the link. The code was written based on the 2.6.19.2 > scheduler. I could forward-port it to the latest kernel if there's > interest and I can find time. :) Here's a description of the design: > http://lkml.org/lkml/2007/4/20/286 I have the interest. I don't see performance issues with any of the schedulers, but am rather interested in the feature. -- wli - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Esben Nielsen on 5 May 2007 04:40 On Wed, 2 May 2007, Ingo Molnar wrote: > > * Balbir Singh <balbir(a)linux.vnet.ibm.com> wrote: > >> The problem is with comparing a s64 values with (s64)ULONG_MAX, which >> evaluates to -1. Then we check if exec_delta64 and fair_delta64 are >> greater than (s64)ULONG_MAX (-1), if so we assign (s64)ULONG_MAX to >> the respective values. > > ah, indeed ... > >> The fix is to compare these values against (s64)LONG_MAX and assign >> (s64)LONG_MAX to exec_delta64 and fair_delta64 if they are greater >> than (s64)LONG_MAX. >> >> Tested on PowerPC, the regression is gone, tasks are load balanced as >> they were in v7. > > thanks, applied! > > Ingo I have been wondering why you use usigned for timers anyway. It is also like that in hrtimers. Why not use signed and avoid (almost) all worries about wrap around issues. The trick is that when all a < b is be replaced by a - b < 0 the code will work on all 2-complement machines even if the (signed!) integers a and b wrap around. In both the hrtimer and CFS patch 32 bit timers could be used internally on 32 bit architectures to avoid expensive 64 bit integer calculations. The only thing is: timeouts can not be bigger than 2^31 in the chosen units. I have successfully coded a (much more primitive) hrtimer system for another OS on both ARM and PPC using the above trick in my former job. On both I used the machine's internal clock as the internal representation of time and I only scaled to a struct timespec in the user interface. Esben - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Linus Torvalds on 5 May 2007 13:50 On Sat, 5 May 2007, Esben Nielsen wrote: > > I have been wondering why you use usigned for timers anyway. It is also like > that in hrtimers. Why not use signed and avoid (almost) all worries about wrap > around issues. The trick is that when all > a < b > is be replaced by > a - b < 0 > the code will work on all 2-complement machines even if the (signed!) integers > a and b wrap around. No. BOTH of the above are buggy. The C language definition doesn't allow signed integers to wrap (ie it's undefined behaviour), so "a-b < 0" can be rewritten by the compiler as a simple signed "a < b". And the unsigned (or signed) "a < b" is just broken wrt any kind of wrap-around (whether wrapping around zero or the sign bit). So the _only_ valid way to handle timers is to - either not allow wrapping at all (in which case "unsigned" is better, since it is bigger) - or use wrapping explicitly, and use unsigned arithmetic (which is well-defined in C) and do something like "(long)(a-b) > 0". Notice? The signed variant is basically _never_ correct. Linus - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Willy Tarreau on 6 May 2007 04:40 Hi Ingo, On Sun, May 06, 2007 at 10:29:11AM +0200, Ingo Molnar wrote: > > * Linus Torvalds <torvalds(a)linux-foundation.org> wrote: > > > So the _only_ valid way to handle timers is to > > - either not allow wrapping at all (in which case "unsigned" is better, > > since it is bigger) > > - or use wrapping explicitly, and use unsigned arithmetic (which is > > well-defined in C) and do something like "(long)(a-b) > 0". > > hm, there is a corner-case in CFS where a fix like this is necessary. > > CFS uses 64-bit values for almost everything, and the majority of values > are of 'relative' nature with no danger of overflow. (They are signed > because they are relative values that center around zero and can be > negative or positive.) (...) > - if (key < entry->fair_key) { > + if ((s64)(entry->fair_key - key) > 0) { Just a hint: while your code here is correct, it is a good practise to check against < 0 instead, so that if for any reason you sometimes forget to cast to signed, the compiler will emit a warning stating that the condition is always false. This would simply become : - if (key < entry->fair_key) { + if ((s64)(key - entry->fair_key) < 0) { Just my .02 euros :-) Willy - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
From: Ingo Molnar on 6 May 2007 04:40
* Linus Torvalds <torvalds(a)linux-foundation.org> wrote: > So the _only_ valid way to handle timers is to > - either not allow wrapping at all (in which case "unsigned" is better, > since it is bigger) > - or use wrapping explicitly, and use unsigned arithmetic (which is > well-defined in C) and do something like "(long)(a-b) > 0". hm, there is a corner-case in CFS where a fix like this is necessary. CFS uses 64-bit values for almost everything, and the majority of values are of 'relative' nature with no danger of overflow. (They are signed because they are relative values that center around zero and can be negative or positive.) there is one value that is of 'absolute' nature though: the 'fair clock' (which is the same as the normal system clock when load is 1.0, and it slows down in a load-proportional way as load increases), which has units of nanoseconds - and the 'keys' in the rbtree are derived from such clock values. That particular clock could produce an s64 overflow at around 292 years after bootup (a bit later if the system is also used for something in that timeframe). While i dont think that's realistic to worry about, the fix below should solve that theoretical problem too. Ingo Index: linux/kernel/sched_fair.c =================================================================== --- linux.orig/kernel/sched_fair.c +++ linux/kernel/sched_fair.c @@ -60,7 +60,7 @@ static inline void __enqueue_task_fair(s * We dont care about collisions. Nodes with * the same key stay together. */ - if (key < entry->fair_key) { + if ((s64)(entry->fair_key - key) > 0) { link = &parent->rb_left; } else { link = &parent->rb_right; - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo(a)vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/ |