Java Synchronized List Deadlock

Question

From Effective Java 2nd edition item 67 page 266-268:

The background thread calls s.removeObserver, which attempts to lock observers, but it can’t acquire the lock, because the main thread already has the lock. All the while, the main thread is waiting for the background thread to finish removing the observer, which explains the deadlock.

I am trying to find out which threads deadlock in the main method by using ThreadMXBean (http://stackoverflow.com/questions/1102359/programmatic-deadlock-detection-in-java) , but why does it not return the deadlocked threads? I used a new Thread to run the ThreadMXBean detection.

public class ObservableSet<E> extends ForwardingSet<E> { 
  public ObservableSet(Set<E> set) { super(set); }
  private final List<SetObserver<E>> observers =
          new ArrayList<SetObserver<E>>();
  public void addObserver(SetObserver<E> observer) { 
    synchronized(observers) {
      observers.add(observer);
    }
  } 
  public boolean removeObserver(SetObserver<E> observer) {
    synchronized(observers) { 
      return observers.remove(observer);
    }
  } 
  private void notifyElementAdded(E element) {
    synchronized(observers) {
      for (SetObserver<E> observer : observers)
         observer.added(this, element);
      }
  }
  @Override 
  public boolean add(E element) { 
    boolean added = super.add(element); if (added)
    notifyElementAdded(element); return added;
  }
  @Override 
  public boolean addAll(Collection<? extends E> c) { 
    boolean result = false; for (E element : c)
    result|=add(element); //callsnotifyElementAdded 
    return result;
  }

  public static void main(String[] args) { 
    ObservableSet<Integer> set =
            new ObservableSet<Integer>(new HashSet<Integer>());

    final ThreadMXBean threadMxBean = ManagementFactory.getThreadMXBean();

    Thread t = new Thread(new Runnable() {
        @Override
        public void run() {
            while( true ) {
                long [] threadIds = threadMxBean.findDeadlockedThreads();
                if( threadIds != null) {
                    ThreadInfo[] infos = threadMxBean.getThreadInfo(threadIds);
                    for( ThreadInfo threadInfo : infos) {
                        StackTraceElement[] stacks = threadInfo.getStackTrace();
                        for( StackTraceElement stack : stacks ) {
                            System.out.println(stack.toString());
                        }
                    }
                }
                try {
                    System.out.println("Sleeping..");
                    TimeUnit.MILLISECONDS.sleep(1000);
                } catch (InterruptedException e) {
                    // TODO Auto-generated catch block
                    e.printStackTrace();
                }
            }
        }
    });
    t.start();


    set.addObserver(new SetObserver<Integer>() { 
       public void added(ObservableSet<Integer> s, Integer e) {
         ExecutorService executor = Executors.newSingleThreadExecutor();
         final SetObserver<Integer> observer = this; try {
         executor.submit(new Runnable() { 
            public void run() {
              s.removeObserver(observer);
         } }).get();
         } catch (ExecutionException ex) {
             throw new AssertionError(ex.getCause());
         } catch (InterruptedException ex) {
             throw new AssertionError(ex.getCause());
         } finally {
            executor.shutdown();
         }
       }
    });

    for (int i = 0; i < 100; i++) 
      set.add(i);
    }
 }

 public interface SetObserver<E> { 
   // Invoked when an element is added to the observable set 
   void added(ObservableSet<E> set, E element);
 }


 // ForwardingSet<E> simply wraps another Set and forwards all operations to it.

Answer 1

Are you sure that a deadlock happens? Try running the program with the following changes:

1) Add a log message when the observer is removed:

     executor.submit(new Runnable() { 
        public void run() {
          s.removeObserver(observer);
          System.out.println("Removed myself from observers")
     } }).get();

2) Marking the deadlock-detection thread as a daemon:

t.setDaemon(true);
t.start();

My guess is that the deadlock might not be happening.

Answer 2

You have a deadlock.

However, you do not have a cycle, which is what the ThreadMXBean#findDeadlockedThreads method states it searches for. From the javadoc:

Finds cycles of threads that are in deadlock waiting to acquire object monitors or ownable synchronizers. Threads are deadlocked in a cycle waiting for a lock of these two types if each thread owns one lock while trying to acquire another lock already held by another thread in the cycle.

In this case, the main thread is waiting on the results of a Future. While another thread (which holds no locks) is waiting for the main thread to release its locks.