The Problem with Threads

Threads are a fact of life for the modern programmer. They can be found eveywhere, even on embedded systems. However, threads destroy determinism and make it much harder to reliably predict how your program will behave.

We are familiar with the types of problems that arise from using threads: mutal exclusion, deadlocks, priority inversion, and blocking inappropriately. We have developed tools to work around these problems, but we have been unable to eliminate these problems from our software. What makes threading so hard for us to grasp and implement successfully?

In "The Problem With Threads", Edward A. Lee dives into the issues with threading and our sequential programming models. He provides some tools, frameworks, and alternative languages to help address concurrent programming problems. Lee also points out the limitations with many of these approaches and provides his thoughts on the future of concurrent software development.

Even if you don't change the tools that you use, it is important to understand their limitations. Threads are everywhere - use them carefully and be aware of the consequences.

Although threads seem to be a small step from sequential computation, in fact, they represent a huge step. They discard the most essential and appealing properties of sequential computation: understandability, predictability, and determinism.

Read "The Problem With Threads".


My Highlights

From the abstract:

Threads, as a model of computation, are wildly nondeterministic, and the job of the programmer becomes one of pruning that nondeterminism

Rather than pruning nondeterminism, we should build from essentially deterministic, composable components. Nondeterminism should be explicitly and judiciously introduced where needed, rather than removed where not needed.

Humans and Concurrency:

Sutter and Larus observe [47] “humans are quickly overwhelmed by concurrency and find it much more difficult to reason about concurrent than sequential code. Even careful people miss possible interleavings among even simple collections of partially ordered operations.”

The blame does not rest on our brains, but on the model we have chosen to adopt:

Yet humans are actually quite adept at reasoning about concurrent systems. The physical world is highly concurrent, and our very survival depends on our ability to reason about concurrent physical dynamics. The problem is that we have chosen concurrent abstractions that do not even vaguely resemble the concurrency of the physical world. We have become so used to these computational abstractions that we have lost track of the fact that they are not immutable.

Alternatives to threads mentioned in the article:

  • MapReduce pattern
  • data parallel language extensions
  • message passing libraries
  • PVM
  • MPI
  • OpenMP

Coordination languages or extensions mentioned by Lee:

  • Split-C
  • Cilk

Alternative concurrency models in embedded systems:

Embedded computing also exploits concurrency models other than threads. Programmable DSP architectures are often VLIW machines. Video signal processors often combine SIMD with VLIW and stream processing. Network processors provide explicit hardware support for streaming data. However, despite considerable innovative research, in practice, programming models for these domains remain primitive. Designers write low-level assembly code that exploits specific hardware features, and combine this assembly code with C code only where performance is not so critical.

Threads destroy the goals of reliability and predictability:

An interesting property of many embedded applications is that reliability and predictability are far more important than expressiveness or performance. It is arguable that this should be true in general purpose computing, but that’s a side argument. I will argue that achieving reliability and predictability using threads is essentially impossible for many applications.

We conclude that with threads, there is no useful theory of equivalence.

Threads, on the other hand, are wildly nondeterministic. The job of the programmer is to prune away that nondeterminism. We have, of course, developed tools to assist in the pruning. Semaphores, monitors, and more modern overlays on threads (discussed in the following section) offer the programmer ever more effective pruning. But pruning a wild mass of brambles rarely yields a satisfactory hedge.

Our inabiliity to squash concurrency bugs will result in an annoying future where our old software doesn't work.

I speculate that most multithreaded programs have such bugs. I speculate further that the bugs have not proved to be major handicaps only because today’s architectures and operating systems deliver modest parallelism. The cost of context switching is high, so only a tiny percentage of the possible interleavings of thread instructions ever occur in practice. I conjecture that most multi-threaded general-purpose applications are, in fact, so full of concurrency bugs that as multi-core architectures become commonplace, these bugs will begin to show up as system failures.

Choose when to add nondeterminism. Don't accept it as the fact of life.

In all four cases (rendezvous, PN, SR, and DE), we have started with a fundamentally deterministic (and concurrent) interaction mechanism (deterministic in the sense of the computation being performed, though in the first three cases not deterministic in the sense of timing). Nondeterminism has been judiciously introduced exactly where needed. This style of design is very different from the threads style, which starts with a wildly nondeterministic interaction mechanism and attempts to prune away undesired nondeterminism.

If we have alternatives, why are threads so dominant?

The fact is that alternatives to threads have been around for a long time, and yet threads dominate the concurrent programming language landscape. There are, in fact, many obstacles to these alternatives taking root. Probably the most important is that the very notion of programming, and the core abstractions of computation, are deeply rooted in the sequential paradigm. The most widely used programming languages (by far) adhere to this paradigm. Syntactically, threads are either a minor extension to these languages (as in Java) or just an external library. Semantically, of course, they thoroughly disrupt the essential determinism of the languages. Regrettably, programmers seem to be more guided by syntax than semantics. The alternatives to threads that have taken root, like MPI and OpenMP, share this same key feature. They make no syntactic change to languages. Alternatives that replace these languages with entirely new syntax, such as Erlang or Ada, have not taken root, and probably will not. Even languages with minor syntactic modifications to established languages, like Split-C or Cilk, remain esoteric.

Nice note on libraries:

However, building on them using only libraries is not satisfactory. Libraries offer little structure, no enforcement of patterns, and few composable properties.