Sunday, October 3, 2010

How to avoid deadlock in Java Threads

How to avoid deadlock in Java is one of the question which is flavor of the season for multithreading , asked more at a senior level and with lots of follow up questions , though question looks very basic but most of developer get stuck once you start going deep.

questions starts with "What is deadlock ?"
answer is simple , when two or more threads waiting for each other to release lock and get stuck for infinite time , situation is called deadlock . it will only happen in case of multitasking.


How do you detect deadlock in Java ?
though this could have many answers , my version is first I would look the code if I see nested synchronized block or calling one synchronized method from other or trying to get lock on different object then there is good chance of deadlock if developer is not very careful.

other way is to find it when you actually get locked while running the application , try to take thread dump , in Linux you can do this by command "kill -3" , this will print status of all the thread in application log file and you can see which thread is locked on which object.

other way is to use jconsole , jconsole will show you exactly which threads are get locked and on which object.

once you answer this , they may ask you to write code which will result in deadlock ?
here is one of my version

public void method1(){
synchronized(String.class){
System.out.println("Aquired lock on String.class object");

synchronized (Integer.class) {
System.out.println("Aquired lock on Integer.class object");
}
}
}

public void method2(){
synchronized(Integer.class){
System.out.println("Aquired lock on Integer.class object");

synchronized (String.class) {
System.out.println("Aquired lock on String.class object");
}
}
}


If method1() and method2() both will be called by two or many threads , there is a good chance of deadlock because if thead 1 aquires lock on Sting object while executing method1() and thread 2 acquires lock on Integer object while executing method2() both will be waiting for each other to release lock on Integer and String to proceed further which will never happen.

now interviewer comes to final part , one of the most important in my view , How to fix deadlock ? or How to avoid deadlock in Java ?

if you have looked above code carefully you may have figured out that real reason for deadlock is not multiple threads but the way they access lock , if you provide an ordered access then problem will be resolved , here is
the fixed version.





public void method1(){
synchronized(Integer.class){
System.out.println("Aquired lock on Integer.class object");

synchronized (String.class) {
System.out.println("Aquired lock on String.class object");
}
}
}

public void method2(){
synchronized(Integer.class){
System.out.println("Aquired lock on Integer.class object");

synchronized (String.class) {
System.out.println("Aquired lock on String.class object");
}
}
}


 

Now there would not be any deadlock because both method is accessing lock on Integer and String object in same order . so if thread A acquires lock on Integer object , thread B will not proceed until thread A releases Integer lock , same way thread A will not be blocked even if thread B holds String lock because now thread B will not expect thread A to release Integer lock to proceed further.

hope this would be useful.

26 comments :

Javin @ Tibco RV Tutorial said...

Thanks Gautam.
Yes you are right deadlock is the most common problem arise with little bit of carelessness during multi threading programming and it can completely stop the program.

Thanks
Javin

Jaroslav Sedlacek said...

Consistent lock acquisition ordering prevents deadlock indeed. But it is possible to have a deadlock even then. Not common scenario but plausible - Deadlock despite consistent lock acquisition ordering

Anonymous said...

never read such a great article on deadlock. deadlock in java or any other programming language is quite common because of multi-threading behavior and I agree its favorite interview topic. the best part of this java interview is how to fix deadlock in java, simply great.

Anonymous said...

are you trying to answer "What is deadlock in Java" or "How to fix deadlock in Java", what I think the key is to write thread-safe, deadlock free concurrent code in java.

Anonymous said...

Using this example there is a very bit chance to get deadlock! Just try this example :) You'll be running it for years to get a deadlock.

I'd like to suggest following sample that produces deadlock with 100% guarantee.


public class DeadLockTest
{

static class ThreadOne implements Runnable {

public void run()
{
synchronized (Integer.class)
{
System.out.println(Thread.currentThread().getName() + " - Got lock on Integer.class");
synchronized (String.class)
{
System.out.println(Thread.currentThread().getName() + " - Got lock on String.class");
}
}
}
}

static class ThreadTwo implements Runnable {

public void run()
{
synchronized (String.class)
{
System.out.println(Thread.currentThread().getName() + " - Got lock on String.class");
synchronized (Integer.class)
{
System.out.println(Thread.currentThread().getName() + " - Got lock on Integer.class");
}
}
}

}
/**
* @param args
*/
public static void main(String[] args)
{
new Thread(new ThreadOne(), "ThreadOne").start();
new Thread(new ThreadTwo(), "ThreadTwo").start();
}

}

You are free to use this sample in your article. Please, just mention my name - Arseny Kovalchuk.

Thanks for initial info that caused my to check this.

Javin @ thread interview questions said...

Hi Arseny Kovalchuk, Thanks for your example but will you explain what is difference between earlier example and this for everybody's understanding , what I see run() method of your example is similar to method1, Also to get guaranteed deadlock one can use Sleep to hold one thread to hold the lock and increase deadlock chance , isn't it ?

Anonymous said...

@Javin, The main difference in my sample is that the synchronized block in the run methods are nested. And the major thing to get a deadlock is

1. threadOne acquires the lock on monitorOne
2. threadTwo acquires the lock on monitorTwo
3. threadOne wants to get lock on monitorTwo, but !mportant! it should not release lock on monitorOne, until it gets the lock on monitorTwo
4. at this time threadTwo wants to get lock on monitorOne, and it doesn't release lock on monitorTwo, until it gets lock on monitorOne.

That's the deadlock. In your sample there is a possibility for both threads to release the lock!

Regards, Arseny Kovalchuk.

Javin @ java interview questions said...

