Why java does not recover from deadlock?

Question

I am reading the book Java Concurrency in Practice, and here is what it says about deadlock.

JVM does not recover from deadlock, and only way to get rid of dead lock is to restart the server. It also mentions that JVM uses graph search where Thread acts as graph node and edge between two threads A and B is defined as Thread A is waiting for lock on resource already held by thread B. This graph is directed and if there is any cycle in this graph, then there is deadlock

Now my question is that if JVM knows that there is deadlock, then why does not it kill one thread and let other proceed? is there any specific reason behind this or my question itself is based on wrong conclusion?

Please let me know your views about this. Thanks in advance!!!

• AKS: As I always mention, Comments are more useful than downvoting. so please put your comments rather than simply downvoting.
• Mac: I think that this question doesn't deserve downvote. +1 for counter balancing downvote. Now , a quick question for you : How JVM will come to know that Which thread do you want to kill in case of deadlock?
• AKS: @Mac, I am assuming if JVM kills any one of the threads, then deadlock will be resolved, but Yes, I agree, it will be unfair to the thread which will get killed, but at least no restart will be required. And my question is inspired from database transaction deadlocks, where one of the transactions are killed in case of deadlock.
• Mac: By not killing on of the threads in deadlock situation, JVM ensures the safety of your code by avoiding unpredictable and inconsistent changes in state variables, or any inconsistent transaction and many other shared among the threads.
• AKS: @Mac, Now I am getting the reason, and I agree that data inconsistency is the main reason that JVM does not interferes in this situation.

Answer 1

Now my question is that if JVM knows that there is deadlock, then why does not it kill one thread and let other proceed? is there any specific reason behind this or my question itself is based on wrong conclusion?

How could the JVM make the decision about which thread to kill? What if the JVM, in releasing the lock by force, allowed invalid data to enter some sort of critical database?

The JVM cannot make these sort of decisions arbitrarily. It reports on the deadlock but cannot automagically recover from it.

You could see this problem in any situation where two critical objects are being modified with locks but two threads are locking them in a different order. Database transactions are able to recover from such deadlocks because they are designed to roll back tables and indices but Java synchronized locks don't have implicit memory rollback capabilities. By killing one thread and releasing its locks, the JVM would be allowing partial memory updates to be propagated.

• AKS: What invalid data can enter into system? Yes, I understand that it will be unfair for JVM to arbitrarily decide which one to kill, but Database transaction locks follows this logic. In database transactions, if there is deadlock then one of them is killed and other one goes through. I am sure there must be some reason for JVM to not kill any thread, but I am just trying to explore all possibilities.
• Gray: Any situation @AKS, where two critical objects are being modified with locks but two threads are locking in different order. Database transactions do work this way but java synchronized locks don't have implicit memory rollback capabilities. In my answer I meant "database" in a generic sense.
• Mac: @Gray: Now you have made you answer automagically more beautiful and informative by giving an example of database :). Wish to +1 more
• Peter Lawrey: +1 it is a problem which requites the developer to fix the code.

Answer 2

Killing one thread would not allow the other to proceed sanely. In fact, killing the thread would be fatal. The reason a thread acquires a lock in the first place is to keep other threads out of some data structure while that data structure is an inconsistent state. Releasing the lock with the data structure still in an inconsistent state would fatally contaminate the process context.

For example:

1. Thread A locks object 1.

2. Thread B locks object 2.

3. Thread A puts object 1 in an inconsistent state.

4. Thread B puts object 2 in an inconsistent state.

5. Thread A blocks on object 2.

6. Thread B blocks on object 1.

How can either thread proceed now? Each is waiting for the other thread to return an object into a consistent state.

Here's a clearer example in case you don't understand what I mean by an inconsistent state. Consider this code:

1. Acquire the lock that protects foo and bar.
2. Start World War III if foo plus bar is not 10. (No worries, the programmer carefully made sure foo plus bar is always 10 unless he actually has to start World War III.)
3. Increment foo.
4. Acquire some other lock.
5. Decrement bar
6. Release the other lock.
7. Release the lock that protects foo and bar.

What do you do if you deadlock at step 4? You cannot release the lock that protects foo and bar as the next thread to run this code would start World War III. Clearly, detailed understanding of what this specific code does is needed to untangle the deadlock.

• Mac: I guess that in case of implicit locking , killing thread would simply release the lock that it has acquired..correct me if I am wrong.
• David Schwartz: @Mac: Releasing the lock would be catastrophic, as it would allow other threads to see the object's inconsistent state. Not releasing the lock would, likewise, be catastrophic as any thread that touched the lock would stall forever.
• AKS: @DavidSchwartz I agree with you, now I can buy the argument that although locks will be released by killing one thread, but data might be in inconsistent state. But not sure whether killing a thread will release the lock or not, not sure how JVM behaves in this case. Going to try in my eclipse and see what it does.
• David Schwartz: See my updates which make it clearer why you cannot just release locks.
• cHao: @Mac: It wouldn't allow the other to proceed sanely. Presumably the locks were acquired in order to keep other threads from seeing half an update. If you kill the holder of the lock while it's updating...sure, the locks are released, and the other thread would be able to acquire them. But what they were protecting is probably broken all to hell now, which is a worse case than simply being deadlocked.