Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1994-04-11
2001-04-24
Banankhah, Majid (Department: 2755)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
Reexamination Certificate
active
06223200
ABSTRACT:
This invention relates generally to computer systems which provide multiple users with access to the same logical resource, and more particularly to methods and techniques for detecting deadlocks involving a transaction which has locked one required resource while being locked out of another required resource.
BACKGROUND OF THE INVENTION
Generally speaking, a deadlock arises in a computer system whenever transactions require the use of more than one resource in order for the transaction to be completed. In other words, it is typical for a transaction to lock a resource so that such a transaction becomes the “owner” of that resource thereby temporarily precluding another transaction from having any access to that resource. A deadlock occurs when transactions seem to be in an infinite wait for a resource and are unable to complete.
There are three types of techniques for dealing with the deadlocks: timeout, deadlock prevention, or deadlock detection. Timeout causes all requests for resources to be denied after some specified waiting interval. It has the disadvantage that as the system becomes more congested, more and more transactions are prematurely terminated, since timeout puts an upper limit on the duration of a transaction's request. Thus, the dynamic properties of timeout make it acceptable for a lightly loaded system, but inappropriate for a congested system.
Deadlock prevention is achieved by requesting all locks at once, or by requesting locks in a specified order, or by never allowing a transaction to wait for a resource. Where deadlock prevention is employed, there is usually the tendency to lock up too many resources at one time, thereby resulting in a very slow and inefficient system.
Accordingly, various schemes have been developed to overcome the deficiencies of timeout and deadlock prevention by providing a sequence of steps for achieving deadlock detection, and initiating resolution procedures whenever deadlock occurs. Prior art techniques usually follow the steps of detecting the deadlock, picking a pending transaction to be the victim in order to break the impasse by preempting the victim from the system, backing such victim(s) out of the system in order to remove any locks on resources which are held by the victim(s), making such a released resource accessible to another pending transaction which is waiting for it, and then in some instances restarting the victim transaction.
However, prior art deadlock detection schemes have proven to be inefficient in congested systems, and have sometimes taken many hours to provide detection and resolution of deadlock situations.
OBJECTS AND BRIEF SUMMARY OF THE INVENTION
It is therefore an object of the invention to provide a unique method and technique for shortening the time required to detect and resolve deadlocks in a congested system where multiple users require access to many of the same resources in order to complete their transactions.
The invention constitutes an improvement over existing deadlock detection techniques by maintaining an updated lock wait matrix based on the maximum number of transactions and the number of critical shared resources which can be locked and waited on by a pending transaction, building a wait tree from such a matrix, periodically pruning in a predetermined pattern the tree branches including turning non-terminal nodes in the tree into terminal nodes, while traversing the tree to detect and resolve deadlocks, with the pruning being done in a manner which minimizes the number of times that nodes representing the same transaction are processed.
These and other objects will be apparent to those skilled in the art in view of the following description of a preferred embodiment of the invention as shown in the accompanying drawings.
REFERENCES:
patent: 3579194 (1971-05-01), Weinblatt
patent: 4189771 (1980-02-01), Roever
patent: 4224664 (1980-09-01), Trinchieri
patent: 4318182 (1982-03-01), Bachman et al.
patent: 4403285 (1983-09-01), Kikuchi
patent: 4435766 (1984-03-01), Haber et al.
patent: 4791554 (1988-12-01), Hirota et al.
patent: 4914569 (1990-04-01), Levine et al.
patent: 5008882 (1991-04-01), Peterson et al.
patent: 5123104 (1992-06-01), Levine et al.
Roesler et al, Efficient Deadlock Resolution For Lock-Based Concurrency Control Schemes, Conference Paper, Jun. 13-17, 1988, Publisher IEEE Computer Society Press, Washington DC.*
Elmagarmid et al, Two-Phase Deadlock Detection Algorithm, IEEE Transactions on Computers, vol. 37, No. 11, Nov. 1988.*
Information Processing Letters, vol. 17, No. 4, Nov. 1983, pp. 185-188; Shmueli: ‘Dynamic Cycle Detection’.
Distributed Algorithms, 3rd Int'l Workshop; Sep. 1989, Nice, France, pp 195-206; RUKPZ: ‘A Distributed Solution for Detecting Deadlock in Distributed Nested Transaction Systems’.
J. Eliot B. Moss, Nested Transactions, An Approach To Reliable Distributed Computing, 1985, pp. 94-114.*
Eigh, M. H. Graph Directed Locking, IEEE Transactions on Software Engineering, vol. 14, No. 2 Feb. 1988.*
Agrawal et al, The Performance of Alternative Strategies for Dealing With Deadlocks In Database Management Systems, IEEE Trans, on Soft. Eng. vol. SE-13, No. 12 Dec. 1987 pp. 1349-1361.*
Wuu et al, False Deadlock Detection in Distributed Systems, IEEE Trans, On Soft. Engr. vol. SE-11 No. 8 Aug. 1985, pp 820-821.
Barnes Cherie Carlyle
Wierbowski David John
Banankhah Majid
International Business Machines - Corporation
Samodovitz Arthur J.
LandOfFree
System and method for reducing research time through a lock... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for reducing research time through a lock..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for reducing research time through a lock... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2508890