Understanding and Handling Deadlock in Operating Systems

In previous reviews, we touched upon deadlock briefly. However, this concept is so crucial that it deserves a focused, in-depth discussion. A Deadlock occurs when two or more threads/processes are mutually waiting for each other to release resources they need. Wikipedia^1 provides an excellent real-life analogy: two people meeting face-to-face in a narrow alley, where neither will back down, and both are waiting for the other to move out of the way.

Observing Deadlock

Resource Allocation Graph

A Resource Allocation Graph (RAG) visualizes the current allocation of resources among processes.

As shown above: we use circles to represent processes, and boxes containing small circles to represent resource types and their quantities (units). An edge from a resource unit to a process indicates that the unit is currently being used by that process. An edge from a process to a resource indicates that the process is requesting that resource. Because resources are finite, a process will enter a blocked state if it cannot obtain the requested resource immediately. For example, in the figure, $R_{1}$ has only one unit of resource, which is currently being used by $P_{1}$. If $P_{2}$ requests resource $R_{1}$, it will enter a blocked state and can only use it after $P_{1}$ releases the resource.

Note: When discussing deadlocks, we assume the code for processes is “correct.” Correctness, in this context, means that no logical errors occur. For example, a process $P$ already using a finite resource would not request that same resource again, causing it to lock itself.

Deadlock and Reusable Resources

A Reusable Resource is a resource where each unit can be requested by different processes over time.

State Transition Diagram

While a Resource Allocation Graph represents resource allocation at a specific moment, another model for representing changes in resource allocation is called State Transitions. We know that operations between processes and resources are essentially of three types:

1. Requesting a resource
2. Using a resource
3. Releasing a resource

Deadlock State vs. Safe State

If a process is in a blocked state in state S, and no subsequent change in state can ever change that condition, then we say the blocked process is deadlocked.

A state containing two or more blocked processes is called a Deadlock State. Conversely, we call it a Safe State.

As shown below, because the resources requested by $P_{2}$ and $P_{3}$ are already occupied, they are both locked. This entire graph represents one configuration in the changing relationship between processes and resources, which we call a State. And because this state contains two blocked processes, we refer to it as a deadlock state.

As shown below, $S_{0}$ is a deadlock state because it contains two blocked processes. By performing a resource release operation, $S_{0}$ can transition to $S_{1}$. In $S_{1}$, a resource use operation can be performed so that $P_{2}$ can use resource $R_{3}$. It can be seen that we resolved the deadlocked processes when transitioning from $S_{0}$ to $S_{2}$. Recalling the definition above: a process is deadlocked only if it remains blocked regardless of how future states change. Therefore, $P_{1}$ in $S_{0}$ was not deadlocked.

By exhausting all possible states, we can observe whether process competition might lead to a deadlock state. Of course, I haven’t drawn them all. The state diagram above doesn’t need to show all details; we only need to know what $S_{0}$ looks like to understand the subsequent states. Therefore, it can also be drawn like this:

Students who have studied automata theory might recognize this as a Deterministic Finite Automaton (DFA), but that’s a side note.

Deadlock Detection

We can use a simplification algorithm to check if a resource allocation graph contains a deadlock:

while (there are non-blocked processes in the graph):
  select a non-blocked process P
  remove P, including all edges requesting resources from P and allocated resources to P

After removing those $P$s, the remaining graph provides information about the deadlock. Remember two theorems:

1. A state S is a deadlock state if and only if this resource graph cannot be fully reduced.
2. For graphs with the same number of processes and resources, fully simplified resource allocation graphs look identical.

Let’s simplify the resource-process graph from the previous example:

First is $P_{1}$. Since $P_{1}$ is in a non-blocked state, we can remove $P_{1}$ and its edges. After $P_{1}$ is removed, $P_{2}$ becomes non-blocked and can also be removed.
If there are processes in a deadlock state in the most simplified resource graph, this graph will not be fully reducible (not all processes can be removed).

Continuous Deadlock Detection

Testing for deadlock can be more efficient if we do it in a continuous manner. Let’s first define a few logical statements:

$I(x)$: State $x$ is a deadlock state.
$P(p, x)$: Process $p$ requesting resource $x$ is currently deadlocked.
$K(p, x)$: Process $P$ executing the request is blocked in state $s$.
$C(x)$: The operation transitioning to state $x$ is a request operation.

Then we present a valid theorem:

