Java Reference
In-Depth Information
has been partially completed and knows not to try immediately to apply its own update. Then
B
can wait (by repeatedly examining the queue state) until
A
finishes, so that the two don't
get in each other's way.
While this trick by itself would suffice to let threads “take turns” accessing the data structure
without corrupting it, if one thread failed in the middle of an update, no thread would be able
to access the queue at all. To make the algorithm nonblocking, we must ensure that the failure
of a thread does not prevent other threads from making progress. Thus, the second trick is to
make sure that if
B
arrives to find the data structure in the middle of an update by
A
, enough
information is already embodied in the data structure for
B
to
finish the update for A
. If
B
“helps”
A
by finishing
A
's operation,
B
can proceed with its own operation without waiting
for
A
. When
A
gets around to finishing its operation, it will find that
B
already did the job for
it.
LinkedQueue
in
Listing 15.7
shows the insertion portion of the Michael-Scott nonblocking
linked-queue algorithm (
Michael and Scott, 1996
)
, which is used by
Concur-
rentLinkedQueue
. As in many queue algorithms, an empty queue consists of a “sentinel”
or “dummy” node, and the head and tail pointers are initialized to refer to the sentinel. The
tail pointer always refers to the sentinel (if the queue is empty), the last element in the queue,
or (in the case that an operation is in mid-update) the second-to-last element.
Figure 15.3
il-
lustrates a queue with two elements in the normal, or
quiescent
, state.
Figure 15.3. Queue with Two Elements in Quiescent State.
Inserting a new element involves updating two pointers. The first links the new node to the
end of the list by updating the
next
pointer of the current last element; the second swings
the tail pointer around to point to the new last element. Between these two operations, the
queue is in the
intermediate
state, shown in
Figure 15.4
.
After the second update, the queue
is again in the quiescent state, shown in
Figure 15.5
.
