scientific article; zbMATH DE number 4001481

From MaRDI portal
Publication:4727428





[For the entire collection see Zbl 0596.00021.] When serially reusable multiunit resources are shared among many processes, each of which has exclusive control over some resource units, it is possible for deadlocks to happen. The work of Holt stated the problem of deadlock detection as a directed multigraph problem. In this paper we examine the possibility of existence of fast parallel algorithms for deadlock detection. Although many graph problems have efficient parallel solutions (in parallel polylogarithmic time, by using only a polynomial number of processors), we present strong evidence that this is not the case for the general deadlock detection problem. We show that the problem is complete in P under log-space reductions and thus probably not efficiently parallelizable. Fortunately, when the problem is restricted (e.g. single-unit requests of processes or single-unit resources), then it falls in NC. We present efficient parallel algorithms for the restricted versions of the deadlock detection problem.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4727428)