Re: JavaMemoryModel: october JMM spec seems to break java's threading model

From: Doug Lea (dl@cs.oswego.edu)
Date: Thu Nov 06 2003 - 13:20:00 EST


> although java doesn't have fairness guarantees for good reasons, i
> think it intends to have a kind of execution guarantee, something like
> "at least one thread of the set of currently runnable threads will
> make progress" (is it written somewhere?)

No, and it would surely not hold in most (all?) JVMs in which
prgrammer-visible threads do not progress during stop-the-world GC,
sometimes during JIT compilation, or just because the OS didn't give
the JVM any cycles. The best you can say is "over sufficiently long
observation periods, unblocked threads will progress", but this is
just the same as saying that rate of progression is a quality of
implementation issue that falls ouside JLS spec.

So, I think the premise of your arguments, that spurious wakeups
nullify prgress guarantees does not hold.

To discuss them anyway: Yours is, I believe, a slightly different
proposal than similar ones that have appeared on this list: That
spurious wakeups be made illegal at the expense of laxer rules for
notify vs interrupts.

Before doing so, it is worth mentioning a general bias of some of us
on this list. Ever since spuriousness was first introduced in early
DEC SRC papers/systems (firefly, mesa, modula-3), many of us have
bought into the notion that spuriousness is a good property, for
software engineering reasons that other people may find perverse: The
potential for spurious wakeups makes it ALWAYS wrong to not use wait
inside a loop that checks the condition being waited on, as opposed to
merely ALMOST always wrong. This makes it easier to enforce good
design/coding practices.

> i see from reading some postings here that re-notification is a
> cause for spurious wakeups, but is it the only one?

Almost. The two principal causes here are timeouts and interrupts,
both of which may occur asynchronously wrt notifications, and thus
form an intrinsic race condition. As Sylvia once showed, this race CAN
be avoided by using a global "giant" per-JVM lock for all waits,
notifies, and interrupts. But I think almost everyone believes this
(or any other known) cure is vastly worse than the disease, and no one
has suggested an alternative that did not end up somehow weakening the
spec.

> i think maybe "notifications cannot be lost due to interrupts" should
> be left out from the spec, maybe explicitly permitting the
> re-notification after interrupt behaviour instead. or maybe the part
> that defines notify that says "if m's wait set is not empty, a thread
> u that is a member of m's current wait set is selected and removed
> from the wait set" should be changed to something that expresses that
> a notify will schedule the selection and removal of a thread from a
> wait set for later execution (but only if the wait set is not empty,
> otherwise a problem would arise if you notify a monitor with an empty
> wait set: the notify could be postponed indefinetly, you could get the
> notify in a wait that's invoked much latter).

This is pretty close to what JSR166 ReentrantLock does internally (See
internal documentation of
http://gee.cs.oswego.edu/cgi-bin/viewcvs.cgi/jsr166/src/main/java/util/concurrent/locks/ReentrantLock.java).
But I don't see how this can be generalized into a specification that
doesn't mandate a particular mechanism for tracking threads, which we
have to avoid.

> public void join(long timeout) throws InterruptedException
> {
> synchronized (lock) { if (block) lock.wait(timeout); } // FUTURE BUG ???
> }

Notice that the javadoc spec for Object.wait(long) says it
waits until ...
  The specified amount of real time has elapsed, more or less.
And the standard practical idioms for using timed waits (rechecking
the time upon wakeup) have appeared in a lot of places. But I suppose
that even when done in the above way, it is practically never actually
harmful to applications when they return early, since timeouts are
practically always heuristic.

-Doug
-------------------------------
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel



This archive was generated by hypermail 2b29 : Thu Oct 13 2005 - 07:00:53 EDT