Messages in this thread | | | From | (John Alvord) | Subject | Re: No 100 HZ timer ! | Date | Wed, 11 Apr 2001 19:21:38 GMT |
| |
On Wed, 11 Apr 2001 20:57:04 +0200, Jamie Lokier <lk@tantalophile.demon.co.uk> wrote:
>george anzinger wrote: >> > A pointer-based priority queue is really not a very complex thing, and >> > there are ways to optimise them for typical cases like the above. >> > >> Please do enlighten me. The big problem in my mind is that the >> pointers, pointing at points in time, are perishable. > >Um, I'm not sure what perishability has to do with anything. Timers at >the moment can be added, deleted and destroyed and it's no big deal. > >Look in an algorithms book under "priority queue". They usually don't >say how to use a heap-ordered tree -- usually it's an array -- but you >can use a tree if you want. In such a tree, each timer has a link to >_two_ next timers and one previous timer. (The previous timer link is >only needed if you can delete timers before they expire, which is >required for Linux). > >I'm not saying saying a heap-ordered tree is fastest. But it's ok, and >doesn't require any more storage than the `struct timer' objects >themselves. > >It's possible to optimise this kind of data structure rather a lot, >depending on how you want to use it. Linux' current timer algorithm is >a pretty good example of a priority queue optimised for timer ticks, >where you don't mind doing a small amount of work per tick. > >One notable complication with the kernel is that we don't want every >timer to run at its exactly allocated time, except for some special >timers. For example, if you have 100 TCP streams and their >retransmission times are scheduled for 1.0000s, 1.0001s, 1.0002s, etc., >you'd much rather just process them all at once as is done at the moment >by the 100Hz timer. This is because cache locality is much more >important for TCP retransmits than transmit timing resolution. > >There's literature online about this class of problems: look up "event >set" and "simulation" and "fast priority queue".
I bumped into a funny non-optimization a few years ago. A system with a timer queue like the above had been "optimized" by keeping old timer elements... ready for new tasks to link onto and activate. The granularity was 1 millsecond. Over time, all timer values from 0 to roughly 10 minutes had been used. That resulted in 60,000 permanent storage fragments laying about... a significant fragmentation problem. The end was a forced recycle every month or so.
john alvord - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |