What is a deadlock?

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 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.