Subject: Re: Preparing callout(9) for a HZ-less kernel
To: None <>
From: David Laight <>
List: tech-kern
Date: 10/23/2007 18:46:21
On Tue, Oct 23, 2007 at 02:10:46PM +0200, Joerg Sonnenberger wrote:
> > 
> > Apart from the requirement to scan empty slots - which should be quite
> > fast if there aren't too many of them - it should be ok provided you
> > restrict the granularity a bit.
> > Remember that the large majority of timers (esp in network code) are
> > 'guard' timers that don't expire.
> Keep in mind that it also means that you push them around in the call
> wheel a lot, which is not free either.

I think you need to look at the call wheel code more closely.
Each callout can be processed a maximum of 3 times (5 if you include
adding/removing it).
With a 1ms resolution [1], most callouts will probably need to be moved
once only - in the last quarter second before expiry (the 2nd move
happens when there are ~65 seconds to expiry).
Redistributing callouts into the next level is also cheap.

I'm not suggesting it isn't a good idea to avoid taking an interrupt
every tick, just that you want to keep callouts set to fixed timed
points, and that the call wheel code is a very good scheme.

You might want to consider something else for the last row, but again
scanning an array of pointers (looking for a non-empty queue) is
actually probably quicker that any fancy search - given the likely
number of empty slots to skip.


[1] and the existing 4 layer, 8 bits each system.

David Laight: