Prevention of deadlock in a distributed computing environment

1. A method of preventing deadlock in a distributed computing system, the method comprising the steps of:

receiving as input a sorted set of containers defining a unique global sequence of containers for servicing process requests;

populating at least one table based at least in part on off-line analysis of call graphs defining corresponding transactions for a given order of the containers in the sorted set, the at least one table comprising local information such that at run time each container uses the local information, without accessing a central point in the system and without accessing another container, for making decisions related to at least one of preemption, reservation, allocation and de-allocation of resources used for servicing the process requests;

storing within each container at least a portion of the at least one table;

allocating one or more threads in a given container according to at least a portion of the at least one table stored within the given container, the step of allocating one or more threads in a given container further comprising the steps of:

upon receiving a process request corresponding to a transaction, determining whether a unique identifier has been assigned to the request;

when a unique identifier has not been assigned to the request, generating a unique identifier and assigning the identifier and a transaction type to the request;

determining whether a thread is allocated for the transaction corresponding to the identifier;

when a thread has not been allocated for the transaction, determining whether a thread is reserved for the transaction corresponding to the identifier;

when a thread is not reserved for the transaction, sending a thread reservation request to at least one selected container in the sorted set of containers and allocating a thread to the process request based at least in part on at least one reservation reply from the at least one selected container;

when a thread is reserved for the transaction, allocating the reserved thread to the process request; and

adding an entry to an allocation table corresponding to the at least one selected container, the entry indicating that a thread has been allocated to the transaction corresponding to the identifier;

after processing a method corresponding to a transaction associated with the given container, determining whether a thread used to process the method corresponding to the transaction has been released back to a thread pool maintained by the container;

when the thread has been released back to the thread pool, removing an entry from an allocation table associated with the container, the entry corresponding to the transaction;

determining whether there is a corresponding entry for the transaction in a reservation table associated with the container;

when there is a corresponding entry for the transaction in the reservation table, decrementing a counter, the counter being used to track a number of entries corresponding to the transaction in the reservation table; and

when the counter has a value of zero, removing the entry corresponding to the transaction in the reservation table and returning the thread to the thread pool;

wherein the off-line analysis of call graphs comprises:

for a given call graph and a corresponding global container sequence, computing an ordered set CR(C) for an entry {tx-type, CR(C)} in a commanding table of a container C, where tx-type is a transaction type for the given call graph;

defining an ordering relation “>” between two containers C 1 and C 2 , such that C 1 > C 2 when C 1 comes before C 2 in the global container sequence;

defining an ordering relation “>” between two nodes (M 1 , C 1 ) and (M 2 , C 2 ) in the given call graph, such that (M 1 , C 1 )>(M 2 , C 2 ) when (M 1 , C 1 ) is an ancestor of (M 2 , C 2 ) in the given call graph;

computing all flows (F 1 , F 2 , . . . , F n ) present in the call graph, where n is an integer;

computing a set OoO((M, C), F i ) for every node (M, C) in flow F i according to an expression OoO((M, C), F i )={(M x , C x )|(M x , C x ) F i , (M, C)>(M x , C x ), C x >C}, where i is an integer, the set OoO((M, C), F i ) including nodes (M x , C x ) of the flow F i such that (M, C)> (M x , C x ) and C x >C; and

computing a set RT((M, C), F i ) including containers to whom container C will send thread reservation requests before allocating a thread to the flow.