Deadlocks In Operating system for Gate CSE

 DeadLocks

A Deadlock is a situation where each of the computer processes waits for a resource which is being assigned to some other process. In this situation, none of the process gets executed since the resource it needs is held by some other process which is also waiting for some other resource to be released.

Example for deadlock:

There are following 4 necessary conditions for the occurrence of deadlock-

1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait
   
   

1. Mutual Exclusion

• There must exist at least one resource in the system which can be used by only one process at a time.
• If there exists no such resource, then deadlock will never occur.
• Printer is an example of a resource that can be used by only one process at a time

2. Hold and wait

• There must exist a process which holds some resource and waits for another resource held by some other process.

3. No preemption

• Once the resource has been allocated to the process, it can not be preempted.
• It means resource can not be snatched forcefully from one process and given to the other process.
• The process must release the resource voluntarily by itself.

4. circular wait

• All the processes must wait for the resource in a cyclic manner where the last process waits for the resource held by the first process.

NOTE

• All these 4 conditions must hold simultaneously for the occurrence of deadlock.
• If any of these conditions fail, then the system can be ensured deadlock free.

Deadlock Handling Strategies

1. Deadlock Prevention
2. Deadlock Avoidance
3. Deadlock Detection and Recovery
4. Deadlock Ignorance

Formulas on Deadlock:

Maximum Number Of Units That Ensures Deadlock-

Maximum number of units of resource R that ensures deadlock

= (x₁-1) + (x₂-1) + (x₃-1) + …. + (x_n-1)

= ( x₁ + x₂ + x₃ + …. + x_n ) – n

= ∑x_i – n

= Sum of max needs of all n processes – n

Minimum Number Of Units That Ensures No Deadlock-

Minimum number of units of resource R that ensures no deadlock

= One more than maximum number of units of resource R that ensures deadlock

= (∑x_i – n) + 1

 

Problems on no. of resources required
1Q. A system is having 3 user processes each requiring 2 units of resource R. The minimum number of units of R such that no deadlock will occur-

 Ans: 4

2Q. A system is having 8 user processes each requiring 3 units of resource R. The minimum number of units of R such that no deadlock will occur _____.

Ans: 17

Problems on no. of processes required

3Q. If there are 6 units of resource R in the system and each process in the system requires 3 units of resource R, then how many processes can be present at maximum so that no deadlock will occur?

Ans: 

• Process P1 holds 2 units of resource R
• Process P2 holds 2 units of resource R
• Process P3 holds 2 units of resource R

 

Therefore,

• Minimum number of processes that ensures deadlock = 3
• Maximum number of processes that ensures no deadlock = 3 – 1 = 2

4Q. If there are 100 units of resource R in the system and each process in the system requires 4 units of resource R, then how many processes can be present at maximum so that no deadlock will occur?

Ans: 

• Process P1 holds 3 units of resource R
• Process P2 holds 3 units of resource R
• Process P3 holds 3 units of resource R and so on.
• Process P33 holds 3 units of resource R
• Process P34 holds 1 unit of resource R

 

Thus,

• Minimum number of processes that ensures deadlock = 34
• Maximum number of processes that ensures no deadlock = 34 – 1 = 33

Next article: Bankers algorithm