Re: spurious wakeup

Discussion in 'C++' started by Markus Elfring, Nov 27, 2004.

  1. > That's a lot of lines compared to while (!predicate) wait(condition);

    If you want to provide protection against spurious wakeups by a
    library function or method, you need to pass the predicate and the
    surrounding and corresponding code as (template) parameters.
    Would you like to use a similar service quality like it is available
    for the algorithms "std::for_each()" and "std::find_if()"?


    > If the condition variable is wrapped together with the predicate, I
    > expect waiting to be equivalent to the above while loop, because this
    > is the classic pattern of waiting for a condition. In this case it
    > doesn't matter whether the "raw" condition wait has spurious wakeups
    > (the predicate should not have side effects and should not take too
    > long to compute). When the predicate is satisfied, the waiting
    > function returns.


    It does matter if the documentation leaves out that spurious wakeups
    can happen.
    How many libraries do implement just the pthreads behaviour?

    http://wefts.sourceforge.net/wefts-apidoc-0.99c/classWefts_1_1Condition.html#a0
    http://www.gnu.org/software/commoncpp/docs/refman/html/class_conditional.html#a0
    http://www.home.unix-ag.org/weitzel/threadspp.php

    But the page "http://zthread.sourceforge.net/html/classZThread_1_1Condition.html"
    contains the following statement.
    "...
    A Condition is not subject to spurious wakeup.
    ...."

    Regards,
    Markus
     
    Markus Elfring, Nov 27, 2004
    #1
    1. Advertising

  2. Sorry, I don't read comp.lang.c++, and my response is more about threading
    than about C++, so I'm setting Followup-To back to comp.programming.threads.

    (Markus Elfring) writes:

    >> That's a lot of lines compared to while (!predicate) wait(condition);

    >
    > If you want to provide protection against spurious wakeups by a
    > library function or method, you need to pass the predicate and the
    > surrounding and corresponding code as (template) parameters.


    The while loop protects against spurious wakeups too. It's not a
    method, but so what? It can be wrapped in a macro if you insist on
    a simpler syntax.

    > Would you like to use a similar service quality like it is available
    > for the algorithms "std::for_each()" and "std::find_if()"?


    In these cases:
    - it's not the only solution available: you can advance iterators
    manually too;
    - the corresponding loop is a bit more complex than this while loop,
    so it's more often a win than here.

    You can provide a function which takes the predicate as an object,
    but I would not like to be forced to use it as the only option. It's
    equivalent to the while loop anyway, so it doesn't provide anything
    new. And the while loop is usually easier to write because C++ lacks
    function closures.

    In general I avoid C and C++ all, except for implementing a runtime
    of a higher level language.

    >> If the condition variable is wrapped together with the predicate, I
    >> expect waiting to be equivalent to the above while loop, because this
    >> is the classic pattern of waiting for a condition. In this case it
    >> doesn't matter whether the "raw" condition wait has spurious wakeups
    >> (the predicate should not have side effects and should not take too
    >> long to compute). When the predicate is satisfied, the waiting
    >> function returns.

    >
    > It does matter if the documentation leaves out that spurious wakeups
    > can happen.


    Then it's the documentation that should be fixed.

    My model of usage of conditions assumes that:

    - Each condition is associated with a predicate, which is consistently
    used for waiting for the condition (but see below).

    Technical note: in languages with function closures the predicate
    is better physically attached to the condition; in languages without
    closures an explicit while loop will be easier to use. The semantics
    is the same in either case, as long as you stick to the conventions.

    - The predicate doesn't have side effects and takes a short amount of
    time, thus it doesn't matter how often it's called.

    - Soon after each state change which *may* cause the predicate to
    change from false to true and which is followed by releasing the
    mutex, the thread calls Notify / pthread_cond_broadcast / notifyAll
    / PulseAll (whatever it's called in the given language or threading
    library).

    You may safely notify in more cases than needed (degrading
    performance), but you must not notify less.

    Even though the set of places where notification should be inserted
    is roughly determined by the semantics of the code (modulo the fact
    that it can be larger than needed if it's more convenient), the
    programmer must do this himself. It's because it is impractical
    for the compiler to detect all such cases automatically. An easily
    automatizable safe approximation (e.g. notifying in all cases when
    the mutex is being released) is too wasteful.

    - The call to Notify can be optimized to Notify1 / pthread_cond_signal
    / notify / Pulse, in case we know that any waiting thread will cause
    the predicate to become false again (or will notify another thread
    itself), and thus at most one thread will benefit from being woken up.

    This optimization is optional. You can stick to always notifying all
    threads (degrading performance), but you must not apply it when more
    than one thread should be woken up.

    Again it is done manually because automatic detection by the
    compiler of cases when it is safe to apply would be too hard.

    Note that it's the broadcast version which is the conceptual
    default. I think that languages which give the wake-up-one-thread-only
    version a simpler name had made a worse choice of names.

    Under these assumptions it doesn't matter whether the low-level
    condition wait has spurious wakeups. There are no cases when the
    predicate has become true, yet no waiting thread should be woken up
    now, and the code would try to archieve that by omitting a call to
    notify. This would not work (a thread could be woken up nevertheless
    because of a spurious wakeup), but this never happens under these
    assumptions. The code must be careful to notify in *all* cases when
    the predicate might have changed to true. And if it did not change,
    a spurious wakeup has no visible effect.

    I believe these assumptions cover all practical uses of conditions,
    i.e. using low-level condition primitives in ways not adhering to
    the assumptions is never necessary. A minor speed-up caused by e.g.
    evaluating the predicate after low-level waiting at least once
    (if we know it was false before the loop) is really minor.

    Well, in my language I allowed one extension of these assumptions
    (after someone's advice in c.p.treads, and without a concrete
    practical use case in mind): the predicate can be slightly different
    in various invocations of Wait on the same condition, i.e. you can
    supply a different predicate during waiting, which replaces the
    predicate stored in the condition. All variations must be covered
    by notification of course. This usage is probably very rare.

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Nov 28, 2004
    #2
    1. Advertising

  3. > The while loop protects against spurious wakeups too. It's not a
    > method, but so what? It can be wrapped in a macro if you insist on
    > a simpler syntax.


    You must remember to repeat this loop at all places of the wait call
    if the library's implementation does not offer the suggested
    protection. How big is the probability to forget its application?
    Templates are the safe syntax for a lot of macros.

    Regards,
    Markus
     
    Markus Elfring, Nov 28, 2004
    #3
  4. (Markus Elfring) writes:

    >> The while loop protects against spurious wakeups too. It's not a
    >> method, but so what? It can be wrapped in a macro if you insist on
    >> a simpler syntax.

    >
    > You must remember to repeat this loop at all places of the wait call
    > if the library's implementation does not offer the suggested
    > protection.


    There is no substitute to remembering to use the correct API. If he
    can forget that waiting should be in a loop, he can as well forget
    your template name, or misuse its arguments.

    The loop is usually necessary anyway, even without spurious wakeups:

    - Another thread may get the mutex between the thread that notified
    about change of the condition, and the thread which was woken up.
    It can cause the condition to become false again.

    - If several threads are woken up, it's probable that one of them will
    make the condition false before others have a chance to run, and
    they should wait again.

    - It's can be convenient to notify when the condition *might* become
    true when the thread is in a particular place, without precise
    checking of all values of variables which influence the predicate.
    Examples of this were in my elevator sample.

    In general it's the responsibility of the waiting thread to ensure
    that it really wants to proceed. Other threads must only ensure that
    they will not miss any possibility of changing of the predicate,
    but they may notify in more cases than needed: they don't have to
    duplicate the work of checking the predicate precisely.

    Thus the fact that waiting is associated wich a predicate which should
    be tested in a loop should be taught when the concept of condition
    variables is introduced. It is even said in X/Open documentation,
    which is not a tutorial but a reference. It's just a part of the
    knowledge about how to use condition variables.

    I think it's easier to make a bug in emulating a first-class function
    in C++, than in forgetting that pthread_cond_wait should be inside
    'while' rather than 'if'.

    > How big is the probability to forget its application?
    > Templates are the safe syntax for a lot of macros.


    If you value safety so much, using C++ is a bad idea (lots of
    potential undefined behavior out there if you forget about other
    things).

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Nov 28, 2004
    #4
  5. > Thus the fact that waiting is associated wich a predicate which should
    > be tested in a loop should be taught when the concept of condition
    > variables is introduced. It is even said in X/Open documentation,
    > which is not a tutorial but a reference. It's just a part of the
    > knowledge about how to use condition variables.
    >
    > I think it's easier to make a bug in emulating a first-class function
    > in C++, than in forgetting that pthread_cond_wait should be inside
    > 'while' rather than 'if'.


    Are you interested to encapsulate the predicate handling into a class?
    Can a "convenient" wait method (without spurious wakeups) become part
    of a library API?

    Regards,
    Markus
     
    Markus Elfring, Nov 29, 2004
    #5
  6. (Markus Elfring) writes:

    > Are you interested to encapsulate the predicate handling into a class?


    In languages with function closures - yes.
    In languages without - no.

    > Can a "convenient" wait method (without spurious wakeups) become part
    > of a library API?


    Depends on the above.

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Nov 29, 2004
    #6
  7. > > Are you interested to encapsulate the predicate handling into a class?
    > In languages with function closures - yes.
    > In languages without - no.


    Would you like to show an example for such a "closure"?
    Can it be emulated in C++?

    I hope that the ZThread's wait method will not remain the only
    implementation free of spurious wakeups.

    Regards,
    Markus
     
    Markus Elfring, Nov 30, 2004
    #7
  8. Markus Elfring

    Joe Seigh Guest

    Markus Elfring wrote:
    >
    > > > Are you interested to encapsulate the predicate handling into a class?

    > > In languages with function closures - yes.
    > > In languages without - no.

    >
    > Would you like to show an example for such a "closure"?
    > Can it be emulated in C++?


    A C define should do it (error checking aside).

    #define WaitForCond(cv, m, p) while (!(p)) pthread_cond_wait(cv, m)

    >
    > I hope that the ZThread's wait method will not remain the only
    > implementation free of spurious wakeups.
    >


    You should probably use a different term than spurious. In Posix it
    means wakeups not caused by a signal and has nothing to do with whether
    a predicate is true or not on wakeup. You can have a predicate be
    true on a spurious Posix wakeup.

    Joe Seigh
     
    Joe Seigh, Nov 30, 2004
    #8
  9. (Markus Elfring) writes:

    >> > Are you interested to encapsulate the predicate handling into a class?

    >> In languages with function closures - yes.
    >> In languages without - no.

    >
    > Would you like to show an example for such a "closure"?


    E.g. if the condition is "x > 0", it might look like this, depending
    on the language:

    Dylan: method () x > 0 end
    Haskell: do v <- readIORef x; return (v > 0)
    Kogut: {x > 0}
    Lisp: #'(lambda () (> x 0))
    ; or just (> x 0) when waiting is wrapped by a macro
    OCaml: fun () -> !x > 0
    Perl: sub {$x > 0}
    Python: lambda: x > 0
    Ruby: {x > 0}
    # must be written after arguments of a method call
    Scheme: (lambda () (> x 0))
    ; or just (> x 0) when waiting is wrapped by a macro
    Smalltalk: [x > 0]
    SML: fn () => !x > 0

    > Can it be emulated in C++?


    Gt0(&x)
    // when Gt0 is defined thus (at the toplevel):
    class Gt0 {
    int *var;
    public:
    Gt0(int *v): var(v) {}
    bool operator() const {return *var > 0;}
    };

    > I hope that the ZThread's wait method will not remain the only
    > implementation free of spurious wakeups.


    IMHO wrapping the waiting loop in a function is not worth the price of
    emulation of function closures in C++. It's simpler to remember to prefix
    pthread_cond_wait by 'while' instead of 'if'.

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Nov 30, 2004
    #9
  10. Markus Elfring, Nov 30, 2004
    #10
  11. (Markus Elfring) writes:

    >> In languages with function closures - yes.
    >> In languages without - no.

    >
    > Would you like to adjust your view if you consider the following articles?
    > - http://en.wikipedia.org/wiki/Closure_(computer_science)
    > - http://en.wikipedia.org/wiki/Function_object


    I've already said what my view is. I know what is a function closure
    and I know how it can be emulated in C++. It doesn't change my view
    that it's inconvenient when not supported by the language directly.

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Nov 30, 2004
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. eidosh
    Replies:
    3
    Views:
    4,110
    Darryl L. Pierce,,,
    Mar 3, 2004
  2. Markus Elfring

    Re: spurious wakeup

    Markus Elfring, Nov 25, 2004, in forum: C++
    Replies:
    0
    Views:
    438
    Markus Elfring
    Nov 25, 2004
  3. Erich Schreiber

    Premature wakeup of time.sleep()

    Erich Schreiber, Sep 12, 2005, in forum: Python
    Replies:
    5
    Views:
    497
    Peter Hansen
    Sep 13, 2005
  4. Mark Volkmann

    opposite of Thread.wakeup

    Mark Volkmann, Jan 10, 2006, in forum: Ruby
    Replies:
    4
    Views:
    114
    Andrew Johnson
    Jan 11, 2006
  5. Laurent
    Replies:
    2
    Views:
    170
    Robert Klemme
    May 14, 2007
Loading...

Share This Page