Deadlock in Java
FREEDeadlock in Java is a situation where two or more processes wait indefinitely for one another's action. Deadlock situation takes place mainly in Multithreaded programming. For example, a deadlock can occur when a thread is waiting to acquire an object's lock acquired by another thread, and the second thread is waiting to acquire another object's lock acquired by the first thread. Hence, both threads are waiting for each other to release the lock, creating a deadlock situation.
What is Deadlock?
Let us understand deadlock in a real-world scenario. Imagine a narrow bridge where only a single vehicle can pass at a time. Two vehicles, V1 and V2, are crossing the bridge at the same time but from opposite ends of the bridge, as shown in the figure below.
Consider that both the vehicles don’t have a reverse gear.
In the above situation, neither V1 nor V2 can cross the bridge as both vehicles block the bridge for each other. To clear the path for V1, V2 has to go back or else vice versa, but both vehicles can't go back. So, this is considered to be a deadlock situation. Both vehicles would have to wait indefinitely to cross the bridge.
The above example was in layman's terms. Have you ever wondered how deadlock occurs in local machines? Let's look at an example to understand deadlock in computer systems.
Consider two threads, T1 and T2, and both have locked/occupied the resources, R1 and R2, respectively. Now thread T1 is requesting the resource R2, and T2 is requesting the resource R1. Both the threads T1 and T2 won’t set free their respective resources R1 and R2 until they finish the execution of the thread.
The image below represents the current situation.
Hence, this situation is a deadlock. It is a state where the progress of all the processes is zero, and all the processes effectively prevent each other from moving ahead with the execution. The processes in the deadlock wait for each other to release resources for an infinite amount of time.
Note:
In the above example, we have seen a deadlock for two threads, but in general, there can be more than two threads where every thread will be in the wait state.
What is Deadlock in Java?
To understand deadlock in Java, we need to learn about threads and the wait state of a thread.
Threads
In the context of Java, a thread is the path followed when executing a program. It is a sequence of executed statements or method calls that allow multiple activities within a single process. All programs have at least one thread (main thread) provided by the JVM, which invokes the main method.
Wait State
The situation where a thread gets stuck due to resource unavailability can be termed a wait state.
This unavailability of resources happens because the resource is non-sharable and is locked by another thread. For example, if a user wants to print a document through the p1 process, the printer becomes a resource necessary for p1's execution. However, if the printer is already occupied by some other process, p2 and p1 would have to wait as some other process locks the printer. The above-explained situation is a wait state for p1.
Now, imagine two threads, A and B, are in a waiting state due to the following conditions:
- A requires a non-sharable resource of B, and B requires a non-sharable resource of A.
- Both the threads are not willing to give up their resources.
- Both threads are waiting for the other to release the required resources.
This situation is an example of a deadlock in Java.
Deadlock Example in Java
Let us implement the example discussed above-involving threads T1 and T2 and resources R1 and R2.
Example
Output
Explanation
In the above code snippet, we first declare the strings R1 and R2 as resources. In the main method, we create two threads, T1 and T2. In thread T1, we create a run method to lock the resource R1 using the synchronized method. Similarly, in thread T2, we lock the resource R2.
Inside the synchronization block of thread T1, we request the resource R2, which is locked by the thread T2. In the synchronization block of thread T2, we request the resource R1, which is locked by the thread T1. Now, we are starting both threads. We can observe that both threads could not execute completely. Hence, the program will run for an infinite time.
Note:
The synchronized keyword makes a class or method thread-safe, meaning that only one thread can hold the method's lock and use it; all other threads must wait until the lock releases before attempting to acquire it.
Conditions for Deadlock
There are four necessary conditions for deadlock in Java.
Mutual Exclusion
One of the essential conditions of deadlock is mutual exclusion. Here, all the resources that are shared with their respective threads must be non-shareable with other threads when a particular thread accesses them. In other words, resources can be shared with only one thread at a time.
Hold and Wait
As we know, in a deadlock situation, two or more threads lock a resource and request another resource; this is what the hold and wait condition is. In simple words, a particular thread holds a non-shareable resource and requests another non-shareable resource.
No Preemption
Under no preemption condition, a thread can voluntarily release its resources with no fixed schedule.
Deadlock arises because a process can not be stopped once it starts. However, if we take the resource away from the process causing deadlock, we can prevent deadlock. But, this is not a good approach since if we take a resource away which is being used by the process, then all the work it has done till now can be lost.
Circular Wait
Let us understand this condition by an example. Consider four threads: T1, T2, T3, and T4. Each thread holds a non-shareable resource R1, R2, R3, R4, respectively. Now thread T1 is requesting for a resource R2; similarly, T2 is requesting for R3, T3 for R4, and T4 for R1. In the above situation, every thread is in a wait state, and all the threads and resources form a circular structure, where each thread locks a particular resource and requests another resource. So, the above state of all the threads is known as circular wait. The image below represents the situation.
How to Detect a Deadlock in Java?
Detecting deadlocks is a very difficult process, and analyzing all the locks and resources is burdensome. However, we can detect deadlocks using terminal commands. For the above-taken example, let us try to detect deadlocks.
Step 1:
Compile and run the code we implemented while illustrating deadlock and check the output. (Running the above code will give the following output)
Step 2:
Our program will be associated with a PID(Process Identifier). The following code will get the PIDs of all the processes running on your local machine. Make sure that you run the following command on the new terminal.
Step 3:
Now, we will see the deadlocks in our code using the jcmd command. In step two, we can see that our program is running under PID number 5728. Type the following in the terminal, and you will get all the deadlocks in your program.
Explanation
The output of the above command will be extremely large. However, the important point that concerns us is the last few paragraphs, which give us information about the number of deadlocks and the names of the threads involved in the deadlock.
How to Avoid Deadlock in Java?
Deadlock cannot be completely removed, but we can reduce the possibility of deadlock. Below are some methods that will help us to reduce the deadlock situations.
Avoid Nested Locks
One of the most important reasons for deadlock is nested locks. Try not to give locks to the multiple threads, leading to a deadlock situation. If a thread already has a lock try not to give another nested lock.
Avoid Unnecessary Locks
Use locks on those members who are needed to be locked. Unnecessarily applying locks can also lead to a deadlock situation.
Using Thread Joins
The basic condition of deadlock is to put one thread on a wait state until the other thread finishes its task, which in turn is waiting for the first thread to release some resources. Threads in Java provide an essential method called join() that allows one thread to wait until another thread finishes its execution. The Thread.join() method takes a parameter that denotes the maximum time the execution will take place.
Conclusion
- Threads waiting for each other to terminate is a deadlock situation.
- It is the situation that occurs when we use multiple threads in our program.
- Deadlock results in no progress of the threads involved in a deadlock situation.
- Threads are in a wait state for an infinite amount of time.
- There are four necessary conditions for a deadlock to happen: Mutual Exclusion, Hold and Wait, No preemption, and Circular Wait.
- Avoiding nested and unnecessary locks and thread joins will help in avoiding the deadlock situation.