How Deadlock arises in the given Java program?

Question

The following code snippet is taken from Java Tutorials which says that the threads remain blocked for ever but I am unable to make out how. Please explain.

Is it something that both synchronized methods share the same intrinsic lock?

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

If you search this site for "alphonse gaston", you'll realize your question has been asked several dozen times. — Marko Topolnik, Mar 07 '14 at 13:33
Please note that tutorial says: "*it's **extremely likely** that both threads will block when they attempt to invoke bowBack*" (emphasis is mine). So deadlock is not guaranteed on each run. — PM 77-1, Mar 07 '14 at 13:36

sakura · Answer 1 · 2014-03-07T13:38:16.257

In above sample there might be following situation:

alphonse has his own lock
gaston has his own lock

As both call bow() method in their own thread using their own locks. And if you will carefully see, in the bow() method the alphonse is now calling bowback() using another reference i.e. using gaston's lock.

So, there may be a case when gaston has already entered in bow() method using his own lock but alphonse's thread is trying to enter in bowback() method which is already locked by the gaston's thread. Same is true vice-versa.

so, the reversing of reference to call the bowback() method is error prone which can cause a deadlock.

   public synchronized void bow(Friend bower) {
        System.out.format("%s: %s"
            + "  has bowed to me!%n", 
            this.name, bower.getName());
        bower.bowBack(this); // <---------  This Line 
        // here bower is not the same person how acquired
        // the lock while calling bow() method
    }

score 0 · Answer 2 · answered Mar 07 '14 at 13:29

0

Yes, there is the same lock (the object itself I guess) for both methods, as they state here:

When one thread is executing a synchronized method for an object, all other threads that invoke synchronized methods for the same object block

answered Mar 07 '14 at 13:29

Joffrey

32,348
6
68
100

score 0 · Answer 3 · answered Mar 07 '14 at 13:31

In one Thread's context from method bow is called method in other Thread's context and that is problem.

It is different this object for Alphonse and Gaston, and synchronization is done on those two in two threads sequentially. First thread that enters will take first lock and try to take second, but it will be stopped since other lock is taken by other thread.

Problem would not appear if one Thread waited for other to complete full computation.

score 0 · Answer 4 · answered Mar 07 '14 at 13:32

0

Thread A obtains lock for alphonse when bow(gaston) Thread B obtains lock for gaston when bow(aphonse) Thread A waits for lock when bowBack(gaston) Thread B waits for lock when bowBack(aphonse)

answered Mar 07 '14 at 13:32

Harmlezz

7,972
27
35

score 0 · Answer 5 · edited May 23 '17 at 11:52

From your link:

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.

What is a Deadlock?

Generally a deadlock happens when a thread (1) lock a resource (A) and then attempt to lock another resource (B), but the resource B is locked from another thread (2) which attempt to lock the resource A.

In this case no threads will grain the access to the two resources and will wait forever until the resource is free.

Anyway as Jamie noticed a deadlock could not happen if you are lucky, but with an i7 i get this

Alphonse: Gaston  has bowed to me!
Gaston: Alphonse  has bowed to me!

Remember synchronized in method means synchronized(this) .

As @Nikita Rybak answer in the same question (Java deadlock question) (upvote his answer!)

Enter alphonse.bow(gaston);, alphonse is now locked due to synchronized keyword
Enter gaston.bow(alphonse);, gaston is now locked
Can't execute bower.bowBack(this); from first bow method call because gaston (bower) is locked. Wait for lock to be released.
Can't execute bower.bowBack(this); from second bow method call because alphonse (bower) is locked. Wait for lock to be released.

How Deadlock arises in the given Java program?

5 Answers5