Java Reference
In-Depth Information
Even ignoring these hazards, locking is simply a heavyweight mechanism for fine-grained
operations such as incrementing a counter. It would be nice to have a finer-grained technique
for managing contention between threads—something like volatile variables, but offering the
possibility of atomic updates as well. Happily, modern processors offer us precisely such a
mechanism.
15.2. Hardware Support for Concurrency
Exclusive locking is a
pessimistic
technique—it assumes the worst (if you don't lock your
door, gremlins will come in and rearrange your stuff) and doesn't proceed until you can guar-
antee, by acquiring the appropriate locks, that other threads will not interfere.
For fine-grained operations, there is an alternate approach that is often more efficient—the
optimistic
approach, whereby you proceed with an update, hopeful that you can complete
it without interference. This approach relies on
collision detection
to determine if there has
been interference from other parties during the update, in which case the operation fails and
can be retried (or not). The optimistic approach is like the old saying, “It is easier to obtain
forgiveness than permission”, where “easier” here means “more efficient”.
Processors designed for multiprocessor operation provide special instructions for managing
concurrent access to shared variables. Early processors had atomic
test-and-set
,
fetch-and-in-
crement
, or
swap
instructions sufficient for implementing mutexes that could in turn be used
to implement more sophisticated concurrent objects. Today, nearly every modern processor
has some form of atomic read-modify-write instruction, such as
compare-and-swap
or
load-
linked/store-conditional
. Operating systems and JVMs use these instructions to implement
locks and concurrent data structures, but until Java 5.0 they had not been available directly to
Java classes.
15.2.1. Compare and Swap
The approach taken by most processor architectures, including IA32 and Sparc, is to imple-
ment a
compare-and-swap
(CAS) instruction. (Other processors, such as PowerPC, imple-
ment the same functionality with a pair of instructions:
loadlinked
and
store-conditional
.)
CAS has three operands—a memory location
V
on which to operate, the expected old value
A
, and the newvalue
B
. CAS atomically updates
V
to the new value
B
, but only if the value
in
V
matches the expected old value
A
; otherwise it does nothing. In either case, it returns the
value currently in
V
. (The variant called compare-and-set instead returns whether the opera-
tion succeeded.) CAS means “I think
V
should have the value
A
; if it does, put
B
there, oth-
erwise don't change it but tell me I was wrong.” CAS is an optimistic technique—it proceeds
