Deadlock Prevention and Avoidance | No Mutual Exclusion Condition | Preemption Condition | No Hold and Wait | Deadlock Avoidance
Deadlock prevention ensures that deadlock is excluded from the beginning by invalidate at least one of the four necessary conditions, however deadlock prevention is often impossible to implement.
No Mutual Exclusion Condition
We have to share resources, however it is impossible for practical system. Non-blocking synchronization algorithms can avoid mutual exclusion.
When a process is holding some resources and waiting for another resources that can not be allocated to it, then this process releases all resources so other process can complete their execution. But some resources like printer, tap drivers can not be preempted.
No Hold and Wait
When a process ready to execute and requires some resources then all resources should be allocated at once that means there will not be wait for required resources. But sometime a process can be suffer from starvation and very low resource utilization.
No Circular Wait
To avoid circular wait, processes must request resources in increasing order only. But resource numbering may affects efficiency and a process may have to request a resource before it need.
Deadlock avoidance algorithm ensures that a processes will never enter into unsafe or deadlock. The system requires additional apriori information regarding potential use of each resource for each process that means each process declare the maximum number of resources of each type that it may need, number of available resources, allocated resources, maximum demand of the processes. Processes inform operating system in advance that how many resources they will need.
If we allocated resources in a order such that requirement can be satisfied for each process and deadlock can not be occur then this state is called as safe state. A safe state is not a deadlocked state and not all unsafe states are deadlocked, but an unsafe state deadlock may occur.
Resource allocation graph(RAG) states resources is held by which process and which process is waiting for a resource of a particular type. If resources are single instances type and resource allocation graph has cycle then the system is deadlocked. If resources are multiple instances type and resource allocation graph has cycle then system may have deadlock; and we can recognise deadlock using Banker's algorithm. If RAG does not have any cycle then deadlock never occurred in the system.
Deadlocked system with single instance type resources:
Not deadlock with multiple instances type resources:
Deadlocked system with multiple instances type resources: