How to reliably create and detect a thread deadlock

Question

I've got a method in a tools class that should detect the existence of a deadlock during runtime:

/**
 * Returns a list of thread IDs that are in a deadlock
 * @return the IDs or <code>null</code> if there is no
 * deadlock in the system
 */
public static String[] getDeadlockedThreads() {
    ThreadMXBean threadBean = ManagementFactory.getThreadMXBean();
    long[] vals = threadBean.findDeadlockedThreads();
    if (vals == null){
        return null;
    }
    String[] ret = new String[vals.length];
    for (int i = 0; i < ret.length; i++){
        ret[i] = Long.toString(vals[i]);
    }
    return ret;
}

I created a JUnit test that tests that functionality. It works well on Windows but on a Linux system the test fails 8 times out of 10. This is my test code:

/**
 * Tests the correct functionality of the get deadlock info functionality
 * 
 * @throws Exception Will be thrown if there was an error
 *             while performing the test
 */
public void testGetDeadlockInformation() throws Exception {
    assertNull("check non-existance of deadlock", ThreadUtils.getDeadlockedThreads());

    final String monitor1 = "Monitor1";
    final String monitor2 = "Monitor2";

    Thread[] retThreads = createDeadlock(monitor1, monitor2, this);

    String[] res = ThreadUtils.getDeadlockedThreads();
    assertNotNull("check existance of returned deadlock info", res);
    assertEquals("check length of deadlock array", 2, res.length);

    retThreads[0].interrupt();
    retThreads[0].interrupt();
    Thread.sleep(100);

    res = ThreadUtils.getDeadlockedThreads();
    assertNotNull("check existance of returned deadlock info", res);
    assertEquals("check length of deadlock array", 2, res.length);
}

/**
 * Creates a deadlock
 * 
 * @param monitor1 monitor 1 that will be used for synchronization
 * @param monitor2 monitor 2 that will be used for synchronization
 * @param waitMonitor The monitor to be used for internal synchronization
 * @return The threads that should be deadlocked
 * @throws InterruptedException Will be thrown if there was an error
 *             while setting up the deadlock
 */
public static Thread[] createDeadlock(final String monitor1, final String monitor2, Object waitMonitor) throws InterruptedException {
    DeadlockThread dt1 = new DeadlockThread(monitor1, monitor2, waitMonitor);
    DeadlockThread dt2 = new DeadlockThread(monitor2, monitor1, waitMonitor);
    DeadlockThread[] retThreads = new DeadlockThread[] {
            dt1,
            dt2,
    };

    synchronized (waitMonitor) {
        dt1.start();
        waitMonitor.wait(1000);
        dt2.start();
        waitMonitor.wait(1000);
    }
    synchronized (monitor1) {
        synchronized (monitor2) {
            monitor1.notifyAll();
            monitor2.notifyAll();
        }
    }
    Thread.sleep(4000);
    return retThreads;
}

private static class DeadlockThread extends Thread {
    private String monitor1;
    private String monitor2;
    private Object waitMonitor;

    public DeadlockThread(String monitor1, String monitor2, Object waitMonitor) {
        this.monitor1 = monitor1;
        this.monitor2 = monitor2;
        this.waitMonitor = waitMonitor;
        setDaemon(true);
        setName("DeadlockThread for monitor " + monitor1 + " and " + monitor2);
    }

    @Override
    public void run() {
        System.out.println(getName() + ": Running");
        synchronized (monitor1) {
            System.out.println(getName() + ": Got lock for monitor '" + monitor1 + "'");
            synchronized (waitMonitor) {
                waitMonitor.notifyAll();
            }
            try {
                System.out.println(getName() + ": Waiting to get lock on '" + monitor2 + "'");
                monitor1.wait(5000);
                System.out.println(getName() + ": Try to get lock on '" + monitor2 + "'");
                synchronized (monitor2) {
                    monitor2.wait(5000);
                }
                System.out.println(getName() + ": Got lock on '" + monitor2 + "', finished");
            } catch (Exception e) {
                // waiting
            }
        }
    }
}

This is the output when running the testcase:

DeadlockThread for monitor Monitor1 and Monitor2: Running
DeadlockThread for monitor Monitor1 and Monitor2: Got lock for monitor 'Monitor1'
DeadlockThread for monitor Monitor1 and Monitor2: Waiting to get lock on 'Monitor2'
DeadlockThread for monitor Monitor2 and Monitor1: Running
DeadlockThread for monitor Monitor2 and Monitor1: Got lock for monitor 'Monitor2'
DeadlockThread for monitor Monitor2 and Monitor1: Waiting to get lock on 'Monitor1'
DeadlockThread for monitor Monitor1 and Monitor2: Try to get lock on 'Monitor2'
DeadlockThread for monitor Monitor2 and Monitor1: Try to get lock on 'Monitor1'

According to the output there should be a deadlock, so either the way I try to detect deadlocks is wrong or something else, I'm missing here, doesn't work as I expect it. But then, the test should fail all the time and not only most of the time.

When running the test on Windows, the output is the same.

Answer 1

Just a guess. Your use of Thread.sleep() seems highly dubious. Try using some form of communication to determine with both threads are ready to be deadlocked.

Untested:

   private Thread[] creadDeadlock() throws InterruptedException {
      Thread[] deadLocked = new Thread [2];
      CountDownLatch gate = new CountDownLatch( 2 );
      CountDownLatch ready = new CountDownLatch( 2 );
      Object monitor1 = new Object();
      Object monitor2 = new Object();
      Runnable r1 = () -> {
         synchronized( monitor1 ) {
            try {
               gate.countDown();
               gate.await();
               ready.countDown();
               synchronized( monitor2 ) {
                  wait();
               }
            } catch( InterruptedException ex ) {
               // exit
            }
         }
      };
      Runnable r2 = () -> {
         synchronized( monitor2 ) {
            try {
               gate.countDown();
               gate.await();
               ready.countDown();
               synchronized( monitor1 ) {
                  wait();
               }
            } catch( InterruptedException ex ) {
               // exit
            }
         }
      };

      deadLocked[0] = new Thread( r1 );
      deadLocked[1] = new Thread( r2 );
      deadLocked[0].start();
      deadLocked[1].start();
      ready.await();
      return deadLocked;
   }