Page History

...

Contrary to what is expected, this program does not print the total count, that is, the number of times doSomething() is invoked. This is because it is susceptible to a thread starvation deadlock because the size of the thread pool (10) does not allow either thread from perTab() to invoke the doSomething() method. The output of the program varies for different values of numberOfTimes and the thread pool size. Note that different threads are allowed to invoke doSomething() in different order; we are concerned only with the maximum value of count to determine how many times the method executed.

Compliant Solution

This compliant solution selects tasks for scheduling and avoids the thread starvation deadlock. Every level (worker) must have a double ended queue where all sub-tasks are queued. Each level removes the most recently generated sub-task from the queue so that it can process it. When there are no more threads left to process, the current level runs the least-recently created sub-task of another level by picking and removing it from that level's queue.

This compliant solution sets the {{CallerRuns}} policy on a {{ThreadPoolExecutor}}, and uses a synchronous queue \[[Gafter 06|AA. Java References#Gafter 06]\].

public class BrowserManager {
  static ThreadPoolExecutor pool =
    new ThreadPoolExecutor(0, 10, 60L, TimeUnit.SECONDS,
                          new SynchronousQueue<Runnable>());
  int numberOfTimes;
  private static volatile int count = 0;

  static {
    pool.setRejectedExecutionHandler(
    new ThreadPoolExecutor.CallerRunsPolicy());
  }

  // ... 
}	

According to the Java API, class java.util.concurrent.ThreadPoolExecutor.CallerRunsPolicy documentation:

A handler for rejected tasks that runs the rejected task directly in the calling thread of the execute method, unless the executor has been shut down, in which case the task is discarded.

This compliant solution is subject to the vagaries of the thread scheduler which may not optimally schedule the tasks, however, it avoids the thread starvation deadlock.

Risk Assessment

Executing interdependent tasks in a thread pool can lead to denial of service.

...