Processes that compete for the use of scarce resources may maneuver themselves into a deadlock situation. The paper establishes two necessary and sufficient conditions that guarantee the absence of deadlock under the expedient allocation policy. Their equivalence is proved. It is shown that the condition for deadlock-freedom is just another form of the well- known condition for the existence of systems of distinct representatives as expressed in the König-Hall theorem. For binary resources deadlock- freedom turns out to be equivalent to the absence of cycles in hypergraphs. It is furthermore interesting that, in contrast to earlier work, the condition for deadlock-freedom is proved without using König- Hall or equivalent theorems.
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Deadlock-Free Systems for a Bounded Number of Processes
- scientific article; zbMATH DE number 3400923 (Why is no real title available?)
- On Representatives of Subsets
- Prevention of system deadlocks
- Testing Deadlock-Freedom of Computer Systems
- Deadlock prevention with collectively occupied resources
- Rendezvous deadlocks in interacting parallel processes
- On the optimality of randomized deadlock avoidance policies
- A minimal property for characterizing deadlock-free programs
- Deadlock-freedom in component systems with architectural constraints
- Instance Deadlock: A Mystery behind Frozen Programs
- Design of Minimum-Cost Deadlock-Free Systems
- Random Resource Allocation Graphs and the Probability of Deadlock
- Revisiting deadlock prevention: a probabilistic approach
- On deadlocks of exclusive AND-requests for resources
- Separating Lock-Freedom from Wait-Freedom
- The pursuit of deadlock freedom
- Manifest deadlock-freedom for shared session types
- Cut-off theorems for the \textit{PV}-model
This page was built for publication: Deadlock-freedom in resource contentions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q801672)
