Using poll for timeout

Hi

I have written a timer class using which i can register callback
functions to be invoked at timeout. I am however facing a problem. The
code for the thread that checks for timeout is as follows:

while(true)
{
poll(0,0,1000);
sched_yield();
// take a thread from thread pool and ask it to execute the
functions registered by the timers that timeout now
........
}


Regarding the implementation of this class. I have chosen a timer
wheel implementation. So insertion, deletion and timeout all are O(1)
and this implementation also suits my application as it needs a lot of
timers.


So here is the description of the problem :-
Say i have registered 100 timers and each times out 10 second after
its preceding timer i.e timer t1 times out at 10 second from now t2 20
seconds from now and t3 30 seconds from now and so on ......

1) Before registering any timer, i do time(0) and store this value.
Lets say this value is X


2)So when the timer times out and a thread from thread pool begins to
execute the callback function registered with the timer i do time(0),
as the first statement of that function and store this value. Lets say
this value is Y

3) Then i do Y - X for each of the timer and find out that while most
of the timer show 10 seconds i.e timeout occurred after 10 seconds.
Some show 11 and some even show a value of 9.


This behaviour baffles me because essentially registering a timer and
timeout are O(1) and so i expect all my timers to give me Y - X = 10
and not an error of 1 second.

Is the fault in poll ??? I have even used nanosleep in place of poll
and the problem reproduces.
Is the fault in time(0) function ?

I would be grateful if some one provides some help on this issue.

Regarding, what i want to do is simple. Register a timer, note the
time of registration. Note the timeout of timeout and just make sure
the difference = time for which the timer was registered for timeout.

What should i do ? I am confused :p

Thank you all for your patience.

Regards
Kartik Mahajan

On Nov 11, 5:05*am, "lali.cpp" <lali....@gmail.com> wrote:
[color=blue]
> So here is the description of the problem :-
> Say i have registered 100 timers and each times out 10 second after
> its preceding timer i.e timer t1 times out at 10 second from now t2 20
> seconds from now and t3 30 seconds from now and so on ......
>
> 1) Before registering any timer, i do time(0) and store this value.
> Lets say this value is X
>
> 2)So when the timer times out and a thread from thread pool begins to
> execute the callback function registered with the timer i do time(0),
> as the first statement of that function and store this value. Lets say
> this value is Y
>
> 3) Then i do Y - X for each of the timer and find out that while most
> of the timer show 10 seconds i.e timeout occurred after 10 seconds.
> Some show 11 and some even show a value of 9.[/color]

You are rounding to the nearest second, so even if the timer is
exactly dead on, you will sometimes get a measurement that is off by a
second.
[color=blue]
> This behaviour baffles me because essentially registering a timer and
> timeout are O(1) and so i expect all my timers to give me Y - X = 10
> and not an error of 1 second.
>
> Is the fault in poll ??? I have even used nanosleep in place of poll
> and the problem reproduces.
> Is the fault in time(0) function ?[/color]

The 'time(0)' function has a granularity of one second and it gives
you the system's best estimate of wall clock time. Differences in wall
clock time are a very imprecise way to measure interval time.

DS

David Schwartz <davids@webmaster.com> writes:[color=blue]
> On Nov 11, 5:05*am, "lali.cpp" <lali....@gmail.com> wrote:[/color]

[...]
[color=blue][color=green]
>> Is the fault in poll ??? I have even used nanosleep in place of poll
>> and the problem reproduces.
>> Is the fault in time(0) function ?[/color]
>
> The 'time(0)' function has a granularity of one second and it gives
> you the system's best estimate of wall clock time.[/color]

The return value of time(0) is supposed to be the 'number of seconds
elapsed since the epoch'. 'Number of seconds elapsed since the epoch',
is defined as

A value that approximates the number of seconds that have
elapsed since the Epoch

additionally qualified by

The relationship between the actual time of day and the
current value for seconds since the Epoch is unspecified

and

How any changes to the value of seconds since the Epoch are
made to align to a desired relationship with the current
actual time is implementation-defined

IOW, the return value of time(0) is an implementation-defined value
which has some implementation-defined relation to the current, actual
time.
[color=blue]
> Differences in wall clock time are a very imprecise way to measure
> interval time.[/color]

