Deadlock - how does it happen in this example?

Question

can anyone explain:

1. why do we get a deadlock?
2. how can Gaston enter function bow before Alphonse exit that function? (it should return from function bowBack() in order to exit the function bow() - or)?

This is the output I get - and then program is stuck!

Alphonse: Gaston has bowed to me!

Gaston: Alphonse has bowed to me!

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

Answer 1

What happens in your example:

1. Thread Alphonse is acquiring the lock to Alphonse by entering the function bow.

2. Thread Gaston is acquiring the lock to Gaston by entering the function bow.

3. Thread Alphonse is requesting the lock to Gaston to enter the function bowBack but that lock is currently held by Thread Gaston, so Alphonse is forced to wait.

4. Thread Gaston is requesting the lock to Alphonse to enter the function bowBack but that lock is currently held by Thread Alphonse, so Gaston is forced to wait.

Dead-lock.

Why this is happening:

A synchronized function is syntactic sugar for synchronized(this) { ... } So the class above could also be written like this:

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

this in this example is however the instance of the class, so each instance has it's individual lock. If you want to lock on the same object in all instances of a class, you need to lock on a static object like this:

protected static final Object STATIC_LOCK = new Object();

public void bow(Friend bower) {
    synchronized (STATIC_LOCK) {
        System.out.format("%s: %s has bowed to me!%n", this.name, bower.getName());
        bower.bowBack(this);
    }
}

public void bowBack(Friend bower) {
    synchronized (STATIC_LOCK) {
        System.out.format("%s: %s has bowed back to me!%n", this.name, bower.getName());
    }
}

Since this LOCK object is static, both threads will now lock on the same object, and therefore correctly lock out each other. Notice the keyword final which is strongly recommended in this case, because otherwise what synchronized locks on could change during execution (by bugs or oversights in your code), which would put you back into the dead-lock situation for the exact same reason as above.

Answer 2

First of all, the usage of synchronized is wrong. The oracle tutorial nicely states:

First, it is not possible for two invocations of synchronized methods on the same object to interleave.

As explained by the other answer: the code shown in the example does not use a "common lock" (synchronized methods on two different objects do not affect the "other" method call).

Beyond that: as soon as you remove those System.out.format() calls - your program can (will most often) not run into a deadlock.

Or: put a println() in your main before you start the threads - again, the program will not deadlock.

In other words: printing to the console is extremely time consuming. Therefore this affects the timing of your threads dramatically! What happens here is that most of the time is spent for those console output actions. See here for a similar question that even uses the same names ;-)

Answer 3

Thread 1: alphonse instance gets locked from alphonse.bow(gaston); which prints a line and then calls gaston.bowBack() (but gaston is locked from Thread 2 due to synchronized bow() instance called on it below)

Thread 2: gaston instance gets locked from gaston.bow(alphonse); which prints a line and then calls alphonse.bowBack()(but alphonse is locked from Thread 1 due to synchronized bow() instance called on it)

So they're both waiting for the release and cannot exit bow() method, hence the Deadlock

Answer 4

The synchronized block / method is synchronized to this, that is the object instance the block / method is called. (For static "object instance" is to be replaced with "class instance".)

That is your 2 objects get synchronized to themselves, not a common object.

Try something like this:

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