[concurrency-interest] spurious wakeups semantics

P.H.Welch P.H.Welch at kent.ac.uk
Wed Nov 2 12:09:12 EST 2005

Matthias and Tim both raise the defence for while-not-condition-wait-loops
with the classical argument that something might have unset the waited-for
condition between the notifyer setting it up and the waiter reacquiring
the monitor.  Of course that may happen ... but only if the logic in the
programmed system is sloppy (I used the term "lazy" last time).

I come from a different school.  With Hoare monitors, a waiting process
atomically reacquires the monitor from a "notifying" process that has
set up the condition being awaited - the term "signal" is used rather
than "notify".  That allows proofs of liveness - that a waiting process
will eventually proceed if enough signals happen.

The Java "notify" retains the monitor, allowing silly things to be done
- like unsetting the condition about which you just notified.  Worse -
because it's more complex - entirely different threads can acquire the
monitor between notification and reacquisition by the waiting thread and,
as you say, they can unset the condition.  So, we "have" to put our
wait()s inside a while-not-condition loop.  But ... only because of
sloppy design ... conjecture again!

Why does the Java "notify" retain the monitor?  Probably to reduce context
switching (and consequent cache missing) - I guess??

But the cost is busy - possibly infinite - waiting to get out of that
while-not-condition-wait-loop.  It's easy to create an example of a system
that's 99% of its time asleep - waiting for things to happen - with all
the wait()s protected by while-loops waiting for the right condition and
with all the notifying processes doing "notifyAll()"s ... and yet some
threads never progress out of their while-not-condition-wait-loops ...
all the rules in the text book have been followed!  Not good.

Matthias noted:
> A trivial implementation of a concept does not render the concept
> nonsensical.  The implementation is just not useful then.

But our programs must survive being executed on such a useless, but legal,
implementation.  I suspect most would not?  The fact that a trivial
implementation of a concept might exist means that our use of the concept
must cope with that implementation ... and if it can't, that renders
the concept (or at least our use of it) useless.

Tim noted:
> Who would benefit?
> Not JVM designers, since they would have to work around the possibility
> of spurious wakeups at the OS level, with a consequent cost in performance.

It's surely much better for the JVM to protect the Java system from broken
OS threading mechanisms.  Allowing the spurious wakeups through has an
effect of performance as well -- pulling the woken thread off the wait-set
and into the acquire-the-monitor-set, scheduling that woken thread,
executing its code to test (folornly) its while-condition, and finally
putting that woken thread back in the wait-set and scheduling another
thread.  That doesn't look too attractive.

Better: don't build your JVM on a broken threading mechanism ... it is
possible to have unbroken ones that don't do things when they shouldn't.

> Imagine what would happen if spurious wakeups were disallowed. First,
> programmers (those who never really bought into the idea that premature
> optimization is evil) would rush to turn this ... <description of
> while-wait-loop turned into if-wait>.

It sounds like you're threatening us with spurious wakeups just to make
us keep the while-wait-loop, :).

I would hope that - alongside converting while-wait-loop to if-wait -
they would look very carefully at the logic of their monitor methods
to ensure that the condition can't be unset between notification and
re-acquisition.  Getting that wrong is as bad as the spurious wakeup
and as costly for performance (perhaps infinitely so).  Of course,
the same duty must be imposed on maintainers of the system.

And, of course, this might be very difficult ... but that's a problem with
working with monitors ...  and, indeed, with most kinds of object locking.

Just seen ...

Brian wrote:
> Hoare monitors are a mathematical abstraction.  Spurious wakeups are
> permitted in recognition of the fact that real life is messy.  You can
> build an OS / thread package that NEVER delivers spurious wakeups, but
> there is a real engineering cost.  It is far more practical and
> efficient to allow the odd spurious wakeup.

Clean mathematical abstractions are *necessary* (though not sufficient)
for clean - and, hence, fast, simple and efficient - systems.  Hoare's
mathematical abstractions have proved pretty successful in guiding some
really spectacular engineering developments that deal with real messy

It's the absence of clean mathematical abstractions that leads to real
engineering costs (that you mention).  I just don't believe that never
delivering a spurious wakeup should impose such a cost (assuming we're
not trying to guard against hardware corruption).

Peter (who must get back to his day job!).

More information about the Concurrency-interest mailing list