A deadlock is a situation in computing where two or more processes or threads are unable to proceed because each is waiting for the other to release a resource. For example: if there are two processes, Process 1 and Process 2 and two resources, resource 1 and resource 2 . To complete a certain task both processor need both resources. Suppose if process 1 acquires resource 1 and process 2 acquires resource 2, after that process 1 requires resource 2 and tries to acquire resource 2 but it is held by process 2 so process 1 has to wait similarly process 2 has to wait for acquiring resource1 which is held by process 1.
Conditions for Deadlock
a) Mutual Exclusion: This means that at least one resource must be used by only one process at a time.
b) Hold and Wait: This means that a process is holding at least one resource while simultaneously requesting additional resources that are currently held by other processes.
c) No Preemption: This means that resources cannot be forcibly taken away from a process and should be released voluntarily by the process.
d) Circular Wait: This occurs when there is a circular chain of two or more processes, each waiting for a resource held by the next process in the chain.
Deadlock Prevention :
Deadlock prevention aims to eliminate at least one of the four necessary conditions for deadlock ,mutual Exclusion ,Hold and Wait ,No Preemption and Circular Wait.
- For eliminating mutual exclusion : using shareable resouces like read-only files
- For Eliminate Hold and Wait: Require all resource requests at the starting of execution or release all resources before new requests.
- For Allowing Preemption: The system can force a process to release resources if needed by another process.
- For Eliminate Circular Wait: Total ordering of resource types should be imposed.
Deadlock avoidance:
Deadlock avoidance refers to strategies used to prevent deadlocks from occurring.
- Resource Allocation State: The system constantly monitors the resource allocation state, which includes the available resources, allocated resources, and maximum needs of processes.
- Safe State: The system ensures it always remains in a safe state, where there's at least one sequence in which all processes can complete without causing a deadlock.
- Resource Request Analysis: Before granting any resource request, the system analyzes whether doing so would lead to a safe state or not.
- Advance Information: The system requires advance knowledge about the maximum number of resources each process might request during its lifetime.
Deadlock Detection:
Deadlock detection is a method where the system allows deadlocks to occur but has mechanisms in place to identify when they have happened.
Detection methods:
- Resource Allocation Graph : It is a visual representation that uses vertices for processes and resources, with edges indicating requests and assignments.
- Wait-For Graph: This simplifies the concept by focusing solely on processes, where edges represent one process waiting for a resource held by another.
- State Detection Algorithm: The state detection Algorithm , sometimes adapted from the Banker's Algorithm, takes a different approach by checking if the system is in a safe state. It calculates available resources, simulates allocations, and determines if all processes can complete without causing a deadlock.
