> This seems to be in conflict with my proposed solution.
Here's how this plays out in what I believe to be typical Java
implementations.
First, a reminder (to other readers) that java notify() is unlike
posix pthreads condvar signal() in that the notifying thread must hold
the lock. (In posix, it need not; both schemes have their advantages
and disadvantages.)
This enables notify to be implemented as a "queue transfer": The
notified thread is not actually woken up; instead a record of it is
moved from a monitor wait queue to the lock (re)acquisition queue,
where it will be woken up when the lock is available. (For simplicity
below, suppose that queue transfer is an atomic operation.) The Java
monitor lock is NEVER available during the notify because the
notifying thread holds the lock. So it would cause unecessary context
switches to wake up the notified thread just to have it immediately
block again.
Now, suppose you implement this using a "leaky" underlying blocking
primitive. As in last mail, most if not all underlying mechanisms are
leaky. So, sometimes waiting threads wake up independently of this
scheme. And in addition to spurious wakeups, threads can awaken due
to interrupts and timeouts, but in general, the "reason" for any given
wakeup is unknown. (Note that when threads wake up in the midst of
notification mechanics, they do undergo the extra context switches
otherwise avoided by the above scheme, but this is OK performance-wise
under the assumption that these wakeups are not common.)
All this can lead to the following interaction between signalling
thread S and waiting thread W. There are other scenarios along these
lines too, but this is the main one under consideration.
S W
... ...
Block in monitor-wait queue
Choose W from monitor-wait queue
Wake up
Notice you are interrupted or timed-out
Transfer record of W to lock queue(*)
Try but fail to transfer your record
to lock queue because already there
(**)
Block waiting for lock
In this scenario S could have made a mistake because W was actually
interrupted or timed out before the transfer at (*), but S didn't
know. Even if S checks for this before the transfer, there's a race
window. And it's not clear to me that any amount of extra locking
would solve this. Extra locking would allow S and W to agree on the
decision, but the decision could be wrong with respect to actual
orderings because spurious wakeups, interrupts, and timeouts are all
asynchronous with respect to these operations.
The extra-notification proposal amounts to having W, when it loses the
abiove queue transfer race, perform notification(s) at (**) before
reblocking waiting for lock, just in case it lost unfairly because S
made a mistake.
The alternative proposal amounts to not having W do anything in this
case except to reblock waiting for the lock.
-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:50 EDT