Trying to wrap my wee brain around how threads deadlock...

Question

First, here's a sample:

public class Deadlock {
    static class Friend {
        private final String name;
        public Friend(String name) {
            this.name = name;
        }
        public String getName() {
            return this.name;
        }
        public synchronized void bow(Friend bower) {
            System.out.format("%s: %s has bowed to me!%n", 
                    this.name, bower.getName());
            bower.bowBack(this);
        }
        public synchronized void bowBack(Friend bower) {
            System.out.format("%s: %s has bowed back to me!%n",
                    this.name, bower.getName());
        }
    }

    public static void main(String[] args) {
        final Friend alphonse = new Friend("Alphonse");
        final Friend gaston = new Friend("Gaston");
        new Thread(new Runnable() {
            public void run() { alphonse.bow(gaston); }
        }).start();
        new Thread(new Runnable() {
            public void run() { gaston.bow(alphonse); }
        }).start();
    }
}

What I don't get is how the blockage occurs. The main function initiates two threads that each begin their own bows.

What exactly does 'synchronized' block? The same function running for the same object (as I originally thought)? The same function for all objects of the same class? All synchronized functions for the same object? All synchronized functions for all objects of the same class?

Help me out here.

Answer 1

Synchronized has two effects:

• First, it is not possible for two invocations of synchronized methods on the same object to interleave. When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods for the same object block (suspend execution) until the first thread is done with the object.
• Second, when a synchronized method exits, it automatically establishes a happens-before relationship with any subsequent invocation of a synchronized method for the same object. This guarantees that changes to the state of the object are visible to all threads.

So in short, it blocks any invocations of synchronised methods on the same object.

Answer 2

All synchronized functions for the same object. Marking a method "synchronized" is very similar to putting a "synchronized (this) {" block around the entire contents of the method. The reason I don't say "identical" is because I don't know offhand whether the compiler emits the same bytecode or not, but AFAIK the defined runtime effect is the same.

The deadlock is a classic locking inversion. One thread locks alphonse. Then (or simultaneously on a multi-core system) the other thread locks gaston. This part requires that the scheduling of the threads just so happens to interleave at the right points.

Each thread (in whatever order or simultaneously) then attempts to acquire a lock which is already held by the other thread, and hence each thread goes to sleep. Neither will wake until the other releases its lock, but neither will release its lock until it wakes (or is terminated).

Answer 3

In Java, each Object provides the ability for a Thread to synchronize, or lock, on it. When a method is synchronized, the method uses its object instance as the lock. In your example, the methods bow and bowBack are both synchronized, and both are in the same class Friend. This means that any Thread executing these methods will synchronize on a Friend instance as its lock.

A sequence of events which will cause a deadlock is:

1. The first Thread started calls alphonse.bow(gaston), which is synchronized on the alphonse Friend object. This means the Thread must acquire the lock from this object.
2. The second Thread started calls gaston.bow(alphonse), which is synchronized on the gaston Friend object. This means the Thread must acquire the lock from this object.
3. The first thread started now calls bowback and waits for the lock on gaston to be released.
4. The second thread started now calls bowback and waits for the lock on alphonse to be released.

To show the sequence of events in much more detail:

1. main() begins to execute in the main Therad (call it Thread #1), creating two Friend instances. So far, so good.
2. The main Thread starts its first new Thread (call it Thread #2) with the code new Thread(new Runnable() { .... Thread #2 calls alphonse.bow(gaston), which is synchronized on the alphonse Friend object. Thread #2 thus acquires the "lock" for the alphonse object and enters the bow method.
3. A time slice occurs here and the original Thread gets a chance to do more processing.
4. The main Thread starts a second new Thread (call it Thread #3), just like the first one. Thread #3 calls gaston.bow(alphonse), which is synchronized on the gaston Friend object. Since no-one has yet acquired the "lock" for the gaston object instance, Thread #3 successfully acquires this lock and enters the bow method.
5. A time slice occurs here and Thread #2 gets a chance to do more processing.
6. Thread #2 now calls bower.bowBack(this); with bower being a reference to the instance for gaston. This is the logical equivalent of a call of gaston.bowBack(alphonse). Thus, this method is synchronized on the gaston instance. The lock for this object has already been acquired and is held by another Thread (Thread #3). Thus, Thread #2 has to wait for the lock on gaston to be released. The Thread is put into a waiting state, allowing Thread #3 to execute further.
7. Thread #3 now calls bowback, which in this instance is logically the same as the call alphonse.bowBack(gaston). To do this, it needs to acquire the lock for the alphonse instance, but this lock is held by Thread #2. This Thread is now put into a waiting state.

And you are now in a position where neither Thread can execute. Both Thread #2 and Thread #3 are waiting for a lock to be released. But neither lock can be released without a Thread making progress. But neither thread can make progress without a lock being released.

Thus: Deadlock!

Deadlocks very often depend on a specific sequence of events occurring, which can make then difficult to debug since they can be difficult to reproduce.

Answer 4

The synchronized method is the same as enclosing all those methods code into a

synchronized(this) {
  /// code here ...
}

block.

For a given object instance o, only one thread at a time can run any synchronized(o) block. Every other thread that tries to will wail, until the thread that runs that block (has the synchronized lock on it) exits that block (relinquishes the lock).

In your case, the deadlock happens when Alphonse starts bowing in thread 1, thus entering the synchronized block. Thread 1 then gets swapped out by the system, so Thread 2 can start, and have Gaston bowing. But Gaston cannot bow back yet, because it is synchronizing on Alphonse, and Thread 1 already has that lock. It will thus wait for Thread 1 to leave that block. The system will then swap Thread 1 back in, which will try to have Alphonse bow back. Except it cannot do so because Thread 2 has the synchronized lock on Gaston. Both Threads are now stuck, waiting for the other to finish bowing before being able to bow back...