Deadlock in os

DEADLOCK

• what is deadlock ?

• Deadlock is a situation in which two computer processes share only one resource, due to which no process can access the resource.

That is, a deadlock is a condition in which two or more processes fight  for only one resource, due to which no one is able to access the resource.

• For example, suppose there are two friends and both want to play computer games, due to which both fight. One has a remote control and the other has a cd of games.

 Due to which neither of the two friends are able to play but neither of them is ready to cooperate. This condition is called deadlock.

According to the picture we have two processes A and B and two resources r1 and r2. It contains resource r1 that is allocated with process A, and resource r2 that is allocated with process B. But resource r2 is required to complete the process so it requests r2, but r2 is already allocated with B.
Similarly process B requires r1 to complete its execution, but r1 is already allocated with A.
Both A and B are always waiting for each other's resources. The same process is called DEADLOCK.

CONDITIONS OF DEADLOCK 

There are four conditions of deadlock which are as follows: -
1: - mutual exclusion
2: - hold & wait
3: - no preemption
4: - circular wait

1: - Mutual exclusion: - In this case, there is one such resource which cannot be shared between processes at a time .

2: - Hold & wait: - In this, processes are holding one resource while waiting for another resource.

3: - No preemption: - A resource that has been allocated for a process cannot be forcibly allocated to another process.

4: - Circular wait: - In this case, each process waits for a resource which is held by another process.

Deadlock avoidance and prevention 

Deadlock prevention: -

• We can prevent the conditions of deadlock to some extent. Mostly we cannot prevent them because our resources are limited. Some resources are sharable and some are non sharable.

     If we can prevent any of these 4 conditions       then there will be no deadlock in the system. deadlock prevention

1: - Mutual exclusion: - If we can share resources, then we can prevent mutual exclusion.

If we have non-sharable resources which cannot be shared, then in that case we cannot prevent mutual exclusion from happening.

For example Printer is a non sharable resource. In this situation, mutual exclusion cannot be prevented.
But if you have a sharable resource, then you can prevent mutual exclusion by sharing it.
Like: - We can share memory.
2: - Hold & wait: - If the resources are allocated to the processes before its execution, then we can prevent the hold & wait condition from happening. But its disadvantage is that it reduces the utilization of the system.

For example, a process requires a printer later. And we allocate it to the printer in advance. So until its execution is finished, this printer will remain blocked and other processes cannot use it in its free time.

And its other disadvantage is that there is starvation in it.

3: - No preemption: - If a process has held resources and is waiting for other resources then all resources are released from that process so that other processes can complete their execution.

But some resources like: - printer, tape drivers cannot be preempted.

4: - Circular wait: - To stop the circular wait, you can allocate resources to the process in increasing order only.

That is, there is a sequence of resources according to which the resources are allocated to the processes.

For example: - If process P2 is allocated R6 resource then next time P2 will not be allocated resources of R5, R4 or below. Only resources above R6 will be allocated to P2.

But its disadvantage is that it reduces the resource utilization very rarely.

Effects of deadlock prevention

The following are the effects of deadlock prevention.

•   This greatly reduces the utilization of the device.

•     This greatly reduces the throughput of  the system.

                            deadlock avoidance 

• As we have read that deadlock prevention algorithms are not good, which reduces resource utilization and system throughput. But we can avoid deadlock.
  

• The deadlock avoidance algorithm ensures that processes will never go into an unsafe state.

• It consists of two states: -

•     Safe state

•     Unsafe state

• safe state: - safe state is the state in which we execute processes in a safe sequence.

In this, the process exists in a safe sequence in such a way that the first process has enough resources to execute. And when the execution is finished, after the release of the resources of this process, there will be enough resources for execution of the next process.

• unsafe state: - If processes are not in a safe sequence then it is in unsafe state and deadlock can occur in unsafe state.

Suppose for example we have 11 tape drivers.

     processes              maximum required          current hold

    P0                              9                      5
    P1                              4                      2
    P2                              8                      2

Our current hold of tape drivers is - 5 + 2 + 2 = 9

We have the remaining tape drivers: 11-9 = 2.

First of all we look at P0, so we cannot execute P0 first because it needs 4 more tape drivers but we only have 2.

Now let's look at P1. P1 needs 2, so we execute it. Now after its execution is complete, it will release 4 tape drivers.
 
Now we will execute P0 because it needs 4 tape drivers, so after its execution it will release 9 tape drivers.

And then we will execute P2, P2 needs 6 and if we have 9 tape drivers then P2 will also be executed.

So our safe sequence will be: -

P1, P0, P2