Re: JavaMemoryModel: Prioritizing IE without notifyAll().

From: Doug Lea (dl@cs.oswego.edu)
Date: Sat Nov 22 2003 - 19:54:23 EST


Sylvia,

I admire your persistence. Especially since it sometimes it pays off!

I agree that your approach (as revised in your second posting) can
work. Here's a sketch of a slightly simpler and cheaper variant that I
think fits in well with typical implementations (including JSR166
ReentrantLock.Condition). This assumes wait-queues are kept in FIFO
order:

1. Associate with each monitor
     int notifyCounter;
2. Associate with each wait-queue node
     final int notificationGroup;
3. Before each return from notify, do
     notifyCounter++;
4. On entry into wait, make a node and set
     node.notificationGroup = notifyCounter;
5. On exit from wait, if the thread was interrupted after a notify,
   notify head of wait-queue if its notificationGroup is same as
   current node's.

In essence, this technique removes the uncertainty about whether the
head of wait-queue was waiting early enough to get the notification.
Thus, it avoids spurious notifications that otherwise might occur.

The fields don't need to be volatile or atomically incremented because
they are always accessed while lock is held. So the only cost is an
extra field per monitor and per wait-queue node, along with
the unnoticeable overhead of doing the increments etc.

The only constraint here is that the implementation must be able to
determine that an interrupt occurred after a notify. But as in my post
a few days ago, the Thread.interrupt spec gives implementations enough
freedom in deciding when an interrupt has taken effect that this isn't
a burden.

Similar mechanics apply to timeouts. These encounter the usual
intrinsic uncertainties about making progress surrounding time-checks.
(As in: you check time, think you are not timed out, but immediately
get swapped out, so become unknowingly timed out when you next make
progress.) But nothing I see that affects the logic of this solution.

I haven't tested this out thoroughly, but plan to.

-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:54 EDT