Interviewer: What are deadlocks? How will you detect and avoid them?

In the digital world, where traffic over the services is very high, engineers often face problems with handling concurrency in a system. Deadlock plays an important role in the discussions whenever devs talk about concurrency issues.

So, what is a deadlock?

Deadlock is a condition that occurs when multiple concurrent processes hold resources and wait for each other to release them, forming a circular dependency.

As you can see in the image below, R1 is acquired by P1, R2 is acquired by P2, and R3 is acquired by P3. And P1 is requesting R2, P2 is requesting R3, and P3 is requesting R1, forming a circular dependency.

Deadlock Detection

We know what a deadlock is, but how can one detect it in the application?

There are some common tools, like JStack and ThreadMXBean in Java, using which deadlock can be detected.

JStack: Jstack can be used to print the Java stack trace of threads for a specific process. Analysing the stack trace can help in the detection of a deadlock. Here is the sample stack trace for deadlock detection:

Found one Java-level deadlock:
=============================
"TP-Processor10":
  waiting for ownable synchronizer 0x00002aaaf58q55f0, (a java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync),
  which is held by "indexTrackerThread1"
"indexTrackerThread1":
  waiting for ownable synchronizer 0x00002aaaf4245580, (a java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync),
  which is held by "TP-Processor1"
"TP-Processor1":
  waiting for ownable synchronizer 0x00002aaaf58e70f0, (a java.util.concurrent.locks.ReentrantReadWriteLock$NonfairSync),
  which is held by "indexTrackerThread1"

ThreadMXBean: ThreadMXBean is an interface for managing Java threads of the JVM. This interface exposes a function findMonitorDeadlockedThreads which returns the threadIds which are under deadlock condition. We can further get the details of the threads and get to the actual reason.

ThreadMXBean threadMXBean = ManagementFactory.getThreadMXBean();
long[] ids = threadMXBean.findDeadlockedThreads();

Deadlock Prevention

Now, can you think of how to avoid the deadlock?

Before jumping to the prevention strategy, let's understand in which conditions deadlock occurs.

Coffman Conditions

If the application satisfies these four conditions (popularly known as the Coffman condition), then it can undergo a deadlock state.

1. Mutual Exclusion: A resource cannot be shared among other processes.
2. No preemption: A resource cannot be taken away from the process forcefully.
3. Hold & Wait: A process holds a resource while waiting to acquire the resource held by another process.
4. Circular wait: A circular dependency where multiple concurrent processes wait for the next process to release the resource.

If you are thinking that if any of the four conditions hold false, then we can avoid the deadlock state, then you are thinking in the right direction.

Let's discuss in detail how one can make either of the four conditions false and prevent the application from deadlocking.

Mutual Exclusion

This means a resource cannot be shared among multiple processes concurrently. To make this condition false, we have to make our resource shared among multiple processes. But we cannot make this blindly, as this is very crucial for maintaining consistency within the application.

We can analyze the requirement of the resource and mindfully make it shareable. A few examples are:

a. Check if the resources are immutable; then there's no need to lock them while processing.

b. Use ConcurrentHashMap for key-value pairs; this will lock the key instead of locking the complete map, making it shareable among other processes.

c. Functional Design and Actor Model: By avoiding the shared mutual resources.

These are some ways that, if used properly, can help in achieving no mutual exclusion eventually helps in avoiding deadlock.

No preemption

When a process holds a resource, the resource cannot be taken away from it unless the process releases it voluntarily.

So, how to make a process preemptive?

Simple, if we define the time for which a process can hold the resources, then the process will voluntarily release the resource in case of threshold breach, and the resource will be used by another process waiting for it, which eventually prevents the deadlock condition.

In the above image, you can see. Process 1 releases the resource R1, which results in process 2 proceeding further and eventually process 3.

This is how deadlock can be avoided.

No Hold & Wait

This means that the process holds the resource when required which can cause a deadlock when a resource required in between processing and it is acquired by other process.

To avoid this, the process should hold all the necessary resources at the beginning of the process and release them at the end of it.

This will ensure that the resource will be available throughout the processing but in this case resource is not utilised properly, which can cause delays in other processes.

Circular wait

Circular wait means that when multiple processes acquire the resources that other processes are looking to complete their processing, they form a circular dependency.

To avoid this, we can assign a global ordering to all resources and ensure that each process requests them in a strictly increasing order.

These are some ways using which deadlock conditions can be prevented.

Conclusion

In this article, we discussed what a deadlock is, how to detect it, and how to prevent it. I hope this article will help you in preventing deadlock in your next application.

If you found this helpful, please clap, share, and follow me for more insights on tech and distributed systems!