Why does "header.get() + footer.get()" result in deadlock, when using a single threaded Executor? [duplicate]

Question

This is listing 8.1 in Java Concurrency In Practice:

public class ThreadDeadlock  {
   ExecutorService exec = Executors.newSingleThreadExecutor();

   public class RenderPageTask implements Callable<String>  {
      public String call() throws Exception  {
         Future<String> header, footer;
         header = exec.submit(new LoadFileTask("header.html"));
         footer = exec.submit(new LoadFileTask("footer.html"));
         String page = renderBody();

         //Will deadlock -- task waiting for result of subtask
         return header.get() + page + footer.get();
      }
   }
}

It's in

Chapter 8: Thread Pools > Section 8.1.1 Thread starvation deadlock

and has the caption:

"Task that deadlocks in a single-threaded Executor. Don't do this."

Why does this result in a deadlock? I thought header.get() is called, and then footer.get() is called, which each result appended to the string. Why wouldn't a single threaded Executor be enough to run these one after the other?

Relevant chapter text:

8.1.1 Thread starvation deadlock

If tasks that depend on other tasks execute in a thread pool, they can deadlock. In a single-threaded executor, a task that submits another task to the same executor and waits for its result will always deadlock. The second task sits on the work queue until the first task completes, but the first will not complete because it is waiting for the resut of the second task. The same thing can happen in larger thread pools if all threads are executing tasks that are blocked waiting for other tasks still on the work queue. This is called thread starvation deadlock, and can occur whenever a pool task initiates an unbounded blocking wait for some resource or condition that can succeed only through the action of another pool task, such as waiting for the return value or side effect of another task, unless you can guarantee that the pool is large enough.

ThreadDeadlock in Listing 8.1 illustrates thread starvation deadldock. RenderPageTask submits two additional tasks to the Executor o fetch the page header and footer, renders the page body, waits for the results of the header and footer tasks, and then combines the header, body, and footer into the finished page. With a single-threaded executor, ThreadDeadlock will always deadlock. Similarly, tasks coordinating amongst themselves with a barrier could also cause thread starvation deadlock if the pool is not big enough.

Answer 1

The actual deadlock will occur will occur as soon as an instance of RenderPageTask is submitted to the very same executor instance where it submits its task.

For example, add

exec.submit(new RenderPageTask());

and you will experience a deadlock.

Of course this can be considered a problem of the surrounding code (i.e., you could simply define and document that your RenderPageTask should not be submitted to this executor instance), but a good design would avoid such pitfalls entirely.

A possible solution for this would be to use ForkJoinPool, which uses work stealing to avoid this form of possible deadlocks.