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)?