A Concurrent Affair

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.”

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

public class RenderPageTask implements Callable {
public String call() throws Exception {
Future 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
}
}
}
[/cc_java]

This is the same situation that we’ve often encountered, and that I have written about in papers and my theses, namely calling [cc_java inline=”true”]SwingUtilities.invokeAndWait(Runnable r)[/cc_java] 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 [cc_java inline=”true”]ListenableFuture[/cc_java] to register a listener or callback that gets executed when the future finishes.

[cc_java]
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);
}
}
}
[/cc_java]

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.

My old Dell Dimension 9200 computer broke yesterday. I took a look at it today and couldn’t figure out what the problem was. Just diagnostic lights 1, 2, and 3 lit, which according to Dell’s Users Guide means “other failure.” I checked all hard drive and power connectors, re-seated all RAM modules and extension cards, to no avail.

I had thought before that maybe I have too many computers in the house, definitely more than I need. I don’t do as much with my computers at home anymore, so I didn’t put as much energy into fixing the Dimension 9200 as I would have in the past.

Still, this was a good computer. I bought it in January 2007, and with its 2.4 GHz Core 2 Duo CPU, 2 GB of RAM (later 4 GB), and 7200 RPM SATA hard drive, it greatly sped up a lot of my research work in grad school. It had a great, simple, and expandable case.

I do have to admit, though, that a few years ago, the power supply gave out, and I had to replace it. The computer that it replaced was rather short-lived, from mid-2005 to January 2007. The computer before that, a Pentium III 733 MHz from Micron, lasted me from the beginnings of undergrad in August 2000 until I moved to Seattle in 2011 (although it wasn’t my primary machine anymore after mid-2005).

I’ll miss the Dimension 9200.

I’ve been working with [cc_java inline=”true”]ThreadPoolExecutor[/cc_java] and [cc_java inline=”true”]RejectedExecutionHandler[/cc_java]. The executor framework provides a convenient way to distribute concurrent tasks to multiple threads, and the different [cc_java inline=”true”]RejectedExecutionHandler[/cc_java] policies, [cc_java inline=”true”]ThreadPoolExecutor.DiscardOldestPolicy[/cc_java], for instance, enable your program to shed load if there is more work than it can reliably handle.

Unfortunately, when I started using [cc_java inline=”true”]Future[/cc_java]s, things became complicated. Consider the following example:

[cc_java]
ThreadPoolExecutor es = new ThreadPoolExecutor(10, 10, 1, TimeUnit.MINUTES, new ArrayBlockingQueue(10),
new ThreadPoolExecutor.DiscardOldestPolicy());

List> futures = Lists.newArrayList();
for(int i=0; i<30; ++i) { final int ii = i; futures.add(es.submit(new Callable() {
public Integer call() {
System.out.println(“Running task ” + ii);
try {
Thread.sleep(1000);
} catch(InterruptedException e) {
// ignore
}
System.out.println(“Task ” + ii + ” ends”);
return ii;
}
}));
}

for(Future f: futures);
System.out.println(“Result: ” + f.get());
}
[/cc_java]

It creates a thread pool with a maximum of 10 threads, and a work queue that can hold another 10 items. The policy to shed load is [cc_java inline=”true”]ThreadPoolExecutor.DiscardOldestPolicy[/cc_java], which means it will favor newer tasks over older tasks, if the queue has reached its capacity.

Then the program creates 30 tasks and submits them to the executor service. The tasks each sleep for a second to make sure we actually hit the capacity of the thread pool executor. As a result, only 20 can be submitted (10 running, but sleeping, and another 10 in the work queue), and 10 need to be rejected. The tasks that are rejected are actually the ones that were in the queue first (the older tasks), so we can expect tasks 0 to 9 as well as 20 to 29 to execute.

There is a problem, however, when we wait for the results of tasks 10 to 19 by calling their [cc_java inline=”true”]Future.get()[/cc_java] methods: Because the tasks have been rejected, they never start running, which means they will never finish. The program hangs here.

