scale. Instead, let us focus here on one
abstract data structure—a stack—and
use it as an example of how the design
process might proceed.
I use as a departure point the acceptable sequentially specified notion
of a Stack<T> object: a collection of
items (of type T) that provides push()
and pop() methods satisfying the
last-in-first-out (LIFO) property: the last
item pushed is the first to be popped.
We will follow a sequence of refinement steps in the design of concurrent
versions of stacks. Each step will expose various design aspects and relax
some property of the implementation.
My hope is that as we proceed, the reader will grow to appreciate the complexi-ties involved in designing a correct
scalable concurrent data-structure.
tion’s value is equal to the expected
value, then it is replaced by the update
value, and otherwise the value is left
unchanged. The method call returns a
Boolean indicating whether the value
changed. A typical CAS takes significantly more machine cycles than a read
or a write, but luckily, the performance
of CAS is improving as new generations
of multicore processors role out.
In Figure 1, the push() method creates a new node and then calls tryPush() to try to acquire the lock. If the
CAS is successful, the lock is set to true
and the method swings the top reference from the current top-of-stack to
its successor, and then releases the
lock by setting it back to false. Otherwise, the tryPush() lock acquisition
attempt is repeated. The pop() method
figure 1. a lock-based Stack<T>: in the push() method, threads alternate between
trying to push an item onto the stack and managing contention by backing off before
retrying after a failed push attempt.
a Lock-based stack
We begin with a LockBasedStack<T>
implementation, whose Java pseudocode appears in figures 1 and 2. The
pseudocode structure might seem a bit
cumbersome at first, this is done in order to simplify the process of extending
it later on.
The lock-based stack consists of a
linked list of nodes, each with value
and next fields. A special top field
points to the first list node or is null if
the stack is empty. To help simplify the
presentation, we will assume it is illegal
to add a null value to a stack.
Access to the stack is controlled
by a single lock, and in this particular
case a spin-lock: a software mechanism
in which a collection of competing
threads repeatedly attempt to choose
exactly one of them to execute a section
of code in a mutually exclusive manner. In other words, the winner that
acquired the lock proceeds to execute
the code, while all the losers spin, waiting for it to be released, so they can attempt to acquire it next.
The lock implementation must enable threads to decide on a winner. This
is done using a special synchronization
instruction called a compare And Set()
(CAS), available in one form or another
on all of today’s mainstream multicore
processors. The CAS operation executes
a read operation followed by a write operation, on a given memory location, in
one indivisible hardware step. It takes
two arguments: an expected value and
an update value. If the memory loca-
1 public class LockBasedStack<T> {
2 private AtomicBoolean lock =
3 new AtomicBoolean(false);
4...
5 protected boolean tryPush(Node node) {
6 boolean gotLock = lock.compareAndSet(false, true);
7 if (gotLock) {
8 Node oldTop = top;
9 node.next = oldTop;
10 top = node;
11 lock.set ( false );
12 }
13 return gotLock;
14 }
15 public void push(T value) {
16 Node node = new Node(value);
17 while (true) {
18 if (tryPush(node)) {
19 return;
20 } else {
21 contentionManager.backoff();
22 }
23 }
24 }
figure 2. the lock-based Stack<T>: the pop() method alternates between trying to pop
and backing off before the next attempt.
1 protected Node tryPop() throws EmptyException {
2 boolean gotLock = lock.compareAndSet(false, true);
3 if (gotLock) {
4 Node oldTop = top;
5 if (oldTop == null) {
6 lock . set ( false );
7 throw new EmptyException();
8 }
9 top = oldTop.next;
10 return oldTop;
11 lock . set ( false );
12 }
13 else return null ;
14 }
15 public T pop() throws EmptyException {
16 while (true) {
17 Node returnNode = tryPop();
18 if (returnNode != null) {
19 return returnNode.value ;
20 } else {
21 contentionManager.backoff();
22 }
23 }
24 }
