Date: Thu, 25 Sep 1997 05:39:49 +0200 (MET DST) From: Finn Arne Gangstad <finnag@guardian.no> To: Archie Cobbs <archie@whistle.com> Cc: current@FreeBSD.ORG Subject: Re: timeout management (was: Re: cvs commit: ...) Message-ID: <Pine.LNX.3.95.970925053231.28877A-100000@lucifer.guardian.no> In-Reply-To: <199709250229.TAA16784@bubba.whistle.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Wed, 24 Sep 1997, Archie Cobbs wrote:
> > > Another algorithm that Julian and I discussed the other day has
> > > these properties:
> > >
> > > FUNCTION TIMING (amortized)
> > > add new timeout O(1)
> > > check for timeout O(1)
> > > remove a timeout O(1) (requires a handle)
> > > process one timeout O(lg T) for T = number of ticks alive
> > >
> > > That is, if a timeout event lives for T ticks (whether it's cancelled
> > > or expires after T ticks), it requires O(lg T) total work.
> > >
> > > Therefore, any event that is cancelled before 1/2 of it's timeout
> > > period has expired only requires O(1) work.
> > >
> > > The disadvantage is that you can do a lot of work duiring a single
> > > tick: O(N), where N is the number of timeout events still alive
> > > in the queue after 1/2 of their timeout periods.
> >
> > so, do you still have to do some work after each tick?? or were does this
> > come into play??
>
> Yes.. each tick you do up to O(N) work (N defined as above).
>
> > > So if 99% of timeouts expire within the first half of their timeout
> > > period, then this algorithm is "optimal".
> >
> > hmm.. if you have something typed up about the design of this algo,
> > could you send it to me in private mail...
>
> I don't, but here's the general idea: for every range of ticks
> of the form 2^n .. 2^(n+1) - 1 you split the range into two
> halves and create a doubly linked list ("box") for each half. This is
> the situation at t=0. The two halves are 2^n .. 2^n + 2^(n-1) - 1
> 2^n + 2^(n-1) .. 2^(n+1) - 1.
>
> When any event is scheduled, you put it in the linked list corrsponding
> to the range into which it's timeout value falls.
>
> Now here's where it starts getting complicated...
>
Have you guys looked at the timer code in Linux? It basically is a small
variation of this, which makes all operations O(1) for almost
every timer.
The idea is that instead of splitting each range into 2, you split each
range into 256 (for the first range) and 32 for all other ranges.
Most timers will be less than 256 ticks into the future, so they will
never be moved, and 99% of the rest will in the 32 * 256 ticks range, and
will, if they are not cancelled (which around 90% seem to be), only be
moved once.
It's in kernel/sched.c if you're unfamiliar with Linux :)
- Finn Arne
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.LNX.3.95.970925053231.28877A-100000>