General Deadlock Detection (GDD)

Input

A multigraph $D = (V, E)$ with $V = \pi \cup \rho$, where $\pi = \{p_1, \ldots, p_n\}$ is the set of process vertices and $\rho = \{r_1, \ldots, r_m\}$ is the set of resource vertices; and a set $T = \{t_1, \ldots, t_m\}$, where $t_i$ denotes the number of units of $r_i$.

Problem

Is $D$ a deadlock state?

Definitions

The bipartite multigraph $D$ represents the state of the system. The edges in $V$ are of the form $(p_i, r_j)$ denoting a request of process $p_i$ for resource $r_j$ or of the form $(r_j, p_i)$ denoting an allocation of resource $r_j$ to process $p_i$.

A deadlock state is one in which there is a nontrivial subset of the processes that cannot change state and will never change state in the future.

Status

$\P$-complete (Spirakis [1]).

Remarks

The reduction to show hardness is from MCVP. The problem continues $\P$-complete if maximum number of units of any resource is two. The problem is in $\NC$ if $t_i$ equals 1 for all $i$ [1]. That is, if there is only one unit of each resource. If the system states are expedient, the resource allocator satisfies them as soon as possible, and at most one request can be connected to any process at a given time, then the problem is in $\NC$ [1].