DOI:10.1145/1839676.1839698
NOVE MBE R 201 0 | VOL. 5 3 | NO. 11 | COM MU NIC ATIO NS OF TH E AC M 85
Goldilocks:
A Race-Aware Java Runtime
By Tayfun Elmas, Shaz Qadeer, and Serdar Tasiran
Abstract
We present G, a Java runtime that monitors
program executions and throws a DataRaceExcept ion
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 compu-
tational 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 execu-
tions 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 incorpo-
rates 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 pro-
gram state, a race condition is said to occur. An equiva-
lent 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 asso-
ciate 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 detec-
tion when higher-level specifications such as atomicity
annotations do not exist. Second, a race condition makes
the outcome of certain shared variable accesses nondeter-
ministic. 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 execu-
tions 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 unde-
fined (as is the case for C++MM
2
) 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 G runtime for Java provides a
new exception, DataRaceException,
a
that is thrown pre-
cisely 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 program-
mer’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 syn-
chronization necessary to avoid a race in the meantime.
Since the first paper on the G runtime,
6
the idea
that certain concurrency errors, especially ones that result
in sequential consistency violations, should result in excep-
tions has gained significant support and several implemen-
tations of the idea have been investigated.
9, 11
To support a DataRaceException, a runtime must
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.
a
We define DataRaceException as a subclass of the Runtime-
Exception class in Java.
yanerabc900228
- 粉丝: 0
- 资源: 1
评论0