title: Java: two WAITING + one BLOCKED threads, notify() leads to a livelock, notifyAll() doesn't, why?
body: <p>I was trying to implement something similar to Java's bounded <a href="https://docs.oracle.com/javase/7/docs/api/java/util/concurrent/BlockingQueue.html">BlockingQueue</a> interface using Java synchronization "primitives" (synchronized, wait(), <a href="https://docs.oracle.com/javase/7/docs/api/java/lang/Object.html#notify()">notify()</a>) when I stumbled upon some behavior I don't understand.</p>
  
  <p>I create a queue capable of storing 1 element, create two threads that wait to fetch a value from the queue, start them, then try to put two values into the queue in a synchronized block in the main thread. Most of the time it works, but sometimes the two threads waiting for a value start seemingly waking up each other and not letting the main thread enter the synchronized block.</p>
  
  <p>Here's my (simplified) code:</p>
  
  <pre><code>import java.util.LinkedList;
  import java.util.Queue;
  
  public class LivelockDemo {
      private static final int MANY_RUNS = 10000;
  
      public static void main(String[] args) throws InterruptedException {
          for (int i = 0; i &lt; MANY_RUNS; i++) { // to increase the probability
              final MyBoundedBlockingQueue ctr = new MyBoundedBlockingQueue(1);
  
              Thread t1 = createObserver(ctr, i + ":1");
              Thread t2 = createObserver(ctr, i + ":2");
  
              t1.start();
              t2.start();
  
              System.out.println(i + ":0 ready to enter synchronized block");
              synchronized (ctr) {
                  System.out.println(i + ":0 entered synchronized block");
                  ctr.addWhenHasSpace("hello");
                  ctr.addWhenHasSpace("world");
              }
  
              t1.join();
              t2.join();
  
              System.out.println();
          }
      }
  
      public static class MyBoundedBlockingQueue {
          private Queue&lt;Object&gt; lst = new LinkedList&lt;Object&gt;();;
  
          private int limit;
  
          private MyBoundedBlockingQueue(int limit) {
              this.limit = limit;
          }
  
          public synchronized void addWhenHasSpace(Object obj) throws InterruptedException {
              boolean printed = false;
              while (lst.size() &gt;= limit) {
                  printed = __heartbeat(':', printed);
                  notify();
                  wait();
              }
              lst.offer(obj);
              notify();
          }
  
          // waits until something has been set and then returns it
          public synchronized Object getWhenNotEmpty() throws InterruptedException {
              boolean printed = false;
              while (lst.isEmpty()) {
                  printed = __heartbeat('.', printed); // show progress
                  notify();
                  wait();
              }
              Object result = lst.poll();
              notify();
              return result;
          }
  
          // just to show progress of waiting threads in a reasonable manner
          private static boolean __heartbeat(char c, boolean printed) {
              long now = System.currentTimeMillis();
              if (now % 1000 == 0) {
                  System.out.print(c);
                  printed = true;
              } else if (printed) {
                  System.out.println();
                  printed = false;
              }
              return printed;
          }
      }
  
      private static Thread createObserver(final MyBoundedBlockingQueue ctr,
              final String name) {
          return new Thread(new Runnable() {
              @Override
              public void run() {
                  try {
                      System.out.println(name + ": saw " + ctr.getWhenNotEmpty());
                  } catch (InterruptedException e) {
                      e.printStackTrace(System.err);
                  }
              }
          }, name);
      }
  }
  </code></pre>
  
  <p>Here's what I see when it "blocks":</p>
  
  <pre><code>(skipped a lot)
  
  85:0 ready to enter synchronized block
  85:0 entered synchronized block
  85:2: saw hello
  85:1: saw world
  
  86:0 ready to enter synchronized block
  86:0 entered synchronized block
  86:2: saw hello
  86:1: saw world
  
  87:0 ready to enter synchronized block
  ............................................
  
  ..........................................................................
  
  ..................................................................................
  (goes "forever")
  </code></pre>
  
  <p>However, if I change the notify() calls inside the while(...) loops of addWhenHasSpace and getWhenNotEmpty methods to notifyAll(), it "always" passes.</p>
  
  <p>My question is this: why does the behavior vary between notify() and notifyAll() methods in this case, and also why is the behavior of notify() the way it is? </p>
  
  <p>I would expect both methods to behave in the same way in this case (two threads WAITING, one BLOCKED), because:</p>
  
  <ol>
  <li>it seems to me that in this case notifyAll() would only wake up the other thread, same as notify(); </li>
  <li>it looks like the choice of the method which wakes up a thread affects how the thread that is woken up (and becomes RUNNABLE I guess) and the main thread (that has been BLOCKED) <em>later</em> compete for the lock — not something I would expect from the javadoc as well as searching the internet on the topic.</li>
  </ol>
  
  <p>Or maybe I'm doing something wrong altogether?</p>