com.bigdata.concurrent
Class TxDag

java.lang.Object
  com.bigdata.concurrent.TxDag

public class TxDag
extends Object

Directed Acyclic Graph (DAG) for detecting and preventing deadlocks in a concurrent programming system. The algorithm takes advantage of certain characteristics of the deadlock detection problem for concurrent transactions and provides a reasonable cost solution for that domain. The design uses a boolean matrix W to code the edges in the WAITS_FOR graph and an integer matrix M to code the the number of different paths between two vertices. Operations that insert one or more edges are atomic -- if a deadlock would result, then the state of the DAG is NOT changed (a deadlock is detected when there is a non-zero path count in the diagonal of W). The cost of the algorithm is less than O(n^^2) and is suitable for systems with a multi-programming level of 100s of concurrent transactions.

This implementation is based on the online algorithm for deadlock detection in Section 5, page 86 of: Bayer, R. 1976. Integrity, Concurrency, and Recovery in Databases. In Proceedings of the Proceedings of the 1st European Cooperation in informatics on ECI Conference 1976 (August 09 - 12, 1976). K. Samelson, Ed. Lecture Notes In Computer Science, vol. 44. Springer-Verlag, London, 79-106. See the citation online.

Given that w is the directed acyclic graph of WAITS_FOR relation among the concurrent transactions. w+ is the transitive closure of w. The online algorithm solves the problem:

 Given w, w+,              calculate
       w', w'+             where
       w' := w U {(ti,tj)} iff inserting an edge, or
       w' := w / {(ti,tj)} iff removing an edge.
 

The approach defines a matrix M[ t, u ] whose cells are the number of different paths from t to u. A deadlock is identified if the update algorithm for M computes a non-zero value for the diagonal.

The update rules for M are as follows. "+/-" should be interpreted as "+" iff an edge is being added and "-" iff an edge is being removed. The "." operator is scalar multiplication.

• M[s,v] := M[s,v] +/- M[s,t] . M[u,v]; s!=t; u!=v
• M[s,u] := M[s,u] +/- M[s,t]; s!=t
• M[t,v] := M[t,v] +/- M[u,v]; u!=v
• M[t,u] := M[t,u] +/- 1

Updates are made tentative using a secondary matrix, M2. The update is applied to M2. If a deadlock would result, then the original matrix is not modified. Otherwise the original matrix is replaced by M2.

The public interface is defined in terms of arbitrary objects designated by the application as "transactions". The DAG is provisioned for a maximum multi-programming level, which is used to dimension the internal matrices. The choosen multi-programming level should correspond to the maximum multi- programming level permitted, i.e., to the #of concurrent transactions which may execute before subsequent requests for a new transaction are queued. Internally the "transaction" objects are mapped using their hash code onto pre-defined Integers corresponding to indices in [0:n-1], where n is the provisioned multi-programming level.

Usage notes

This class is designed to be used internally by a class modeling a ResourceQueue. Edges are added when a transaction must wait for a resource on one or more transactions in the granted group for that resource queue. Transactions are implicitly declared as they are referenced when adding edges. The general case is that there are N transactions in the granted group for some resource, so addEdges(Object blocked, Object[] running) would be used to indicate that a transaction must wait on the granted group.

A transaction in a granted group is guarenteed to be running and hence not waiting on any other transaction(s). When a transaction releases a lock, the ResourceQueue automatically invokes removeEdges(Object tx, boolean waiting) with waiting == false in order to remove all WAITS_FOR relationships whose target is that transaction. (The removeEdges(Object, boolean) method is optimized for the case when it is known that a transaction is not waiting for any other transaction.)

The integration layer MUST explicitly invoke removeEdges(Object, boolean) whenever a transaction commits or aborts in order to remove all WAITS_FOR relationships involving that transaction. Failure to do this will result in false reporting of deadlocks since the transaction is still "on the books". The integration layer should specify waiting == false iff it knows that the transaction was NOT blocked. For example, a transaction which completes normally is never blocked. However, if a decision is made to abort a blocked transaction, e.g., owing to a timeout or external directive, then the caller MUST specify waiting == true and a less efficient technique will be used to remove all edges involving the specificed transaction.

Version:

