Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-07-22
2001-08-14
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C710S200000, C709S241000, C709S201000
Reexamination Certificate
active
06275823
ABSTRACT:
FIELD OF INVENTION
The present invention relates to a method of handling the risk of deadlock between mutually simultaneous transactions in a database.
DESCRIPTION OF THE BACKGROUND ART
When handling transactions in databases, it has long been known to allow a transaction that has been denied access to an object because of a lock from another transaction to wait until the locked object becomes avaliable by virtue of the completion of the transaction that locked the object.
When each of two transactions sets a lock on an object to which the other of said two transactions has requested access, each transaction must wait until access is available and none of the transactions will release its lock, therewith resulting in a deadlock.
A deadlock can be avoided or prevented in different ways.
It is known that respective objects have at least one lockout queue or line, in which the transactions desiring access to the object are placed. The transactions awaiting access to an object are apparent from the a e queue.
This lockout queue can be implemented in different ways, for instance in the form of a list or hash-table, and respective objects may be allotted several lockout queues where different types of locks are placed in different queues.
For the sake of simplicity, the majority of the embodiments of the present invention include only one lockout queue for respective objects. The person skilled in this art, however, will understand that the present invention can also be implemented when several lockout queues are used.
The risk of a deadlock happening can be detected, by comparing the lockout queues for different objects. This comparison involves comparing all transactions present in an object lockout queue with those transactions present in the lockout queues for other objects in the database. If this comparison reveals that two transactions desire access to two (or more) common objects, then the risk of deadlock has been detected.
This may not necessarily mean that the situation will develop into a deadlock, since different time aspects with respect to when the different objects will be accessed by respective transactions, and the type of lock that is set on respective transactions on said different objects will decide whether or not the situation will develop into a deadlock situation.
The time aspect implies that a waiting time may depend on reasons other than a given transaction having caused a deadlock, such as a transaction must await access because of a deadlock caused by completely different transactions, or because of the time taken to carry out preceding transactions in the queue, or because the own access takes time to carry out, without resulting in deadlock.
One type of lock enables access to be achieved as a purely reading transaction, wherewith this transaction will set a so-called divided lock on the object and the object will therefore still be available for reading other transactions.
When the danger of a deadlock is detected, the danger can be avoided by executing different procedures.
These procedures can be divided mainly into two groups, deadlock detection and deadlock avoidance.
When deadlock is detected there is initiated a process in which it is established whether or not deadlock is actually possible, prior to one of the involved transactions being aborted.
A deadlock is avoided by aborting one of the involved transactions immediately the risk of deadlock is detected, without actually establishing whether or not a deadlock exists.
Different methods are known whereby it can be decided which transaction shall be permitted to continue and which transaction shall be aborted. Normally, transactions of higher priorities are given precedence over transactions of lower priority.
When a deadlock occurs between two transactions of mutually the same priority, the older transaction is continued and the younger transaction is aborted, providing that it is possible to decide which transaction is the youngest and which transaction is the oldest, for instance through time stamps.
The present invention is not dependent on the method used when detecting the risk of a deadlock. The implementation of such a method will not therefore be described in this document. Thus, reference is made in the following description solely to the implementation of a further action or procedure subsequent to detecting the risk of a deadlock.
Various methods of implementing deadlock detection are described, e.g., in publications EP-A2-0 433 882, U.S. Pat. No. 5,440,743, SE-T3-0 135 173, and Two-phase Deadlock Algorithm, by A. K. Elmagarmid and A. K. Datta, IBREE Transactions on Computers, Vol. 37, No. 11, November 1998. These applications teach various methods of not only detecting the possible risk of a deadlock but also of detecting whether or not a deadlock actually exists.
It is also known to place all objects in a database in a numbered order relative to each other.
This can be achieved by placing all objects consecutively in a table, one after the other, even when the objects may be placed physically in another order in practice but interlinked in the consecutive order, for instance via a linked list.
For instance, when all tables in a database are given different numbers, table 1, table 2, table 3 and so on, all objects in the total database can be considered to lie in a number order relative to each other, in other words in the consecutive order in the table in combination with the table order.
A database organisation of this kind enables deadlock between two transactions to be prevented, and therewith completely avoided.
This is possible by allowing solely those transactions that are active or ongoing in the database to access relevant objects in number order. If such is the case, a first transaction can never lock a first object and then “back out” in order to access an earlier object in the number order, a second object, that has already been locked by a second transaction that, in turn, desires access to the first object, when the second object lies in front of the first object in the aforedescribed number order.
In this case, waiting times may possibly occur, i.e. “standard” locking, but never a deadlock.
It will be observed that in the case of a database where each object is allotted a specific order in accordance with the aforegoing, transactions that are implemented in accordance with this order and transactions that pay no regard to said order can both be implemented simultaneously. In order to distinguish between these transactions, transactions that pay regard to such an ordered list are described in the following as “strictly growing transactions” while transactions that pay no regard to such an ordered list are referred to as “non-strictly growing transactions”.
In a combination of the two methods, deadlock can occur immediately one transaction is a non-strictly growing transaction, but never between two strictly growing transactions.
It can also be mentioned that the difficulties encountered with monitoring a database with respect to deadlock are particularly significant in distributed databases.
The reader is referred to Principles of Distributed Database Systems by M. Tamer özsu and Patrick Valduriez, ISBN 0-13-691643-0, for further information concerning database handling in general and deadlock and the handling of deadlock situations in particular.
SUMMARY OF THE INVENTION
Technical Problems
When considering the earlier standpoint of techniques as described above, it will be seen that a technical problem resides in the ability to reduce considerably the execution capacity required for monitoring the risk of deadlock in relation to the capacity required in the case of known technology, while maintaining security against deadlock between simultaneous transactions in the database.
Another technical problem resides in the ability to categorise transactions as so-called locking transactions, so as to enable locking and non-locking combinations of transactions to be readily distinguished from each other, by observing the category to which the concerned transactions belong.
A
Alam Hosain T.
Alam Shahid
Burns Doane Swecker & Mathis L.L.P.
Telefonaktiebolaget LM Ericsson (publ)
LandOfFree
Method relating to databases does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method relating to databases, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method relating to databases will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2551799