Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-01-30
2001-05-22
Breene, John (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06236995
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to object-oriented programming and more particularly to a distributed object system with deadlock prevention.
BACKGROUND OF THE INVENTION
Some computer applications are so large and the number of users of the applications so large that it makes sense to divide up the work of the application among multiple computers and, potentially, to store the information used by the application in many different places. Such applications are commonly referred to as distributed applications. Conventional distributed applications store shared information in multiple databases that may reside on many different computers.
Recently, however, software developers have begun to create distributed object systems. Distributed object systems comprise shared objects that may be accessed by one or more processes running on one or more computers. In distributed object systems, then, an additional shared resource, the distributed object, needs to be accounted for.
In a distributed object environment, objects are accessed in the context of transactions. When an object is about to be accessed in the context of a particular transaction but is already in use by another transaction, then the second transaction will often be required to wait until the first transaction has completed in order to ensure that each transaction accomplishes a logically consistent update. Variations in such a locking mechanism may allow read-only transactions to proceed, or may control locking at the level of individual object instance variables or at the level of groups of objects. In any case, when a transaction seeks to access such a locked resource, that transaction may have to wait to use that resource.
Because transactions are operating on multiple objects asynchronously, it is possible that a transaction that is about to go into a wait state may be doing so to wait for a second transaction that is already waiting on the first transaction for access to another resource. This is commonly called a deadlock as each transaction may wait for the other indefinitely.
Although some deadlock detection methods exist, these mechanisms often detect deadlock after the deadlock condition has already occurred, rather than detecting it just prior to its occurrence.
SUMMARY OF THE INVENTION
The invention comprises a distributed object system with deadlock detection and a method for preventing deadlock. One aspect of the invention is a distributed object system with a plurality of resources and a plurality of transactions where at least some of the plurality of transactions make use of at least one of the plurality of resources. A transaction service running on a computer is operable to interact with the resources and transactions. The transaction service comprises a deadlock detector operable to determine whether deadlock will occur if one of the plurality of transactions waits to use a resource currently being used by another of the plurality of transactions. The transaction service further comprises a roll back method operable to roll back a particular transaction if the deadlock detector determines that deadlock will occur if that particular transaction waits to use a resource currently being used by another of the plurality of transactions.
The invention has several important technical advantages. The invention allows potential deadlock to be detected easily and efficiently. The invention does not require the transaction service to maintain complicated data about each transaction to use for deadlock detection. Instead, the invention employs a limited amount of data to use for this purpose. The invention detects deadlock just prior to its occurrence, avoiding an actual deadlock condition. When deadlock is detected, the transaction that would cause deadlock if it was placed into a wait state is simply rolled back to allow the relevant transaction to proceed. Thus, the invention avoids deadlock with the simple roll back of a single transaction.
REFERENCES:
patent: 5377351 (1994-12-01), Kotera et al.
patent: 5764976 (1998-06-01), Hsiao
patent: 5799305 (1998-08-01), Bortvedt et al.
patent: 5832484 (1998-11-01), Sankaran et al.
patent: 5835766 (1998-11-01), Iba et al.
patent: 5872981 (1999-02-01), Waddington et al.
patent: 5940828 (1999-08-01), Anaya et al.
Flatebo et al., Self-Stabilizing deadlock Detection Algorithms, obtained via the internet <http://www.acm.org/pubs/citations/proceedings/csc/131214/p117-flatebo, p. 117-122, Mar. 1992.*
Deitel, Operating Systems, Addison-Wesley Publishing Compant, Chapter 6 p. 153-174, Jan. 1990.*
Document entitled “Transaction Processing Concepts and Techniques” by Jim Gray and Andreas Renter, Morgan-Kaufmann, 1993, pp. 422-429.
Baker & Botts L.L.P.
Breene John
Electronic Data Systems Corporation
Robinson Greta L.
LandOfFree
Distributed object system with deadlock prevention does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Distributed object system with deadlock prevention, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Distributed object system with deadlock prevention will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2470785