Which, in turn, means that this statement is wrong. The quality of
measurements obtained in this way depends a) on the implementaion and
b) on wether the system is using sensible time synchronization policy.

The only generally sensible policy is one which follows the NTP 'clock
correctness principle', meaning, the clock is monotonic during normal
operation. This is a requirement for many distributed systems.

An implementation which cannot support a 'wall clock' in line the the
'clock correctness principle' is broken in this respect.

An installation which doesn't support the 'clock correctness principle'
because of 'administrative confusion' is misconfigured.

On Nov 11, 9:19*am, Rainer Weikusat <rweiku...@mssgmbh.com> wrote:
[color=blue]
> Which, in turn, means that this statement is wrong. The quality of
> measurements obtained in this way depends a) on the implementaion and
> b) on wether the system is using sensible time synchronization policy.[/color]

Perhaps so, but on every system, taking the difference in the system's
best estimate of wall clock time will probably a poor way to measure
an interval time.
[color=blue]
> The only generally sensible policy is one which follows the NTP 'clock
> correctness principle', meaning, the clock is monotonic during normal
> operation. This is a requirement for many distributed systems.[/color]

No, I completely disagree. There are many time functions that are
monotonic, but that's not what 'time' is supposed to return. The
'time' function is supposed to give the system's best estimate of
elapsed wall time. If that best estimate does in fact go backwards,
for whatever reason, the system should not lie and say it didn't.
[color=blue]
> An implementation which cannot support a 'wall clock' in line the the
> 'clock correctness principle' is broken in this respect.[/color]

So if for some reason the system's best estimate of wall clock time
does in fact go backwards, what should the system do? Lie to you and
say it didn't? Not give you its best estimate of wall clock time even
though that's what you asked for?
[color=blue]
> An installation which doesn't support the 'clock correctness principle'
> because of 'administrative confusion' is misconfigured.[/color]

Your principle is wrong. If you ask for the best estimate of wall
clock time, that's what you should get. If you ask for monotonic
elapsed times, that's what you should get. But a correctly designed
and configured system should always give you what you asked for.

The 'time' function asks for a time based on wall clock time. It
should not be monotonic if circumstances are such that the system's
best guess of wall clock time does in fact go backwards. There is no
way to make this impossible to happen and no reason to lie about it if
it does.

DS

Rainer Weikusat wrote:[color=blue]
> David Schwartz <davids@webmaster.com> writes:[color=green]
>> [...][/color]
> [...]
> IOW, the return value of time(0) is an implementation-defined value
> which has some implementation-defined relation to the current, actual
> time.
>[color=green]
>> Differences in wall clock time are a very imprecise way to measure
>> interval time.[/color]
>
> Which, in turn, means that this statement is wrong. The quality of
> measurements obtained in this way depends a) on the implementaion and
> b) on wether the system is using sensible time synchronization policy.[/color]

I think you are mixing up "precision" and "accuracy." No
matter how carefully the clock is or is not synchronized, the
precision of time(0) is one second. The accuracy is a different
matter.

Here is an accurate but imprecise statement: "The value
of pi is about 3."

Here is a precise but inaccurate statement: "The value
of pi is 4.8696044010893586188344909998762."

--
[email]Eric.Sosman@sun.com[/email]

Eric Sosman <Eric.Sosman@sun.com> wrote:[color=blue]
> I think you are mixing up "precision" and "accuracy." No
> matter how carefully the clock is or is not synchronized, the
> precision of time(0) is one second. The accuracy is a different
> matter.[/color]
[color=blue]
> Here is an accurate but imprecise statement: "The value
> of pi is about 3."[/color]
[color=blue]
> Here is a precise but inaccurate statement: "The value
> of pi is 4.8696044010893586188344909998762."[/color]

Eric must lurk in the NTP newsgroups :)

rick jones
--
Wisdom Teeth are impacted, people are affected by the effects of events.
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to post, OR email to rick.jones2 in hp.com but NOT BOTH...

lali.cpp <lali.cpp@gmail.com> wrote:[color=blue]
> Hi[/color]
[color=blue]
> I have written a timer class using which i can register callback
> functions to be invoked at timeout. I am however facing a problem. The
> code for the thread that checks for timeout is as follows:[/color]
[color=blue]
> while(true)
> {
> poll(0,0,1000);
> sched_yield();
> // take a thread from thread pool and ask it to execute the
> functions registered by the timers that timeout now
> .......
> }
> ...
> Is the fault in poll ??? I have even used nanosleep in place of poll
> and the problem reproduces. Is the fault in time(0) function ?[/color]


