Atomic Variables and Nonblocking Synchronization - Java Concurrency in Practice - page 381

Stacks are the simplest linked data structure: each element refers to only one other element
and each element is referred to by only one object reference. ConcurrentStack in Listing
15.6 shows how to construct a stack using atomic references. The stack is a linked list of
Node elements, rooted at top , each of which contains a value and a link to the next element.
The push method prepares a new link node whose next field refers to the current top of the
stack, and then uses CAS to try to install it on the top of the stack. If the same node is still
on the top of the stack as when we started, the CAS succeeds; if the top node has changed
(because another thread has added or removed elements since we started), the CAS fails and
push updates the new node based on the current stack state and tries again. In either case,
the stack is still in a consistent state after the CAS.
CasCounter and ConcurrentStack illustrate characteristics of all nonblocking al-
gorithms: some work is done speculatively and may have to be redone. In Concur-
rentStack , when we construct the Node representing the new element, we are hoping that
the value of the next reference will still be correct by the time it is installed on the stack,
but are prepared to retry in the event of contention.
Nonblocking algorithms like ConcurrentStack derive their thread safety from the fact
that, like locking, compareAndSet provides both atomicity and visibility guarantees.
When a thread changes the state of the stack, it does so with a compareAndSet , which has
the memory effects of a volatile write. When a thread examines the stack, it does so by call-
ing get on the same AtomicReference , which has the memory effects of a volatile read.
So any changes made by one thread are safely published to any other thread that examines
the state of the list. And the list is modified with a compareAndSet that atomically either
updates the top reference or fails if it detects interference from another thread.
15.4.2. A Nonblocking Linked List
The two nonblocking algorithms we've seen so far, the counter and the stack, illustrate the
basic pattern of using CAS to update a value speculatively, retrying if the update fails. The
trick to building nonblocking algorithms is to limit the scope of atomic changes to a single
variable. With counters this is trivial, and with a stack it is straightforward enough, but for
more complicated data structures such as queues, hash tables, or trees, it can get a lot trickier.
A linked queue is more complicated than a stack because it must support fast access to both
the head and the tail. To do this, it maintains separate head and tail pointers. Two pointers
refer to the node at the tail: the next pointer of the current last element, and the tail pointer.
To insert a new element successfully, both of these pointers must be updated—atomically. At