213Livelocks from wait() and notify()

Author: Dr. Heinz M. KabutzDate: 2013-09-20Java Version: 8Category: Language

Abstract: When a thread is interrupted, we need to be careful to not create a livelock in our code by re-interrupting without returning from the method.

Welcome to the 213th issue of The Java(tm) Specialists' Newsletter, sent to you from the wonderful Island of Crete. In August we had another amazing Java Specialist Symposium here in Crete. Our semi-professional team photographer David Gomez did a spectacular job of capturing the spirit of what we did. For our final evening, we had a barbecue and live music with famous Greek singer Manolis Kontaros at our house. It was a perfect ending to an inspiring time.

In my last newsletter, I mentioned that I had gone for a Greek citizenship interview. I heard this week that I passed, which means that in a few months time, I will be Greek. They generously overlooked that my Greek language ability is still not perfect and instead concentrated on my knowledge of Greek culture, my family and my integration into local life. I am very grateful for their kindness.

javaspecialists.teachable.com: Please visit our new self-study course catalog to see how you can upskill your Java knowledge.

Livelocks from wait()/notify()

A few years ago, one of my friends sent me some classes that contained the following code:

public void assign(Container container) {
  synchronized (lock) {
    PooledThread thread = null;
    do {
      while (this.idle.isEmpty()) {
        try {
          lock.wait();
        } catch (InterruptedException ie) {
          Thread.currentThread().interrupt();
        }
      }
      if (!this.idle.isEmpty())
        thread = this.idle.getFirst();
    } while ((thread==null) || (!thread.isRunning()));
    this.moveToRunning(thread);
    thread.start(container);
    lock.notify();
  }
}

Can you spot the problem?

When I looked at the code those many years ago, I recognized that there was an issue with the way that the thread was re-interrupted, without leaving the method. However, it was only a few weeks ago that I realized just how bad this was.

A thread goes through several states. It would typically be in the RUNNABLE state, but if it needed to get a monitor lock with synchronized, it could go into the BLOCKED state if that lock was not available. And if it was suspended due to a wait(), it would go into the WAITING or TIMED_WAITING state, after first releasing the lock. After being released from the wait(), it would have to reacquire the lock. The key is that usually, when we wait(), the lock is also released. However, if the thread is currently interrupted, then the wait() would immediately throw the InterruptedException, without first releasing and then reacquiring the lock.

Here is another example to illustrate this situation:

public class WaitNotifyLivelock {
  private boolean state = false;
  private final Object lock = new Object();
  public static volatile Thread waitingThread = null;

  public void waitFor() {
    synchronized (lock) {
      waitingThread = Thread.currentThread();
      while (!state) {
        try {
          lock.wait();
        } catch (InterruptedException e) {
          // In this context, re-interrupting is a mistake
          Thread.currentThread().interrupt();
        }
      }
    }
  }

  public void notifyIt() {
    synchronized (lock) {
      state = true;
      lock.notifyAll();
    }
  }
}

In our test program, we have three threads at play. The first calls the waitFor() method. A short while later, the main thread interrupts the first thread. After that, a third thread tries to call notifyIt(). Since the first thread never releases the lock as part of the wait() method call, it is impossible for the third thread to get the lock in order to send the notify and change the state.

In order to make this a bit more interesting, I have used the Java 8 Lambda syntax, including the Java 8 method reference wnll::waitFor. The equivalent Java 7 code is in the comments.

import java.util.concurrent.*;

public class WaitNotifyLiveLockTest {
  public static void main(String[] args) throws Exception {
    // Local variables and parameters accessed from inner classes
    // in Java 8 do not need to be explicitly declared as final!
    // They are implicitely final.
    WaitNotifyLivelock wnll = new WaitNotifyLivelock();
    ExecutorService pool = Executors.newCachedThreadPool();
    Future<?> waitForFuture = pool.submit(wnll::waitFor);
    // "wnll::waitFor" is a Java 8 method reference and is
    // roughly equivalent to:
    // pool.submit(new Runnable() {
    //   public void run() {
    //     wnll.waitFor();
    //   }
    // });
    while (WaitNotifyLivelock.waitingThread == null) {
      Thread.sleep(10);
    }
    // now we interrupt the thread waiting for the signal
    WaitNotifyLivelock.waitingThread.interrupt();

    Future<?> notifyFuture = pool.submit(wnll::notifyIt);

    try {
      notifyFuture.get(1, TimeUnit.SECONDS);
    } catch (TimeoutException e) {
      System.err.println("notifyFuture could not complete");
    }
    try {
      waitForFuture.get(1, TimeUnit.SECONDS);
    } catch (TimeoutException e) {
      System.err.println("waitForFuture could not complete");
      System.out.println("Waiting thread state: " +
          WaitNotifyLivelock.waitingThread.getState());
    }
  }
}

The waiting thread gets into an infinite loop looking at the state field. However, since the notifyIt thread cannot get the lock, it is also not able to change the state. We see the following output:

notifyFuture could not complete
waitForFuture could not complete
Waiting thread state: WAITING

However, it is also possible for the "Waiting thread" to be in the RUNNABLE state, as we can see from this thread dump:

"pool-1-thread-2" waiting for monitor entry
   java.lang.Thread.State: BLOCKED (on object monitor)
    at WaitNotifyLivelock.notifyIt(WaitNotifyLivelock.java:22)
    - waiting to lock <0x000000010d402700> (a java.lang.Object)
    at WaitNotifyLiveLockTest$$Lambda$2.run(Unknown Source)
    ...

"pool-1-thread-1" runnable
   java.lang.Thread.State: RUNNABLE
    at java.lang.Object.wait(Object.java:502)
    at WaitNotifyLivelock.waitFor(WaitNotifyLivelock.java:11)
    - locked <0x000000010d402700> (a java.lang.Object)
    at WaitNotifyLiveLockTest$$Lambda$1.run(Unknown Source)
    ...

However, it never lets go of the lock, thus also not allowing the notifying thread from entering the critical section.

Next time you re-interrupt a thread, make sure that your surrounding code is also correct.

Would you like to know more about concurrency? Then take our Concurrency Specialist Course.

Kind regards

Heinz

Comments

We are always happy to receive comments from our readers. Feel free to send me a comment via email or discuss the newsletter in our JavaSpecialists Slack Channel (Get an invite here)

Related Articles

Browse the Newsletter Archive