From: Kevin K. <ke...@ac...> - 2008-07-05 16:56:34
|
Donal K. Fellows wrote: > OK, how do you work out how long until the next event fires without an > absolute time source? For added bonus points, do so with arbitrary > real-time delays between processing points and without extra threads. Donal, Many people here are unquestionably arguing from ignorance, but I do suspect after some conversations with Alexandre Ferrieux that they are onto something with wanting a distinction between absolute and relative times. Absolute time, as far as Tcl is concerned, is UTC with smoothing (http://www.cl.cam.ac.uk/~mgk25/uts.txt). It advances monotonically and (more or less) continuously, ticking at an uneven rate to accommodate TAI-UTC differences and NTP corrections. It *can* be nonmonotonic or discontinuous in unusual circumstances, owing to an act of God (a network outage causing too large an NTP jump to recover by advancing or retarding clock frequency), an act of the operator (adjusting system time by the wristwatch-and- -eyeball method), or an Act of Congress (Daylight Saving Time, on operating systems that use civil time as the reference). Its reference on Unix-like systems is gettimeofday(); on Windows systems its ultimate reference is the system clock returned by GetSystemTimeAsFileTime, with additional precision provided by interpolation using the performace counter. Relative time is not something that Tcl currently recognises, but perhaps should. It is strictly monotonic and uniform; it can be thought of as the independent variable of Newton's Laws of Motion. It is not - indeed, cannot be - tied to any concept of absolute time outside the computer, since all the "acts" above can cause dislocations. Nevertheless, it appears to be what people want in scheduling short-period tasks. Moreover, the anomalies in time handling on Windows (where near the Spring and Autumn transitions of Daylight Saving Time, the "UTC" returned by the system can be an hour off!) appear to be with us to stay. I've seen bugs in that area in every Windows release from 3.1 to Vista. We have historically (and I am an offender in that respect) offered the answer, "make your NTP infrastructure work!" That's certainly part of the answer, and necessary for other reasons (such as making sure that the system clock is reasonably synchronised with the clock of remotely-mounted file systems). It does not address the fact that there are timing windows at the Daylight Saving Time transitions during which the Windows API returns times that are simply incorrect. It also fails to address the concerns of those who deal with systems that have only intermittent network connectivity or lack it altogether. (Tcl gets ported to some very strange places, indeed.) Given these considerations, I think we can all agree that, all else being equal, we might gain something by distinguishing the relative timing function (today's [after] used for short-period tasks with loose accuracy being tolerable) and the absolute timing function (delivery of an event at a given time in the future, accounting for any known dislocations of the clock). The latter might be implemented by a command analogous to 'after' that accepts seconds (milliseconds, microseconds, choose a convenient unit) of UTS time from the epoch instead of milliseconds from the current time. The chief argument against that approach, we have stated in the past, is infeasibility. Unquestionably, we have system calls that delay a certain length of time irrespective of changes to the civil clock - indeed, sleep() and select() on Unix; and Sleep and MsgWaitForMultipleObjectsEx on Windows work that way. What we have lacked, or so we have claimed, is a reliable way to handle multiple relative timers - once the first timer has rung, how do we wind the second timer with the now-shorter interval that it needs? What is needed is a reference clock that advances with the properties that we require (monotonicity, uniformity, but not accuracy nor synchrony with the outside world). I - and apparently you, Donal - had long believed that no portable way existed to get such a clock, but I am coming to suspect that the world is catching up with our needs. On Windows, the information is available with the GetTickCount function, which has existed since the beginning (Windows attempts to calibrate its rate to NTP corrections, but guarantees its monotonicity except for the 49.7-day rollover, which we could deal with easily). Unix-like systems are a tougher nut to crack, but with the Posix standards being implemented more and more widely, I suspect that the times() function is a reasonable reference on Unix-like systems. While its primary purpose is to retrieve CPU time for a process, it has the side effect of returning clock ticks since an arbitrary point in the past, advancing in monotonic fashion. (This reference is needed when successive calls to times() are used to compute percent-CPU-usage.) It remains to be seen whether the combination of times() and GetTickCount() will work on all the platforms that we support, but it's also something that we could exploit anyway, by having the configurator check for the routines and fall back upon today's usage of absolute time if they are not available. I don't personally have the time at the moment to tackle such a project, but if someone else wants to draft a TIP and attempt a reference implementation, I'd be willing to shepherd them through the process. -- 73 de ke9tv/2, Kevin |
From: Donal K. F. <don...@ma...> - 2008-07-05 18:39:11
|
Kevin Kenny wrote: > Many people here are unquestionably arguing from ignorance, but I do > suspect after some conversations with Alexandre Ferrieux that they > are onto something with wanting a distinction between absolute and > relative times. While I could always see how to do it with single sets of timers, I could never work out how to do it reliably with multiple event sequences on different scales (e.g. a 13ms interval and a 1s interval) where the event processing takes an appreciable time w.r.t. the shorter intervals. Which happens for sure when using, say, Tk; redraws are quite expensive. With each pending timer event assigned an absolute time at which it becomes eligible for execution, it's pretty simple to handle. But without it... > I - and apparently you, Donal - had long believed that no portable > way existed to get such a clock, but I am coming to suspect that the > world is catching up with our needs. On Windows, the information is > available with the GetTickCount function, which has existed since the > beginning (Windows attempts to calibrate its rate to NTP corrections, > but guarantees its monotonicity except for the 49.7-day rollover, > which we could deal with easily). Unix-like systems are a tougher > nut to crack, but with the Posix standards being implemented more and > more widely, I suspect that the times() function is a reasonable > reference on Unix-like systems. Alas, no. On Darwin[*], times() is documented as returning the number of clock ticks since the Unix epoch, and so is inherently coupled to absolute time. It's also deprecated in favour of gettimeofday() (and getrusage(), but that's by the by). Without a monotonic reference, the problem's just about impossible without doing something elaborate with a RTOS. Donal. [* I read this in the manual pages on Leopard... ] |
From: Kevin K. <ke...@ac...> - 2008-07-05 23:29:56
|
Donal K. Fellows wrote: > Alas, no. On Darwin[*], times() is documented as returning the number > of clock ticks since the Unix epoch, and so is inherently coupled to > absolute time. It's also deprecated in favour of gettimeofday() (and > getrusage(), but that's by the by). > > Without a monotonic reference, the problem's just about impossible > without doing something elaborate with a RTOS. Does Darwin support clock_gettime(CLOCK_MONOTONIC, ×pec)? That's the current OpenGroup thinking, and I do believe that I'd have the configurator try for that first. (Nope! Looked it up - MacOSX does not support clock_gettime at all. What *were* they thinking?) In any case, on systems where there is no monotonic reference available (I suspect the other BSD's share the problem with Darwin), we can fall back on using gettimeofday() as the reference for relative timers. Darwin is less likely than Windows and Linux to be deployed in an environnment with no possibility of a working NTP infrastructure. (How many Apples do you see running factories or labs?) And it also doesn't have the "guaranteed twice a year" failure that Windows appears to be prone to. Alex's suggestion makes things better on Windows and Linux, and does no harm on HPUX and Solaris. The big hurdle is still autoconf - to recognize the method to be used, from among clock_gettime(CLOCK_MONOTONIC, ...) Solaris, BSD's, newer Linuxes. Solaris needs -lrt or -lposix4 times() HP-UX (lacks CLOCK_MONOTONIC), older Linuxes, older BSD's, AIX GetTickCount() Windows gettimeofday Ultimate fallback, no worse than today. Darwin, others? I could be all wet about some of these. -- 73 de ke9tv/2, Kevin |
From: Daniel A. S. <da...@us...> - 2008-07-06 01:46:46
|
On 05/07/2008, at 19:58, Donal K. Fellows wrote: > On Darwin[*], times() is documented as returning the number > of clock ticks since the Unix epoch, and so is inherently coupled to > absolute time. the Darwin implementation of times() comes from FreeBSD and is completely trivial, the return value is just gettimeofday() in ticks (c.f. Darwin source file Libc/gen/times-fbsd.c reproduced below). Might be worthwhile checking if current *BSDs still use this technique as well... However, Darwin does have a platform-specific function to get a monotonic time reference: mach_absolute_time(), which we are using in Tcl already for high-resolution clicks, c.f. TclpGetWideClicks() and TclpWideClicksToNanoseconds() in tclUnixTime.c. mach_absolute_time() is based on the CPU TSC (adjusted for CPU nap/ sleep) and is guaranteed to be monotonically increasing, see e.g. the following Darwin kernel sources for details: xnu/osfmk/i386/rtclock.c xnu/osfmk/i386/machine_routines_asm.s xnu/osfmk/i386/ommpage/commpage_mach_absolute_time.s xnu/osfmk/i386/commpage/commpage.c (commpage_set_nanotime) All the implementations of relative timers in the OS (nanosleep(), pthread_cond_timedwait_relative_np() etc) are based on this reference. Finding a function that returns an monotonic time reference on a system does not solve the problem of implementing relative timers in Tcl however, you also need a way for the notifier to wait for a relative time interval, e.g. the current threaded unix notifier waiting is based on pthread_cond_timedwait(), which uses absolute time (c.f. Tcl_ConditionWait()). Darwin has pthread_cond_timedwait_relative_np() for exactly this purpose, I don't know if other systems have something equivalent. There is also the problem of what to do in the notifier in the presence of both absolute and relative timers, i.e. use an absolute or a relative timeout? (converting next absolute timer fire to a relative time interval may result in waiting for too long if there are changes to the gettod base). Cheers, Daniel -- ** Daniel A. Steffen ** ** <mailto:da...@us...> ** /*- * Copyright (c) 1990, 1993 * The Regents of the University of California. All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * 3. All advertising materials mentioning features or use of this software * must display the following acknowledgement: * This product includes software developed by the University of * California, Berkeley and its contributors. * 4. Neither the name of the University nor the names of its contributors * may be used to endorse or promote products derived from this software * without specific prior written permission. * * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF * SUCH DAMAGE. */ #if defined(LIBC_SCCS) && !defined(lint) static char sccsid[] = "@(#)times.c 8.1 (Berkeley) 6/4/93"; #endif /* LIBC_SCCS and not lint */ #include <sys/cdefs.h> __FBSDID("$FreeBSD: src/lib/libc/gen/times.c,v 1.2 2002/02/01 01:08:48 obrien Exp $"); #include <sys/param.h> #include <sys/time.h> #include <sys/times.h> #include <sys/resource.h> /* * Convert usec to clock ticks; could do (usec * CLK_TCK) / 1000000, * but this would overflow if we switch to nanosec. */ #define CONVTCK(r) (r.tv_sec * CLK_TCK + r.tv_usec / (1000000 / CLK_TCK)) clock_t times(tp) struct tms *tp; { struct rusage ru; struct timeval t; if (getrusage(RUSAGE_SELF, &ru) < 0) return ((clock_t)-1); tp->tms_utime = CONVTCK(ru.ru_utime); tp->tms_stime = CONVTCK(ru.ru_stime); if (getrusage(RUSAGE_CHILDREN, &ru) < 0) return ((clock_t)-1); tp->tms_cutime = CONVTCK(ru.ru_utime); tp->tms_cstime = CONVTCK(ru.ru_stime); if (gettimeofday(&t, (struct timezone *)0)) return ((clock_t)-1); return ((clock_t)(CONVTCK(t))); } |
From: Alexandre F. <ale...@gm...> - 2008-07-07 14:08:49
|
On 7/6/08, Daniel A. Steffen <da...@us...> wrote: > > All the implementations of relative timers in the OS (nanosleep(), > pthread_cond_timedwait_relative_np() etc) are based on this reference. So, the shell loop 'while :;do sleep 1;echo foo;done' should have visible quirks when someone sets the date, right ? Is the timeout in select() also based on this absolute clock ? > Finding a function that returns an monotonic time reference on a > system does not solve the problem of implementing relative timers in > Tcl however, you also need a way for the notifier to wait for a > relative time interval, e.g. the current threaded unix notifier > waiting is based on pthread_cond_timedwait(), which uses absolute time > (c.f. Tcl_ConditionWait()). That may be another reason to reform the threaded notifier, if you allow me that digression ;-) > Darwin has pthread_cond_timedwait_relative_np() for exactly this > purpose, I don't know if other systems have something equivalent. Don't know either but please notice that going to select() everywhere would solve the problem uniformly. The non-threaded unix notifer has no problem with relative timers, it's just that currently the value is recomputed based on absolute time when it needs be. > (converting next absolute timer fire to a relative > time interval may result in waiting for too long if there are changes > to the gettod base). That's exactly what happens today in Windows and unthreaded unix, since WaitForMultiple* (resp. select()) both take a relative timeout. See TIP302. -Alex |
From: Kevin K. <ke...@re...> - 2008-07-07 14:47:04
|
> Finding a function that returns an monotonic time reference on a > system does not solve the problem of implementing relative timers in > Tcl however, you also need a way for the notifier to wait for a > relative time interval, e.g. the current threaded unix notifier > waiting is based on pthread_cond_timedwait(), which uses absolute > time (c.f. Tcl_ConditionWait()). Is it really true that pthread_cond_timedwait uses an absolute time? That would imply that every pthreads process that's waiting for a timer will freeze if the system clock ever jumps backwards. Do other things freeze on Darwin in that case? It's not, strictly speaking, necessary to have functions that wait for both absolute and relative times. It's good enough if a wait can be interrupted when the system clock is reset. WM broadcasts a WM_SETTINGSCHANGED in that case. -- 73 de ke9tv/2, Kevin |
From: Daniel A. S. <da...@us...> - 2008-07-07 17:45:18
|
On 07/07/2008, at 16:44, Kevin Kenny wrote: >> Finding a function that returns an monotonic time reference on a >> system does not solve the problem of implementing relative timers in >> Tcl however, you also need a way for the notifier to wait for a >> relative time interval, e.g. the current threaded unix notifier >> waiting is based on pthread_cond_timedwait(), which uses absolute >> time (c.f. Tcl_ConditionWait()). > > Is it really true that pthread_cond_timedwait uses an absolute time? > That would imply that every pthreads process that's waiting for a > timer will freeze if the system clock ever jumps backwards. Do > other things freeze on Darwin in that case? no, as I have just discovered, while pthread_cond_timedwait takes an absolute time, it does in fact just wait for the relative interval to the value of gettimeofday() at the start of the call (i.e. if calendar time is adjusted/changed during the waiting, the kernel does not update the timeouts AFAICT). > It's not, strictly speaking, necessary to have functions that wait > for both absolute and relative times. It's good enough > if a wait can be interrupted when the system clock is reset. agreed, Darwin sends a host notification when calendar time is changed via settimeofday() (but not for adjustments due to adjtime()), it might take a separate thread to integrate listening to that notification into the tcl notifier though, I'd have to look into it. Cheers, Daniel -- ** Daniel A. Steffen ** ** <mailto:da...@us...> ** |
From: Daniel A. S. <da...@us...> - 2008-07-07 17:38:27
|
Hi Alexandre, On 07/07/2008, at 16:08, Alexandre Ferrieux wrote: > On 7/6/08, Daniel A. Steffen <da...@us...> wrote: >> >> All the implementations of relative timers in the OS (nanosleep(), >> pthread_cond_timedwait_relative_np() etc) are based on this >> reference. > > So, the shell loop 'while :;do sleep 1;echo foo;done' should have > visible quirks when someone sets the date, right ? no, why? that's a relative timeout, /bin/sleep relies on nanosleep() and is not affected by calendar time changes (i.e. settimeofday() or adjtime()) the 'absolute' in mach_absolute_time() may be confusing matters, that's the monotonic time reference for relative time intervals (i.e. differences of m_a_t() values), whereas absolute timers are calendar time based. However, on Darwin at least it turns out that even the APIs that take an absolute time to wait (like pthread_cond_timedwait()) in fact just wait for the relative interval to the value of gettimeofday() at the start of the call (i.e. if calendar time is adjusted/changed during the waiting, the kernel does not update the timeouts AFAICT). > Is the timeout in select() also based on this absolute clock ? yes, again a relative timeout, c.f. xnu/bsd/kern/sys_generic.c (the timeout is converted to the m_a_t() scale, added to the current m_a_t() and a kernel timer is scheduled to wakeup the calling thread at that deadline). > That may be another reason to reform the threaded notifier, if you > allow me that digression ;-) yes, still working on that one, been busy... >> Darwin has pthread_cond_timedwait_relative_np() for exactly this >> purpose, I don't know if other systems have something equivalent. > > Don't know either but please notice that going to select() > everywhere would solve the problem uniformly. yes, but you would loose all the advantages of the current threaded notifier model (as discussed at length here before), which IMO would be much worse than the absolute/relative timer problems, esp. if we can find equivalents to pthread_cond_timedwait_relative_np()... > The non-threaded unix notifer has no problem with relative timers, > it's just that currently the value is recomputed based on absolute > time when it needs be. However, if you actually want absolute timers (as the current [after] implementation appears to), using select() may be incorrect unless you can find a way to be woken up when the gettod base changes. On Darwin a host notification is sent when calendar time is changed via settimeofday() (but not for adjustments due to adjtime()), I don't know if something similar exists on other platforms. >> (converting next absolute timer fire to a relative >> time interval may result in waiting for too long if there are changes >> to the gettod base). > > That's exactly what happens today in Windows and unthreaded unix, > since WaitForMultiple* (resp. select()) both take a relative timeout. > See TIP302. yes, I know, my question was what to do if in presence of _both_ absolute and relative timeouts (e.g. if your -robust option in TIP302 were adopted in addition to the current [after] based on absolute timers). Cheers, Daniel -- ** Daniel A. Steffen ** ** <mailto:da...@us...> ** |
From: Alexandre F. <ale...@gm...> - 2008-07-07 19:16:40
|
On 7/7/08, Daniel A. Steffen <da...@us...> wrote: > Hi Alexandre, > > On 07/07/2008, at 16:08, Alexandre Ferrieux wrote: > > > On 7/6/08, Daniel A. Steffen <da...@us...> wrote: > > > > > > > > All the implementations of relative timers in the OS (nanosleep(), > > > pthread_cond_timedwait_relative_np() etc) are based on > this reference. > > > > > > > So, the shell loop 'while :;do sleep 1;echo foo;done' should have > > visible quirks when someone sets the date, right ? > > > > no, why? that's a relative timeout, /bin/sleep relies on nanosleep() and is > not affected by calendar time changes (i.e. settimeofday() or adjtime()) > the 'absolute' in mach_absolute_time() may be confusing matters, that's the > monotonic time reference for relative time intervals (i.e. differences of > m_a_t() values), whereas absolute timers are calendar time based. You're right, I was confused :-} > However, on Darwin at least it turns out that even the APIs that take an > absolute time to wait (like pthread_cond_timedwait()) in fact just wait for > the relative interval to the value of gettimeofday() at the start of the > call (i.e. if calendar time is adjusted/changed during the waiting, the > kernel does not update the timeouts AFAICT). OK, so pthread_cond_timedwait is equivalent to the timeout in select() after all. The reform can wait ;-) > However, if you actually want absolute timers (as the current [after] > implementation appears to), using select() may be incorrect unless you can > find a way to be woken up when the gettod base changes. On Darwin a host > notification is sent when calendar time is changed via settimeofday() (but > not for adjustments due to adjtime()), I don't know if something similar > exists on other platforms. Yes. Now what about the following hack: have a coarse-grained periodic task (say every 5 sec or so), based on a relative timer (!), that checks for dicontinuities in gettod() (among others, it would kick in everytime the machine is woken up from hibernation). Wouldn't that be an appropriate replacement for your systemwide event ? The idea being that when gettod is changed, precision under a few seconds is no longer a concern anyway... Regarding your other question: what to do with a mix of relative and absolute timers ? Simple: have two queues of timer tokens, one with targets expressed in ticks (for the relative timers), the other with targets in gettod (for the absolute ones, just like today's [after]). Then, whenever the notifier is preparing for bed, recompute the relative time of the first of each queue, take the min, and sleep for that. Of course the periodic watchdog above can be integrated in this scheme. Even without looking at gettod itself, by the simple fact that it forces the notifier to recompute the next time-jump frequently, this method would guarantee the timely firing of absolute timers even in drastic settod conditions. (Notice that while we qualify today's [after] as absolute, it will only track a settod *if* some event source (timer or not) wakes us up frequently enough. Kevin was in this case if I understand correctly.) -Alex |
From: Daniel A. S. <da...@us...> - 2008-07-07 20:23:05
|
On 07/07/2008, at 21:16, Alexandre Ferrieux wrote: > Now what about the following hack: have a coarse-grained periodic > task (say every 5 sec or so), based on a relative timer (!), that > checks for dicontinuities in gettod() (among others, it would kick in > everytime the machine is woken up from hibernation). Wouldn't that be > an appropriate replacement for your systemwide event ? The idea being > that when gettod is changed, precision under a few seconds is no > longer a concern anyway... agreed, feasible (if possibly somewhat expensive) fallback for systems where there is no gettod base change notification. > Regarding your other question: what to do with a mix of relative and > absolute timers ? Simple: have two queues of timer tokens, one with > targets expressed in ticks (for the relative timers), the other with > targets in gettod (for the absolute ones, just like today's [after]). sure, that wasn't the question ;-) I was asking (before I figured out that pt_c_tw is internally also relying on a relative timeout) how the notifier should wait for both relative as well as absolute timeouts with a single API call, in the face of gettod base changes; the answer appears to be to use a relative timeout and listen to gettod base change notification (or fallback to your periodic gettod check timer above)... Cheers, Daniel -- ** Daniel A. Steffen ** ** <mailto:da...@us...> ** |