Doug Lea wrote:
> 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.
I think the way to solve this problem - which doesn't imply that
current implementations will support this solution - is to ensure that
the notification process leaves a clear indicator that a notification
occurred. We can define the race such that whichever mechanism
(notification, interrupt, timeout) manages to do the queue transfer is
deemed the winner. This need not reflect the true order of things in
an absolute sense but will prevent lost notifications. The problem
with trying to do this in a lock-free based implementation is that we
need to atomically update the queue reference and some kind of marker
field. This can be done at the C level using aligned pointers (the low
order bits can be used for flags) but is harder at the Java level.
However, the problem is compounded when an implementation wants to
give preference to the interrupt, due to this being an explicit
cancelation point. In that case, the implementation will still have to
issue a notifyAll if it wants to throw the IE when interruption was
not the cause of the transfer. But at least that might be less
frequent than doing a notifyAll on every interrupt detection.
David Holmes
-------------------------------
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