[concurrency-interest] spurious wakeups semantics

P.H.Welch P.H.Welch at kent.ac.uk
Thu Nov 3 15:59:26 EST 2005


Apologies!  Maybe I was trying to stir things up a bit ... I expected
to get bitten back.  :)

Thank you to all who responded (some privately).  I'll try to respond
carefully and briefly!

Re. the thought-JVM in which wait/notify/notifyAll were implemented as no-ops,
Brian Goetz wrote:
> the JLS requires it to release the lock as part of a wait, so the
> unlock^n-lock^n cannot be optimized away.  See JLS/3e 17.8.1.  (You
> might consider looking at the spec before making claims like "X would be
> a valid implementation, but that would break real programs" when the
> spec very clearly outlaws X.)`

In my defence, I did (partly) withdraw the wait-as-a-no-op idea:
> Humm ... maybe the "wait()" can't be a no-op since it must release
> the monitor?  But it could be implemented as a release-monitor-lock
> then "Thread.yield()" them spurious-wakeup then acquire-monitor-lock.

Before blowing it with the incorrect:
> Actually, I think that's optimisable back to a no-op!

Though then proceeding that, even if wait can only reduce to release-acquire:
> all those waits-inside-while-condition loops become busy-polling, :(,

When we need polling, we do it.  Doing it as the default way of design
just feels wrong.

Maybe some of this is bound up with another complaint from Brian:
> > It's surely much better for the JVM to protect the Java system from broken
> > OS threading mechanisms.
> 
> You have done nothing to support your claim of brokenness.  As far as I
> can tell, all you've said is that you personally find it ugly.  You may
> be right, but that doesn't mean its broken.

If I say to Fred: "wake me up when Jim's made the porridge" ... and Fred goes
and wakes me up before Jim's made the porridge ... and Fred is a computer
programmed to do that task ... then I'd say Fred is broken.

I want to commit the sin of *sometimes* (maybe quite often) doing a wait()
without surrounding it with a while-not-condition loop ... something I just
can't do in the context of spurious wakeups.  The reason for not wanting
the loop is not to do with saving the cost of rechecking the condition ...
it's to do with semantic clarity ... not cluttering the system with stuff
we don't need ... "Ockham's Razor" ... :).

Doug Lea wrote:
>                                         Notice that if threads do
> spuriously wake up on modern OSes, then it (is) performance-neutral whether
> the OS or the monitor implementation or application code puts
> them back to sleep when necessary.

Great!  So let's get the OS or the monitor implementation to do it and
not impose a logic-non-neutral complexity burden on the application code.
The OS or monitor implementation only has to be made right once.

Getting back to my reasons for sin ...

Sometimes, a thread has grabbed a monitor lock and finds that it simply
has to wait().  This is in one branch of its logic.  Now, just because
of spurious wakeups, I either must distort that logic into a loop ...
or leave the simple branch, invent an extra boolean field and expand
the simple wait() into one governed by a loop ... and modify the notifier
to set that extra boolean.  Extra engineering like this is bad, simply
because it is there.  And it doesn't have to be there ... were it not
for those spurious wakeups.

Of course, as Brian points out in a later posting discussing notify()
versus notifyAll(), for the above to work the monitor object must be
hidden from the rest of the system.  It also helps if only one thread
can be doing that wait()ing at any time.

Various replies mention that we need the while-not-condition-wait loop
when different monitor methods of the same object are waiting for
different conditions - e.g. a bounded buffer where the pusher needs
some room and the puller needs something to be there.  [This is with
classical Java monitors, before Java 5.]

The above is true, of course.  Even so, it is possible to design bounded
buffers with loop-free logic.  One way uses 3 monitor objects: one on
which the pushers must first lock, another for the pullers and the third
to sort out contention between an (at most) single puller and (at most)
single pusher for the actual buffer (and on which the wait/notifying
gets done).  We don't need notifyAll because there is (at most) one
party to notify.  We don't need a loop round the wait because there
is only you waiting for that notification (except for that darn spurious
wakeup).

But you probably won't like that approach because of the performance hit
from the extra lock that needs to be acquired?  Humm ... maybe that hit
should be reduced a couple of orders of magnitude ...

Mis-quoting Brian (apologies):
> I share your hopes, but ... <snip> ... this is in the same category
> as hoping to wake up taller tomorrow.

Nevertheless, it can be done ... though maybe we need a fresh start.

A comment on performance was made:
> OS'es which permit spurious wakeups may do so because by doing so
> because they can improve overall performance.  Again, I refer you to the
> fair/nonfair issue with locks.  Sure, fairness is prettier, but
> starvation-free nonfair locks can be implemented a lot more efficiently.

and, earlier, someone mentioned that imposing "fairness" cost 2 orders
of magnitude extra overhead?  But low cost "fair" algorithms -- for example
for concurrent-read-exclusive-write (CREW) locks have long been around.
One is given and documented in the JCSP library:

  http://www.cs.kent.ac.uk/projects/ofa/jcsp/jcsp1-0-rc4/jcsp-docs/jcsp/lang/Crew.html

(though please read the "Cautionary Note" in the above).

Another comment on Hoare's "real" monitors:
> > 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
> > life.
> 
> Except that a monitor-based design for a system of even moderate
> complexity will almost certainly deadlock.  This is (one reason) why the
> monitor-like approach that Java uses was taken over "real" monitors.

The "Except ..." sentence is way too strong and unsupported by evidence
or explanation.

Also, Java monitors may be less prone to deadlock -- but they are still
very prone to it -- but are, in consequence, more prone to livelock ...
which may be worse ("will I ever get out of this wait-loop?").

Finally, Doug wrote:
> 3. We hope that people will increasingly use the more convenient,
> semantically cleaner,  and often significantly more efficient
> medium/higher level constructs that java.util.concurrent offers
> rather use monitor/condition operations at all. In fact, whenever people
> post on this list that they are using them, I often wonder to myself
> what higher-level construct we might put in j.u.c. that they could use
> instead.

Yes.  The original Java monitor design is specialised for certain
kinds of threading logic and works well if that's what you want.  But
it's not really a "low-level" concurrency primitive on which you can
build what-you-really-want-to-do, get-it-right and get-it-efficient.

Rebuilding from a highly efficient lower set of primitives -- and,
thank you, offering those primitives -- seems a much better bet.

My interest is building concurrency mechanisms on top of CSP (and,
recently, pi-calculus) primitives.  These are not so far from Doug's
set, :).

If any are still reading and were curious:

  http://www-128.ibm.com/developerworks/java/library/j-csp2/
  http://www.cs.kent.ac.uk/projects/ofa/jcsp/

Really must update the latter!

Peter.


More information about the Concurrency-interest mailing list