Others will be talking about accuracy and precision and such. I'm
going to pick a different nit that is perhaps only tangentially
related to your problem, based on subsequent folks' posts.

Why on earth use poll() for a one second timeout? That is akin to the
proverbial swatting of a fly with a howitzer. I would go with
nanosleep() (or sleep() for that matter if you will always be sleeping
for whole seconds).

The days of needing to use poll()/select() for "short" sleep times
should be _long_ gone now.

rick jones
--
portable adj, code that compiles under more than one compiler
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to post, OR email to rick.jones2 in hp.com but NOT BOTH...

David Schwartz wrote:
[snip][color=blue]
> The 'time' function asks for a time based on wall clock time. It
> should not be monotonic if circumstances are such that the system's
> best guess of wall clock time does in fact go backwards. There is no
> way to make this impossible to happen and no reason to lie about it if
> it does.[/color]

One reason to have a system lie about it is if you (as a system admin)
know that some software you are using depends on monotonicity for
correct operation.

Whether such a dependence is always avoidable is a separate issue, but I
am confident such software exists.

Alex

David Schwartz <davids@webmaster.com> writes:[color=blue]
> On Nov 11, 9:19*am, Rainer Weikusat <rweiku...@mssgmbh.com> wrote:
>[color=green]
>> Which, in turn, means that this statement is wrong. The quality of
>> measurements obtained in this way depends a) on the implementaion and
>> b) on wether the system is using sensible time synchronization policy.[/color]
>
> Perhaps so, but on every system, taking the difference in the system's
> best estimate of wall clock time will probably a poor way to measure
> an interval time.[/color]

The 'best estimate' is something you have made up for yourself in an
area which the UNIX(*)-standard leaves 'implementation defined'.
[color=blue][color=green]
>> The only generally sensible policy is one which follows the NTP 'clock
>> correctness principle', meaning, the clock is monotonic during normal
>> operation. This is a requirement for many distributed systems.[/color]
>
> No, I completely disagree. There are many time functions that are
> monotonic, but that's not what 'time' is supposed to return.[/color]

'time' is supposed to return 'an approximation of the amount of
seconds since the epoch', which relates to the current actual time in
an implementation-defined way and is synchronized to the current
actual time in an implementation defined way.
[color=blue]
> The 'time' function is supposed to give the system's best estimate of
> elapsed wall time. If that best estimate does in fact go backwards,
> for whatever reason, the system should not lie and say it didn't.[/color]

This implies that your idea of a 'wall clock' as random number
generator would not conflict with the UNIX(*) standard. But that
neither makes the 'random number generator' wall clock particularly
useful nor does it cause real-world implementation to behave in this
way.

Eric Sosman <Eric.Sosman@sun.com> writes:[color=blue]
> Rainer Weikusat wrote:[color=green]
>> David Schwartz <davids@webmaster.com> writes:[color=darkred]
>>> [...][/color]
>> [...]
>> IOW, the return value of time(0) is an implementation-defined value
>> which has some implementation-defined relation to the current, actual
>> time.
>>[color=darkred]
>>> Differences in wall clock time are a very imprecise way to measure
>>> interval time.[/color]
>> Which, in turn, means that this statement is wrong. The quality of
>> measurements obtained in this way depends a) on the implementaion and
>> b) on wether the system is using sensible time synchronization policy.[/color]
>
> I think you are mixing up "precision" and "accuracy." No
> matter how carefully the clock is or is not synchronized, the
> precision of time(0) is one second. The accuracy is a different
> matter.[/color]

I wasn't using the term 'imprecise' to express my heart-felt belief
that the clock of a UNIX(*) system should not be useful to measure
time, but to provide a sequence of random numbers :->.

Alex Fraser <me@privacy.net> writes:[color=blue]
> David Schwartz wrote:
> [snip][color=green]
>> The 'time' function asks for a time based on wall clock time. It
>> should not be monotonic if circumstances are such that the system's
>> best guess of wall clock time does in fact go backwards. There is no
>> way to make this impossible to happen and no reason to lie about it if
>> it does.[/color]
>
> One reason to have a system lie about it is if you (as a system admin)
> know that some software you are using depends on monotonicity for
> correct operation.
>
> Whether such a dependence is always avoidable is a separate issue,
> but I am confident such software exists.[/color]

