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.

Answer 2

First, Java's built-in monitors (synchronized and wait) are more efficient than many may think. See biased locking, and there are further improvements planned that make use of hardware transactional memory.

Second, the mechanism you're looking for and the one provided by synchronized/wait serve difference purposes. The latter protects some guarded resource, and must contain a lock because it assumes that following wait you want to be inside the critical section. What you're looking for is provided by other Java concurrency primitives like CountDownLatch, Phaser or Semaphore.

Answer 3

More of a thought experiment than some real working code but this seems to work.

// My lock class.
public static class Padlock<E extends Enum<E>> {

    // Using Markable because I think I'm going to need it.
    public final AtomicReference<E> value;
    // Perhaps use a set to maintain all waiters.
    Set<Thread> waiters = ConcurrentHashMap.newKeySet();

    public Padlock(E initialValue) {
        this.value = new AtomicReference<>(initialValue);
    }

    /**
     * Waits for the locks value to become the specified key value.
     *
     * @param waitFor - The desired key.
     */
    public void compareAndWait(E waitFor) {
        log("Wait for " + waitFor);
        // Spin on the value.
        while (value.get() != waitFor) {
            log("Park waiting for " + waitFor);
            // Remember me as waiting.
            waiters.add(Thread.currentThread());
            // TODO: What do we do here??
            LockSupport.park();
            log("Awoke " + waitFor);
        }
    }

    /**
     * Sets the locks value to the key value.
     *
     * If this resulted in a change - notify all changers.
     *
     * @param shouldBe - What it should be now.
     * @param makeIt - The new value to set.
     */
    public void setAndNotify(E shouldBe, E makeIt) {
        log("Set " + shouldBe + "->" + makeIt);
        if (value.compareAndSet(shouldBe, makeIt)) {
            log("Notify " + shouldBe + "->" + makeIt);
            // It changed! Notify the waiters.
            for (Thread t : waiters) {
                // Perhaps
                log("Unpark " + t.getName());
                LockSupport.unpark(t);
            }
        }
    }
}

enum State {

    Off, On;
}

private static final long TESTTIME = 30000;
private static final long TICK = 100;

private static final void log(String s) {
    System.out.println(Thread.currentThread().getName() + ": " + s);

}

static class MutexTester implements Runnable {

    final Padlock<State> lock;

    public MutexTester(Padlock<State> lock) {
        this.lock = lock;
    }

    @Override
    public void run() {
        Thread.currentThread().setName(this.getClass().getSimpleName());
        long wait = System.currentTimeMillis() + TESTTIME;
        do {
            // Wait for an On!
            lock.compareAndWait(Test.State.On);
            try {
                log("Got it!");
                try {
                    Thread.sleep(TICK);
                } catch (InterruptedException ex) {
                    log("Interrupted!");
                }
            } finally {
                // Release
                lock.setAndNotify(Test.State.On, Test.State.Off);
            }
        } while (System.currentTimeMillis() < wait);
        log("Done");
    }
}

static class RandomSwitcher implements Runnable {

    final Padlock<State> lock;
    final Random random = new Random();

    public RandomSwitcher(Padlock<State> lock) {
        this.lock = lock;
    }

    @Override
    public void run() {
        Thread.currentThread().setName(this.getClass().getSimpleName());
        long wait = System.currentTimeMillis() + TESTTIME;
        do {
            // On!
            lock.setAndNotify(Test.State.Off, Test.State.On);
            log("On!");
            pause();
            lock.setAndNotify(Test.State.On, Test.State.Off);
            log("Off!");
            pause();
        } while (System.currentTimeMillis() < wait);
        log("Done");
    }

    private void pause() {
        try {
            // Random wait.
            Thread.sleep(TICK * random.nextInt(10));
        } catch (InterruptedException ex) {
            System.out.println("Interrupted! " + Thread.currentThread().getName());
        }
    }
}

public void test() throws InterruptedException {
    final Padlock<State> lock = new Padlock<>(State.Off);
    Thread t1 = new Thread(new MutexTester(lock));
    t1.start();
    Thread t2 = new Thread(new RandomSwitcher(lock));
    t2.start();
    t1.join();
    t2.join();
}

I've implemented the protocol that compareAndWait waits for exclusive use while setAndNotify releases the mutex.