Deadlock is a situation in an operating system where a set of processes become stuck because each process in the set is waiting for another process to release resources. This leads to a cascade of dependencies where nothing can really progress, thus halting everything.
A deadlock can only occur when the following four conditions are met simultaneously:
1. Mutual Exclusion: At least one resource must be held in a non-sharable mode, and only one process can use the resource at a time.
2. Hold and Wait: A process holding at least one resource is waiting to acquire additional resources that are currently held by other processes.
3. No Preemption: Resources cannot be preempted from the process holding them; they can only be released voluntarily by the process.
4. Circular Wait: There is a set of processes such that each process in the chain is waiting for another which is ahead, forming a circle.
Example Scenario:
Suppose there are two processes and two resources. P1 process requests R1, and P2 requests R1 & holds R2. Neither process will release the resources it currently holds, and neither can proceed until it is able to acquire a resource that both processes are waiting on for completion. Therefore, both stall simultaneously, giving rise to deadlock.
Operating systems employ various strategies to prevent or avoid deadlock:
- Deadlock Prevention: This is a set of methods for ensuring that at least one of the necessary conditions cannot hold. It can be done by requiring all processes to ask for resources at once or by preventing circular wait, etc.
- Deadlock Avoidance: It employs algorithms like the Banker’s Algorithm, which dynamically check the state of resource allocation to make sure a system will never enter an unsafe state where deadlock can happen.
Some systems may allow deadlocks to occur but have standby algorithms in place for detection and recovery, such as terminating one or more processes involved to free up resources.