JavaMemoryModel: wait/notify/interrupt - a visible state model - FWIW
From: Sylvia Else (firstname.lastname@example.org)
Date: Tue Nov 25 2003 - 18:00:47 EST
For what it's worth.
Some of the debate here has made it clear (at least to me) that the way
wait/notify/interrupt interactions are specified is less than
One of the problems is that the specification makes reference to a wait
set, whose state is not in general visible to the program. A thread
calling wait initially enters the wait set, but later is removed from the
wait set and placed into the monitor acquisition queue, still later it
returns from wait. In the mean time there are strange interactions with
The notify method has no synchronously visible effect. There is no
Object.isWaitSetEmpty() method, and no Thread.isNotified() method.
Similarly, as Doug has argued, the Thread.interrupt() method
spefification uses terminology that allows its effects to be
This means that the threading model is described in terms that are
difficult to reason with.
I have conceived the following model.
Each monitor is represented by two sets and a counter.
The group counter is the number of completed notify() method
The insideWait set contains all the threads that have currently invoked
wait on the monitor, but not yet returned. Associated with each thread is
a copy of the group counter of the monitor when the thread called
The acquireSet contains monitor acquisition actions (about which more
When a thread calls wait, it either immediately throws
InterruptedException (IE), or enters the insideWait set, and releases the
When notify is called, it places a notify action into the acquireSet.
This action contains a copy of the group counter, before it is
incremented at the end of the notify call.
When a thread is interrupted, and is in an insideWait set, an interrupt
action is placed into the aquireSet, if there is not one there already
for the thread.
If a thread tries to lock a currently locked monitor, then a wakeup
action for the thread is placed into the acquireSet.
On release of a monitor, an action is removed from the acquireSet.
If the action is to wakeup a thread, then that thread is granted the lock
on the monitor, and wakes up.
If the action is a notify, then a thread is removed from the insideWait
set. There is a constraint here. The notify action can only choose a
thread whose groupCounter is <= to that of the notify action. Further,
a thread with groupCounter n cannot be chosen if the number of
notifies with groupCounter <= n is greater than or equal to the
number of threads with groupCounter <= n. If there is an
interrupt action in the acquireSet for the chosen thread, then its
interrupted flag is set (but it will not throw InterruptedException). The
interrupt action is removed. The thread is granted the lock on the
monitor, and wakes up.
If the action is an interrupt, then the thread is granted the lock on the
monitor, and wakes up throwing InterruptedException.
There is no order attached to the monitorAquire set, so the
implementation can prioritize interrupts relative to notifies in any way
The state of the acquireSet is not visible to the program, so my goal of
a model based entirely on visible state has not been reached. However,
its unordered quality would very much limit the inferences that could be
drawn even if its state was visible.
Doug: This model does not allow the trace we've been discussing, so it
must embody my interpretation of the current speficication. At the
moment, I'm not sure how it could rationally be altered to allow that
JavaMemoryModel mailing list - http://www.cs.umd.edu/~pugh/java/memoryModel
This archive was generated by hypermail 2b29
: Thu Oct 13 2005 - 07:00:54 EDT