Question About Deadlock Situation in Java

Question

I'm learning about deadlocks in Java, and there's this sample code from Sun's official tutorial:

Alphonse and Gaston are friends, and great believers in courtesy. A strict rule of courtesy is that when you bow to a friend, you must remain bowed until your friend has a chance to return the bow. Unfortunately, this rule does not account for the possibility that two friends might bow to each other at the same time.

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();
    }
}

Here's Sun's explanation:

When Deadlock runs, it's extremely likely that both threads will block when they attempt to invoke bowBack. Neither block will ever end, because each thread is waiting for the other to exit bow.

I don't quite seem to follow. When alphonse.bow(gaston) runs, the bow method is locked. So now it'll first print "Gaston has bowed to me!". Then it'll go on and call bowBack, and locks bowBack as well. How can this cause a deadlock? Am I misunderstanding what happens when a synchronized method is called?

If someone can give me a easy explanation, thanks.

Answer 1

One important point to note is that it is not methods which are locked but object instances.

When you call alphonse.bow(gaston), it tries to acquire the lock on alphonse. Once it has the lock, it prints a message, then calls gaston.bowBack(alphonse). At this point, it tries to acquire the lock on gaston. Once it has the lock, it prints a message, then releases the lock, and finally the lock on alphonse is released.

In deadlock, the locks are acquired in such an order that there's no way for either thread to proceed.

• Thread 1: acquires lock on alphonse
• Thread 2: acquires lock on gaston
• Thread 1: prints message
• Thread 1: tries to acquire lock on gaston - can't, because Thread 2 already has it.
• Thread 2: prints message
• Thread 2: tries to acquire lock on alphonse - can't, because Thread 1 already has it.

Answer 2

alphonse and gaston are two different objects. Each object has an intrinsic monitor (lock) that is associated with it.

It could happen like this:

alphonse is created. His object monitor is 1.

gaston is created. His object monitor is 2.

alphonse.bow(gaston); alphonse now owns lock #1

gaston.bow(alphonse); gaston now owns lock #2

alphonse calls bowBack on gaston and is waiting for lock #2 gaston calls bowBack on alphonse and is waiting for lock #1

Make sense? Using the synchronized keyword locks that instances monitor for the duration of the method. The example could be rewritten as follows:

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