Java Specialists' Java Training Europehome of the java specialists' newsletter

The Java Specialists' Newsletter
Issue 2132013-09-20 Category: Language Java version: Java 1 to 8

GitHub Subscribe Free RSS Feed

Livelocks from wait/notify

by Dr. Heinz M. Kabutz
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.

NEW: Please see our new "Extreme Java" course, combining concurrency, a little bit of performance and Java 8. Extreme Java - Concurrency & Performance for Java 8.

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 explicitely 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

Language Articles Related Java Course

Extreme Java - Concurrency and Performance for Java 8
Extreme Java - Advanced Topics for Java 8
Design Patterns
In-House Courses

© 2010-2016 Heinz Kabutz - All Rights Reserved Sitemap
Oracle and Java are registered trademarks of Oracle and/or its affiliates. Other names may be trademarks of their respective owners. JavaSpecialists.eu is not connected to Oracle, Inc. and is not sponsored by Oracle, Inc.