In a computing context, “deadlock” refers to a condition when two or more processes are each waiting for a resource held by another process, or when more than two processes are waiting for resources in a circular chain. Generally, only a process holding a resource may release the resource, and typically a process will not release the resource until processing has been completed.
Consider an enterprise service oriented architecture (SOA) environment, which can be seen as a set of web services deployed on middleware associated with a number of web service containers. One web service exposes a number of operations/methods and a method implementation may invoke one or more methods of other web services (often referred to as “nested calls”). A web service container typically hosts a number of web services and provides various resources that are necessary to process the requests made to the respective web service methods. Resources provided by the container are shared among processing of different requests to web service methods. A processing thread, or simply a “thread,” is one such resource.
In prevalent design of web service containers, the web service container maintains a pool of threads, often referred to as a “thread pool.” When a request for a web service method arrives at the container, it picks an available thread in the thread pool and allocates the thread to process the request. If there is no thread available in the thread pool, the request is added to a waiting queue. The allocated thread is not released until the processing of the request has been completed. When a thread is released back into the thread pool, it is allocated to a request waiting in the queue, if any, based on a prescribed queuing policy (e.g., first-in first-out (FIFO)).
Typically, an upper bound is kept on the number of threads in the thread pool. This upper bound is established for various performance reasons, including, but not limited to, the significant cost of the overhead associated with thread management. Due to the upper bound on the thread pool size, various scenarios in a distributed SOA environment can lead to distributed deadlock. These scenarios may include cases where no cycles are present at a service component layer. Consider the following illustrative scenario:                two web services containers, C1 and C2, each having an upper bound of one on the thread pool size.        Container C1 hosts two web services methods, M1 and M1-2. Container C2 hosts two web services methods, M2 and M2-1.        Implementation of method M1-2 invokes method M2, and implementation of method M2-1 invokes method M1.        
Now consider a situation when container C1's thread and container C2's thread are allocated to web service requests for methods M1-2 and M2-1, respectively. During the processing of these methods, M1-2 invokes method M2, and method M2-1 invokes method M1, but none of these nested calls can be processed since, in both containers, all threads (one thread each) are busy and thus no threads are available for allocation to these requests. Furthermore, the threads will not be released by the ongoing requests processing methods M1-2 and M2-1 since completion of their respective processing is dependent on the completion of these nested calls. Accordingly, a deadlock situation arises. Even when the upper bound on the size of the thread pool is greater than one, such deadlocks can occur due to concurrent transactions.
The deadlock problem is not new in distributed systems and has been a subject of interest from theoretical as well as practical perspectives. However, in enterprise component middleware, deadlock was not observed as frequently, since a tiered architecture was the most common style of developing applications. As SOA becomes more widespread as an architecture style for reusing business functions in the form of web services and describing business processes in the form of composite services, there is a motivation to find efficient solutions for the deadlock problem.
In distributed systems, three major strategies that are applicable to handling deadlock are: deadlock prevention (e.g., designing offline resource requesting protocols); deadlock detection and recovery, which includes development of algorithms for detecting deadlock in a system and providing measures to bring the system back to a deadlock-free state; and deadlock avoidance, which includes development of online control policies that keep track of current resource allocation status, possibly combined with information about future process resource requirements, to keep the system away from deadlock states.
Conventional methodologies for deadlock detection and recovery generally involve maintaining a wait-graph of requests and preempting processes (e.g., removing a resource from a process) when deadlock is detected, which is undesirable. With regard to deadlock avoidance, one classic deadlock avoidance algorithm for non-distributed systems is the well-known Dijkstra's Banker's algorithm. However, for distributed systems, the general solution to distributed deadlock is impractical since it requires global atomic actions, or distributed synchronization.
Accordingly, there exists a need for deadlock prevention techniques that do not suffer from one or more of the limitations exhibited by conventional approaches.