When do deadlocks occur?

Question

I was reading about deadlocks in Operating Systems. Where I came across two examples below.

Circles with label $P_x$ are processes. Squares with label $R_x$ are resources. Each dot in the square represents single instance of resource type $R_x$. An edge from $R_x$ to $P_x$ means an instance of resource $R_x$ is allocated to process $P_x$. An edge from $P_x$ to $R_x$ means the process $P_x$ is waiting for getting an instance of resource $R_x$ allocated.

Now consider below two resource allocation graphs

The example on left involves deadlock while the one on the right did not involved deadlock.

I can understand that in right-side figure, if $P_2$ releases its instance of $R_1$, it can be assigned to $P_1$, breaking the circular wait. Or if $P_4$ release its instance of $R_2$, it can be assigned to $P_3$, breaking the circular wait. However we cannot break circular wait in left-side figure.

While I can try out this on any given resource allocation graph and decide if there is deadlock or not, I want to know can we have a generalized rule for this which can tell what exactly it is which is contributing to the deadlock, especially in case of multiple instances of resources are there. I did not found any reference / book speaking of this clearly. So after a bit of thinking I came up with following fact:

If there are multiple instances of same resource, for deadlock to exist, for any combination of two processes, if both are allocated an instance of same resource, then both should be a part of at least one cycle.

In right-side figure above, there is no deadlock because

• processes $P_2$ and $P_3$ are allocated instances of $R_1$, but they both are not part of any cycle
• similarly processes $P_1$ and $P_4$ are allocated instances of $R_2$, but they both are not part of any cycle

In left-side figure above, there is a deadlock because

• processes $P_1$ and $P_2$ are allocated instances of resource $R_3$ and are part of same cycle,$P_1-R_1-P_2-R_3-P_3-R_3-P_1$

So am I correct with the above realization of fact? Or there are more aspects/conditions to the above fact (of when deadlock is present and when not) that I am missing?

What I am asking is if there is any other condition which if met, instead of the above one, will still result in the deadlock (in the context of multiple instances of resources and apart from four classic conditions of deadlock: mutual exclusion, no preemption, hold and wait and circular wait)?

Answer 1

All 4 conditions must be satisfied at the same time.

• Hold and Wait
• Non-preemption of resources
• Mutual Exclusion
• Circular wait

In case of single instance of resources:

Cycle in resource allocation graph represents deadlock.

In case of multiple instance of resources:

Cycle in RAG doesn't mean deadlock. You must check in the same way as you did. Let me write clear steps.

• We need to identify a process, in the cycle, which can execute without any dependency and execute that.
• Release the resources held by process.
• Next check the process which has all the resources to execute and execute completely and release the resources held by it.
• Keep doing till all the processes are executed.
• If you can't execute all the processes this way, then there is deadlock.

Hope that helps!

Answer 2

Your logic follows, and falls in line with the need for a circular wait in a deadlock.

Answer 3

A different type of diagram and model may help in answering the question “is there any other condition which if met […] will still result in the deadlock?” (“When do deadlocks occur?”, 2015).

Consider a Petri Net model of the process-resource system, based on the left resource allocation graph and the following assumptions:

1. Process P_1 requires one unit of Resource R_1 and one unit of Resource R_3 to perform its task.
2. P_2 requires one unit of R_1 and two units of R_3 to perform its task.
3. P_3 requires two units of R_3 to perform its task.
4. A process takes one unit of a resource at a time.
5. A process returns every unit of every resource it has taken at a time.
6. All processes run on a single processor. The processor can handle one and only one process at a time.

Figure 1: A Petri Net Model Based on the Left Resource Allocation Graph -- with Deadlock

A deadlock occurs in a system if or when the system “keeps waiting” for one or more resources it needs but the resource or resources will never be available. There are two reasons why the resource or resources will never be available. First, the resource was taken but never returned. Second, there was never “enough resources” to begin with.

If the left allocation graph is in a state of deadlock, then Figure 1 is one possible model that can reach this state.

Assuming there is enough resources, one way to prevent a deadlock is for a process to release the resources it has taken if one or more of the other resources it needs are not available. Another way to prevent a deadlock would be for a process allocate the resources it needs only if all of the resources it needs are available; otherwise, the process should not allocate any of the resources. The Petri Net in Figure 2 was designed this way – resources are allocated at the same time to a process if and only if every resource needed by the process is available.

Figure 2: A Petri Net Model for Allocating Resources without Deadlock

Notes

For the PDF version, Figure 1 and Figure 2 are interactive, dynamic diagrams. You can step through each process and see the state changes – including the occurrence of deadlock in Figure 1.

Figure 1 can be initialized in two ways: no resource is allocated to any process, and the resource allocation based on the left resource allocation graph.

References

“When do deadlocks occur?” (2015). Computer Science Stack Exchange. Retrieved on Nov. 27, 2015.

Chionglo, J. F. (2015) "A Reply to 'When do deadlocks occur?' at Computer Science Stack Exchange.