Re: HZ, preferably as small as possible

[Richard B. Johnson]

On Wed, 17 Jul 2002, Daniel Phillips wrote:

> On Monday 15 July 2002 07:06, Linus Torvalds wrote:
> > There is, of course, the option to do variable frequency (and make it
> > integer multiples of the exposed "constant HZ" so that kernel code
> > doesn't actually need to _care_ about the variability). There are
> > patches to play with things like that.
> 
> We don't have to feel restricted to integer multiples.  I'll paste in my 
> earlier post, for your convenience:
> 
> > ...If somebody wants a cruder scheduling interval than the raw timer
> > interrupt, that's child's play, just step the interval down.  The
> > only slightly challenging thing is do that without restricting
> > choice of rate for the raw timer and scheduler, respectively.  Here,
> > a novel application of Bresenham's algorithm (the line drawing
> > algorithm) works nicely: at each raw interrupt, subtract the period
> > of the raw interrupt from an accumulator; if the result is less
> > than zero, add the period of the scheduler to the accumlator and
> > drop into the scheduler's part of the timer interrupt.
> 
> [which just increments the timer variable I believe]
> 
> > This Bresenham trick works for arbitrary collections of interrupt
> > rates, all with different periods.  It has the property that,
> > over time, the total number of invocations at each rate remains
> > *exactly* correct, and so long as the raw interrupt runs at a
> > reasonably high rate, displacement isn't that bad either.
> 
> This technique is scarcely less efficient than the cruder method.

It is hardly novel and I can't imagine how Bresenham or whomever
could make such a claim to the obvious. Even the DOS writer(s) used
this technique to get one-second time intervals from the 18.206
ticks/per second. This is simply division by subtraction, but you
don't throw away the remainder. Therefore, in the limit, there is
no remainder. However, at any instant, the time can be off by as
much as the divisor -1. FYI, you make digital filters using this
same method, it's hardly novel.

Cheers,
Dick Johnson

Penguin : Linux version 2.4.18 on an i686 machine (797.90 BogoMips).

                 Windows-2000/Professional isn't.