A deadlock in an operating system occurs when a set of processes are blocked indefinitely because they are each waiting for another process in the set to release a resource, causing a circular dependency. In other words, each process in a deadlock is holding a resource and waiting for another resource held by another process, and no process can proceed.
Deadlocks are a serious problem in multi-processing and multi-threading environments, especially in systems that involve shared resources. If a system enters a deadlock state, it can lead to a halt in system execution or a significant degradation of performance.
Deadlocks can occur if all of the following four conditions, known as the Coffman conditions, are met simultaneously:
These four conditions together create a situation where processes cannot make progress, resulting in a deadlock.
Consider a system with two resources, Resource 1 and Resource 2, and two processes, Process A and Process B:
Now, Process A is waiting for Resource 2 to be released by Process B, and Process B is waiting for Resource 1 to be released by Process A. Since neither process can proceed and both are waiting for each other, a deadlock has occurred.
Operating systems use different strategies to deal with deadlocks: prevention, avoidance, and detection.
Deadlock prevention aims to eliminate one or more of the Coffman conditions to prevent deadlock from occurring in the system.
Breaking Mutual Exclusion: This is difficult because some resources, such as printers or files, inherently need to be used exclusively. Thus, this condition is typically left intact.
Breaking Hold and Wait: To prevent hold and wait, a process must either request all of the resources it needs at once (before execution starts) or release all its resources before requesting any new resources. This could lead to inefficiencies, as processes might be forced to wait for resources that they do not need immediately.
Breaking No Preemption: Allow preemption of resources. If a process holding some resources is waiting for other resources, the system can preempt the resources it holds and allocate them to other processes.
Breaking Circular Wait: This can be avoided by enforcing a strict ordering of resource requests. Each resource is assigned a unique number, and processes are required to request resources in an increasing order of their numbers.
Deadlock avoidance requires the system to make decisions about whether to grant a resource request based on the current state of resource allocation.
A famous approach for deadlock avoidance is the Banker's Algorithm, which is used to decide whether resource allocation will lead to a safe state (where no deadlock will occur). The system checks if granting a resource request would keep the system in a "safe" state, where all processes can eventually finish execution.
To determine whether the system is in a safe state, the Banker's algorithm evaluates each resource request by considering whether it can be satisfied while ensuring the system remains in a safe state. If granting the request would lead to an unsafe state, the request is denied.
Deadlock detection allows deadlocks to occur but actively looks for signs of deadlock in the system, then recovers from them. The system must periodically check the state of resource allocation to identify deadlocks.
Example of wait-for graph:
If Process A is waiting for Process B to release a resource, and Process B is waiting for Process A to release a resource, a cycle forms in the graph, indicating deadlock.
Detection Algorithms: These algorithms check the resource allocation graph for cycles. If a cycle is found, a deadlock has occurred. For example, the Banker's algorithm for deadlock detection can be used to examine whether it’s possible to allocate resources in a way that all processes can eventually complete.
Recovery from Deadlock: Once a deadlock is detected, the system must recover. Recovery strategies include:
Once a deadlock is detected, the operating system needs to choose one of the following strategies for resolution:
Process Termination: Kill one or more processes involved in the deadlock. The process can be chosen in several ways:
Resource Preemption: Take resources away from one or more processes involved in the deadlock. This can be tricky because it may require rolling back processes to a safe state, and could potentially create starvation if the preempted process is repeatedly unable to get resources.
Consider a system with three resources (A, B, C) and four processes (P1, P2, P3, P4):
The resource allocation graph would show a cycle between P1 → P2 → P3 → P1. This cycle indicates a deadlock, as each process in the cycle is waiting for a resource that is held by another process in the cycle.
Deadlocks are a critical issue in operating systems that can halt system execution or cause significant delays. To handle deadlocks, operating systems use strategies like deadlock prevention, deadlock avoidance, and deadlock detection. Deadlock prevention eliminates one of the necessary conditions for deadlock, deadlock avoidance ensures the system stays in a safe state, and deadlock detection periodically checks for deadlocks and attempts to recover from them. Effective deadlock management is crucial for maintaining the performance and reliability of a system.
Open this section to load past papers