Detecting a state change in a lock structure to validate a...

Details Detecting a state change in a lock structure to validate a... Detecting a state change in a lock structure to validate a...

1999-02-23

2001-10-16

Auve, Glenn A. (Department: 2181)

Electrical computers and digital data processing systems: input/

Access locking

Reexamination Certificate

active

06304938

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to deadlock handling, and in particular, to validating potential deadlocks.
BACKGROUND OF THE INVENTION
One of the long standing challenges in computing is the detection of deadlocks. A deadlock is a state assumed by a set of entities wherein each entity in the set is waiting for the release of at least one resource owned by another entity in the set. Entities capable of owning a resource are referred to herein as possessory entities. In the context of a database system, for example, possessory entities include processes and transactions. A transaction is an atomic unit of work.
For example, a transaction T1 may seek exclusive ownership of resource R1 and R2. If R1 is available and R2 is currently exclusively owned by another transaction T2, transaction T1 may acquire exclusive ownership of R1 but must wait for R2 to become available. A deadlock will occur if a transaction T2 exclusively owns R2 but seeks ownership of R1, and T2 is suspended to wait for R1 without releasing R2. Because both T1 and T2 are waiting for each other, they are deadlocked.
Computer systems employ a variety of deadlock handling mechanisms (deadlock handlers) that detect deadlocks. Many of deadlock handlers employ the “cycle” technique to detect deadlocks. In the cycle technique, after a process waits a threshold period of time for a resource, a wait-for graph is generated and examined for any cycles. If any cycles are identified, then the deadlock detection mechanism has identified a deadlock.
A wait-for graph is a graph that includes vertices that represent resources (“resource vertices”) and vertices that represent possessory entities (“entity vertices ”). An arc from an entity vertex to a resource vertex represents that the respective possessory entity represented by the entity vertex is waiting for ownership of the resource. An arc from a resource vertex to an possessory entity node represents that the resource represented by the resource vertex is owned by the possessory entity. A cycle is detected when a chain of arcs leads both to and from the same vertex.
FIG. 1
shows an exemplary wait-for graph
100
, which includes entity vertices
111
and
112
and resource vertices
121
and
122
. Wait-for graph
100
was generated when a deadlock handler detected that the process represented by entity vertex
111
had waited a threshold period of time for the resource represented by resource vertex
121
. Arc
131
represents that the process represented by entity vertex
111
is waiting for the release of the resource represented by resource vertex
121
. Arc
132
represents that the resource represented by resource vertex
121
is owned by the process represented by entity vertex
112
. Arc
133
represents that the process represented by entity vertex
112
is waiting for the release of the resource represented by resource vertex
122
. Arc
134
represents that the resource represented by resource vertex
122
is owned by the resource represented by entity vertex
111
.
Arcs
131
,
132
,
133
, and
134
form a loop that both extends from and leads to entity vertex
111
, and thus represents a cycle. The processes represented the entity vertices of wait-for graph
100
are therefore potentially deadlocked.
In practice, deadlocks detected through the cycle technique may not actually exist. One reason the cycle technique is not completely accurate is that relationships between possessory entities and resources change while a wait-for graph is being generated. For example, while in the process of generating a wait-for graph, a deadlock handler determines that arc
131
should connect entity vertex
111
to resource vertex
121
because the process represented by entity vertex
111
is waiting for the release of the resource represented by resource vertex
121
. Next, the deadlock handler determines that arc
132
should connect resource vertex
121
to entity resource
112
because resource vertex
121
is owned by entity resource
112
. The deadlock handler then generates the remainder of wait-for graph
100
.
While generating the remainder of wait-for graph
100
, the process represented by entity vertex
112
relinquishes ownership of the resource represented by resource vertex
121
. Thus upon completion of the wait-for graph, arc
132
in fact represents a nonexistent relationship, and the cycle represented by arcs
131
,
132
,
133
, and
134
represents a nonexistent deadlock.
Because deadlocks identified through the cycle technique may or may not exist, such deadlocks are subjected to further verification before they are treated as deadlocks that exist. The process of verifying the existence of previously identified deadlocks is referred to as “validation”. Deadlocks that have been detected but have not yet been subjected to validation are referred to herein as potential deadlocks.
Typically, validation of a potential deadlock involves regenerating a wait-for graph, and determining whether the regenerated wait-for graph contains the same previously identified cycle. If the same cycle exists, the probability that the potential deadlock is an actual deadlock increases greatly, and the potential deadlock is handled as a deadlock. Such handling includes causing one of the possessory entities to relinquish ownership of a resource, thus “breaking the cycle.” A potential deadlock that is treated as a real deadlock because its existence has been verified through validation, is referred to herein as a true deadlock.
As shown above, identifying true deadlocks may entail the generation of at least two wait-for graphs. Validating a possible deadlock without performing the amount of work required to generate a second wait-for graph would substantially improve the efficiency of performing validation. It is therefore desirable to provide a method for validation that requires less work than regenerating a wait-for graph, and in particular, requires less work without sacrificing accuracy in validating potential deadlocks.
SUMMARY OF THE INVENTION
A mechanism for deadlock validation is described. According to an embodiment of the present invention, a potential deadlock is validated by detecting whether a state change has occurred in a member of a set of lock structures that correspond to entities and resources involved in a potential deadlock. The state change detected should have occurred after the state of the lock structures is captured during, for example, the generation of a wait-for graph. For purposes of illustration, potential deadlocks are identified by generating a wait-for graph and detecting cycles in the wait-for graph. While generating wait-for graphs, lock structures are accessed to determine whether a vertex in the wait-for graph should be generated, and the place of the vertex in the wait-for graph. After accessing a particular lock structure for this purpose, the lock structure's state is captured. If the state of the lock structure changes after the state is captured, then any cycle that includes the lock structure may not be valid, and a potential deadlock identified by the cycle is deemed a false deadlock.


REFERENCES:
patent: 5442763 (1995-08-01), Bartfai et al.
patent: 5459871 (1995-10-01), Van Den Berg
patent: 5544332 (1996-08-01), Chen
patent: 5764976 (1998-06-01), Hsiao
patent: 6065063 (2000-05-01), Abali

Affiliated with

Also associated with

Rating

Detecting a state change in a lock structure to validate a... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Detecting a state change in a lock structure to validate a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Detecting a state change in a lock structure to validate a... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2592542