What are race conditions?.
In shared-memory parallel programs that use explicit synchronization, race conditions result when accesses to shared memory are not properly synchronized. Race conditions are often considered to be manifestations of bugs, since their presence can cause the program to behave unexpectedly.  Unfortunately, there has been little agreement in the literature as to precisely what constitutes a race condition. Two different notions have been implicitly considered: one pertaining to programs intended to be deterministic (which we call general races) and the other to nondeterministic programs containing critical sections (which we call data races). However, the differences between general races and data races have not yet been recognized. This    paper examines these differences by characterizing races using a formal model and exploring their properties. We show that two variations of each type of race exist: feasible general races and data races capture the intuitive notions desired for debugging and apparent races capture less accurate notions implicitly assumed by most dynamic race detection methods. We also show that locating feasible races is an NP-hard problem, implying that only the apparent races, which are approximations to feasible races, can be detected in practice. The complexity of dynamically locating apparent races depends on the type of synchronization used by the program. Apparent races can be exhaustively located efficiently only for weak types of   synchronization that are incapable of implementing mutual exclusion. This result has important implications since we argue that debugging general races requires exhaustive race detection and is inherently harder than debugging data races (which requires only partial race detection). Programs containing data races can therefore be efficiently debugged by locating certain easily identifiable races. In contrast, programs containing general races require more complex debugging techniques.
Introduction
In shared-memory parallel programs, if accesses to shared memory are not properly synchronized, time-dependent
failures called race conditions can result. Race conditions occur when different processes access shared
data without explicit synchronization. Because races can cause the program to behave in ways unexpected by the
programmer, detecting them is an important aspect of debugging. However, in the literature, there seems to be little
agreement as to precisely what constitutes a race condition. Indeed, two different notions have been used, but the
distinction between them has not been previously recognized. Because no consistent terminology has appeared,
several terms have been used with different intended meanings, such as access anomaly[6-8, 12, 18], data
race[1, 4, 5, 11, 16, 20, 22], critical race[13], harmful shared-memory access[24], race condition[10, 26], or just
race[2, 9, 17]. This paper explores the nature of race conditions and uncovers some previously hidden issues
regarding the accuracy and complexity of dynamic race detection. We present the following results.
(1) Two fundamentally different types of races, that capture different kinds of bugs in different classes of parallel
programs, can occur. General races cause nondeterministic execution and are failures in programs
intended to be deterministic. Data races cause non-atomic execution of critical sections and are failures in
(nondeterministic) programs that access and update shared data in critical sections # .
To represent the sources of race conditions precisely, we formally characterize the intuitive notion of a race
we wish to detect for debugging (which we call a feasible race). In contrast, we show that there is a simpler
to detect but less accurate notion of a race that most previously proposed race detection methods locate
(which we call an apparent race). Feasible races are based on the possible behavior of the program;
apparent races, which are approximations to feasible races, are based on only the behavior of the program's
explicit synchronization (and not the semantics of the program's computation).
(3) Exactly locating the feasible general races or data races is an NP-hard problem. This result implies that the
apparent races, which are simpler to locate, must be detected for debugging in practice.
Apparent races can be exhaustively located efficiently only for programs that use synchronization incapable
of implementing mutual exclusion (such as fork/join or Post/Wait synchronization without Clear opera-
tions); detection is NP-hard for more powerful types of synchronization (such as semaphores).
Debugging race conditions in programs intended to be deterministic is inherently more difficult than in non-deterministic
programs. Races that cause non-atomic execution of critical sections (data races) are "local"
properties of the execution and can be detected directly from an execution trace. In contrast, races that cause
nondeterministic execution (general races) are "global" properties of the program whose detection requires
analyzing the entire execution to compute alternative event orderings possibly exhibited by the program.
These results provide an understanding of race conditions important for dynamic race detection. Previous
work has not provided unambiguous characterizations of the different types of race conditions or related races to
program bugs. For example, race conditions have only been defined as occurring when two shared-memory
To be consistent with the fault tolerant research community[25], a failure occurs when a program's external behavior differs from its
specification, and a fault is its algorithmic cause (although we use the term bug).
# There is some controversy over terminology that is the most descriptive. In place of data race and general race, atomicity race and determinacy
race have also been suggested.
references "can potentially execute concurrently"[6] or have no "guaranteed run-time ordering"[10]. Our work is
novel since we explicitly characterize two different types of race conditions using a formal model and explore their
properties. The distinction between general races and data races is necessary because they are manifestations of different
types of program bugs and require different detection techniques. Using a model has the advantage that
issues regarding the accuracy and complexity of dynamic race detection then become clear. The accuracy issues
have implications for debugging: accurate race detection means that races that are direct manifestations of program
bugs are pinpointed, while less accurate detection can report spurious races that mislead a programmer. The complexity
issues show which types of races allow exact and efficient detection and which can be only approximately
located.
Our results show that locating exactly the desired races (the feasible races) is computationally intractable.
Indeed, previously proposed race detection methods take an easier approach and locate only a subset of the apparent
races. However, we argue that apparent races can often be spurious, and that effective debugging requires more
sophisticated techniques. Race conditions can be debugged by attempting to determine which of these located
(apparent) races are of interest for debugging (i.e., are feasible). Our results show that there is also a fundamental
disparity between debugging race conditions in deterministic and nondeterministic programs. Nondeterministic programs
that use critical sections can be safely debugged (to find data races) because we can easily determine if an
execution is data-race free; when data races occur, the feasible races can be approximately located. However,
debugging programs intended to be deterministic (to find general races) is inherently harder. We can be confident
that execution was deterministic only if exhaustive race detection shows an absence of general races (and this is
efficient only for programs using synchronization incapable of implementing mutual exclusion).
2. Examples
Explicit synchronization is often added to shared-memory parallel programs to coordinate accesses to shared
data. Without proper coordination, different types of race conditions can result. To motivate these different types
of races, we present an example of each. In subsequent sections we will characterize them in terms of a formal
model and investigate their properties.
One purpose of adding explicit synchronization to shared-memory parallel programs is to implement critical
sections, which are blocks of code intended to execute as if they were atomic. Atomic execution means that the
final state of variables read and written in the section depends only upon their initial state at the start of the section
and upon the operations performed by the code (and not operations performed by another process). Bernstein's conditions
state that atomic execution is guaranteed if shared variables that are read and modified by the critical section
are not modified by any other concurrently executing section of code[3]. A violation of these conditions has typically
been called a data race[1, 4, 5, 11, 16, 17, 20, 22] or access anomaly[6-8, 18]. We prefer the term data race.

Figure

1 shows an example program for which a data race is considered a failure. This program processes
commands from bank tellers that make deposits and withdrawals for a given bank account. Figure 1(a) shows a
correct version of the program. Since the variables balance and interest are shared, operations that manipulate
them are enclosed in critical sections. Because critical sections can never execute concurrently, this version
will exhibit no data races. Figure 1(b) shows an erroneous version that can exhibit data races; the P and V operations
that enforced mutual exclusion are missing. The deposit and withdraw code can therefore execute con-
currently, causing their individual statements to effectively interleave, possibly violating the atomicity of one of the
Process 1 Process 2
if (balance < amount)
else {
no-data-race version
Process 1 Process 2
if (balance < amount)
else {
data-race version

Figure

1. (a) C program fragment manipulating bank account, and (b) erroneous version exhibiting data races
intended critical sections. The data races in this program are considered failures because the intent was that the
deposit and withdrawal code execute atomically, without interference from other processes.
Even though programs like the one in Figure 1 may contain critical sections, they are often intended to be
nondeterministic (e.g., the order of deposits and withdrawals may occur unpredictably, depending on how fast the
tellers type). However, other classes of programs are intended to be completely deterministic, and a different type
of race condition pertains to such programs. In these programs, synchronization provides determinism by forcing
all accesses to the same shared resource to always execute (on a given input) in a specific order. For a given input,
all executions of such programs always produce the same result, regardless of any random timing variations among
the processes in the program (e.g., due to unpredictable interrupts, or other programs that may be executing on the
same processors). Nondeterminism is generally introduced when the order of two accesses to the same resource is
not enforced by the program's synchronization. The existence of two such unordered accesses has been called a
race condition[9, 10, 26], access anomaly[12], critical race[13], or harmful shared-memory access[24]. For a more
consistent terminology, we propose the term general race, since such a race is more general than a data race.
As an example of programs for which general races are manifestations of bugs, consider parallel programs
that are constructed from sequential programs by parallelizing loops. The sequential version of a program behaves
deterministically, producing a particular result for any given input. Typically, the parallelized version is intended to
have the same semantics. Preserving these semantics can be accomplished by adding synchronization to the program
that ensures all of the data dependences ever exhibited by the sequential version are also exhibited by the
parallel version. Such programs exhibit no general races, since preserving these dependences requires that all
operations on any specific location are performed in some specific order (independent of external timing variations).
Both general races and data races are notions that are necessary for debugging. Although they both occur
when shared-memory accesses occur in an incorrect or unexpected order, they are manifestations of different types
of bugs that occur in different classes of parallel programs.
The notion of a data race is needed to discover critical sections that were not implemented properly (i.e., those
whose atomicity may have failed). The notion of a general race is needed to discover potential nondeterminism
anywhere in the program execution. Data races alone will not suffice for these purposes, since a program can exhibit
no data races but still be nondeterministic. General races alone will not suffice, since general races that are not
data races are not always failures. The preceding examples illustrate these cases. For example, the no-data-race
version of Figure 1 executes nondeterministically, depending on when commands are entered by the tellers. This
version correctly exhibits no data races (its critical sections execute atomically), even though it is nondeterministic.
However, even though general races occur, they are not considered to be manifestations of bugs.
General races and data races also pertain to different classes of parallel programs. General races are typically
of interest for programs in which determinism is implemented by forcing all shared-memory accesses (to the same
location) to occur in a specific order. Many scientific programs fall into this category (e.g., those constructed by
many automatic parallelization techniques). In contrast, data races are typically of interest for asynchronous pro-
grams. Programs using shared work-pools fall into this category. They are not intended to be deterministic, but
critical sections (that access shared data) are still expected to behave atomically.
Emrath and Padua have also characterized different types of race conditions but have only addressed programs
intended to be deterministic[9]. They considered four levels of nondeterminism of a program (on a given
input). Internally deterministic programs are those whose executions on the given input exhibit no general races.
Externally deterministic programs exhibit general races, but they do not cause the final result of the program to
change from run to run. Associatively nondeterministic programs exhibit general races only between associative
arithmetic operations and are externally nondeterministic only because of roundoff errors (different runs can produce
different roundoff errors). Finally, completely nondeterministic programs are those exhibiting general races
that do not fall into one of the above categories. Our work complements these characterizations by also considering
nondeterministic programs and data races, and by using a formal framework.
3. Formal Model for Reasoning About Race Conditions
Now that we have given examples illustrating different types of race conditions, we next discuss how they can
be characterized using a formal model. Doing so not only provides unambiguous characterizations of each, but also
provides a mechanism with which to reason about their properties. In this section, we briefly overview our model
for reasoning about race conditions that was first presented in an earlier paper[22] and that is based on Lamport's
theory of concurrent systems[15]. Our model consists of two parts: one to represent the actual behavior exhibited
by the program and the other to represent potential behaviors possibly exhibited by the program.
3.1. Actual Program Executions
The first part of our model is simply a notation for representing an execution of a shared-memory parallel program
on a sequentially consistent[14] processor + . A program execution, P, is a triple, -E, T , D -, where E is a
finite set of events, and T (the temporal ordering relation) and D (the shared-data dependence relation) are
relations # over those events. Intuitively, E represents the actions performed by the execution, T represents the
order in which they are performed, and D shows how events affect one another through accesses to shared
memory. We refer to P as an actual program execution when P represents an execution that the program at hand
actually performed.
Each event e - E represents both the execution instance of a set of program statements and the sets of shared
memory locations they read and write. A synchronization event represents an instance of some synchronization
operation; a computation event represents the execution instance of any group of statements (belonging to the same
process) that executed consecutively, none of which are synchronization operations. A data conflict exists between
two events if one writes a shared memory location that the other reads or writes.
For two events, a and b, a T b means that a completes before b begins (in the sense that the last action of a
can affect the first action of b), and a /
means that a and b execute concurrently (i.e, neither completes before
the other begins). We should emphasize that T is defined to describe the actual execution order between
events in a particular execution; e.g., a /
means that a and b actually execute concurrently; it does not mean
that they could have executed in any order. A shared-data dependence a D b exists if a accesses a shared variable
that b later accesses (where at least one access modifies the variable), or if a precedes b in the same process
(since data can in general flow through non-shared variables local to the process). A dependence also exists if there
is a chain of dependences from a to b; e.g., if a accesses a shared variable that another event, c, later accesses, and c
then references a variable that b later references.
3.2. Feasible Program Executions
An actual program execution is a convenient notation for describing the behavior of a particular execution.
However, to characterize race conditions, it is necessary to also describe behavior that the program could have exhi-
bited. Most previous work has not explicitly considered this issue; race conditions have typically been defined only
as data-conflicting accesses "that can execute in parallel"[6] or whose execution order is not "guaranteed"[10].
Such definitions implicitly refer to a set of alternative orderings that had the potential of occurring. Our work is
novel in that we explicitly define these sets of orderings. The second part of our model characterizes sets of feasible
program executions, which represent other executions that had the potential of occurring. We next discuss several
possible ways in which these sets can be defined. Instead of simply intuitively reasoning about alternative order-
ings, formally defining these sets uncovers issues important for debugging.
Sequential consistency ensures that shared-memory accesses behave as if they were all performed atomically and in some linear order.
The model also contains axioms describing properties that any program execution must possess[22]. We omit these axioms here as they are un-necessary
for simply characterizing race conditions.
Superscripted arrows denote relations, and a b is a shorthand for -(a b) -(b a).
To characterize when a race condition exists between two events, a and b, in an actual program execution
we must consider other program executions that also perform a and b. Characterizing such executions
allows us to determine if a and b can potentially execute in an order different than in P. We focus on program
executions, P-E-, T , D -, that are prefixes of P and implicitly consider executions on the same input
as P. P - is a prefix of P if each process in P - performs the same events as some initial part of the corresponding process
in P. Focusing on prefixes allows us to pinpoint where nondeterminacy is introduced. If P - were not required
to be a prefix of P, we could not in general determine where or if a and b occur in P -. When P - contains a different
number of execution instances of some statement, we can not draw a correspondence between events in P and
events in P - (because events are defined to represent the execution instance of one or more statements).
We define three sets of program execution prefixes by considering successively fewer restrictions on the different
ways in which P's events could have been performed. We will see that these different sets characterize races
with varying accuracy and complexity. The first two sets are restricted to contain only program executions that are
feasible (i.e., that could have actually occurred); these sets characterize races most accurately. The first set, denoted
F SAME , contains all feasible executions that exhibit the same shared-data dependences as the second set, denoted
F DIFF , contains feasible executions with no restrictions on their shared-data dependences. F DIFF includes all executions
that perform a prefix of the events performed by P regardless of which shared-data dependences may result.
F SAME includes the executions that perform exactly the same events and exhibit the same shared-data dependences
as P.
Definition 3.1
F SAME is the set of program executions, P-E-, T , D -, such that
represents an execution that the program could actually perform,
Definition 3.2
F DIFF is the set of program executions, P-E-, T , D -, such that
represents an execution the program could actually perform,
(2) P - is a prefix of P, and
(3) D - represents any shared-data dependences that satisfy (1) and (2).
The last set, denoted F SYNC , also contains executions with arbitrary shared-data dependences, but they are no
longer required to be feasible; they are only required to obey the semantics of the program's explicit synchroniza-
tion. This simpler set characterizes races less accurately, but is a useful approximation to F DIFF that involves only
the semantics of explicit synchronization (and not the program). Moreover, since previous race detection methods
analyze only explicit synchronization, F SYNC is the set of alternative executions they implicitly assume.
The structure of this set depends on the details of our definition of shared-data dependence. Although different definitions are possible
(e.g., that characterize only flow dependences), they would not alter this structure in a significant way.
F SYNC is the set of program executions, P-E-, T , D -, such that
obeys the semantics of the program's explicit synchronization,
(2) P - is a prefix of P, and
(3) D - represents any shared-data dependences that satisfy (1) and (2).
F SYNC includes all executions that would have been possible had P not exhibited any shared-data dependences
(or any dependences that affect control flow). Since programs in general access shared-memory, F SYNC may include
executions the program could never exhibit. For example, assume that one process in P assigns to a shared variable
S the value 1, and then another process conditionally executes a procedure only if S equals 1. If no explicit synchronization
forces the assignment to occur before the procedure call, then F SYNC will contain an execution in which
the procedure is called before S is assigned 1. However, since the procedure can be called only if S equals 1, such
an execution is not feasible (assuming that S is not initialized to 1). In general, for another execution to perform the
same events as P, it must also exhibit the same shared-data dependences as when general races occur (whether or
not they are considered failures), F SYNC may contain infeasible executions[19, 22]. As discussed later, the existence
of such infeasible executions impacts the accuracy of races reported by methods that analyze only explicit synchron-
ization. Nevertheless, we will see that this notion is useful because it allows a simple characterization of race conditions
that are easy to detect.
4. Issues in Characterizing Race Conditions
We now characterize general races and data races in terms of our model and explore some issues that arise.
We show that two different types of each race exist. One type, the feasible race, captures the intuitive notion that
we wish to express, but is NP-hard to locate exactly. The other type, the apparent race, captures a less accurate notion
(assumed by most race detection methods) but can be more easily detected. Moreover, we argue that debugging
programs intended to be deterministic (to find general races) requires exhaustive race detection and is inherently
harder than debugging nondeterministic programs that use critical sections (to find data races), which requires
only partial race detection.
4.1. General Races and Data Races
Intuitively, a general race potentially introduces nondeterminism and exists in a program execution P if two
events a and b have data conflicts and their access order is not "guaranteed" by the execution's synchronization. A
data race potentially causes the atomicity of critical sections to fail and exists if a and b either execute concurrently
or have the potential of doing so. To explore the nature of races, we first formalize what it means to potentially execute
concurrently (or in a different order) by using the different sets of program executions discussed above. For
example, a general race exists if a and b occur in some feasible program execution in an order different than in P.
Similarly, a data race exists if some feasible program execution exists in which a and b execute concurrently. We
first define the notion of a general race or data race between a and b (denoted -a,b-) over some given set of program
executions, F, and then consider the implications of different choices for the set F.
A general race -a,b- over F exists iff
(1) a data conflict exists in P between a and b, and
(2) there exists a program execution, P-E-, T , D - F, such that a,b - E - and
(a) b T - a if a T b, or
(b) a T - b if b T a, or
(c) a /
Condition (2) is true if a and b can occur in an order opposite as in P or concurrently; these cases capture the notion
that the execution order among a and b is not "guaranteed".
Definition 4.2
A data race -a,b- over F exists iff
(1) a data conflict exists in P between a and b, and
(2) there exists a program execution, P-E-, T , D - F, such that a,b - E - and a /
4.2. Feasible Races
The most natural way to characterize a race -a,b- is to consider races over F DIFF , since F DIFF precisely captures
the set of possible executions that also perform a and b. For general races, we have no choice: the smaller set
F SAME is inadequate since, by definition, a general race exists between two accesses only if they execute in an order
different than in P (and therefore the shared-data dependence between them is also different). In contrast, data races
could be reasonably viewed as occurring over either F DIFF or F SAME .
Definition 4.3
A feasible general race -a,b- exists iff a general race -a,b- over F DIFF exists.
A feasible data race -a,b- exists iff a data race -a,b- over F DIFF exists.
A feasible race locates precisely those portions of the execution that allowed a race, and thus represents the
intuitive notion of a race illustrated in Section 2. However, checking for the presence of a feasible general race or
data race -a,b- requires determining whether a feasible program execution in which b T - a (or a T - b, or a
a member of F DIFF . We have proven that deciding these membership problems is NP-hard (no matter
what type of synchronization the program uses) and that locating feasible races is also NP-hard[19, 21]. It is therefore
an intractable problem to locate precisely the race conditions exhibited by an execution of the program. This
result suggests that, in practice, we must settle for an approximation, discussed next. Indeed, previously proposed
race detection methods compute such an approximation.
4.3. Apparent Races
In practice, locating the intuitive notion of a race (a feasible race) would require analyzing the program's semantics
to determine if the execution could have allowed b to precede a (or b to execute concurrently with a). Previously
proposed methods take a simpler approach and analyze only the explicit synchronization performed by the
execution. For example, a and b are said to have potentially executed concurrently (or in some other order) if no
explicit synchronization prevented them from doing so. We can characterize the races detected by this approach by
using F SYNC , which is based only on orderings that the program's explicit synchronization might allow. Because the
program may not be able to exhibit such orderings, these races capture a less accurate notion than feasible races.
Definition 4.4
An apparent general race -a,b- exists iff a general race -a,b- over F SYNC exists.
An apparent data race -a,b- exists iff a data race -a,b- over F SYNC exists.
Because not all program executions in F SYNC are feasible, some apparent races may be spurious. Spurious
races can occur whenever the values of shared variables are used (directly or indirectly) in conditional expressions
or shared-array subscripts[20, 22]. In such cases, the existence of one event may depend on another event occurring
first. For example, consider one process in P that adds data to a shared buffer and then sets a flag BufEmpty to false,
and another process that first tests BufEmpty and then removes data from the buffer only if BufEmpty equals false.
Such an execution has two apparent general races, between the accesses to BufEmpty and between the accesses to
the buffer. However, the race involving the buffer is spurious - no feasible execution exists in which data is removed
from the buffer before the buffer is filled (since BufEmpty is first tested before data is removed). If the
operations on the shared buffer were instead complex and involved many shared-memory references, a large
number of spurious races could be reported. Spurious races pose a problem since they are not direct manifestations
of any program bug[20, 22]. The programmer can be overwhelmed with large amounts of misleading information,
irrelevant for debugging, that masks the location of actual failures. Nonetheless, apparent race detection provides
valuable information, since apparent races exist if and only if at least one feasible race exists somewhere in the exe-
cution[22]. Moreover, we have proven results showing how to reason about the potential feasibility of apparent
races, and how a post-mortem race detector can be extended to conservatively determine which apparent races are
feasible and of interest for debugging[20-22].
We have also proven that, for program executions using synchronization powerful enough to implement two-process
mutual exclusion, determining membership in F SYNC and locating apparent races is NP-hard[19]. Membership
in F SYNC is efficiently computable only for weaker synchronization incapable of implementing mutual exclusion
(such as Post/Wait style synchronization without Clear operations); all apparent races can thus be efficiently
detected in executions of such programs[23]. It is important to note that data races are not of interest for such programs
since weaker synchronization cannot implement critical sections. Exhaustively locating all apparent data
races is therefore always NP-hard. In contrast, the complexity of apparent general race detection depends on the
type of synchronization used. However, as we discuss next, it is sufficient for debugging data races to detect only a
certain subset of the apparent races, while debugging general races requires exhaustive detection.
4.4. Debugging with Race Condition Detection
An important aspect of debugging involves determining whether portions of the execution are race-free in the
sense that they are unaffected by incorrect or inconsistent data produced by a race[5, 20]. For example, a programmer
browsing an execution trace might focus only on portions of the trace recorded before any races occurred.
These portions of the trace contain events that are guaranteed to be unaffected by the outcome of any race. Locating
such events is important because the program may exhibit meaningless behavior after a race. In Figure 1(b), for ex-
ample, a data race that results in a negative balance might cause subsequent withdrawals to fail because of
insufficient funds when in fact more money has been deposited than withdrawn. To locate events unaffected by a
race, it is necessary to determine if portions of the execution are race free. However, we now argue that making this
determination is inherently harder for general races (which introduce nondeterminism) than for data races (which
only cause critical sections to fail). For executions containing data races, it suffices to detect the presence (or ab-
sence) of only a certain subset of the apparent races. In contrast, to debug executions containing general races, it is
necessary to perform exhaustive apparent general race detection.
Data races can be viewed as a local property of the execution which can be determined directly from the actual
program execution, P. Because an intended critical section can execute non-atomically only when other data-
conflicting events are concurrently executing, an actual data race can be detected directly from P.
Definition 4.5
An actual data race -a,b- exists iff a data race -a,b- in P exists
An actual data race indicates the possibility that the atomicity of a critical section may have actually failed. In con-
trast, general races are a global property of the program which can be determined only by computing alternative
event orderings. In general, determining if two events could have occurred in a different order requires analyzing
the synchronization over the entire execution; there is no notion of an actual general race. Thus, unlike general
races, actual data races can be easily located if the temporal ordering, T , is known; computing alternative orderings
is unnecessary.
This difference has important implications for debugging. Apparent data races that are not actual data races
cannot produce inconsistent data (because no critical sections fail), but any apparent general race indicates such a
possibility (because two shared-memory accesses could have executed in the incorrect order). The absence of an
actual data race therefore indicates that all intended critical sections in P executed atomically, and the location of an
actual race pinpoints places in the execution where inconsistent data should be expected. Even though not all apparent
data races can be efficiently located, we can efficiently determine whether any actual data races occurred.
Thus, we can easily determine whether the observed execution contains inconsistent data which cannot be relied
upon for debugging. However, because there is no notion of an actual general race, we must exhaustively locate all
apparent general races to make this determination. Only if no apparent races exist can we be sure that all shared-memory
references occurred in the expected order (because no other order was possible).
These results suggest that we can efficiently debug programs containing data races by locating all actual and
some apparent data races. However, we can only apply such an approach to programs containing general races if all
apparent races can be efficiently located. As discussed above, exhaustive apparent general race detection is efficient
only for programs that use synchronization incapable of implementing mutual exclusion. However, for more
powerful types of synchronization (such as semaphores), conservative approximations that locate a superset of the
apparent general races have been proposed[10, 11]. Such methods provide a means of debugging general races in
programs using such synchronization, but have the potential of misleading the programmer with potentially large
numbers of spurious race reports.
data race in P exists iff a data race exists over {P}, the set containing only P.
5. Conclusion
This paper explores the nature of race conditions that can arise in shared-memory parallel programs. By employing
a formal model we uncover previously hidden issues regarding the accuracy and complexity of dynamic
race detection. We show that two fundamentally different types of races can occur: general races, pertaining to
deterministic programs, and data races, pertaining to nondeterministic programs that use critical sections. We formally
characterize these types of races. Previously, races have only been defined intuitively as occurring between
data-conflicting blocks of code that "can potentially execute concurrently" or whose execution order is not
"guaranteed". Our work is novel in that we explicitly characterize sets of alternative orderings that had the potential
of occurring. Doing so is important because properties of the defined races, such as the accuracy and complexity
of detecting them, depend upon which sets are considered. We uncover two variations of each type of race: one
describes the intuitive notion of a race (the feasible race) and the other describes a less accurate notion (the apparent
race) assumed by most race detection methods. Since locating the feasible races is NP-hard, the less accurate apparent
races must be relied upon for debugging in practice. Moreover, we uncover fundamental differences in the
complexity of debugging general races and data races. Debugging general races requires exhaustively computing
alternative orderings (to determine whether the execution is nondeterministic), which is NP-hard for programs using
synchronization powerful enough to implement mutual exclusion. Debugging data races requires simpler analyses
(to determine if critical sections fail), which can be efficiently performed.



--R

"Debugging Fortran on a Shared Memory Machine,"
"Compile-time Detection of Race Conditions in a Parallel Pro- gram,"
"Analysis of Programs for Parallel Processing,"
"Techniques for Debugging Parallel Programs with Flowback Analysis,"
"Race Frontier: Reproducing Data Races in Parallel Program Debug- ging,"
"The Task Recycling Technique for Detecting Access Anomalies On- The-Fly,"
"An Empirical Comparison of Monitoring Algorithms for Access Anomaly Detection,"
"Detecting Access Anomalies in Programs with Critical Sections,"
"Automatic Detection Of Nondeterminacy in Parallel Programs,"
"Event Synchronization Analysis for Debugging Parallel Programs,"
"Analyzing Traces with Anonymous Synchronization,"
"Parallel Program Debugging with On-the-fly Anomaly Detection,"
"Critical Races in Ada Programs,"
"How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Pro- grams,"
"The Mutual Exclusion Problem: Part I - A Theory of Interprocess Communication,"
"On-the-Fly Detection of Data Races for Programs with Nested Fork-Join Parallelism,"
"A Mechanism for Efficient Debugging of Parallel Programs,"
"An Efficient Cache-based Access Anomaly Detection Scheme,"
"On the Complexity of Event Ordering for Shared-Memory Parallel Program Executions,"
"Improving the Accuracy of Data Race Detection,"
"Race Condition Detection for Debugging Shared-Memory Parallel Programs,"
"Detecting Data Races in Parallel Program Executions,"
"Efficient Race Condition Detection for Shared-Memory Programs with Post/Wait Synchronization,"
"Tools for the Efficient Development of Efficient Parallel Programs,"
"Reliability Issues in Computing System Design,"
"Making Asynchronous Parallelism Safe for the World,"
--TR
The mutual exclusion problem
A mechanism for efficient debugging of parallel programs
Automatic detection of nondeterminacy in parallel programs
Critical Races in Ada Programs
Event synchronization analysis for debugging parallel programs
Making asynchronous parallelism safe for the world
An empirical comparison of monitoring algorithms for access anomaly detection
An efficient cache-based access anomaly detection scheme
Improving the accuracy of data race detection
Race Frontier
Parallel program debugging with on-the-fly anomaly detection
Techniques for debugging parallel programs with flowback analysis
Detecting access anomalies in programs with critical sections
On-the-fly detection of data races for programs with nested fork-join parallelism
Pace condition detection for debugging shared-memory parallel programs
Compile-time detection of race conditions in a parallel program
Reliability Issues in Computing System Design

--CTR
M. Erkan Keremoglu , Serdar Tasiran , Tayfun Elmas, A classification of concurrency bugs in java benchmarks by developer intent, Proceeding of the 2006 workshop on Parallel and distributed systems: testing and debugging, July 17-17, 2006, Portland, Maine, USA
Michal Young, State-space analysis as an aid to testing, Proceedings of the 1994 ACM SIGSOFT international symposium on Software testing and analysis, p.203, August 17-19, 1994, Seattle, Washington, United States
Utpal Banerjee , Brian Bliss , Zhiqiang Ma , Paul Petersen, A theory of data race detection, Proceeding of the 2006 workshop on Parallel and distributed systems: testing and debugging, July 17-17, 2006, Portland, Maine, USA
Michiel Ronsse , Koen De Bosschere , Mark Christiaens , Jacques Chassin de Kergommeaux , Dieter Kranzlmller, Record/replay for nondeterministic program executions, Communications of the ACM, v.46 n.9, p.62-67, September
Arndt Mhlenfeld , Franz Wotawa, Fault Detection in Multi-Threaded C++ Server Applications, Electronic Notes in Theoretical Computer Science (ENTCS), v.174 n.9, p.5-22, June, 2007
Bartosz Bali , Marian Bubak , Wodzimierz Funika , Roland Wismller, A monitoring system for multithreaded applications, Future Generation Computer Systems, v.19 n.5, p.641-650, July
Brad Richards , James R. Larus, Protocol-based data-race detection, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.40-47, August 03-04, 1998, Welches, Oregon, United States
Efficient on-the-fly data race detection in multithreaded C++ programs, ACM SIGPLAN Notices, v.38 n.10, October
Mingdong Feng , Charles E. Leiserson, Efficient detection of determinacy races in Cilk programs, Proceedings of the ninth annual ACM symposium on Parallel algorithms and architectures, p.1-11, June 23-25, 1997, Newport, Rhode Island, United States
Roberto Barbuti , Stefano Cataudella , Luca Tesei, Abstract Interpretation Against Races, Fundamenta Informaticae, v.60 n.1-4, p.67-79, January 2004
Peter A. Buhr , Martin Karsten , Jun Shih, KDB: a multi-threaded debugger for multi-threaded applications, Proceedings of the SIGMETRICS symposium on Parallel and distributed tools, p.80-87, May 22-23, 1996, Philadelphia, Pennsylvania, United States
Jrgen Vollmer, Data flow analysis of parallel programs, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.168-177, June 27-29, 1995, Limassol, Cyprus
Min Xu , Rastislav Bodik , Mark D. Hill, A "flight data recorder" for enabling full-system multiprocessor deterministic replay, ACM SIGARCH Computer Architecture News, v.31 n.2, May
Christoph von Praun , Luis Ceze , Calin Cacaval, Implicit parallelism with ordered transactions, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA
Prem Uppuluri , Uday Joshi , Arnab Ray, Preventing race condition attacks on file-systems, Proceedings of the 2005 ACM symposium on Applied computing, March 13-17, 2005, Santa Fe, New Mexico
Greg Hoover , Forrest Brewer , Timothy Sherwood, A case study of multi-threading in the embedded space, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea
Dejan Perkovic , Peter J. Keleher, A Protocol-Centric Approach to on-the-Fly Race Detection, IEEE Transactions on Parallel and Distributed Systems, v.11 n.10, p.1058-1072, October 2000
Robert O'Callahan , Jong-Deok Choi, Hybrid dynamic data race detection, ACM SIGPLAN Notices, v.38 n.10, October
Jong-Deok Choi , Keunwoo Lee , Alexey Loginov , Robert O'Callahan , Vivek Sarkar , Manu Sridharan, Efficient and precise datarace detection for multithreaded object-oriented programs, ACM SIGPLAN Notices, v.37 n.5, May 2002
Michiel Ronsse , Koen De Bosschere, RecPlay: a fully integrated practical record/replay system, ACM Transactions on Computer Systems (TOCS), v.17 n.2, p.133-152, May 1999
Jeffrey K. Hollingsworth, Critical Path Profiling of Message Passing and Shared-Memory Programs, IEEE Transactions on Parallel and Distributed Systems, v.9 n.10, p.1029-1040, October 1998
Hiroyasu Nishiyama, Detecting data races using dynamic escape analysis based on read barrier, Proceedings of the 3rd conference on Virtual Machine Research And Technology Symposium, p.10-10, May 06-07, 2004, San Jose, California
Christoph von Praun , Thomas R. Gross, Object race detection, ACM SIGPLAN Notices, v.36 n.11, p.70-82, 11/01/2001
Amir Kamil , Jimmy Su , Katherine Yelick, Making Sequential Consistency Practical in Titanium, Proceedings of the 2005 ACM/IEEE conference on Supercomputing, p.15, November 12-18, 2005
Min Xu , Rastislav Bodk , Mark D. Hill, A serializability violation detector for shared-memory server programs, ACM SIGPLAN Notices, v.40 n.6, June 2005
Hagit Attiya , Roy Friedman, Programming DEC-Alpha based multiprocessors the easy way (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.157-166, June 27-29, 1994, Cape May, New Jersey, United States
Michiel Ronsse , Koen De Bosschere, Non-Intrusive Detection of Synchronization Errors Using Execution Replay, Automated Software Engineering, v.9 n.1, p.95-121, January 2002
nonblocking communication for partitioned global address space programs, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington
Guang-Ien Cheng , Mingdong Feng , Charles E. Leiserson , Keith H. Randall , Andrew F. Stark, Detecting data races in Cilk programs that use locks, Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures, p.298-309, June 28-July 02, 1998, Puerto Vallarta, Mexico
Arun Kejariwal , Hideki Saito , Xinmin Tian , Milind Girkar , Wel Li , Utpal Banerjee , Alexandru Nicolau , Constantine D. Polychronopoulos, Lightweight lock-free synchronization methods for multithreading, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia
Bohuslav Krena , Zdenek Letko , Rachel Tzoref , Shmuel Ur , Tom Vojnar, Healing data races on-the-fly, Proceedings of the 2007 ACM workshop on Parallel and distributed systems: testing and debugging, July 09-09, 2007, London, United Kingdom
Eran Yahav, Verifying safety properties of concurrent Java programs using 3-valued logic, ACM SIGPLAN Notices, v.36 n.3, p.27-40, March 2001
John S. Danaher , I.-Ting Angelina Lee , Charles E. Leiserson, Programming with exceptions in JCilk, Science of Computer Programming, v.63 n.2, p.147-171, 1 December 2006
Hagit Attiya , Soma Chaudhuri , Roy Friedman , Jennifer L. Welch, Shared memory consistency conditions for non-sequential execution: definitions and programming strategies, Proceedings of the fifth annual ACM symposium on Parallel algorithms and architectures, p.241-250, June 30-July 02, 1993, Velen, Germany
Cherri M. Pancake , Robert H. B. Netzer, A bibliography of parallel debuggers, 1993 edition, ACM SIGPLAN Notices, v.28 n.12, p.169-186, Dec. 1993
race conditions;critical sections;nondeterminacy;parallel programs;debugging;data races