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 fights. One has a remote control, 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 p1 and p2 and two resources r1 and r2. It contains resource r1 that is allocated with process p1 and resource r2 that is allocated with process p2. But resource r2 is required to complete the process so it requests r2, but r2 is already allocated with p2.
Similarly, process p2 requires r1 to complete its execution, but r1 is already allocated with p1.
Both p1 and p2 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 that cannot be shared between processes.
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 that is held by another process.
Deadlock avoidance and prevention
As we have already read what the deadlock is and the conditions for the deadlock to happen have also been read. So today in this post, we will read about prevention and prevention of deadlock, so let’s start.
Deadlock prevention: –
The conditions of deadlock that we can prevent 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.
1: – Mutual exclusion: – If we can share resources, then we can prevent mutual exclusion.
If we have non-sharable resources that cannot be shared, then, in that case, we cannot prevent mutual exclusion from happening.
For example, a 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 for the 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 the 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 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.
As we have read that the algorithms of deadlock prevention are not good, which reduces resource utilization and system throughput. But we can avoid deadlock.
The deadlock avoidance algorithm ensures that processes 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 the 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