Java Executors, Continuations, and Small Step Semantics

In my book club at work, we’re discussing the book Java Concurrency in Practice by Brian Goetz et al. This Tuesday, we talked about Chapter 8, Applying Thread Pools, and in particular about how to correctly size thread pools.

Listing 8.1 in the book points out what the authors call “thread starvation deadlock.”

1
2
3
4
5
6
7
8
9
10
11
12
13
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();
      return header.get() + page + footer.get(); // will deadlock -- task waiting for result of subtask
    }
  }
}

This is the same situation that we’ve often encountered, and that I have written about in papers and my theses, namely calling SwingUtilities.invokeAndWait(Runnable r) from within the event dispatch thread. The task A currently running in a thread is waiting for another task B to finish running in that thread, but task B can never even start because A is still running.

Here, of course, the problem is made deterministically repeatable because there is only one thread. The above code is guaranteed to deadlock. It is noteworthy that this kind of thread starvation deadlock can happen with multiple threads as well. Let’s say, for example, that our executor has 10 threads running. It is possible that all 10 of the threads run tasks that get to a point where they schedule a subtask and wait for that task’s completion. These tasks cannot be executed right away, so they go into a queue — and that’s where they will sit forever, at least if the queue can accommodate at least 10 subtasks. If submitting one of those tasks get rejected, then it is possible that the parent task fails and frees up a thread, but that’s still not certain.

After going back and forth in trying to either prevent bad things from happening, or at least detecting when they do, we came to the conclusion that submitting subtasks to the same executor from which the current thread originated is generally a bad idea.

The right thing to do is to schedule subtasks and return. The parent task should never wait for the subtasks. If you need to perform some kind of processing on the finished subtasks, you can use Guava’s ListenableFuture to register a listener or callback that gets executed when the future finishes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ThreadDeadlock {
  ListenableExecutorService exec =
    MoreExecutors.listeningDecorator(
      Executors.newSingleThreadExecutor());

  public class RenderPageTask implements Runnable {
    public void run() {
      final ListenableFuture<?> header, footer;
      header = exec.submit(new LoadFileTask("header.html"));
      footer = exec.submit(new LoadFileTask("footer.html"));
      final String page = renderBody();
      header.addListener(new Runnable() {
        public void run() {
          footer.addListener(new Runnable() {
            public void run() {
              String result = header.get() + page + footer.get();
              // now how do we get this result out?
            }
          }, exec);
        }
      }, exec);
    }
  }
}

What I thought was interesting here was that we were using continuations here. This may have been obvious to everyone else, but it had never occurred to me that the right way of using Java executors was by modeling continuations. Then my programming languages background kicked in, and I noticed that we were using a small-step semantics here. I’ve always felt that big-step is conceptually simpler to understand, but that small-step has so many advantages. Better, safer concurrency in Java is one I hadn’t considered.

Share

About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply