scientific article; zbMATH DE number 4001481
[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.
- scientific article; zbMATH DE number 947017
- scientific article; zbMATH DE number 3976331
- Time efficient deadlock resolution algorithms
- A parallel multi-unit resource deadlock detection algorithm with \(O(\log _2(\min (m, n)))\) overall run-time complexity
- Efficiently verifiable conditions for deadlock-freedom of large concurrent programs
- Deadlock prevention with collectively occupied resources
- Rendezvous deadlocks in interacting parallel processes
- On the complexity of deadlock-free programs on a ring of processors
- Time efficient deadlock resolution algorithms
- A model for deadlock detection based on automata and languages theory
- Deadlock resolution in wait-for graphs by vertex/arc deletion
- Resource-Oriented Deadlock Analysis
- scientific article; zbMATH DE number 5629953 (Why is no real title available?)
- scientific article; zbMATH DE number 3976331 (Why is no real title available?)
- Design of Minimum-Cost Deadlock-Free Systems
- scientific article; zbMATH DE number 4070293 (Why is no real title available?)
- An Automatic Approach to Deadlock Detection and Resolution in Discrete Simulation Systems
- Expected deadlock time in a multiprocessing system
- On the undecidability of deadlock detection in families of nets
- scientific article; zbMATH DE number 947017 (Why is no real title available?)
- Deadlock detection in MPI programs
- Easy cases of deadlock detection in train scheduling
- The Banker's problem with precedences
- Cut-off theorems for the \textit{PV}-model
- A parallel multi-unit resource deadlock detection algorithm with \(O(\log _2(\min (m, n)))\) overall run-time complexity
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)