Subject: Data Structures

Topic: Synchronization

Difficulty: Medium

Solution:

What is Deadlock?

• It is a situation where a set of processes are blocked because each process is holding a resource, and waiting for another resource acquired by some other process, It's also known as deadlock.

• Example, We have two processes P1 and P2. Now, process P1 is holding the resource R1 and is waiting for the resource R2. At the same time, the process P2 is having the resource R2 and is waiting for the resource R1. So, the process P1 is waiting for process P2 to release its resource and at the same time, the process P2 is waiting for process P1 to release its resource.
• This leads to perform infinite waiting and no work is done here.

Necessary Conditions for Deadlock:

• There are four different conditions that for Deadlock.

• 1) Mutual Exclusion.

• 2) Circular Wait.

• 3) Hold and Wait.

• 4) No preemption.

1) Mutual Exclusion:

• Mutual exclusion is a resource can be held by only one process at a given time.

• In this fig., if a process P1 is using some resource R at a particular instant of time, then some other process P2 can't hold or use the same resource R at that time.

• The process P2 can make a request for that resource R, but it can't use that resource simultaneously with process P1.

2) Circular Wait:

• When the first process is waiting for the resource held by the second process, the second process is waiting for the resource held by the third process, it's also known as circular wait condition.

• The last process is waiting for the resource held by the first process. So, every process is waiting for each other to release the resource and no one is releasing their own resource. Everyone is waiting here for getting the resource.

3) Hold and Wait:

• This process is currently holding at least one resource and requesting additional resources which are being held by other processes.

• Example, a process P1 can hold two resources R1 and R2 and at the same time, it can request some resource R3 that is currently held by process P2.

4) No preemption:

• Resources cannot be removed from the processes are used to completion or released voluntarily by the process holding it.

• This process P1 is using some resource R, then some other process P2 can't forcefully take that resource. so, then what's the need for various scheduling algorithm. The process P2 can request for the resource R and can wait for that resource to be freed by the process P1.