Deadlock detection is really cheap

ABSTRACT

The treatment of deadlock has previously been considered as expensive, and implementations of the involved algorithm have appeared rather complex. In this paper a new algorithm for the treatment of deadlock is described. It is not only very efficient (in the worst case O(e) where e is the number of the edges in the “wait-for” graph) but also fairly simple. With this algorithm one can detect all deadlocks as soon as possible and list all participators in the corresponding cycle of the “wait-for” graph. The algorithm is described for the use of database transaction management.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Transaction processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Deadlock avoidance

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Analysis of algorithms

General Terms:
Algorithms, Design, Management