Java Reference
In-Depth Information
The performance reversal between locks and atomics at differing levels of contention illus-
trates the strengths and weaknesses of each. With low to moderate contention, atomics offer
better scalability; with high contention, locks offer better contention avoidance. (CAS-based
algorithms also outperform lock-based ones on single-CPU systems, since a CAS always suc-
ceeds on a single-CPU system except in the unlikely case that a thread is preempted in the
middle of the read-modify-write operation.)
a
ThreadLocal
for the PRNG state. This implementation approach changes the behavior
of the class—each thread sees its own private sequence of pseudorandom numbers, instead
of all threads sharing one sequence—but illustrates that it is often cheaper to not share state
at all if it can be avoided. We can improve scalability by dealing more effectively with con-
tention, but true scalability is achieved only by eliminating contention entirely.
15.4. Nonblocking Algorithms
Lock-based algorithms are at risk for a number of liveness failures. If a thread holding a
lock is delayed due to blocking I/O, page fault, or other delay, it is possible that no thread
will make progress. An algorithm is called
nonblocking
if failure or suspension of any thread
cannot cause failure or suspension of another thread; an algorithm is called
lock-free
if, at
each step,
some
thread can make progress. Algorithms that use CAS exclusively for coordin-
ation between threads can, if constructed correctly, be both nonblocking and lock-free. An
uncontended CAS always succeeds, and if multiple threads contend for a CAS, one always
wins and therefore makes progress. Nonblocking algorithms are also immune to deadlock or
priority inversion (though they can exhibit starvation or livelock because they can involve
repeated retries). We've seen one nonblocking algorithm so far:
CasCounter
. Good non-
blocking algorithms are known for many common data structures, including stacks, queues,
priority queues, and hash tables—though designing new ones is a task best left to experts.
15.4.1. A Nonblocking Stack
Nonblocking algorithms are considerably more complicated than their lock-based equival-
ents. The key to creating nonblocking algorithms is figuring out how to limit the scope of
atomic changes to a
single
variable while maintaining data consistency. In linked collection
classes such as queues, you can sometimes get away with expressing state transformations
as changes to individual links and using an
AtomicReference
to represent each link that
must be updated atomically.