Such software will exist for the simple reason that pre POSIX.4
implementations didn't provide a way to measure time intervals other
than by using the wall clock under the assumption that D. Schwartz
wasn't there and hasn't turned it into a random number generator
because that would be useless.

Rainer Weikusat wrote:[color=blue]
> Alex Fraser <me@privacy.net> writes:
>[color=green]
>>David Schwartz wrote:
>>[snip]
>>[color=darkred]
>>>The 'time' function asks for a time based on wall clock time. It
>>>should not be monotonic if circumstances are such that the system's
>>>best guess of wall clock time does in fact go backwards. There is no
>>>way to make this impossible to happen and no reason to lie about it if
>>>it does.[/color]
>>
>>One reason to have a system lie about it is if you (as a system admin)
>>know that some software you are using depends on monotonicity for
>>correct operation.
>>
>>Whether such a dependence is always avoidable is a separate issue,
>>but I am confident such software exists.[/color]
>
>
> Such software will exist for the simple reason that pre POSIX.4
> implementations didn't provide a way to measure time intervals other
> than by using the wall clock under the assumption that D. Schwartz
> wasn't there and hasn't turned it into a random number generator
> because that would be useless.[/color]

My take on it is that the reasoning for the wording in the definition of
time() was not to make it monotonic, but to simplify the implementation.

If the superuser sets system time backwards manually, then the result of
calling time() will also jump backwards. Same with gettimeofday().

For the benefit of the original poster, one POSIX way to get a monotonic
time suitable for measuring intervals is to use
clock_gettime(CLOCK_MONOTONIC).

Chris

On Nov 11, 11:31*am, Alex Fraser <m...@privacy.net> wrote:
[color=blue]
> David Schwartz wrote:[/color]
[color=blue][color=green]
> > The 'time' function asks for a time based on wall clock time. It
> > should not be monotonic if circumstances are such that the system's
> > best guess of wall clock time does in fact go backwards. There is no
> > way to make this impossible to happen and no reason to lie about it if
> > it does.[/color][/color]
[color=blue]
> One reason to have a system lie about it is if you (as a system admin)
> know that some software you are using depends on monotonicity for
> correct operation.[/color]

Sure, break the OS to work around broken software. But this question
is about writing software that's not broken in the first place.
[color=blue]
> Whether such a dependence is always avoidable is a separate issue, but I
> am confident such software exists.[/color]

Probably, but to create more broken software is not acceptable.
Understand that 'time' asks for a time based on wall clock time. If
you don't want that, don't ask for it.

DS

On Nov 11, 11:41*am, Rainer Weikusat <rweiku...@mssgmbh.com> wrote:
[color=blue]
> Such software will exist for the simple reason that pre POSIX.4
> implementations didn't provide a way to measure time intervals other
> than by using the wall clock under the assumption that D. Schwartz
> wasn't there and hasn't turned it into a random number generator
> because that would be useless.[/color]

The system's best estimate of wall clock time is not useless. There
are times when that is precisely what you want.

However, it is absolutely vital that software that has specific
accuracy or monotonicity requirements do whatever it takes to make
sure those requirements are met. What that is can certainly vary, but
failure to do so means the software is broken.

DS

> Sure, break the OS to work around broken software. But this question[color=blue]
> is about writing software that's not broken in the first place.[/color]

While I am not going to hold them up as a Paragon of Programming
Virtue, feel free to tell the likes of Oracle how their software is
broken :)

FWIW, the NTP daemon will only "step" adjust time (either forwards or
backwards) if the system time is off by more than some quantity,
otherwise it will slew the rate at which the system clock advances to
allow it to come into line with NTP's time view. Some system/OS
vendors were required by their customers to create versions of the NTP
daemon which "never" step the time precisely to meet the expectations
of not-quite random database software and the like.

rick jones
--
Wisdom Teeth are impacted, people are affected by the effects of events.
these opinions are mine, all mine; HP might not want them anyway... :)
feel free to post, OR email to rick.jones2 in hp.com but NOT BOTH...