$Id: TxDag.java 2265 2009-10-26 12:51:06Z thompsonbry $

Author:

Bryan Thompson

TODO:

This implementation does not help the application to decide the minimum "cost" set of transactions which would result in an acyclic graph if their WAITS_FOR relationships (edges) were removed from the graph. This could probably be achieved by an analysis of the path count matrix in which the deadlock was detected combined with information about the sunk cost of each transaction., The use of DAGs for detecting and breaking deadlocks in support of concurrent programming may require interaction with the locking protocol. For example, a transaction requesting a lock which would result in a deadlock may be moved up in the request queue for a lock if that would resolve the deadlock., Consider requiring explicitly registration of transactions. This is parallel to the requirement for explicitly removal of transactions using {@link #removeEdges(Object, boolean)., This class should probably be unsynchronized and should place the burden for synchronization on the caller.

Nested Class Summary

static class

TxDag.Edge A representation of an edge in the DAG used for export of information to the caller.

Field Summary

static boolean	cacheOrder This field controls whether or not the result of getOrder() is cached.
protected static boolean	DEBUG
protected static boolean	INFO
protected static org.apache.log4j.Logger	log Logger for this class.
static boolean	sortOrder This field controls whether or not the result of getOrder() and getOrder(int, int) are sorted.
static boolean	sortOrderForDisplay This field controls whether or not the order[] is cloned and then sorted by toString().
static int	UNKNOWN The constant used by lookup(Object, boolean) to indicate that the named vertex was not found in the DAG (-1).

Constructor Summary

TxDag(int capacity)
Constructor.

Method Summary

void	addEdge(Object blocked, Object running) Add an edge to the DAG.
void	addEdges(Object blocked, Object[] running) Add a set of edges to the DAG.
int	capacity() The maximum multi-programming level supported (from the constructor).
TxDag.Edge[]	getEdges(boolean closure) Return an array of the edges asserted for the graph.
boolean	hasEdge(Object blocked, Object running) Return true iff the described edge exists in the graph.
boolean	isFull() Return true iff adding another transaction would exceed the configured multi-programming capacity.
boolean	releaseVertex(Object tx) Releases the vertex by (a) removing it from the mapping and (b) updating the list of available indices.
void	removeEdge(Object blocked, Object running) Removes an edge from the DAG.
void	removeEdges(Object tx, boolean waiting) Remove all edges whose target is tx.
int	size() The current multi-programming level.
String	toString() Returns a representation of the state of the graph suitable for debugging the algorithm.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

log

protected static final org.apache.log4j.Logger log

Logger for this class.

INFO

protected static final boolean INFO

DEBUG

protected static final boolean DEBUG

sortOrder

public static boolean sortOrder

This field controls whether or not the result of getOrder() and getOrder(int, int) are sorted. Sorting is not required for correctness, but sorting may make it easier to follow the behavior of the algorithm. The default is false.

sortOrderForDisplay

public static boolean sortOrderForDisplay

This field controls whether or not the order[] is cloned and then sorted by toString(). The default is true.

cacheOrder

public static boolean cacheOrder

This field controls whether or not the result of getOrder() is cached. Caching is enabled by default but may be disabled for debugging.

UNKNOWN

public static final int UNKNOWN

The constant used by lookup(Object, boolean) to indicate that the named vertex was not found in the DAG (-1).

See Also:

Constant Field Values

Constructor Detail

TxDag

public TxDag(int capacity)

Constructor.

Parameters:

capacity - The multi-programming level. This is the maximum number of concurrent transactions permitted by the application.

IllegalArgumentException - If n < 2 (the minimum value for concurrency).

Method Detail

capacity

public int capacity()

The maximum multi-programming level supported (from the constructor).

Returns:

The maximum vertex count.

See Also:

size()

size

public int size()

The current multi-programming level. This is simply the #of distinct transactions in the WAITS_FOR relationship or alternatively the #of vertices in the DAG.

Returns:

The vertex count.

See Also:

capacity()

isFull

public boolean isFull()

Return true iff adding another transaction would exceed the configured multi-programming capacity.

releaseVertex

public boolean releaseVertex(Object tx)

Releases the vertex by (a) removing it from the mapping and (b) updating the list of available indices.

Parameters:

tx -

Returns:

true iff the vertex was known. FIXME Should it be an error if there is an edge remaining for that vertex? if we do not detect this condition then is is possible that uncleared edges will remainin in the WAITS_FOR graph and will interfere with reuse of the recycled index?

addEdge

public void addEdge(Object blocked,
                    Object running)
             throws DeadlockException

Add an edge to the DAG. The edge has the semantics blocked -> running[ i ], i.e., the blocked transaction WAITS_FOR the running transaction.

Parameters:

blocked - A transaction. If the transaction is not already registered as a vertex of the graph, then it is implicitly declared by this method. See lookup(Object, boolean).

running - A different transaction. If the transaction is not already registered as a vertex of the graph, then it is implicitly declared by this method. See lookup(Object, boolean).

Throws:

IllegalArgumentException - If either argument is null.

IllegalArgumentException - If the same transaction is specified for both arguments.

IllegalStateException - If the described edge already exists.

DeadlockException - If adding the edge to the DAG would result in a cycle. The state of the DAG is unchanged if this exception is thrown.

toString

public String toString()

Returns a representation of the state of the graph suitable for debugging the algorithm.

Overrides:

toString in class Object

addEdges

public void addEdges(Object blocked,
                     Object[] running)
              throws DeadlockException

Add a set of edges to the DAG. Each edge has the semantics blocked -> running[ i ], i.e., the blocked transaction WAITS_FOR the running transaction.

Parameters:

blocked - A transaction that is blocked waiting on one or more transactions.

running - One or more transactions in the granted group for some resource.

Throws:

IllegalArgumentException - If either argument is null.

IllegalArgumentException - If any element of running is null.

IllegalArgumentException - If blocked == running[ i] for any element of running .

IllegalArgumentException - If running.length is greater than the capacity of the DAG.

IllegalStateException - If creating the described edges would cause a duplicate edge to be asserted (either the edge already exists or it is defined more than once by the parameters).

DeadlockException - If adding the described edges to the DAG would result in a cycle. The state of the DAG is unchanged if this exception is thrown.

hasEdge

public boolean hasEdge(Object blocked,
                       Object running)

Return true iff the described edge exists in the graph.

Parameters:

blocked - A transaction.

running - A different transaction.

Returns:

true iff the edge exists.

Throws:

IllegalArgumentException - If either argument is null.

IllegalArgumentException - If the same transaction is specified for both arguments.

getEdges

public TxDag.Edge[] getEdges(boolean closure)

Return an array of the edges asserted for the graph. The length of the array is the #of in use transactions in the graph. Each element of the array represents a single edge. The state of the returned object is current as of the time that this method executes and is not maintained.

Returns:

Return the edges of the graph. The edges are not in any particular order.

See Also:

TxDag.Edge

removeEdge

public void removeEdge(Object blocked,
                       Object running)

Removes an edge from the DAG.

Note: This method does NOT does not recycle the vertex associated with a transaction which no longer has any incoming or outgoing edges. See removeEdges(Object, boolean).

Parameters:

blocked - A transaction which is currently waiting on running .

running - Another transaction.

Throws:

IllegalArgumentException - If either argument is null.

IllegalArgumentException - If the same transaction is specified for both arguments.

IllegalStateException - If the described edge does not exist.

removeEdges

public void removeEdges(Object tx,
                        boolean waiting)

Remove all edges whose target is tx. This method SHOULD be used when a running transaction completes (either aborts or commits). After calling this method, the transaction is removed completely from the DAG. Failure to use this method will result in the capacity of the DAG being consumed as vertices will not be recycled unless you call releaseVertex(Object).

Parameters:

tx - A transaction.

waiting - When false, caller asserts that this transaction it is NOT waiting on any other transaction. This assertion is used to optimize the update of the path count matrix by simply removing the row and column associated with this transaction. When [waiting == true], a less efficient procedure is used to update the path count matrix.

Do NOT specify [waiting == false] unless you know that the transaction is NOT waiting. In general, this knowledge is available to the 2PL locking package.

TODO:

Write test cases for this method. It duplicates much of the logic of removeEdge(Object, Object) and therefore must be evaluated separately.