The only [cc_java inline=”true”]RejectedExecutionHandler[/cc_java]s in the JDK that function correctly here are [cc_java inline=”true”]ThreadPoolExecutor.AbortPolicy[/cc_java] and [cc_java inline=”true”]ThreadPoolExecutor.CallerRunsPolicy[/cc_java]. [cc_java inline=”true”]ThreadPoolExecutor.AbortPolicy[/cc_java] throws a [cc_java inline=”true”]RejectedExecutionException[/cc_java] at the time the task is submitted to the executor service already, not later, and therefore does not return a [cc_java inline=”true”]Future[/cc_java] to wait for. [cc_java inline=”true”]ThreadPoolExecutor.CallerRunsPolicy[/cc_java] executes the task at the time it is executed at the time it is added to the executor service, and while it returns a [cc_java inline=”true”]Future[/cc_java], that [cc_java inline=”true”]Future[/cc_java] is done immediately, and therefore, getting the [cc_java inline=”true”]Future[/cc_java]’s result later will not block.

But what’s the right thing to do here for [cc_java inline=”true”]ThreadPoolExecutor.DiscardPolicy[/cc_java] and [cc_java inline=”true”]ThreadPoolExecutor.DiscardOldestPolicy[/cc_java]? Submitting tasks with these policies does return a [cc_java inline=”true”]Future[/cc_java], but if the task is rejected, that [cc_java inline=”true”]Future[/cc_java] will never be done.

I haven’t found a good solution with the built-in classes of the JDK yet. What I have done now is to cancel the [cc_java inline=”true”]Future[/cc_java] in the [cc_java inline=”true”]RejectedExecutionHandler[/cc_java]. Unfortunately, that can’t easily be done with the existing [cc_java inline=”true”]RejectedExecutionHandler[/cc_java] policies, like [cc_java inline=”true”]ThreadPoolExecutor.DiscardOldestPolicy[/cc_java].

[cc_java]
public class DiscardAndCancelOldestPolicy implements RejectedExecutionHandler {
public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
if (!e.isShutdown()) {
Runnable rejected = e.getQueue().poll();
if (rejected instanceof Future) {
((Future) rejected).cancel(false);
}
e.execute(r);
}
}
}
[/cc_java]

[cc_java]
public class DiscardAndCancelPolicy implements RejectedExecutionHandler {
public void rejectedExecution(Runnable r, ThreadPoolExecutor e) {
if (r instanceof Future) {
((Future) r).cancel(false);
}
}
}
[/cc_java]

Now we can use those policies, and the program behaves as expected. For example:

[cc_java]
ThreadPoolExecutor es = new ThreadPoolExecutor(10, 10, 1, TimeUnit.MINUTES, new ArrayBlockingQueue(10),
new DiscardAndCancelOldestPolicy());

List> futures = Lists.newArrayList();
for(int i=0; i<30; ++i) { final int ii = i; futures.add(es.submit(new Callable() {
public Integer call() {
System.out.println(“Running task ” + ii);
try {
Thread.sleep(1000);
} catch(InterruptedException e) {
// ignore
}
System.out.println(“Task ” + ii + ” ends”);
return ii;
}
}));
}

for(Future f: futures);
try {
System.out.println(“Result: ” + f.get());
} catch(CancellationException e) {
System.out.println(“Task was cancelled”);
}
}
[/cc_java]

Note that now you have to catch the [cc_java inline=”true”]CancellationException[/cc_java] when getting the [cc_java inline=”true”]Future[/cc_java]’s result, because discarding the task will cancel the [cc_java inline=”true”]Future[/cc_java].

Guava’s [cc_java inline=”true”]Futures.successfulAsList[/cc_java] method makes things a bit easier if what you want to do is wait for all [cc_java inline=”true”]Future[/cc_java]s to finish, and then look at the results. It returns [cc_java inline=”true”]null[/cc_java] for failed or cancelled tasks, including the ones our policies reject:

[cc_java]
ThreadPoolExecutor tpe = new ThreadPoolExecutor(10, 10, 1, TimeUnit.MINUTES, new ArrayBlockingQueue(10),
new DiscardAndCancelOldestPolicy());
ListeningExecutorService es = MoreExecutors.listeningDecorator(tpe);

// …

Future> all = Futures.successfulAsList(futures);
List results = all.get();
[/cc_java]

Got something better?

Here is a raw transcript of my hand-written notes from the ACM Turing Centenary Celebration in San Francisco a couple of weeks ago.

Please note that these are my thoughts and impressions, not necessarily those of the speakers, and that it is quite possible that I misheard or misunderstood a few things, or that I incorrectly attributed the wrong person. If you think I made a mistake, please let me know.

Turing, the Man

