Re: spurious wakeup

From: Marcin 'Qrczak' Kowalczyk (qrczak_at_knm.org.pl)
Date: 11/28/04 

Date: Sun, 28 Nov 2004 01:39:22 +0100

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@web.de (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
   \__/       qrczak@knm.org.pl
    ^^     http://qrnik.knm.org.pl/~qrczak/

Relevant Pages

  • Re: calling wait outside of loop
    ... and notify has been called prior to wait, ... what is the argument for calleding after the loop. ... Typically you may have multiple threads waiting, only one of which can proceed. ... Each thread will need to check the notify is for them. ...
    (comp.lang.java.programmer)
  • Re: illegalMonitorStateException
    ... you are waiting for *something* to ... because the notify() that it was waiting for has ... checking the predicate and wait ... That's true for two distinct reasons: ...
    (comp.lang.java.programmer)
  • Re: How to notify specific thread??
    ... > while loop is false the wait is invoked on the thread. ... > But I would like to be able to notify only the correct thread. ... It is impossible to notify a specific thread that's waiting on a ... then you can split the monitor into several monitors. ...
    (comp.lang.java.help)
  • Re: calling wait outside of loop
    ... How does waiting in the loop prevent that: ... and notify has been called prior to wait, ... what is the argument for calleding after the loop. ... Do you mean that you are calling notify sometimes before the obj.waitand its loop are called? ...
    (comp.lang.java.programmer)
  • Re: How to notify specific thread??
    ... > If I have x number of threads that is waiting and I only want to notify a ... > specific object is inserted into a Database. ... > while loop is false the wait is invoked on the thread. ... > But I would like to be able to notify only the correct thread. ...
    (comp.lang.java.help)