$$(¬I(CurrentState) \to I(NextState)) \to (P(Process, NextState) \land C(NextState))$$

Translated:

If the current state S is not in a deadlock state, then its next state S’ is a deadlock only if:

1. The transition to S’ is a request operation.
2. The process P that made the request operation is deadlocked in S’.

The steps for continuous deadlock state detection are as follows:

If the current operation is a request operation and the process making this request is blocked in the next state, then proceed with the state diagram simplification algorithm until:

1. The process is removed from the state diagram, or
2. There are no more blocked processes in the graph.

If $P$ is removed from the state diagram, then S’ is not a deadlock state, and the algorithm is complete. Let’s look at an example:

Now we have such a state transition: $S_{0}$ enters $S_{1}$ through a request operation. At this point, only one process is blocked, so the state is not deadlocked. $S_{1}$ enters $S_{2}$ through a request operation, where two processes are blocked.

According to the algorithm, when we detect a state like $S_{2}$ appearing, we test for continuous deadlock:
Remove $P_{2}$ and its edges, and we find that $P_{1}$ and $P_{3}$ jump out of the deadlock state. Therefore, $S_{2}$ is not a deadlock state.

Deadlock Detection for Single-Unit Resources

A Wait-For Graph is a resource allocation graph containing only processes. Each process in the graph can have multiple occupied resources but only one requested resource.

As shown above, the left is the resource allocation graph, and the right is the corresponding wait-for graph. “Waiting” means that a resource requested by a process is occupied by another process, causing it to enter a blocked state. Furthermore, we have a theorem:

The appearance of a cycle (like $P_{1}$ and $P_{2}$ waiting for each other in the figure) is a necessary and sufficient condition for deadlock.

Dynamic Deadlock Avoidance

Instead of solving deadlock after detecting it, as shown above, we can resolve it before it happens.

Resource Claim Graph

A Maximum Resource Claim refers to all resources a process needs. Resources a process will request in the future can be represented by a dashed edge.

A Resource Claim Graph (RCG) adds new elements to the resource allocation graph, including:

1. Current allocation of resources among processes.
2. Current resource requests and potential resource requests.

The figure below shows a resource claim graph where $P_{1}$ has the potential to request $R_{1}$ and $R_{1}$ in the next state.

Banker’s Algorithm

The Banker’s Algorithm is an algorithm that simulates a bank providing loans. Think about it: bank loans and system resource allocation have similar operations.

Bank	Operating System
Loan	Resource Allocation
Customer Credit	Maximum Resource Claim

The Banker’s Algorithm:

1. In state S, there is a resource request. Assume the resource request is successful.
2. Use the simplification algorithm to simplify the new state S’.
3. If the graph can be fully simplified, then accept this new state; otherwise, refuse the resource allocation and revert to S.

Theorem:

If the state after allocating resources cannot be fully simplified, then refuse that allocation. In this way, the resource claim graph will always remain in a safe state.

Let’s look at the example above. Our Banker’s Algorithm first assumes that $P_{1}$’s request will succeed and enters S’. Since two processes are blocked, we need to use the simplification algorithm to remove $P_{1}$. The remaining $P_{2}$ and $P_{3}$ can be removed sequentially. Therefore, $P_{1}$’s request can be accepted. By this method, we can find all safe states.

Deadlock Prevention

Compared to detecting deadlock at every step, resolving the existence of deadlock from its root can take it up another notch. Let’s think about how deadlock is generated:

1. Hold and Wait: A process holds resource A while waiting for resource B.
2. Circular Wait: Process A holds resource A while waiting for resource B, while Process B holds resource B while waiting for resource A.

If we could force all processes to either wait for resources or use resources, but not both, would this problem be solved?

Solving Hold and Wait

Three methods can solve the Hold and Wait problem.

1. The first method allows a process to perform only one type of operation: either requesting all resources or using all resources. Doing so might lead to inefficient resource allocation, but it always avoids deadlock.
2. If process A is using resource 1 and now needs resource 2, it must first release resource 1 before requesting resource 2. This to some extent solves the allocation problem in method 1.
3. If process A is using resource 1 and now needs resource 2, it will first check the usage status of resource 2. If no other process is occupying it, it can use resource 2. If it is occupied, it will release all currently used resources and re-request resource 2.

Solving Circular Wait:

We order all resources, $R_{0} \dots R_{n}$. A process currently occupying $R_{i}$ cannot request $R_{k}$, where $k < i$. This solves the circular wait.