Doi: 10.1145/1839676.1839698
Goldilocks:
A Race-Aware Java Runtime
abstract
We present Goldilocks, a Java runtime that monitors
program executions and throws a DataRaceException
when a data race is about to occur. This prevents racy
accesses from taking place, and allows race conditions to
be handled before they cause errors that may be difficult
to diagnose later. The DataRaceException is a valuable
debugging tool, and, if supported with reasonable computational overhead, can be an important safety feature for
deployed programs. Experiments by us and others on race-aware Java runtimes indicate that the DataRaceException
may be a viable mechanism to enforce the safety of executions of multithreaded Java programs.
An important benefit of DataRaceException is that
executions in our runtime are guaranteed to be race free
and thus sequentially consistent as per the Java Memory
Model. This strong guarantee provides an easy-to-use, clean
semantics to programmers, and helps to rule out many
concurrency-related possibilities as the cause of errors. To
support the DataRaceException, our runtime incorporates the novel Goldilocks algorithm for precise dynamic race
detection. The Goldilocks algorithm is general, intuitive, and
can handle different synchronization patterns uniformly.
1. intRoDuction
When two accesses by two different threads to a shared
variable are enabled simultaneously, i.e., at the same program state, a race condition is said to occur. An equivalent definition involves an execution in which two threads
make conflicting accesses to a variable without proper
synchronization actions being executed between the two
accesses. A common way to ensure race freedom is to associate a lock with every shared variable, and to ensure that
threads hold this lock when accessing the shared variable.
The lock release by one thread and the lock acquire by the
next establish the required synchronization between the
two threads.
Data races are undesirable for two key reasons. First, a
race condition is often a symptom of a higher-level logical
error such as an atomicity violation. Thus, race detectors
serve as a proxy for more general concurrency-error detection when higher-level specifications such as atomicity
annotations do not exist. Second, a race condition makes
the outcome of certain shared variable accesses nondeterministic. For this and other reasons, both the Java Memory
Model (JMM) 10 and the C++ Memory Model (C++MM) 2 define
well-synchronized programs to be programs whose executions are free of race conditions. For race-free executions,
these models guarantee sequentially consistent semantics;
in particular, every read deterministically returns the value
of the “last” write. This semantics is widely considered to
be the only simple-enough model with which writing useful
concurrent programs is practical. For executions containing
race conditions, the semantics is either completely undefined (as is the case for C++MM2) or is complicated enough
that writing a useful and correct program with “benign
races” is a challenge.
Detection and/or elimination of race conditions has been
an area of intense research activity. The work presented in
this paper (and initially presented in Elmas et al. 6) makes
two important contributions to this area.
First, for the first time in the literature, we propose that
race conditions should be language-level exceptions just
like null pointer dereferences and indexing an array out of
its bounds. The Goldilocks runtime for Java provides a
new exception, DataRaceException,a that is thrown precisely when an access that causes an actual race condition is
about to be executed. Since a racy execution is never allowed
to take place, this guarantees that the execution remains
sequentially consistent.
The DataRaceException brings races to the programmer’s attention explicitly. When this exception is caught, the
recommended course of action is to terminate the program
gracefully. This is because, for racy Java programs, a wide
range of compiler optimizations are allowed by the JMM,
and this makes it complicated to relate program executions
to source code. If the exception is not caught, the Goldilocks
runtime terminates the thread that threw the exception.
While not recommended, the programmer could also
choose to make optimistic use of a DataRaceException
by, for instance, retrying the code block that led to the race,
hoping that the conflicting thread has performed the synchronization necessary to avoid a race in the meantime.
Since the first paper on the Goldilocks runtime, 6 the idea
that certain concurrency errors, especially ones that result
in sequential consistency violations, should result in exceptions has gained significant support and several implementations of the idea have been investigated. 9, 11
To support a DataRaceException, a runtime must
a We define DataRaceException as a subclass of the Runtime-Exception class in Java.
The original version of this paper was published in the
Proceedings of the ACM SIGPLAN 2007 Conference on
Programming Language Design and Implementation (PLDI),
June 2007.