Communications - November 2010

Doi: 10.1145/1839676.1839697

technical Perspective
Data Races are evil
with no exceptions
By Sarita Adve

exPLoITINg ParaLLeLISM haS become the primary means to higher performance. Shared memory is a pervasively used programming model, where parallel tasks or threads communicate through a global address space. Popular languages, such as C, C++, and Java have (or will soon have) standardized support for shared-memory threads. Unfortunately, shared-memory programs are notoriously prone to subtle bugs, often due to data races.

Languages that allow data races obfuscate true communication and synchronization. Since any load or store may communicate or synchronize with another thread through a data race, it becomes difficult to reason about sections of code in isolation. Data races also create non-determinism since the ordering between two racing accesses is timing-dependent. Racy programs therefore require reasoning about many interleavings of individual memory accesses and their executions are difficult to reproduce. Data races have therefore been widely considered as symptoms of bugs and there is much research to automatically detect them.

An arguably more fundamental
problem with data races concerns se-
mantics. Every programming language
must specify what value a load can re-
turn, also called the memory model.
It has been surprisingly difficult to
specify an acceptable model that bal-
ances ease-of-use and performance
for languages that allow data races. 1
Programmers usually expect a sequen-
tial interleaving-based model called se-
quential consistency. For data-race-free
programs, it is straightforward to pro-
vide sequential consistency and high
performance. With racy code, however,
routine compiler and hardware opti-
mizations can result in surprising be-
haviors. Consequently, the upcoming C
and C++ memory models specify “unde-
fined” behavior for programs with data
races. This gives freedom to implement-
ers but poses challenges for debugging
racy code. Java’s safety requirements
preclude the use of “undefined” behav-
ior. The Java memory model, therefore,
specifies very weak semantics for racy
programs, but is extremely complex and
currently has known bugs.

References

1. adve, s. V. and Boehm, H-J. memory models: a case for rethinking parallel languages and hardware. Commun. ACM 53, 8 (aug. 2010) 90–101.

2. Bocchino, r. L. et al. a type and effect system for deterministic parallel Java. In Proceedings of the International Conference on Object-Oriented Programming, Systems, Languages, and Applications, 2009.

3. Lucia, B. et al. conflict exceptions: providing simple concurrent language semantics with precise hardware exceptions. In Proceedings of the International Symposium on Computer Architecture, 2010.