Java Reference
In-Depth Information
needed. (The atomic field updaters are also useful when you want to perform atomic updates
while preserving the serialized form of an existing class.)
15.4.4. The ABA Problem
The
ABA problem
is an anomaly that can arise from the naive use of compare-and-swap in
algorithms where nodes can be recycled (primarily in environments without garbage collec-
tion). A CAS effectively asks “Is the value of
V
still
A
?”, and proceeds with the update if so.
In most situations, including the examples presented in this chapter, this is entirely sufficient.
However, sometimes we really want to ask “Has the value of
V
changed since I last observed
it to be
A
?” For some algorithms, changing
V
from
A
to
B
and then back to
A
still counts as a
change that requires us to retry some algorithmic step.
This
ABA problem
can arise in algorithms that do their own memory management for link
node objects. In this case, that the head of a list still refers to a previously observed node
is not enough to imply that the contents of the list have not changed. If you cannot avoid
the ABA problem by letting the garbage collector manage link nodes for you, there is still
a relatively simple solution: instead of updating the value of a reference, update a
pair
of
values, a reference and a version number. Even if the value changes from
A
to
B
and back
to
A
, the version numbers will be different.
AtomicStampedReference
(and its cous-
in
AtomicMarkableReference
) provide atomic conditional update on a pair of vari-
ables.
AtomicStampedReference
updates an object reference-integer pair, allowing
ableReference
updates an object reference-boolean pair that is used by some algorithms
to let a node remain in a list while being marked as deleted.
[9]
Summary
Nonblocking algorithms maintain thread safety by using low-level concurrency primitives
such as compare-and-swap instead of locks. These low-level primitives are exposed through
the atomic variable classes, which can also be used as “better volatile variables” providing
atomic update operations for integers and object references.
Nonblocking algorithms are difficult to design and implement, but can offer better scalability
under typical conditions and greater resistance to liveness failures. Many of the advances in
concurrent performance from one JVM version to the next come from the use of nonblocking
algorithms, both within the JVM and in the platform libraries.
