Browse Prior Art Database

EFFICIENT DEADLOCK DETECTION AND RESOLUTION FOR SHARED DISK MULTI-PROCESSOR

IP.com Disclosure Number: IPCOM000013216D
Original Publication Date: 2001-Apr-01
Included in the Prior Art Database: 2003-Jun-18
Document File: 2 page(s) / 53K

Publishing Venue

IBM

Abstract

Disclosed is a technique for efficiently detecting and resolving deadlocks between transactions running on shared disk multi-processor database management system (DBMS).

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 41% of the total text.

Page 1 of 2

  EFFICIENT DEADLOCK DETECTION AND RESOLUTION FOR SHARED DISK MULTI-PROCESSOR

    Disclosed is a technique for efficiently detecting and resolving deadlocks between transactions running on shared disk multi-processor database management system (DBMS).

    In a single processor DBMS transactions accessing a given database execute on one copy of the DBMS software (although, in the case of distributed database, the transaction may not have originated on that copy). Information regarding deadlocks involving those transaction's access to that database can be determined solely from that DBMS. If a transaction does not use distributed access methods then all deadlocks involving that transaction can be detected on that system.

    In contrast on a shared disk multi-processor DBMS transactions accessing a given database can execute on any copy of the DBMS. Even if that transaction does not use distributed access methods then one instance of the DBMS does not necessarily have enough information to detect deadlocks involving that transaction.

    The term local deadlock is used to refer to a deadlock involving transactions at one DBMS image. The term global deadlock is used to refer to a deadlock involving transactions at two or more DBMS images. Deadlock detection is centered around a structure known as the transaction wait-for graph (TWFG). The TWFG represents the transactions that may be involved in deadlocks and the wait-for relationships between those transactions.

Deadlock processing consists of three major steps:
1. Collection (Build transaction wait-for graph) The lock wait-for conditions are identified and represented as a TWFG. All wait-for relationships known to this DBMS are represented in the graph.
2. Detection (Scan the TWFG for deadlocks) All deadlocks contained in the TWFG are detected. This step can use any of the known algorithms for detecting cycles in a directed graph.
3. Resolution (Pick a victim to break each deadlock and kill it) All deadlocks that were detected during the previous phase are resolved by selecting victims and causing those victims to roll-back. One DBMS by itself does not have enough information to detect and resolve a global deadlock. A given DBMS knows information about the transactions it manages, what locks they hold and what locks they are waiting for. They may not know what transactions block those pending locks. For this reason it is only when all DBMSs cooperate can global deadlocks be detected and resolved.

    The notion of a node external is used. The node external represents that part of the global TWFG not visible to a given DBMS. If a DBMS does not know what transactions or collections of transactions it is waiting for then it is said to be waiting for the node external. Similarly if a DBMS does not know what transactions or collections of transactions are waiting for it then the node external is said to be waiting for it.

    Just knowing that this DBMS waits for node external is not paricularly useful information....