JavaMemoryModel: wait/notify/interrupt - a visible state model - FWIW

From: Sylvia Else (sylviae@optushome.com.au)
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 clear.

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 interrupt.

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 non-synchronous.

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 calls.

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 wait.

The acquireSet contains monitor acquisition actions (about which more later).

When a thread calls wait, it either immediately throws InterruptedException (IE), or enters the insideWait set, and releases the monitor.

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 it wants.

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 trace.

Sylvia.
------------------------------- 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