What is a deadlock?

Question

When writing multi-threaded applications, one of the most common problems experienced are deadlocks.

My questions to the community are:

1. What is a deadlock?

2. How do you detect them?

3. Do you handle them?

4. And finally, how do you prevent them from occurring?

Solution 1

A lock occurs when multiple processes try to access the same resource at the same time.

One process loses out and must wait for the other to finish.

A deadlock occurs when the waiting process is still holding on to another resource that the first needs before it can finish.

So, an example:

Resource A and resource B are used by process X and process Y

• X starts to use A.
• X and Y try to start using B
• Y 'wins' and gets B first
• now Y needs to use A
• A is locked by X, which is waiting for Y

The best way to avoid deadlocks is to avoid having processes cross over in this way. Reduce the need to lock anything as much as you can.

In databases avoid making lots of changes to different tables in a single transaction, avoid triggers and switch to optimistic/dirty/nolock reads as much as possible.

Solution 2

Let me explain a real world (not actually real) example for a deadlock situation from the crime movies. Imagine a criminal holds an hostage and against that, a cop also holds an hostage who is a friend of the criminal. In this case, criminal is not going to let the hostage go if cop won't let his friend to let go. Also the cop is not going to let the friend of criminal let go, unless the criminal releases the hostage. This is an endless untrustworthy situation, because both sides are insisting the first step from each other.

Criminal & Cop Scene

So simply, when two threads needs two different resources and each of them has the lock of the resource that the other need, it is a deadlock.

Another High Level Explanation of Deadlock : Broken Hearts

You are dating with a girl and one day after an argument, both sides are heart-broken to each other and waiting for an I-am-sorry-and-I-missed-you call. In this situation, both sides want to communicate each other if and only if one of them receives an I-am-sorry call from the other. Because that neither of each is going to start communication and waiting in a passive state, both will wait for the other to start communication which ends up in a deadlock situation.

Solution 3

Deadlocks will only occur when you have two or more locks that can be aquired at the same time and they are grabbed in different order.

Ways to avoid having deadlocks are:

• avoid having locks (if possible),
• avoid having more than one lock
• always take the locks in the same order.

Solution 4

To define deadlock, first I would define process.

Process : As we know process is nothing but a program in execution.

Resource : To execute a program process needs some resources. Resource categories may include memory, printers, CPUs, open files, tape drives, CD-ROMS, etc.

Deadlock : Deadlock is a situation or condition when two or more processes are holding some resources and trying to acquire some more resources, and they can not release the resources until they finish there execution.

Deadlock condition or situation

In the above diagram there are two process P1 and p2 and there are two resources R1 and R2.

Resource R1 is allocated to process P1 and resource R2 is allocated to process p2. To complete execution of process P1 needs resource R2, so P1 request for R2, but R2 is already allocated to P2.

In the same way Process P2 to complete its execution needs R1, but R1 is already allocated to P1.

both the processes can not release their resource until and unless they complete their execution. So both are waiting for another resources and they will wait forever. So this is a DEADLOCK Condition.

In order for deadlock to occur, four conditions must be true.

1. Mutual exclusion - Each resource is either currently allocated to exactly one process or it is available. (Two processes cannot simultaneously control the same resource or be in their critical section).
2. Hold and Wait - processes currently holding resources can request new resources.
3. No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.
4. Circular wait - Each process is waiting to obtain a resource which is held by another process.

and all these condition are satisfied in above diagram.

Solution 5

A deadlock happens when a thread is waiting for something that never occurs.

Typically, it happens when a thread is waiting on a mutex or semaphore that was never released by the previous owner.

It also frequently happens when you have a situation involving two threads and two locks like this:

Thread 1               Thread 2

Lock1->Lock();         Lock2->Lock();
WaitForLock2();        WaitForLock1();   <-- Oops!

You generally detect them because things that you expect to happen never do, or the application hangs entirely.

View more solutions

Comments

[Voicu]

You first, my dear.

[Keith]

I'm using process here as a generalisation, not specifically an OS Process. These could be threads, but could also be completely different applications, or database connections. The pattern is the same.

[Qiang Xu]

The 3rd point to prevent a deadlock (always take the locks in the same order) is vital, which is rather easy to be forgotten in coding practice.

[user207421]

A deadlock happens when a thread is waiting for something that cannot occur.

[user207421]

This describes a lock, not a deadlock.

[Hai Nguyen]

I vote up to you. Your answer is more concise then above because they make confuse deadlock happen by process or thread. Some one say process, some one say thread :)

