Deadlock refers to a situation where multiple processes are waiting indefinitely for an event to occur. It arises when each process holds resources needed by another process, creating a circular dependency.
Deadlock Conditions
Deadlock occurs when four necessary conditions are met:
1. Mutual Exclusion: Resources are allocated exclusively to one process at a time.
2. No Pre-emption: Once a process acquires a resource, it cannot be forcibly taken away.
3. Hold and Wait: Processes hold onto resources while waiting for additional resources.
4. Circular Wait: A circular dependency exists, where each process waits for a resource held by the next process in the sequence.
Deadlock Examples
Bank Account Example:
- Customer requests account opening but must first deposit funds.
- Bank requires deposit before opening account.
- Both parties are waiting for the other's action, leading to a deadlock.
Vehicle Example:
- Two cars approach from opposite directions, each assuming the path is clear.
- Both cars become deadlocked, unable to proceed until one reverses direction
in a defined order to avoid circular dependencies.
Necessary and Sufficient Conditions
The four conditions mentioned above are both necessary and sufficient for deadlock to occur. If any of these conditions are not met, deadlock cannot occur. However, if all four conditions are met, deadlock is inevitable.
Deadlock Handling Methods
- Four important methods are used to handle deadlocks:
1.Deadlock Ignorance
- This method, also known as the Ostrich method, involves ignoring deadlocks.
- This is a widely used strategy, especially in operating systems like Windows and Linux.
- The method is based on the belief that deadlocks occur rarely, and it is more efficient to ignore them and restart the system if they do occur.
- This method does not address the underlying causes of deadlocks and can lead to system instability if deadlocks occur frequently
2. Deadlock Prevention:
. This method aims to prevent deadlocks from occurring in the first place.
- It involves removing or disabling one or more of the necessary conditions for a deadlock to occur.
- By ensuring that at least one of these conditions is not met, deadlocks can be prevented.
- This method requires careful analysis of the system and may involve modifying the way resources are allocated or processes are scheduled.
- It can be more complex and resource-intensive than other methods but provides strong guarantees against deadlocks.
3.Deadlock Avoidance:
•This method involves dynamically checking for potential deadlocks before they occur.
- It uses algorithms to predict the resource needs of processes and avoid allocating resources that could lead to a deadlock.
- Deadlock avoidance requires accurate knowledge of the resource requirements of processes, which can be difficult to obtain in complex systems.
- It can lead to lower system utilization compared to other methods as resources may be held unnecessarily to avoid deadlocks.
4. Deadlock Detection and Recovery:
•This method involves detecting deadlocks when they occur and taking steps to recover the system.
- It uses algorithms to identify processes involved in deadlocks and can involve forcibly terminating processes or preempting resources to break the deadlock.
- Deadlock detection and recovery can be complex and time-consuming.
- It can lead to data loss or system instability if not implemented carefully.
- This method is typically used as a last resort when other prevention or avoidance methods are not feasible or effective.
