Java Deadlock code explanation

Question

Could someone please explain why the following code results in deadlock. My understanding is that when alphonse(thread) run then it acquires lock on friend obj because it invokes bow() method but how come gaston(another thread) is able to acquires the lock on the same friend obj while the alphonse haven't finished/released the lock on friend obj.

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.println("invoked by " + name);
        System.out.format("%s: %s"
            + "  has bowed to me!%n", 
            this.name, bower.getName());
        bower.bowBack(this);
        System.out.printf("finished by " + name);
    }
    public synchronized void bowBack(Friend bower) {
        System.out.format("%s: %s"
            + " has bowed back to me!%n",
            this.name, bower.getName());
        System.out.println("exiting bowBack()");
    }
}

public static void main(String[] args) throws InterruptedException {
    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();
}

}

Answer 1

1. thread 1: alphonse.bow(). To enter this method, thread 1 acquires the lock of alphonse, since the bow() method is synchronized.
2. thread 2: gaston.bow(). To enter this method, thread 2 acquires the lock of gaston, since the bow() method is synchronized.
3. thread 1: gaston.bowBack(). To enter this method, thread 1 needs to acquire the lock of gaston, since the bowBack() method is synchronized. It waits until thread 2 has released the lock of gaston
4. thread 2: alphonse.bowBack(). To enter this method, thread 2 needs to acquire the lock of alphonse, since the bowBack() method is synchronized. It waits until thread 1 has released the lock of alphonse

The two threads end up waiting for each other. It's a deadlock.

Answer 2

Imagine the two threads executing in parallel:

thread1                               thread2
-----------------------------------   -----------------------------------
enter alphonse.bow(gaston)            enter gaston.bow(alphonse)
  - acquire lock on alphonse            - acquire lock on gaston

gaston.bowBack(alphonse)              alphonse.bowBack(gaston)
  - try to acquire lock on gaston;      - try to acquire lock on alphonse;
    blocked because of gaston.bow()       blocked because of alphonse.bow()

At this point, both threads are waiting for the other to release a lock, and neither can complete the synchronized method so that it'll release the lock (because it's waiting for the other).

Answer 3

You have a circular chain of locks: alphonse.bow acquires lock on alphonse and then tries to take on gaston which might already be taken. gaston.bow acquires lock on gaston and then tries to take on alphonse, but it is already taken.

To analyze/visualize this, draw a diagram of threads (say two circles) and resources (say two rectangles). When a thread asks for resource draw an arrow from thread to resource. When a resource is granted, draw an arrow from that resource to the owner thread. Everything is fine as long as you don't have loops. If you end up with a loop, then you need to sacrifice something in that loop to break the loop

Answer 4

This is the classic deadlock scenario: You have N objects, where each object has its own lock and you're aquiring multiple of these locks in random order.

The problem occurs when two treads are trying to "bow" to each other. Each thread aquires the lock for its own person (alphonse and gaston), then tries to aquire the lock of the friend while still holding the lock to its own person.

This can be resolved in different ways.

The simplest would be to generally use a global lock (e.g. a static locking object defined inside the Friend class). That generally allows only one thread to perform the bow/bowback sequence at a time. Sometimes thats just fine, sometimes it can be a performance bottleneck.

The more complicated solution is to ensure locks are aquired in a deterministic order, e.g. ensure that the lock for alphonse is always aquired before the lock to gaston. For that you can introduce an ordering criterion to the objects to be locked, for simplicity lets assume we could rely on the names of the friends to be unique.

That makes implementation a tad bit more complicated, but allows for more concurrency than a global lock while still avoiding deadlocks. Insted of blindly synchronizing on "self" the method now decides a priority order in which to synchronize on whom:

public void bow(Friend bower) {
    // determine locking order
    Friend first, second;
    if (getName().compareTo(bower.getName()) > 0) {
        first = this;
        second = bower;
    } else {
        first = bower;
        second = this;
    }
    synchronized (first) {
        synchronized (second) {
             // perform bow normally
        }
    }
}

This works because no matter if alphonse bows to gaston or vice versa, they each would aquire the locks in the same order.