• Turing was misunderstood and discriminated against. Who are the misfits now? Who should be supported?
• Turing’s mom thought the Turing Award maybe was an award given to long-distance runners. Turing was a runner.
• Apparently, none of the 32 Turing award laureates in the audience knew of Turing when they did their award-winning work? That is hard to believe. Knuth said he knew of Turing. Maybe I misunderstood the question.
• Knuth: Turing was the first person with the mind of a geek.
• Turing did things from first principles. That’s why Turing machines are more understandable than Church’s lambda calculus (says Dana Scott).

Human and Machine Intelligence

• Jim Gray: AI should speak like a native speaker, hear like a native speaker, and see like a person.
• Interesting definition: all humans can do that. But is this harder than playing chess or proving theorems? Interestingly, it is harder. The easy things are hard.
• Turing: We should build a “child machine” and educate it.
• Book: Human Problem Solving
• Emotions used to re-prioritize goals in multi-agent systems: agents behave better with emotions when there is a lot of uncertainty.
• Much human intelligence is stored, with fast recognition.
• Another reference to “Thinking Fast and Slow”.
• Raj Reddy: “When you have learned something, you store it so you can retrieve it instantly. You dedicate permanent memory to it.” Then why do we forget?
• Creativity: Brilliant move in Deep Blue vs. Kasparov, game 3. (look up)

What Computers Do: Model, Connect, and Engage

• Big data: physics, chemistry, biology, geology, social networks.
• But how much of the data is actually useful? “We only use 10% of our brains” myth, “We only use 10% of our bandwidth”.
• Connectivity, ubiquity, scaling, approximation, AI, reusable components, dependability, uncertainty: key concepts.
• Probability distributions, parameterized over the main, like lists, as standard data type?
• Catastrophe mode – few dependencies on a “catastrophe computing base”, similar to trusted computing base. Make tough choices, but keep your service going.
• Swap people between security and attackers is a good idea.
• Butler Lampson: “A new TCP connection for every mouse click? Madness!”

Systems Architecture, Design, Engineering, and Verification – The Practice in Research and Research in Practice

• Would Turing machines have had the same impact if it had many instructions as opposed to just a few, elegant ones?
• Biggest advances since Turing: operating systems, programming languages, networks.
• Future? Not so rosy, says Thompson.
• 50s: computers were accessible
• 60s: had become inaccessible because of economic concerns and batch computing
• Formal verification: Turing 49 paper, “Checking a Large Routine”
• What makes research practical?
  • Thompson: right people, right time
  • synergism, backing the right people, not just concrete goals
• “Nice theory symptom” – we often like a nice theory, ignore practical problems and needs
• Most software (e.g. incrementally written software) is difficult to verify.
• Airbus software is completely verifiable by design/

Extracting Energy from the Turing Tarpit

• 67% of fossil fuels are burned to create electricity.
• Think of our real goal. We don’t want to create electricity, we want to do something with it. Similarly: our goal is not to write millions of lines of code.
• Alan Kay: “The easiest way to predict the future is to prevent it.” – Lots of things that barely scaled when they were invented are still around and still do not scale.

The Turing Computational Model

• Widening gap between users and programmers. Users’ expectation and programmers accomplishments.
• 1960s customs are a source of bugs. We don’t see them as just customs, though, we see them more as “laws”.
• 
• 
• Big-oh does generally not take into account communication costs. What if communication costs become dominant, or if it can break down?
• Vivek Sarkar: “What about energy? It seems like the Turing model is good to account for energy, as it takes energy to move the tape.

Computer Architecture

• Sutherland: communication dominates logic in hardware; we must begin to use clock-free designs.
• Fred Brooks: Turing’s ACE Pilot architecture assumed hardware is expensive and dear, and programmers are abundant and cheap.
• Chuck Thacker: “Cutting it [knowledge about the way computers work] off at the C computer level seems limiting.”

Programming Languages – Past Achievements and Future Challenges

• Nicklaus Wirth: “We don’t teach programming anymore. Students come to university already knowing it.” Really? IT seems like he is talking about wasteful programming.
• Liskov:
  • programming methodology first; then maybe find some programming language features that help.
  • Software architects: “Settle on a simple memory model. If all we can do is put in fences because we can’t reason about it, we haven’t achieved much.”
  • We now teach with Python. We may create a generation of programmers who don’t understand the importance of modularity.
• Wirth: “Vicious cycle between language used in academia and industry; can only be broken at the university.”

An Algorithmic View of the Universe

