lkml.org 
[lkml]   [2002]   [Jul]   [17]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    From
    SubjectRe: HZ, preferably as small as possible
    Date
    On Wednesday 17 July 2002 22:31, Richard B. Johnson wrote:
    > 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.

    It's novel for Linux then, because it seems not to have occured to
    anyone here. I'll take your agressive response as a vote in favor.

    --
    Daniel
    -
    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/

    \
     
     \ /
      Last update: 2005-03-22 13:27    [W:0.024 / U:63.544 seconds]
    ©2003-2016 Jasper Spaans. hosted at Digital OceanAdvertise on this site