Banker’s algorithm – Knowledge and References

Banker's algorithm

Banker's algorithm is a deadlock avoidance scheme used in computer operating systems. It is designed to prevent resource allocations that could potentially lead to deadlock. The algorithm has a polynomial-time complexity and is frequently used to create deadlock control policies.From: Dictionary of Computer Science, Engineering, and Technology [2017], Polynomial-complexity supervisory control for flexible assembly systems based on Petri nets [2018]

Deadlock

View Chapter

Purchase Book

Published in Ivan Cibrario Bertolotti, Gabriele Manduchi, Real-Time Embedded Systems, 2017

Ivan Cibrario Bertolotti, Gabriele Manduchi

The complexity of the banker’s algorithm is O(mn2), where m is the number of resource classes in the system, and n is the number of processes. This overhead is incurred on every resource allocation and release due to the fact that, in the latter case, any waiting requests shall be reconsidered.

Polynomial-complexity supervisory control for flexible assembly systems based on Petri nets

View Article

Journal Information

Published in International Journal of Computer Integrated Manufacturing, 2018

Hao Yue, Hesuan Hu, Weimin Wu, Hongye Su, Jihui Zhang

The Banker’s algorithm (BA) is of polynomial-time complexity and has been frequently used to design deadlock control policies in computer operating systems. Researchers in the manufacturing field also use it to develop DAPs. Lawley, Reveliotis, and Ferreira (1998) present variants of BA, which are applicable to buffer space allocation in flexible manufacturing systems. Furthermore, they show that these algorithms are not excessively conservative and that, indeed, approaches of BA can provide good operational flexibility when properly applied to the manufacturing environment. Then, many deadlock resolution methods, which are based on BA, have been proposed for RASs (Ezpeleta et al. 2002; Ezpeleta and Valk 2006; Reveliotis 1998; Žarnay and Garca 2014).

Banker's algorithm

Explore chapters and articles related to this topic

Deadlock

Polynomial-complexity supervisory control for flexible assembly systems based on Petri nets