Deadlocks and Synchronized methods

I've found one of the code on Stack Overflow and I thought it is pretty similar to what I am facing but I still don't understand why this would enter a deadlock. The example was taken from Deadlock detection in Java:

Class A
{
  synchronized void methodA(B b)
  {
    b.last();
  }

  synchronized void last()
  {
    System.out.println(“ Inside A.last()”);
  }
}

Class B
{
  synchronized void methodB(A a)
  {
    a.last();
  }

  synchronized void last()
  {
    System.out.println(“ Inside B.last()”);
  }
}

Class Deadlock implements Runnable 
{
  A a = new A(); 
  B b = new B();

  // Constructor
  Deadlock()
  {
    Thread t = new Thread(this); 
    t.start();
    a.methodA(b);
  }

  public void run()
  {
    b.methodB(a);
  }

  public static void main(String args[] )
  {
    new Deadlock();
  }
}

In this case, when the Deadlock() constructor is called, it starts itself as a thread. When it does this, the run() method is invoked. It will call b.methodB(a), which then calls a.last() to just print out a statement. At the same time, a.methodA(b) would call b.last(). There is no cross dependencies on any object and they are not executing a method at a same time too. Even if they are, the synchronized keyword would queue them, wouldn't it? But how come this would occasionally enter a deadlock too? It is n开发者_StackOverflowot all the time but it would sometimes enter a deadlock, which is quite unpredictable. What is it that causes this to go into a deadlock and workarounds?

---

It is possible that the execution of these two statements is interweaved:

Thread 1:  a.methodA(b);    //inside the constructor
Thread 2:  b.methodB(a);    //inside run()

to execute a.methodA(), Thread 1 will need to obtain the lock on the A object.

to execute b.methodB(), Thread 2 will need to obtain the lock on the B object.

For Thread 1's methodA() to then be able to call the sychronized method on the b instance, it will need to obtain the lock on b being held by Thread 2, which will cause Thread 1 to wait until that lock is freed.

For Thread2's methodB() to be able to call the synchronized method on the a instance, it will need to obtain the lock being held on a by Thread 1 - which will cause Thread 2 to wait as well.

Since each thread is holding a lock that the other thread wants, a deadlock will occur where neither thread is able to obtain the lock it wants, and neither thread will release the locks that it does hold.

It's important to understand that this code will not produce a deadlock 100% of the time you run it - only when the four crucial steps (Thread1 holds A's lock and tries to obtain B, which Thread 2 holds B's lock and tries to obtain A's) are executed in a certain order. Run this code enough times and that order is bound to happen though.

---

synchronized places a lock on the object that must be acquired before the methods or codeblocks can execute. Because it locks entire objects, it is an inelegant tool that sometimes looks pretty easy to use, but gives deadlocks like this, where no actual contested data is being read or written.

a.method(b) locks the a object. b.method(a) locks the b object. And neither thread of execution can continue on to calling b.last() or a.last(), because they are both waiting for the other object to release its lock.

---

Calling methodA does (effectively) lock(a), lock(b). If the task switches then and tries methodB, it hits lock(b) right then.