Hi Arseny Kovalchuk, Your Explanation is quite clear and indeed in this condition deadlock will occur, but in my program also synchronized blocks are nested because until its nested probability of deadlock reduces, is it formatting or am I missing something ?

Anonymous said...

@Javin, now it's clear, sorry :) The formatting confused me. I recognized it as synchronized block in series, but not as nested. So, the sample is the same.

Regards, Arseny.

Javin @ abastract class in Java said...

Thanks Arseny ,this discussion make it more clear. I am using blogger and seems [code] is not working, any way I will definitely try to formatting more clear.

Santosh Jha said...

Hi Javin,
I came across a scenario of deadlock in my application and after struggling for a while to detect it, I used the java.util.concurrent.locks.Lock.tryLock(time, unit) method which waits for specified time to acquire a lock and returns a boolean. I used this method for every lock in that scenario and logged the scenario when it could not acquire the lock. This helped me identify and fix all the possible scenarios which can cause dead lock at run time.
Thought, it might be useful to someone if they are trying to detect a dead lock.

Javin @ thread interview questions said...

Thanks for your comment Santosh, isn't tryLock() can return even if there is no deadlock I mean it just not been able to acquire the lock within specified period. I guess taking a thread dump by using kill -3 is another way of finding out which thread is waiting for which lock and than detecting deadlock pattern. JConsole also helps you to find deadlock in Java. Anyway tryLock() can also be used as Indicator and thanks for raising this point.

Santosh Jha said...

You are right Javin, tryLock() false just indicates failure to acquire lock in the specified time. But if we carefully choose the time, based on the context that would only be possible in case of a deadlock (e.g. 10 or 20 minutes) than it would be unlikely that its anything other than a dead lock.

Using kill -3 is a good way, but it requires a manual intervention at the particular time. By putting the tryLock(), we can check the logs anytime.

Using tryLock() can also be used to write some recovery code and the system will never crash because of a dead lock. In worst case a process has to die.

Fahad said...

On event of deadlock in java application you can do following to investigate it:

1) By pressing Ctrl+Break on Windows machines print thread dump in console of Java application. by analyzing this thread dump you will know cause of deadlock.

2) On Linux and Solaris machine you can take thread dump by sending SIGQUIT or kill -3 to Java application process id. From Java 6 onwards budled Jconsole utility can also be attached to hung java process and find out deadlocks in it.

Anonymous said...

hi im arun,the article was very clear for me to know about deadlocks....thanx author

bala said...

Dear Arseny Kovalchuk your example fails ie( dead lock not happens) if first ThreadOne Class completely got executed please check it out

Pallavi S said...

Hi,
Its a gr8 article.. I understood how it results in deadlock but I didnt understand the explanation behind the fix.. I mean u just changed the order. Could u explain the flow please as to how deadlock will not arise ones the order s changed Threads n Java has been my weakest area hence the unclarity

Javin @ CyclicBarrier Example Java said...

Hi Pallavi,not a problem, threads in Java are always confusing. original order of acquring lock in two methods are opposite e..g in method 1 its lock 1-->lock2 while in method 2 its lock2-->lock1 which can result in deadlock because if two thread calls method 1 and method 2 thread 1 may end of lock 1 and thread 2 end of lock 2 and both will wait for other locks, i.e. deadlock.

By having a particular order of acquiring lock e.g. lock1-->lock2 in both method we can eliminate this problem. Also remember to release locks in opposite order e.g. lock2--> lock1.

Anonymous said...

You can also use TIMED and POLLED locks from ReentrantLock to have a probabilistic deadlock avoidation. By using timed and polled lock acquision approach, one thread will eventually back-off, giving another thread to either acquire or release the lock. Though this is not guaranteed, it certainly helps to reduce probability of deadlock in Java program.

Ravi said...

Imposing ordering is an example of avoiding deadlock by braking "Circular Wait" condition. As you know, in order for a deadlock to occur, four condition must met :

1) Mutual Exclusion
2) Hold and Wait
3) No Preemption
4) Circular Wait

Though you can break any of these conditions to avoid deadlock, it's often easy to break circular wait. But, even with consistent ordering, you can not prevent deadlock, if order is not predefined i.e. if Id of next resource comes after acquiring first resource, your system still get into deadlock. This is true for all programming language, which supports multi-threading and concurrency, not just Java.

Gaurav said...

If you talk about How to detect deadlock in Java, then there is a cleaver way by using ThreadMXBean, which provides a method called findDeadLockthreads() which returns id of all those thread which are in deadlock and waiting for each other to release monitor or acquire lock. here is the code :

ThreadMXBean threadMBean = ManagementFactory.getThreadMXBean();

threadMBean.findDeadlockedThreads();

Steyn said...

Just remember, how critical is to write a deadlock free concurrent application in Java, because only way to break deadlock is to restart the server. If you could create deadlock detector at runtime, which can also break deadlock as and when they happen, may be by intruppting or killing thread, without losing data invariant than, it would be just fantastic.

Anonymous said...

hi all, can you explain what is the diff between race condition & deadlock? & how can deadlock be preventive?

Anonymous said...

race condition is when two or more thread trying to use the same block of code/method... i.e racing each other to use particular resoruce and that is locked by one or other thread.

Race condition is sympton of deadlock and go hands in hand.

Anonymous said...

Beginner in java:

I really can't get the difference between the deadlock version example program, and fixed version example program. Please clarify.

Anonymous said...

Perhaps synchronizing the method itself is the best way to avoid deadlock situations rather than block synchronization and ordering...

Uma

Post a Comment