Java wait()/join(): Why does this not deadlock?

Question

Given the following Java code:

public class Test {

    static private class MyThread extends Thread {
        private boolean mustShutdown = false;

        @Override
        public synchronized void run() {
            // loop and do nothing, just wait until we must shut down
            while (!mustShutdown) {
                try {
                    wait();
                } catch (InterruptedException e) {
                    System.out.println("Exception on wait()");
                }
            }
        }

        public synchronized void shutdown() throws InterruptedException {
            // set flag for termination, notify the thread and wait for it to die
            mustShutdown = true;
            notify();
            join(); // lock still being held here, due to 'synchronized'
        }
    }

    public static void main(String[] args) {
        MyThread mt = new MyThread();
        mt.start();

        try {
            Thread.sleep(1000);
            mt.shutdown();
        } catch (InterruptedException e) {
            System.out.println("Exception in main()");
        }
    }
}

Running this will wait for one second and then properly exit. But that is unexpected to me, I expect a dead-lock to happen here.

My reasoning is as follows: The newly created MyThread will execute run(), which is declared as 'synchronized', so that it may call wait() and safely read 'mustShutdown'; during that wait() call, the lock is released and re-acquired upon returning, as described in the documentation of wait(). After one second, the main thread executes shutdown(), which is again synchronized as to not access mustShutdown at the same time as it's being read by the other thread. It then wakes up the other thread via notify() and the waits for its completion via join().

But in my opinion, there's no way that the other thread can ever return from wait(), since it needs to re-acquire the lock on the thread object before returning. It cannot do so because shutdown() still holds the lock while inside join(). Why does it still work and exit properly?

Answer 1

join() method internally calls wait() which will result in releasing of the lock(of Thread object).

See the code of join() below:

public final synchronized void join(long millis) 
    throws InterruptedException {
    ....
    if (millis == 0) {
       while (isAlive()) {
         wait(0);  //ends up releasing lock
       }
    }
    ....
}

Reason why your code sees this and not seen in general:: The reason why your code see this and not is not observed in general, is because the join() method waits() on Thread object itself and consequently relinquishes lock on the Thread object itself and as your run() method also synchronizes on the same Thread object, you see this otherwise unexpected scenario.

Answer 2

The implementation of Thread.join uses wait, which lets go of its lock, which is why it doesn't prevent the other thread from acquiring the lock.

Here is a step-by-step description of what happens in this example:

Starting the MyThread thread in the main method results in a new thread executing the MyThread run method. The main Thread sleeps for a whole second, giving the new Thread plenty of time to start up and acquire the lock on the MyThread object.

The new thread can then enter the wait method and release its lock. At this point the new thread goes dormant, it won't try to acquire the lock again until it is woken up. The thread does not return from the wait method yet.

At this point the main thread wakes up from sleeping and calls shutdown on the MyThread object. It has no problem acquiring the lock because the new thread released it once it started waiting. The main thread calls notify now. Entering the join method, the main thread checks that the new thread is still alive, then waits, releasing the lock.

The notification happens once the main thread releases the lock. Since the new thread was in the wait set for the lock at the time the main thread called notify, the new thread receives the notification and wakes up. It can acquire the lock, leave the wait method, and finish executing the run method, finally releasing the lock.

The termination of the new thread causes all threads waiting on its lock to receive a notification. This wakes up the main thread, it can acquire the lock and check that the new thread is dead, then it will exit the join method and finish executing.

/**
 * Waits at most <code>millis</code> milliseconds for this thread to 
 * die. A timeout of <code>0</code> means to wait forever. 
 *
 * @param      millis   the time to wait in milliseconds.
 * @exception  InterruptedException if any thread has interrupted
 *             the current thread.  The <i>interrupted status</i> of the
 *             current thread is cleared when this exception is thrown.
 */
public final synchronized void join(long millis) 
throws InterruptedException {
long base = System.currentTimeMillis();
long now = 0;

if (millis < 0) {
        throw new IllegalArgumentException("timeout value is negative");
}

if (millis == 0) {
    while (isAlive()) {
    wait(0);
    }
} else {
    while (isAlive()) {
    long delay = millis - now;
    if (delay <= 0) {
        break;
    }
    wait(delay);
    now = System.currentTimeMillis() - base;
    }
}
}