RE: JavaMemoryModel: Thread model algorithm.

From: Sylvia Else (
Date: Tue Nov 18 2003 - 20:43:49 EST

At 08:37 AM 19/11/2003 +1000, David Holmes wrote:
>If spurious wakeups aren't allowed the programmer is more likely to
>code an "if (!condition) wait() ..." rather than a "while (!condition)
>wait() ..." even in circumstances where the "if" is incorrect without
>spurious wakeups.

I'm probably about to get lynched by a posse of right thinking thread
modelers here, but oblivious of the danger, I proceed.

David's comment got me thinking about the situations where the while loop
is still required even in the absence of spurious wakeups.

Consider the currently naive approach to a worker thread implementation.

worker() throws Exception
     for(;;) {
         Object work;
         synchronized(this) { // Line A
             if(workQueue.isEmpty()) {
                 wait(); // Line B
                                         // Line C
             work = workQueue.removeFirst();

         .. do work.

synchronized void allocateWork(Object work)

The reason this breaks is that one of the worker threads may be blocked on
the monitor at line A while the allocating thread holds the monitor. When
the monitor is released, that worker thread gets it, grabs the work off the
queue, and releases the monitor. After that another worker thread that was
blocked in wait() at line B wakes up, because it was notified, and tries to
remove an item of work off the possibly empty work queue.

In general terms, this structure fails because the state established by the
notifying thread no longer pertains when the waiting thread wakes up. If
the state could be guaranteed correct at Line C, just after the wait(),
then this structure would work correctly.

Now, at the point where the allocating thread invokes notify, it holds the
monitor. So the worker threads are either completely outside the
synchronized block, are blocked at line A, or are blocked waiting for
notification at line B. Immediately after the notification, one of the
threads that were blocked waiting for notification are now blocked waiting
for the monitor. I'm assuming here that this transition can be achieved
atomically w.r.t the monitor. That is, that the notified thread will
already be waiting for the monitor before the allocating thread releases it.

So, on the face of it, all that's required to make this structure work is
to guarantee that the monitor will next be acquired by the notified thread,
and not by any other. If the allocating thread issue more than one notify,
then all of the notified threads must acquire the monitor before any other
can. This rule would not conflict with the current specification, which
says nothing at all about the order in which threads acquire monitors.

At the moment, I can't see any reason why my model implementation could not
be modified to incorporate this behaviour (and still without introducing
redundant context switches).

Do I hear horses in the distance?


JavaMemoryModel mailing list -

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