When do deadlocks occur?

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

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!

StackExchange Computer Science Q#49962, answer score: 4