Bounded thread pools allow the programmer to specify an upper limit on the number of threads that can concurrently execute in a thread pool. Programs must not use threads from a bounded thread pool to execute tasks that depend on the completion of other tasks in the pool.
A form of deadlock called thread-starvation deadlock arises when all the threads executing in the pool are blocked on tasks that are waiting on an internal queue for an available thread in which to execute. Thread-starvation deadlock occurs when currently executing tasks submit other tasks to a thread pool and wait for them to complete and the thread pool lacks the capacity to accommodate all the tasks at once.
This problem can be confusing because the program can function correctly when fewer threads are needed. The issue can be mitigated, in some cases, by choosing a larger pool size. However, determining a suitable size may be difficult or even impossible.
Similarly, threads in a thread pool may fail to be recycled when two executing tasks each require the other to complete before they can terminate. A blocking operation within a subtask can also lead to unbounded queue growth [Goetz 2006].
Noncompliant Code Example (Interdependent Subtasks)
This noncompliant code example is vulnerable to thread-starvation deadlock. It consists of the
ValidationService class, which performs various input validation tasks such as checking whether a user-supplied field exists in a back-end database.
fieldAggregator() method accepts a variable number of
String arguments and creates a task corresponding to each argument to enable concurrent processing. The task performs input validation using the
In turn, the
ValidateInput class attempts to sanitize the input by creating a subtask for each request using the
SanitizeInput class. All tasks are executed in the same thread pool. The
fieldAggregator() method blocks until all the tasks have finished executing and, when all results are available, returns the aggregated results as a
StringBuilder object to the caller.
Assume, for example, that the pool size is set to 6. The
ValidationService.fieldAggregator() method is invoked to validate six arguments; consequently, it submits six tasks to the thread pool. Each task submits a corresponding subtask to sanitize the input. The
SanitizeInput subtasks must execute before the original six tasks can return their results. However, this is impossible because all six threads in the thread pool are blocked. Furthermore, the
shutdown() method cannot shut down the thread pool when it contains active tasks.
Thread-starvation deadlock can also occur when a single-threaded
Executor is used, for example, when the caller creates several subtasks and waits for the results.
Compliant Solution (No Interdependent Tasks)
This compliant solution modifies the
ValidateInput<V> class so that the
SanitizeInput tasks are executed in the same threads as the
ValidateInput tasks rather than in separate threads. Consequently, the
SanitizeInput tasks are independent, which eliminates their need to wait for each other to complete. The
SanitizeInput class has also been modified to omit implementation of the
Thread-starvation issues can be partially mitigated by choosing a large thread pool size. However, an untrusted caller can still overwhelm the system by supplying more inputs (see TPS00-J. Use thread pools to enable graceful degradation of service during traffic bursts).
Note that operations that have further constraints, such as the total number of database connections or total
ResultSet objects open at a particular time, impose an upper bound on the usable thread pool size, as each thread continues to block until the resource becomes available.
ThreadLocal variables may be used to maintain local state in each thread. When using thread pools, the lifetime of
ThreadLocal variables should be bounded by the corresponding task [Goetz 2006]. Furthermore, programs must not use these variables to communicate between tasks. There are additional constraints in the use of
ThreadLocal variables in thread pools (see TPS04-J. Ensure ThreadLocal variables are reinitialized when using thread pools for more information).
Noncompliant Code Example (Subtasks)
This noncompliant code example contains a series of subtasks that execute in a shared thread pool [Gafter 2006]. The
BrowserManager class calls
perUser(), which starts tasks that invoke
perProfile() method starts tasks that invoke
perTab(), and in turn,
perTab starts tasks that invoke
BrowserManager then waits for the tasks to finish. The threads are allowed to invoke
doSomething() in any order, provided that
count correctly records the number of methods executed.
Unfortunately, this program is susceptible to a thread-starvation deadlock. For example, if each of the five
perUser tasks spawns five
perProfile tasks, where each
perProfile task spawns a
perTab task, the thread pool will be exhausted, and
perTab() will be unable to allocate any additional threads to invoke the
Compliant Solution (
This compliant solution selects and schedules tasks for execution, avoiding thread-starvation deadlock. It sets the
CallerRunsPolicy on a
ThreadPoolExecutor and uses a
SynchronousQueue [Gafter 2006]. The policy dictates that when the thread pool runs out of available threads, any subsequent tasks will run in the thread that submitted the tasks.
According to Goetz and colleagues [Goetz 2006]:
SynchronousQueueis not really a queue at all, but a mechanism for managing handoffs between threads. In order to put an element on the
SynchronousQueue, another thread must already be waiting to accept the handoff. If no thread is waiting, but the current pool size is less than the maximum,
ThreadPoolExecutorcreates a new thread; otherwise, the task is rejected according to the saturation policy.
a handler for rejected tasks that runs the rejected task directly in the calling thread of the
executemethod, unless the executor has been shut down, in which case, the task is discarded.
In this compliant solution, tasks that have other tasks waiting to accept the hand-off are added to the
SynchronousQueue when the thread pool is full. For example, tasks corresponding to
perTab() are added to the
SynchronousQueue because the tasks corresponding to
perProfile() are waiting to receive the hand-off. Once the pool is full, additional tasks are rejected according to the saturation policy in effect. Because the
CallerRunsPolicy is used to handle these rejected tasks, all the rejected tasks are executed in the main thread that started the initial tasks. When all the threads corresponding to
perTab() have finished executing, the next set of tasks corresponding to
perProfile() are added to the
SynchronousQueue because the hand-off is subsequently used by
CallerRunsPolicy allows graceful degradation of service when faced with many requests by distributing the workload from the thread pool to the work queue. Because the submitted tasks cannot block for any reason other than waiting for other tasks to complete, the policy guarantees that the current thread can handle multiple tasks sequentially. The policy would fail to prevent thread-starvation deadlock if the tasks were to block for some other reason, such as network I/O. Furthermore, this approach avoids unbounded queue growth because
SynchronousQueue avoids storing tasks indefinitely for future execution, and all tasks are handled either by the current thread or by a thread in the thread pool.
This compliant solution is subject to the vagaries of the thread scheduler, which might schedule the tasks suboptimally. However, it avoids thread-starvation deadlock.
Executing interdependent tasks in a thread pool can lead to denial of service.
Section 5.3.3, "Dequeues and Work Stealing"