Threads and memory model for C++

Although some minor bug fixes are always likely, this effort has now been largely completed. The C++0x (most likely really C+11) international standard was recently approved. It contains a carefully defined memory model (mostly in 1.10, with a few pieces in clause 29), an atomic operations library (clause 29), and a threads API (clause 30). The addition of lambda expressions (5.1.2) to the language also makes it easier to write small multithreaded applications.

Here we list some of the documents relevant to that effort.

• A slightly older, publically available draft of the standard This is not entirely up-to-date, but close enough for casual browsing.
• "Mathematizing C++ Concurrency" by Mark Batty et al., POPL 2011. A formalization of the C++ memory model. This is the authors' version of the paper.
• Jaroslav Sevcik's collection of recipes for implementing C++ atomic operations on various architectures.
• Sarita Adve's and Hans Boehm's August 2010 Communications of the ACM article on "Memory models: A case for Rethinking Parallel Languages and Hardware". This takes a broader, not C++-specific, view.
• An introduction to threads and shared variables This addresses the foundations on which we believe programming languages with threads and shared memory should agree, but which in fact seem to be surprisingly controversial. (Hans Boehm)
• A frequently asked questions list which addresses programming in C++ with threads, primarily under the new proposed rules. (Hans Boehm and Paul McKenney)
• Hans Boehm's 2011 HotPar paper "How to miscompile programs with "benign" data races". Summary: There are no benign data races.
• Clark Nelson's and Hans Boehm's concurrency memory model proposal. Much earlier revisions of this contained another piece which revised the traditional single-thread sequencing rules. These have both now been accepted into the working paper.
• Hans Boehm's attempt to explain the concurrency piece of the preceding formal proposal.
• A more recent draft of a rationale for the (very closely related) memory model in the current C language draft.
• "Foundations of the C++ Concurrency Memory Model" by H. Boehm and S. Adve, TR version of PLDI08 paper.
• A proof that the preceding proposal implies sequential consistency for simple race-free programs. This does not extend to "low-level", explicitly ordered, atomics.
• N2338: Anticipated compiler consequences of the memory model proposal.
• Herb Sutter's proposed memory model for Microsoft native code platforms.
• An interesting IBM proposal to modify the N2052 sequencing and the atomic library proposals. Includes examples for which explicit fences significantly improve matters. No longer under consideration in this form, but prompted some fence support in the atomics library. There are ongoing discussions about strengthening this support.
• The most recent atomics library proposal. This was voted into the working paper.
• Several small rationale documents supporting the current memory model and atomics proposals:
  • Why do we leave semantics for races on ordinary variables completely undefined?
  • Why do our atomic operations have integrated memory ordering specifications?
  • Why do we not guarantee that dependencies enforce memory ordering? (Short answer: because that's (nearly?) undefinable.) Note however, that this issue has since been re-raised (see below) and is now under active discussion, using a different approach.
  • Why do our ordering constraints not distinguish between loads and stores, when many architectures provide fences that do?
  • A discussion of out-of-thin-air results and how we might want to prohibit them.
  These were also combined into N2176
• The most recent strawman proposal for the memory model. This is currently very seriously out of date with respect to the preceding documents, but it does include more extensive discussion.
• Overview paper (WG14 N1131) submitted to the C standards committee.
• Lawrence Crowl's proposal for thread thread-local storage (revised again after Portland meeting).
• Lawrence Crowl's proposal for revising initialization and destruction rules to handle concurrency.
• Lawrence Crowl's at_quick_exit() process termination proposal.
• Paul McKenney's, Lawrence Crowl's, and Hans Boehm's proposals which together add data-dependency-based memory ordering: N2359, N2360.
• Hans Boehm's "Reordering Constraints for Pthread-Style Locks." (To appear in PPoPP 2007.) This discusses fences required for locking primitives, and is useful for understanding some subtle design trade-offs.
• Lawrence Crowl's thread API/extension proposal. This is no longer being considered in this form.
• Pete Becker's thread library proposal (based on Boost threads), revision 1.
• Howard Hinnant et al's latest proposal for a thread library API. This was voted into the working paper, though the chapter 31 piece (date/time library) was subsequently removed again. A replacement is under active discussion.
• Nick Maclaren's "Why Posix Threads Are Unsuitable for C++".
• Nick Maclaren's "The Memory Model and the C++ Library, Non-Memory Actions etc." .
• Nick Maclaren's "Generic Support for Threading Models". .
• Slides for the talk presented at the Lillehammer meeting. (pdf, web page)
• Slides from the presentation at the Mont Tremblant meeting (officially N1911).
• Slides from the presentation to the threads/GC sub-subgroup at the Berlin meeting (officially N2010).
• Archive of the mailing list for our group. Note that although the archive is public, we are severely restricting unmoderated participation, for now. If you feel that we are completely off track or really need to participate at this stage, please send mail to one of us individually.
• The beginnings of a frequently-asked-questions list on the memory model itself.

Memory model background papers

Peter Buhr, "Are Safe Concurrency Libraries Possible?". Compressed PostScript. [A much older paper with a similar conclusion, but a different justification.]

Java memory model specification. [The Java memory model specification. This is has to address sand-boxing and type-safety issues. Hence this is not quite the same problem.]

OpenMP Application Program Interface. (Their Architecture Review Board, the authors of this document, has apparently also been concerned with memory model issues. There is some discussion in section 2.7.5, and perhaps in other places.)

Manson, Pugh, Adve, "The Java Memory Model", POPL '05. Author's web site version. [Discussion of the Java memory model.]

Adve, Gharachorloo, "Shared Memory Consistency Models: A Tutorial", DEC WRL Research Report 95/7 HP web site copy. [A very good and relatively brief overview of hardware memory consistency models.]

Sarita Adve, "Designing Memory Consistency Models for Shared-Memory Multiprocessors", University of Wisconsin-Madison Technical Report #1198, December 1993, [Sarita Adve's Ph.D. Thesis. Looks at different memory models along the lines we have been discussing.]

Atomic operations background material

The atomic_ops package.

Alexander Terekhov and Peter Dimov discussion of memory barriers