Deadlock Explained
What is Deadlock ?
A set of processes are said to be in deadlock situation when each process in the set is waiting for an event, that can be caused by another process in the set.
In above example process P1 and P2 are said to be in deadlock situation. Both processes requires R1 and R2 to completes its execution.
Process P1 is having R1 but is waiting for a resource R2, and process P2 is having R2 but is waiting for R1.
Now in this case both processes are waiting for some resource which is already acquired by other process, which is also waiting for some resource to finish its task. This scenario is referred as ‘Deadlock’ in computer science.
Necessary conditions for deadlock
A deadlock can occur if and only if all the following conditions in a system are fulfilled simultaneously. These conditions are called the Coffman conditions.
Mutual exclusion
Each resource can be assigned to only one process at the same time.
Hold and Wait
Process is holding some resource and still waiting for some other resource which is held by other process.
No preemption
No resource can be preempted from process at any time.
Circular wait
Process P1 is waiting for some resource which is held by P2, P2 is waiting for a resource which is held by P3 and so on… Pn is waiting for resource which is held by P1.
Avoidance of Deadlock
To avoid deadlock, any one of four condition should be broken.
Mutual exclusion
To break mutual exclusion, resource should be shared across processes at same time. This is practically not possible, because such resources like printer can’t be accessed at the same time.
Hold and wait
To break hold and wait condition, no process should wait after gaining access to required resource. The best way is to give all resources which are required by process. But then practically resources will not be utilised properly.
No Preemption
To break no-preemption condition, we must ensure that process first release acquired resource before requesting for other resources. OS can have a matrix of process and resource to track the allocated and non-allocated resources.
Circular wait
To break circular wait condition, we must ensure that there is some order either ascending or descending for requesting resources from process which is holding that resource. Let’s take an example of ascending order, P1 can request for resource held by P2, but P2 can’t request for a resource which is held by P1. We should maintain an order.
Prevention of Deadlock
Yes, it is possible to prevent deadlock in a system, before it’s get encountered by OS. It has its own conditions too.
OS must know about the exact resource requirements for process to execute. OS must know about the number of allocated, available and total number of resource in system at any time.
To prevent deadlock, OS first need to find a sequence in which process can request for resource. Sequence could be any (not necessarily in order).
If we take an example of 5 processes named P1, P2, … P5. The sequence to prevent deadlock could be P3, P4, P1, P2, P5 or it could be P2, P1, P5, P3, P4.
This sequence is called safe sequence, because if process request for resources and OS allocate resources to process in this sequence, then deadlock will not occur. To find safe sequence we have Banker’s algorithm. If OS can have safe sequence from this algorithm, then system can be said in safe state.
