Safe states in banker-like resource allocation problems

DOI10.1016/0890-5401(87)90002-2MaRDI QIDQ580968zbMATH OpenOpenAlexFDO

Authors Dirk Hauschildt, Ruediger Valk

Publication date 1987

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0890-5401(87)90002-2

zbMATH Keywords

MINminimal elementsoperating systemsPetri netSAFESORTtime complexity

Mathematics Subject Classification ID

Theory of operating systems (68N25)

Review text

This paper is concerned with methods of describing the set of safe states in the Banker's problem. Using a Petri net model, formulas for this set (SAFE) and for its subset of minimal elements (MIN) are derived. Moreover, by partitioning MIN into subclasses such that elements of the same subclass differ only by a permutation of their components, an even smaller representation is given by a set SORT. Lower and upper bounds for the size of SORT are calculated. Since we give an algorithm which computes SORT in time linear to its size, these bounds are also applicable to the time complexity of computing SORT. Finally, some of the results are extended to the multidimensional Banker's problem with different currencies, whereas other properties are shown to be not extendible to this case.

Recommendations

• scientific article; zbMATH DE number 3990882
• The Banker's problem with precedences
• scientific article; zbMATH DE number 3874587
• scientific article; zbMATH DE number 4045096
• Design of Minimum-Cost Deadlock-Free Systems

Cites work

• Comments on prevention of system deadlocks
• scientific article; zbMATH DE number 3483531 (Why is no real title available?)
• scientific article; zbMATH DE number 3577263 (Why is no real title available?)
• The residue of vector sets with applications to decidability problems in Petri nets

Cited in

(3)

• scientific article; zbMATH DE number 3990882 (Why is no real title available?)
• The Banker's problem with precedences
• The residue of vector sets with applications to decidability problems in Petri nets

This page was built for publication: Safe states in banker-like resource allocation problems

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