What is a deadlock?

Question

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.

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.

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.

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.

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.

You can take a look at this wonderful articles, under section Deadlock. It is in C# but the idea is still the same for other platform. I quote here for easy reading

A deadlock happens when two threads each wait for a resource held by the other, so neither can proceed. The easiest way to illustrate this is with two locks:

object locker1 = new object();
object locker2 = new object();

new Thread (() => {
                    lock (locker1)
                    {
                      Thread.Sleep (1000);
                      lock (locker2);      // Deadlock
                    }
                  }).Start();
lock (locker2)
{
  Thread.Sleep (1000);
  lock (locker1);                          // Deadlock
}

Deadlock is a common problem in multiprocessing/multiprogramming problems in OS. Say there are two processes P1, P2 and two globally shareable resource R1, R2 and in critical section both resources need to be accessed

Initially, the OS assigns R1 to process P1 and R2 to process P2. As both processes are running concurrently they may start executing their code but the PROBLEM arises when a process hits the critical section. So process R1 will wait for process P2 to release R2 and vice versa... So they will wait for forever (DEADLOCK CONDITION).

A small ANALOGY...

Your Mother(OS),
You(P1),
Your brother(P2),
Apple(R1),
Knife(R2),
critical section(cutting apple with knife).

Your mother gives you the apple and the knife to your brother in the beginning.
Both are happy and playing(Executing their codes).
Anyone of you wants to cut the apple(critical section) at some point.
You don't want to give the apple to your brother.
Your brother doesn't want to give the knife to you.
So both of you are going to wait for a long very long time :)