[rickyProgrammer]

Hi, given this scenario: Thread A locks resource A and having a long process. Thread B waiting to lock resource A. CPU time usage : 20%, can you consider that a deadlock situation?

[Keith]

@rickyProgrammer no, that's just a regular lock wait, though the difference is a little academic. B waiting on slow A is a lock, B waiting for A waiting for B is a deadlock.

[rickyProgrammer]

So deadlock is more of two processes with locked resources waiting for those resources to be released..

[Keith]

@rickyProgrammer it's a lock that won't become free, no matter how long you wait, because of the circular queue.

[rickyProgrammer]

@Keith wow i got that, so i tried to rephrase the given scenario, making it a deadlock situation: Thread A locks resource A and waiting to lock resource B. Thread B locks resource B and waiting to lock resource A. i believe this now is a deadlock?

[Lealo]

Why would the be two proccesses that depend on eachother and have independant access to shared resources? Your example helped me understand what a deadlock was but the example seem kind of surreal. Maybe these deadlocks maunly occures when working on large applications and database interactions mainly, or when there is a large staff not in sync, and with poor knowledge of the already extistant processes?

[Keith]

@Lealo they aren't dependent on each other - they might be unrelated or copies of the same thing. In the answer I'm trying to be abstract, but they can occur even in fairly simple looking systems. The only criteria is multiple shared resources - I've even seen competing PhD students deadlocked by extremely rare books, and deadlocks can occur in traffic all the time. The bigger and more complex your system then the more they can occur. Basically: be extremely careful whenever you lock any kind of resource, and avoid locking multiple resources at once as much as you can.

[Lealo]

My mistake about the processes being dependant. From a object orientated and a event driven programming perspective - How can I end up having shared resources and even "multiple shared resources"?

[Keith]

@Lealo depends what you're doing, but files, network sockets, databases, any external resource can be a deadlock issue. If you want to send data to something (write to a file, update a table, etc) you often need to lock it first, or lock it while you're doing it. If your app has no shared, lockable/writable resources then you probably don't have to worry about it.

[Lealo]

You could have one class that does all the external data handling. I usally have a class that does serializing in my programs - but the reason for that is that I have wanted to avoid retyping when I knew I would need the functionality a lot of times anyway. However that also results in that I can easily manage any risk of deadlocking when doing file handling. I assume I could simply declare the methods in that "synchronized". The fact Threads need same data (thus getting it twice) is just bad programming in my opinion. I have no experience of sockets, and not very much of databases.

[Keith]

@Lealo yes, you can route everything through one queue - that's one way to minimise deadlocks, but it's also a bottleneck. If you don't have any parallelism then no deadlocks either, but as the average phone had multiple processors that isn't a common use case. Not sure what you're on about with "Threads need same data" bit, but in any case of parallelism (threads, processes, machines) you'll need to share some data between them somehow, either with copying or pointers, and the comparison between those use cases is far too big for these comments.

[Lealo]

I am talking out of a java program developing perspective, and I don't see any reason why I would get into deadlock situations. If a thread X, wants : A and B. Y wants A and B. I would have a C data package, containg (A and B), and I would only use one Thread to get it, Thread Z. There is no use of getting the data other than that. Thread X and Y should be of different functionality - thus suggesting they need different data aswell. If you must have the data in A:s and B: seperate that must be beacuse you have third thread only taking in A:s and B.s. Restructure your objects.

[Keith]

@Lealo sorry, are you trying to tell me how you avoid deadlocks? That's great, but it's not really what this answer is about - here I'm just trying to help the OP define what a deadlock is. If you want to discuss your strategies to avoid them in Java then maybe that should be its own question? Deadlocks are easy to avoid if you are aware of them and design for the problem, mostly they happen because something was missed - something to be aware of during design and something to look for in bugs. Once you know that a deadlock is happening they're usually fairly trival to actually fix.

[Lealo]

No I was just trying to understand your example and learn something from it (and the conceptual problem of deadlocks). Thank you for your time and effort of this answer.

[lordvcs]

Shoudnt the threads belong to different processes?, can threads belonging to the same process also cause a deadlock?

[Sam Malayek]

@diabolicfreak It doesn't matter if the threads belong to the same process or not.

[LoBo]

Another example from real life could be four cars coming to the crossing of two equal roads in four directions simultaneously. Every one needs to give a way to a car from the right-hand side, so no one can proceed.

[Soup Endless]

Those real life examples are very desriptive and also fun.

[Johan Råde]

Another "real life" example: The dining philosophers