Deadlocks and Synchronized methods

Question

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 not 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?

matt b · Accepted Answer · 2011-06-07T02:39:24.340

23

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.

edited Jun 07 '11 at 02:39

answered Jun 07 '11 at 02:33

matt b

138,234
66
282
345

2

This is the answer, but when will we be able to draw diagram on SO? :-) – Alvin Jun 07 '11 at 02:38
@Alvin you could probably embed a image from http://www.websequencediagrams.com/ or http://yuml.me/ – matt b Jun 07 '11 at 02:40
@matt yes, that would work too, but not as nice as drawing directly on SO ;) – Alvin Jun 07 '11 at 02:42
Is there any way in Java that I can prevent this problem? I am trying to think how I can avoid this deadlock problem but it seems very confusing since they both will occasionally come to a situation where they automatically wait for each other. thanks! – Carven Jun 07 '11 at 02:54
Yes - reasoning about what types of synchronization is necessary in your program, such as preventing different threads from changing the same data in a non-thread-safe manner. You first need to understand what bad things can happen if multiple threads access the same instances of your objects in order to know how to prevent side effects. There is no quick and easy solution, and marking everything `synchronized` doesn't really help - you've likely just made your program single-threaded! – matt b Jun 07 '11 at 02:58
@xEnOn: To avoid this kind of deadlock is easy. If you ever need to lock the same two or more objects in different parts of your program always lock them in the *same order*. – Jake T. Jun 07 '11 at 03:06
the other part of that I would emphasize is *if you ever need to lock the same two or more*... you can't solve synchronization unless you first understand where it's necessary – matt b Jun 07 '11 at 03:09

score 2 · Answer 2 · answered Jun 07 '11 at 02:36

2

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.

answered Jun 07 '11 at 02:36

sarnold

102,305
22
181
238

But if I don't use synchronized, the method may just run half-way and then gets interrupted by the other thread. But using synchronized causes such locking issues to happen. How would one usually solve such a problem? thanks – Carven Jun 07 '11 at 02:55
1

@Xenon, learning how to program concurrent programs correctly is a vast field for study; the best advice I've heard is "lock data, not code". Java's `synchronized` makes it easy to lock code, but locking specific data objects is the more useful tool, in the long run. It is also usually easier to reason about locks on _data_, so you can enforce a lock hierarchy, to prevent deadlocks. – sarnold Jun 07 '11 at 19:41

score 0 · Answer 3 · answered Jun 07 '11 at 02:34

0

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

answered Jun 07 '11 at 02:34

david van brink

3,604
1
22
17

Deadlocks and Synchronized methods

3 Answers3

Linked

Related