• Valiant (?): Turing pointed out “cultural search”, how science progresses.
• CS undergrads not interested in natural science applications. Should there be an explicit unit that introduces them to science applications?
• Karp:
  • “In biology, form is function. Protein folding determines what the protein does.”
  • X-ray crystallography vs. computed folding:
  • Computed folding is computation; therefore, X-ray crystallography is too.
  • Figuring out folding is NP-complete ==> X-ray crystallography is NP-complete
  • How long will it take for a protein to fold? CS can tell biologists: exponential time!
• Adleman:
  • Learned a lot about being a computer scientist in another field. Biologists don’t talk our language. It’s easy to solve the wrong problem.
  • Biologists may want a sample of not-quite-optimal solutions, but faster.
  • CS can contribute a lot with its “algorithmic lens,” but we need to meet with our “customers.”
• Tarjan: learn with skepticism, challenge your instructors and the papers you read — that’s where you’ll find problems to solve.
• Union set: O(inverse Ackerman) – crazy but true
• Can another Turing come along? “Yes. It’s not so important to know everything, but to have the ability to understand everything.” And perhaps to know of everything.
• Favorite algorithms: Shrinking blossoms algorithm (look up)
• Hungarian algorithm for assignment problem
• Is the strong Turing thesis enough to preclude time travel?
• Least favorite algorithms: Adleman, genetic algorithms. “We don’t understand the problem, so we hope the computer will understand.” Genetic algorithm idea taken from biology; why assume that the problem space is the same? But if it works (well enough)? Who says genetics in biology (mutation, sexual reproduction) is the best way to evolve?

Information, Data, Security in a Networked Future

• Shamir: “Codebreakers at Blethley Park not a victory of human brilliance over machines, but a victory of machine power (exhaustive search) over human stupidity (Enigma operator mistakes).”
• Rivest: “Calling a string ‘secret key’ does not make it secret.”
• Maybe we need an attitude adjustment: secret keys are secret most of the time. Users don’t make errors most of the time. That helps recover.
• Many security problems are caused by human error. What can technology do to make humans more trustworthy and compliant?
• Privacy/trust in social networks: needs to be an open architecture.

Again, these are my notes. In particular, all mistakes are mine. Caveat lector.

I absolutely love my Kindle Touch. I’ve already read two books, which embarrassingly is as much as I read all last year. I was skeptical about how easy it is to read, but it’s just as good as reading on paper. Perhaps better. I also would have expected that I’d be more careful with an electronic device, but interestingly, it’s just the opposite: I put it in my pocket, because I’m not worried about bending or tearing pages.

I also bought Legend of Grimrock a couple of weeks ago. Tonight, I finally installed it, and it looks and plays great. I think it could turn into another addiction. You can’t imagine how big this is: It’s the first video game I’ve bought in probably 15 years.

On Wednesday night, I went to Chez Shea in Seattle for dinner. It was fantastic. The food was delicious, and our waitress was great: knowledgeable, polite, attentive, but not pushy.

As appetizers, we had new potatoes and braised fennel salad with tarragon creme fraiche, pickled mustard seed vinaigrette and frisee; as well as Gruyere, spring onion and mushroom tart with baby arugula and jicama salad. The new potatoes were simple, clean, and appealing, and the Gruyere tart was decadent and rich.

Because our next dishes were running a bit behind, we got to try English pea soup, which had a hint of mint in it.

As main course, we chose pan-seared sockeye salmon on green lentils, shiitake mushrooms with bacon, rapini and caper brown butter; and potato gnocchi
with parsley and arugula pesto, roasted tomatoes, parmigiano reggiano, and toasted pine nuts.

Desert chocolate mousse and vanilla creme brulee. As drinks, we had a glass of La Chablisienne, a 2010 French Sauvignon Blanc; a glass of Chateau d’Oupia, a 2010 French Carignan/Syrah/Grenache blend; as well as something called “French Connection”, which was an mandarine-orange flavored drink with green chartreuse in it (can’t find the recipe for that version).

It was a fabulous meal and a great evening. Chez Shea could easily be my favorite Seattle restaurant. Unfortunately, it is closing at the end of this month. So it goes.

Weather forecast for Seattle:

Showers likely. Cloudy with chance of rain in the evening. Then rain likely after midnight.

I’m not even kidding. Those are the first three sentences of the current weather forecast on my phone.

Something anyone writing a paper or doing a presentation needs to keep in mind: Communication.

Here’s the mouseOver text for the image: “Anyone who says that they’re great at communicating but ‘people are bad at listening’ is confused about how communication works.”

Thanks, xkcd.