Levi's Lisp Log

The Problem With Threads

I just read a Technical Report from UC Berkeley's EE/CS department entitled The Problem With Threads, which succinctly and clearly captures the problems with the concurrency mechanisms in our currently popular programming languages. It should be very readable to a lay programmer, since only a small section contains formalisms and most unfamiliar terms are defined in the text or footnotes.

To sum it up, threads (shared-memory concurrency) are an inappropriate method of bringing concurrency to a program because they destroy the inherent determinism of sequential programming languages. The tools we have to help deal with the nondeterminism only chip away at the combinatorial explosion of program interleavings, leaving so much opportunity for error that designing reliable and robust multithreaded software is futile.

The report notes that solutions to the problem that retain as much determinism as possible have existed for years, but have not caught on. The author suggests that instead of creating new programming languages, new coordination languages should be used to coordinate components written in familiar languages.

It's a very thought-provoking paper, and I think the conclusions are right on, as much as I'd like a new language to catch on. Massive concurrency is coming, and our current languages are not equipped to tackle it alone.

Software and Concurrency

As I was doing research for a paper, I hunted down Herb Sutter's article The Free Lunch Is Over: A Fundamental Turn Towards Concurrency in Software to find some passages that supported my thesis. There was quite a buzz about this article when it appeared in Dr. Dobb's Journal and C/C++ Users Journal earlier this year, as it seemed to capture and clearly explain the feeling so many people had been getting while watching what the CPU manufacturers have been doing lately. Everything's going multi-core, even video game processors.

Following a few links, I found that Sutter has written (with James Larus) another article on the subject, this time with a greater focus on software. It's Software and the Concurrency Revolution at the ACM Queue, and it's a broad look at the deficiencies of current programming languages and practices in the face of concurrency, and what sort of changes need to be made to face the future he sees, in which individual processor cores don't get much faster than they are today.

I'm convinced that Sutter's take on the future is at least mostly right, and these articles ought to be required reading for anyone who wants to take up or continue writing software.

Composable Memory Transactions

I've been doing a little bit of research into different ways of handling atomic operations on data in the face of concurrent threads of execution. The standard mutex/semaphore model is fraught with opportunities for programmer error and is difficult to reason about. It also becomes very unwieldy when composition of atomic operations is necessary. A possible solution is to use transactional memory and optimistic synchronization instead of mutexes. There's a good description of how this works in the paper Composable Memory Transactions. There's also an implementation of Optimistic Concurrency in Scheme48.