At 01:20 PM 6/11/2003 -0500, Doug Lea wrote:
>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
I did develop a variant that avoided the global lock, and the other
concerns expressed about context changes. I confess I never got as far as
testing it, because as I've indicated, I had formed the view that even if
it was correct, the community was simply opposed to the idea on grounds
immune to argument.
Although the inherent race remains, I was able to ameliorate it by
implementing the wait set in a way that allow the removal of a thread
without locking. Doing anything to a thread requires that a lock be held on
some internal lock for that thread (ie, not the Thread object's monitor).
On a notify() the notifying thread takes an entry from the wait set, locks
the thread to be notified and then looks to see whether the thread is still
in the wait set. If it is, then the thread can be removed from the wait
set, prior to being unlocked.
If the thread is no longer in the wait set, then it is unlocked, and the
notifying thread tries again. Since the thread calling notify() holds the
object's monitor, no new threads can be added, which means that this loop
An interrupt() locks the thread, and then if the thread is in a wait set,
removes it from the wait set and marks it as due to receive an In
InterruptedException. If it is not in a wait set, then the thread's
interrupted flag is set. Either way the thread's lock is then released.
On a wait(), the thread locks itself, and tests its interrupted flag. If
set, it clears the flag, unlocks itself and throws InterruptedException. If
not set, then it adds itself to the wait set (which is safe because the
thread holds the object's monitor) and unlocks itself.
As an aside, interrupting a waiting thread twice in quick succession should
in my view result both in its throwing InterruptedException, and having its
interrupted flag set, and that is what the above algorithm will do. If the
interrupting thread itself holds the object's monitor, then whether this is
or is not the precise behaviour is observable. It is contrary to the
behaviour stated in the API, and so has to be handled specially. I can't
remember the exact details of what I did.
Sadly, I seem to have lost the code I wrote to model this, and to show how
the multiple context switch issue is handled. No doubt I could recreate it,
but my motivation is lacking if it's just an academic exercise.
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