Saturday, March 24, 2007

Thread starvation in shared thread pool

What is thread starvation?
Starvation describes a situation where a thread is unable to gain regular access to shared resources and is unable to make progress. This happens when shared resources are made unavailable for long periods by "greedy" threads. For example, suppose an object provides a synchronized method that often takes a long time to return. If one thread invokes this method frequently, other threads that also need frequent synchronized access to the same object will often be blocked.
(see "Sun tutorial on Concurrency")

What is thread pool and how it is used?
Obviously, thread pool contains a "pool" of threads and simply allows applications to reuse multiple threads. In JDK1.5 Concurrency package, an task executor manages a thread pool, and decides when to create a new thread or reuse an existing thread from the pool. When a new task is submitted to the executor, the executor checks to see if there are any "free" threads in the pool. If there are free threads, executor simply grab the thread out of the pool. If there are no "free" threads, executor push the task to a task queue. When the task queue reaches its limit, executor checks if it's possible to create a new thread in the pool. Thread pool has a core size and a max size. Executor will only create new thread when the task queue if full, all running threads are busy, and number of running threads is less than the max size.

What is the problem with sharing thread pool in an application?
When using a shared thread pool across an application, starvation can happen when parent threads and child threads are sharing the same thread pool.
Let's say that we have a shared thread pool with core size 2, max size 5 and a blocking task queue with size of 10.
Step 1. A parent thread P needs to run concurrent tasks. It submits 2 tasks to the executor. The executor will create 2 threads in the thread pool. The two threads are off running.
Step 2. One of the child thread, C1 only needs to run some concurrent tasks. It submits 5 tasks to the executor. The executor realizes that there are no more free threads in the pool (since the core size is only 2) so it pushes the task to the task queue.
Step 3. Now, P is waiting for C1 to finish. However, C1's child tasks are in the queue and they won't be executed until the queue is full and executor creates new threads in the pool. C1 will never return, and P will be blocked forever.

What to do now?
Sharing a thread pool in a application is ok as long as all the threads are on the same level. But to avoid the problem, it's a better to just not to use a global thread pool.

No comments: