Programming with Threads: Questions Frequently Asked by C and C++ Programmers

Authors: Hans-J. Boehm, HP Labs & Paul McKenney, IBM

Disclaimer: These are only the authors' opinions.

In the process of trying to define the semantics of threads for C++0x, it has become clear that there are widespread misunderstandings about the use of threads in these languages. This is an attempt to correct some of these.

We cheat in several ways:

• To start with, we pretend that something similar to our current proposals were part of the current language standards, and you could use them with your current compiler. They're not. You can't. They're not even part of the working paper, yet. (For the most part, the basic ideas are uncontroversial, so the odds are good they will be. And nobody currently expects the C++0x standard to be voted out without thread support. But details will change.) We do try to briefly address the additional issues arising with current compilers near the end of this document.
• Not all of these are really frequently asked questions. We made up some that we wish people would ask.

Is this known to reflect the position of any major organization or corporation?

Why are you (mostly) assuming the existence of a standard that is at least two years out?

What basic rules should I follow when writing multi-threaded C or C++ code?

Do not allow data races.

This of course is not the only thing you need to know to write correct parallel code. You still need to make sure that actions that should logically be indivisible actually are, that you avoid deadlocks, that your algorithm is sufficiently parallel for the performance you need, etc. But we do think it addresses much of the confusion that has surrounded this area.

In the past, it was much easier to justify code with "benign" data races, and such code is quite common, particularly for older code, or code that could not tolerate the performance overhead associated with locking. Atomic objects now provide a clearer and safer way to write such code.

So what's a "data race"?

So what's a "synchronization action"?

What's an atomic object?

What does it take to order two memory operations?

So what's a "memory location"?

Why the weird exception for bit-fields?

But what about benign data races?

(This notion does often exist at the machine code level. Hence optimizers might introduce them. But you should never write them in source code.)

Of course, there is no shortage of applications and operating-system kernels written in C or C++ that do contain code with data races. For more on this subject, see the discussion of current compilers near the end of this document.

Does that mean that if I write a program with a data race, the machine is allowed to catch on fire?

But what really happens?

This seems rather draconian. After all these years, why would you outlaw data races like this?

There are several technical reasons, beyond continuity with existing standards, to not only continue with this rule, but to more aggressively insist on adherence to it:

• Code with data races is extremely difficult to get right and understand. If you are clever enough to do so, you should at least extend the reader courtesy of identifying such tricky code by labelling the affected variables as atomic.
• Some hardware does not support efficient atomic updates to certain scalar objects. Another thread trying to concurrently read that value may only see half the update. This is less common now, but is believed to be an issue for some embedded processors. It is certainly an issue for large scalar objects,such as 64-bit integers on 32-bit hardware.
• Compilers are allowed to assume that the value of ordinary variables does not change asynchronously. We believe that this assumption is pervasive, though rarely reflected in the resulting code. It does mean that when faced with code such as

  unsigned x;
  
  ...
  if (x < 5) {
    ... code that doesn't change x ...
    switch (x) {
      case 0:
      	...
      case 1:
      	...
      case 2:
      	...
      case 3:
      	...
      case 4:
      	...
    }
  }
  

  the compiler is allowed to compile the switch statement using a branch table and omit the bounds check for the branch table, since it already knows that x < 5. If in fact the resulting code loads x twice, and x changes in the middle, the resulting code will take a wild branch to an unintended address. There are many other, less spectacular, potential potential failures along these lines.
• The introduction of atomic objects provides essentially the same performance as was previously possible with "benign" races, but clearly defines the responsibilities of both the programmer and the compiler implementor.
• Prohibiting races simplifies the job of race detection tools. Races are bugs. By definition.
• We don't have to define "benign races", which would be a complicated undertaking, and make this FAQ much more confusing.

I've heard that when writing multi-threaded code I have to worry about the order in which memory operations become visible to other threads. How can I deal with that?

In reality, this illusion is maintained mostly because it would require a data race for you to be able to tell that the code is not being executed like that. (And trust us, it isn't.) But that again means that if you introduce a data race, all bets are off. Unfortunately, it even means that if you accidentally introduce a data race, you may encounter strange results while debugging. (Certainly vendors are encouraged to minimize that effect, particularly at low optimization levels. But the (proposed) standard makes no claims about this.)

How do I recognize a "low level" atomic operation when I see one?

When should I use low level atomic operations?

• The alternatives lead to inadequate performance, and you've determined that high level atomics are the problem, and
• You sufficiently understand the relevant memory ordering issues, something that is generally well beyond this FAQ.

In this case, you may see a significant performance benefit, but only on a few architectures, and the resulting code will be harder to reason about as a result. Generally low level atomic operations are intended for implementors of a few other performance critical libraries.

We expect that in some cases coding standards will prohibit the use of low level atomic operations.

Should shared variables be declared as volatile even if they are protected by locks?

But parallel applications written in both C and C++ have been in existence for decades, and many of them do in fact have data races. Given that, what is all this fuss about?

Perhaps most importantly, such coding practices cannot guarantee continued correctness and portability of the application as the compiler evolves and more aggressive optimizations are added, or as the application is moved to a different compiler. The point of the standard is to clearly define the rules by which both the C++ programmer and the C++ compiler-writer must play in order to ensure continuing application correctness.

But why can't we standardize something that better accommodates existing programs with races?

• Also make assumptions about memory visibility that would be expensive to enforce universally, or
• Rely on other nonstandard constructs (e.g. some kind of explicit memory fences) to guarantee the ncessaroy memory visibility ordering.

The advantage of adopting the multi-threading constructs that we expect to be available in the C++0x standard is that you get standard-mandated multi-threaded safety and full access to advanced optimization techniques.

It is likely that compilers that have seen extensive multi-threaded use will provide facilities to ease transition from traditional assumptions to the upcoming standard, but of course the standard has no way to mandate such facilities. If you care about such facilities, we therefore advise you to discuss this with your compiler vendor/provider.

Can you give a specific example of optimizations that would be prohibited if some races were allowed?

If we tried to guarantee that programs with data races behaved sequentially consistently, i.e. as though thread steps were simply interleaved, most code scheduling and loop optimizations would break, at least in the absence of whole program analysis. Thus in reality we would have to provide very weak ordering guarantees for races, which would not do much to preserve correctness of existing code.

If pointer assignment were guaranteed to be atomic, the language would become hard to implement on some embedded processors that don't support atomic pointer-sized stores. Even on larger machines, it is unclear what types should behave atomically and be allowed in races.

It would also be hard to specify, for example, what happens when an object with virtual functions is communicated via a simple pointer assignment to another thread. In many cases, some sort of fence would be needed to ensure visibility of the vtable pointer to the receiving thread. But the vtable pointer is an implementation detail that shouldn't be programmer visible. And it would be expensive to implicitly generate these fences.

Common compiler optimization assumptions would be invalidated. The resulting failures seem to be infrequent in practice, but hard to characterize.

Given that I don't have access to a C++0x implementation, how much of this applies?

• There are no atomic data types or operations, as we described here.
• The notion of a "memory location" used in the definition of a data race is intentionally undefined. That means that updating a scalar object may interfere with an update of a nearby one.
• There is no clear prohibition against "spurious" compiler-introduced stores of the old value back into a global variable x, when such an update is not called for by the source. This may cause a concurrent update to x to be lost, somewhat unpredictably. Many compilers can introduce such updates, though they rarely do so in cases in which it turns out to matter. (See Boehm, Threads Cannot be Implemented as a Library, PLDI 2005 for details.)

How do I deal with the absence of atomic operations before C++0x?

There are many alternatives, all imperfect. There are several packages that provide a generic interface to atomic operations with platform-specific implementations. atomic_ops is one of these. Gcc provides __sync_ operations. Microsoft provides Interlocked operations. They are generally still evolving as we understand the issues better. Many of these, e.g. the gcc __sync_ operations, do not provide a special atomic load, and hence have no way to inform the compiler, other than with the volatile qualifier, that a value may change asynchronously. We recommend that whichever you use, you use a macro to identify such loads, to make it easier to later convert to the more correct C++0x approach.

So should I use volatile to identify variables modified by another thread?

If you do use volatile remember that its detailed semantics vary dramatically across platforms. On some platforms, two consecutive volatile stores may become visible out of order to two consecutive volatile loads in another thread. On other platforms, that is explicitly prevented. Thus platform-dependent mechanisms for memory ordering are usually also needed. (The atomic_ops package uses volatile in platform-dependent ways internally, but adds fences to enforce requested memory ordering.)

It is also important to remember that volatile updates are not necessarily atomic. They may appear to be carried out piecemeal. Whether or not they actually are atomic depends on the platform and alignment.

How about using explicit platform-dependent memory fences with ordinary memory operations, as the Linux kernel does?

If such mechanisms are not correctly used, problems may arise, particularly if a load involved in a race is not followed immediately by a fence. If we write

{
  int local = shared;

  if (local) perform some action;
  A: <code that affects neither shared not local>
  if (local) perform some compensating action;
}

Given the potential pitfalls similar to that illustrated in the above example, it should be clear that obtaining correct results from current compilers given code containing data races requires deep expertise in the target CPU architecture(s), the specific compiler(s) to be used, and in the non-standard extensions that are used to prevent the compiler(s) from carrying out optimizations that, while perfectly safe in single-threaded code, lead to incorrect results when applied to multi-threaded code with data races.

But can't I simply use a volatile cast to prevent this problem?

This may seem like a sorry state of affairs, but please keep in mind that the "volatile" keyword was introduced into the C language long before multi-threaded code and multiprocessor systems were commonly available.

So is it OK to have data races until we get real atomic operations?

So how do I deal with the adjacent field over-write issue?

If you are generating code for an Alpha processor, tell your compiler to generate code for recent processors that support byte loads and stores. If you are generating code for an older Alpha processor, you will need to modify your application to ensure that bytes protected by separate locks are in separate words. Or you will need to upgrade to a more modern CPU.

By far the most common violation of the C++0x rules on current compilers is the treatment of bit-fields that share a word with non-bit-fields, as in

struct {char a; int b:5; int c:9, char d;};

We know of no compilers that allow something other than a struct or class member to update something other than an adjacent struct or class member, although this does appear to be allowed by current standards.

So how do I deal with potential spurious stores in current compilers?

for (p = q; p != 0; p = p->next)
  if (p -> data > 0) count++;

Needless to say, such correctness arguments should be avoided.

Although it is common for compilers to generate technically incorrect (by proposed C++0x standards) for this code, the actual failure scenario seems fairly far-fetched.

More dangerous miscompilations, such as the example described in Boehm, Threads Cannot be Implemented as a Library, PLDI 2005 are fortunately rare, and it is unclear that there are effective counter-measures, other than modifying compilers to comply to the C++0x rules; significant reduction of optimization level; using non-standard directives or compiler switches that prevent such behavior for specified accesses, variables, or compilation units; or manually checking the resulting assembly code.

Explicit optimization-suppression directives in many current compilers may allow this type of code to be safely written. Of course, all such usage is non-standard and very likely also non-portable.

How much of this applies to Java?