Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1995-11-15
2001-01-09
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000, C709S241000
Reexamination Certificate
active
06173308
ABSTRACT:
BACKGROUND TO THE INVENTION
This invention relates to deadlock detection mechanisms for distributed data processing systems.
In a database system it is common to increase performance by allowing multiple transactions to execute concurrently. In order to ensure data consistency, a transaction must lock a data resource before accessing it and unlock it afterwards, and transactions must conform to the two-phase locking protocol. Two-phase locking means that a transaction must take all of its locks before it can release any of its locks (the first phase consists of taking locks, the second phase of releasing locks).
Locking introduces dependencies between transactions: that is, one transaction may be waiting for another transaction to release a lock before it can proceed. If a cyclic chain of dependencies occurs, all the transactions in the chain will be held up, each waiting for another; this is referred to as a deadlock. A mechanism must therefore be provided to detect deadlocks, and to perform appropriate action to break a detected deadlock. This action may involve selecting one of the deadlocked transactions as a victim, and aborting it. Deadlock detection is sometimes performed by a database management system back-end and sometimes by a platform-specific program.
Deadlock detection mechanisms are sometimes called upon to detect forms of deadlock other than that created by data resource locking. In these cases, the two-phase locking protocol may not be followed. The fact that modern database management system backends are multi-threaded means that a transaction might take and release a lock a number of times during its execution. This may cause spurious deadlocks to be detected by conventional deadlock detection mechanisms.
The object of the present invention is to provide a deadlock detection mechanism which enables such spurious deadlocks to be avoided.
SUMMARY OF THE INVENTION
According to the invention, there is provided a distributed data processing system comprising:
(a) initial deadlock detection means for detecting a potential deadlock involving a cyclic chain of dependencies between a plurality of entities (e.g. transactions) in the system;
(b) deadlock doublechecking means, responsive to detection of a potential deadlock, for confirming that all the dependencies in said cyclic chain are co-existent; and
(c) deadlock resolution means responsive to confirmation that all the dependencies in said cyclic chain are co-existent, for performing an action to break said deadlock.
It can be seen that the present invention provides a deadlock detection mechanism which double-checks whether entity dependencies in a possible deadlock all exist concurrently. The present invention therefore avoids the possibility of falsely detecting deadlock in the case when entities do not necessarily follow the two-phase locking protocol.
REFERENCES:
patent: 5459871 (1995-10-01), Van Den Berg
Hilditch Albert Stephen
Pettifer Steve Robert
Siddiqi Nasser
Thomson Colin Michael
Banankhah Majid
International Computers Limited
Lee Mann Smith McWilliams Sweeney & Ohlson
LandOfFree
Deadlock detection mechanism for data processing system,... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deadlock detection mechanism for data processing system,..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deadlock detection mechanism for data processing system,... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2441732