Where is the Deadlock?

Question

This is tutorial from java docs for deadlock. i don't get where threads get blocked. since its synchronized i thought only one thread 'll enter bow. but both entered bow. [one waits [but when?]]

then where is the issue?

when i add comments [print statements to trace]. there's no deadlock. how?

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() {
            @Override
            public void run() { 
               // System.out.println("Thread 1");
                alphonse.bow(gaston); 
               // System.out.println("Th: gaston bowed to alphonse");
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() { 
              //  System.out.println("Thread 2");
                gaston.bow(alphonse);
              //  System.out.println("2.gaston waiting alph bowed");
            }
        }).start();
    }
}

The output is:

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

none bows back!

Answer 1

There are two important things to understand here: 1) What is each concurrently running thread doing? and 2) What are the locks involved?

Last thing first, you created two instances of the Friend class: alphonse and gaston. Each of those objects possesses its own lock. So there are two locks: alphonse's lock and gaston's lock. When you enter a synchronized method of an object, it locks that object's lock. The lock is released (unlocked) when the synchronized method returns.

Now the threads. Your first thread, let's call it Alphone's thread (note capital A to distinguish the thread from the object, alphonse) does this: ("A:" indicates that this is Alphonse's thread.)

A: alphonse.bow(gaston) - acquires alphonse's lock
A: gaston.bowBack(alphonse) - acquires gaston's lock
A: both methods return, thus releasing both locks

Concurrently, Gaston's thread does this: ("G:" indicates that this is Gaston's thread.)

G: gaston.bow(alphonse) - acquires gaston's lock
G: alphonse.bowBack(gaston) - acquires alphonse's lock
G: both methods return, thus releasing both locks

Now we can put these two bits of information together to arrive at our answer. The threads may interleave (i.e., their events occur) in different orders. For example, a deadlock occurs if the events occur in this order:

A: alphonse.bow(gaston) - acquires alphonse's lock
G: gaston.bow(alphonse) - acquires gaston's lock
G: attempts to call alphonse.bowBack(gaston), but blocks waiting on alphonse's lock
A: attempts to call gaston.bowBack(alphonse), but blocks waiting on gaston's lock to

In this case each thread is blocked, waiting to acquire the lock that the other thread holds. However, neither thread will release the lock it holds because it must complete its method in order to do so, which it cannot do since it is blocked waiting on the other thread. Thus they are stuck in place - deadlocked.

However, another possible interleaving (order of events) is one in which one of the threads completes before the other one really gets going, like so:

A: alphonse.bow(gaston) - acquires alphonse's lock
A: gaston.bowBack(alphonse) - acquires gaston's lock
A: both methods return, thus releasing both locks
G: gaston.bow(alphonse) - acquires gaston's lock
G: alphonse.bowBack(gaston) - acquires alphonse's lock
G: both methods return, thus releasing both locks

In this case there is no deadlock. When you added println's and got no deadlock, most likely what's happening is the extra delay of additional println's affects the scheduling and/or rate at which the threads run, so that you get this kind of interleaving instead of the one that deadlocks.

When the outcome is dependent on the ordering of concurrent events (i.e., their scheduling or the rate at which they run) that is called a "race condition". For example, in this program, which thread prints output first depends in the order in which they're scheduled or the rate at which they run. Whether or not the threads deadlock also depends on this. Thus by perturbing that rate (e.g., by adding extra instructions), you may affect the outcome of the race - but that doesn't mean the race has gone away.

Not all race conditions have the potential to cause deadlock. However, in my experience, deadlocks only occur in race conditions. (Perhaps someone who knows could comment on whether that's necessarily the case, or just commonly the case?)

Deadlocks are not easy to understand at first; I did my best to explain, but please let me know if you have any follow-up questions on my post. :)

Answer 2

Consider at some point in time, "Alphonse" and "Gaston" both start bowing, which means they have already possessed their own locks respectively. Then they both want the other one to bow back simultaneously, which means both of them are trying to acquire the other's lock. Since both locks are occupied, the bowBack() call will be blocked. And because bowBack() is within the bow() block, the bow() function cannot return immediately. So they are in the deadlock situation when they have already get some resources, but are still trying to acquire some other resources which have already taken.

Answer 3

Firstly, calling System.out.println() brings in a lot of resources, so it creates a effective delay in processing that can artificially cause/avoid concurrent problems. Don't read too much into the effects of adding prints.

Now then, a deadlock happens when thread A lock X then lock Y, and simultaneously thread B lochs Y then locks X. If both get their first lock, neither can continue = deadlock.

In your case, the method bow() locks the instance it's called on, but then from within that lock calls the bow method of the bowee: synchronisation is locking the instance, so two separate instances can both get their first lock. The second lock is on the other instance, so both threads are waiting on a lock held by the other thread = deadlock.

Answer 4

Here explained precisely. Since 1st object is trying to call something on 2nd object, 2nd object is waiting since it came to synchronized block, so 1st call on bowBack() will never end, and both call be stuck there. Read the article. 1st time I haven't noticed that u were calling bower.getName() from the opposite object. bower.getName() call is causing the deadlock

Answer 5

You've got 2 separate objects there - The synchronised keyword won't prevent bow being called at the same time in object 1 as in object 2. It'll only prevent two threads from entering the synchronised method of the same object.

So then both methods are entered, with locks held on each of the objects. Neither can then enter the method of the other object, as synchronised keywords work on the object level.