Deadlock is when two or more processes wait for the state to do their tasks, but none of them can do so. It is a very common problem that one can see in multiprocessing systems and distributed systems.
In Java, deadlock is a concept in multithreading where one thread locks the object required by the second thread and the second thread locks the object required by the first thread. In this situation, none of the two threads will be able to process themselves, and a deadlock is created.
For example, if a thread A has locked object A, all the other threads that want to acquire object A will get blocked.
Or, if thread A wants the lock of object B, acquired by thread B, there will be a clash between these two threads.
In both conditions, a deadlock will be created.
Conditions for Deadlock
The conditions required to form a deadlock are called "Coffman conditions", given in 1971. These conditions are sufficient to create a deadlock.
A mutual exclusion means that the resource should be non-shareable. One resource should be used by only one of the processes at a time, and no other process can access that resource.
When a process demands-resources allocated to other processes, mutual exclusion arises, and deadlock occurs.
In Java, there is mutual exclusion between the threads. This means that in multithreading, only one thread will execute itself, and at that time, other threads will get stopped.
In case of mutual exclusion between the threads, the resource acquired by the threads becomes non-shareable. Suppose if a thread A is holding a resource, and another thread B comes out and asks for the same resource acquired by the thread A; then, in this case, the resource acquired by the thread A is non-shareable, and hence thread B needs to wait for its turn which can make the completer execution time large. And this can also turn into a deadlock situation if thread A is also waiting for the resource acquired by thread B.
Preemption means switching or sharing resources between processes. No preemption means that if a process is holding one or more resources, then it will not release those resources in any case until and unless it completes its task.
In Java, when one thread is created, and resources are assigned, it doesn't release its resource until its complete execution. When another thread starts executing itself and demands the resources acquired by the first thread, it needs to wait for that thread to complete its execution first. In case, if that another thread waiting for the resource is acquired by the first thread, and similarly, if the first thread is waiting for the resource acquired by another thread, then in this case, both the thread needs to wait for each other and hence a deadlock will be created.
Hold and Wait
Hold and Wait is a situation where one process holds a resource required by another process, and another is holding the resource required by the first process. It can be said that they are holding each other resources and are not ready to release their resources.
In Java, during multithreading, threads are given access to resources. When other threads require the resources from another thread, this makes a clash of resources between the threads, creating a state of deadlock between the threads.
It can be defined as a state of processes, circularly demanding each other resources.
Let's understand it with the help of a table.
|Process||Resource Occupied||Required Resource|
Here we can see that process P1 has an R1 resource, and it requires an R2 resource occupied by the P2 process. Process P2 has an R2 resource, and it requires an R3 resource occupied by the P3 process. Similarly, process P3 has an R3 resource, and it requires an R1 resource occupied by the P1 resource.
So here, we can see a circular loop of resource requirements by three processes. This is called the circular wait.
In the multithreading of threads in Java, there is the same situation with the threads and their resource. In multithreading, a thread gets some resource at the very beginning, and then after that, other threads also request the same resources, which create a deadlock situation for the threads.
Debugging of Deadlock
Debugging a deadlock is not easy because of two reasons.
- In general, it rarely occurs when the two threads time-slice in just the right way.
- It may involve more than two threads and two synchronized objects.
Handling a Deadlock
There are different ways to handle a deadlock. But, the common approach to handling any deadlock is to prevent the conditions from forming a deadlock.
Ignoring a Deadlock
As the name gives the idea, we ignore the deadlock. Deadlock can be ignored if and only if the time between two deadlocks is very large and the data loss between two deadlocks is intolerable.
Detecting a Deadlock
In multiprocessing systems and distributed systems, deadlocks are inevitable. So deadlocks are detected and then resolved with the help of algorithms. The system's state is continuously monitored by an algorithm that takes care of deadlocks. When a deadlock occurs, it restarts some processes based on the system activity. It reallocates resources with the help of a resource scheduler to them to remove the detected deadlock.
Preventing a Deadlock
Preventing a deadlock means preventing any of the four conditions required to form a deadlock.
- To remove a mutual exclusion, we have to ensure that no process has complete access to the resource. In this case, one resource can be shared or switched among multiple processes simultaneously. This is required to prevent the occurrence of deadlock by removing mutual exclusion. But even after removing the mutual exclusion, deadlock can occur.
- Preemption is a term that is difficult to avoid in multiprocessing and distributed systems. Processes must hold the resources for a certain period to perform their task.
If a process is holding a resource and performing some task with the help of that resource, and meanwhile, another process requests for the same resource. If the process releases the resource, its processing will get interrupted, and if it does not release its resource, the other process has to wait for its turn.
Avoiding a Deadlock
At first, avoiding a deadlock can sound like ignoring or preventing a deadlock. But it is much different than these two.
In avoiding a deadlock, we give the Operating system prior information about the resource requirements by the resources running in the system. Each request by the process is analyzed carefully before assigning a resource to the process so that it would not cause a deadlock in any situation.
Avoiding a deadlock uses a different algorithm that checks for the possibility of a deadlock occurring if a resource is allocated to a process.
Correcting a Deadlock
If a deadlock is detected, it can be corrected using two methods.
Terminating a process
Process termination has two ways to correct the deadlock when a deadlock is detected. Terminating a process means aborting a process. We can abort all the running processes in the system and then restart them, but the main problem is that the time and processed data by the process will be wasted.
Another way, rather than terminating all the resources, is by terminating the resources one by one until the deadlock is corrected. But the main problem with this way is that we have to check whether the system is still in deadlock or not every time a process is terminated, making it a complex time way.
Preemption of resource
As we know that preemption means not sharing the resources among the other processes. But while in deadlock, we take the resource from the processes and continuously allocate them to other resources until the deadlock is broken.