An extended banker's algorithm for deadlock avoidance

    Authors

    S. D. Lang

    Comments

    Authors: contact us about adding a copy of your work at STARS@ucf.edu

    Abbreviated Journal Title

    IEEE Trans. Softw. Eng.

    Keywords

    banker's algorithm; deadlock; deadlock avoidance; graph reduction; operating system; worst-case complexity; Computer Science, Software Engineering; Engineering, Electrical &; Electronic

    Abstract

    We describe a natural extension of the banker's algorithm for deadlock avoidance in operating systems. Representing the control flow of each process as a rooted tree of nodes corresponding to resource requests and releases, we propose a quadratic-time algorithm which decomposes each flow graph into a nested family of regions, such that all allocated resources are released before the control leaves a region. Also, information on the maximum resource claims for each of the regions can be extracted prior to process execution. By inserting operating system calls when entering a new region for each process at runtime, and applying the original banker's algorithm for deadlock avoidance, this method has the potential to achieve better resource utilization because information on the "localized approximate maximum claims" is used for testing system safety.

    Journal Title

    Ieee Transactions on Software Engineering

    Volume

    25

    Issue/Number

    3

    Publication Date

    1-1-1999

    Document Type

    Letter

    Language

    English

    First Page

    428

    Last Page

    432

    WOS Identifier

    WOS:000082149000012

    ISSN

    0098-5589

    Share

    COinS