Lock-free variant of wait/notify

Question

Java requires a thread to own the monitor of o before calling o.wait() or o.notify(). This is a well-known fact. However, are mutex locks fundamentally required for any such mechanism to work? What if there was an API which provided

compareAndWait

and

setAndNotify

instead, combining a CAS action with thread scheduling/descheduling? This would have some advantages:

• threads about to enter the waiting state would not impede the progress of notifying threads;

• they would also not have to wait on each other before being allowed to check the waiting condition;

• on the notifying side any number of producer threads could proceed simultaneously.

Is there a fundamental, insurmountable obstacle to providing such an API?

Answer 1

There is no problem implementing arbitrary wait/notify mechanisms using LockSupport.park() and LockSupport.unpark(Thread) as these basic primitives do not require holding any locks.

The reason why neither Object.wait/Object.notify nor Condition.await/Condition.signal offer you such a notification without holding a lock is a semantic one. The concept of the notification is that one thread waits for a condition to be fulfilled while another one stops the waiting when the condition has changed to the fulfilled state. Without holding a lock associated with that condition, there is no guaranty that the condition does not change in between tests for the condition’s state and the change of the thread’s state.

To be more specific, there is the possibility that when a thread which changed the condition notifies another thread, the condition has been modified again before the notification happens. But even worse, the condition could change to “fulfilled” before a thread starts to wait in which case the thread may miss a notification and hang forever.

Even if you are able to fuse the condition test and the wait operation into one atomic operation, it’s no help. Waiting for a condition is not an end in itself. The reason why a thread wants to wait for a condition is that it wants to perform an action for which the condition is a prerequisite and hence must not change while the action is performed. That’s the whole point: the condition test and the action must be implemented as one operation holding the lock, regardless of how the concept of a lock is implemented.

There are special cases where such problems cannot arise, e.g. when it is known that the condition’s state transitions are limited, thus you can preclude that the condition can go back to an unfulfilled state. That’s exactly what tools like CountDownLatch, CyclicBarrier, Phaser are for, but a notification mechanism with the predefined semantics of wait/notify implies not assuming such a special case.