[ntp:questions] how do I lock in average frequency correction

Dennis Ferguson dennis.c.ferguson at gmail.com
Wed Feb 15 17:15:42 UTC 2012

On 14 Feb, 2012, at 22:04 , Garrett Wollman wrote:
> All of these have issues, starting with the fact that they run at
> inconvenient rates.

For a clock implementation which works well in the presence of time
synchronization software there are (i.e. must be) no inconvenient
rates.  That is, even when the frequency written on the oscillator's
package is a nice round number the actual frequency of the oscillator
is going to be different and is unlikely to be "convenient" at all.
Yet if you want the clock to keep accurate time you must be able to
program the clock to operate at the oscillator's actual rate no matter
what that is.

> Modern operating systems are moving towards "tickless" operation to
> improve power efficiency.  This requires an on-board timing device
> that has sufficient range and stability to accurately determine the
> amount of time that has elapsed between two non-periodic interrupts,
> so that the clock can be advanced by the correct amount.

I'm having trouble with this because it implies that the system's
clock must be advanced in an interrupt service routine which samples
a counter.  If the system provides a continuously incrementing counter
then I think the last thing you want to do with it is to use it
in a way which incorporates the jitter and other inaccuracies that
come from interrupt processing into the system clock.  System clocks
maintained by counting interrupts should be reserved for situations
where there are is no other means of measuring the advance of time.
If you have a continuously incrementing counter you are way better
off just deriving the system clock directly from that (which I guess
makes the system clock "tickless" as well).  There is nothing you can
do in an interrupt service routine which helps, in fact trying to do
anything there usually just makes the result worse.

I have had very good results with the following procedure.  If `tc'
is the 64 bit output of a counter which is continuously incremented
at the rate of some oscillator then the time can be computed as follows:

    t = r * (tc << s) + c

The value of `s' is selected so that a second's worth of advance of
tc causes a change to bit 32 of (tc << s); that is, `s' is a constant
pre-computed from the nominal frequency of tc's counter and an assumption
about how far from the actual frequency of the oscillator that might
be.  The multiply (r * (tc << s)), where `r' is a 64 bit value, returns
the high order 64 bits of the 128 bit product.  In my case, `t' (and
hence 'c') was picked to be the time of day computed in the NTP fixed
point format, i.e. a 32 bit integer seconds part and a 32 bit fractional
part, so given a tc from the counter the above converts it directly to
a time of day.  The computation itself takes nanoseconds, or less, on
a modern processor.

Clearly the adjustment interface operates to produce values of `r' and
`c' that minimize the error in the result.  Phase adjustments are implemented
by adding an offset to 'c', and hence have a precision of 233 picoseconds.
Rate (i.e. frequency) adjustments are implemented by modifying the value
of 'r', with a corresponding change to 'c' to ensure phase continuity at
the time of the change, and have a precision of better than 10^-19.  Slews,
a la adjtime(), can be implemented by making a rate change for a fixed
interval, at the end of which `r' is returned to its previous value with
'c' precisely offset.  The only time `r' and `c' change is when the time
synchronization software makes a system call to adjust the clock; there
is no need to do anything in an interrupt service routine (the latter
assumes that the system call interface is not ntp_adjtime() or adjtimex();
while that code can be supported as well there are good arguments for
why you can expect better results, even from ntpd, if you don't include
that code in the kernel, though that's a different topic).  If your TSC
counter is reliable then making the sets of (s, r, c) constants available
to user space on a shared page allows user space processes to obtain
accurate time without system calls.  There are no "inconvenient" clock
rates and the clock precision and jitter is the same as the precision
and jitter of the underlying hardware counter.

If you want a "tickless" kernel the best way to do that might be to
start with a "tickless" system clock.  If you have a continuously
incrementing counter there is nothing that an interrupt service
routine needs to do.

Dennis Ferguson

More information about the questions mailing list