Java Reference
In-Depth Information
Figure 15.4. Queue in Intermediate State During Insertion.
Figure 15.5. Queue Again in Quiescent State After Insertion is Complete.
The key observation that enables both of the required tricks is that if the queue is in the qui-
escent state, the
next
field of the link node pointed to by
tail
is null, and if it is in the
intermediate state,
tail.next
is non-null. So any thread can immediately tell the state of
the queue by examining
tail.next
. Further, if the queue is in the intermediate state, it can
be restored to the quiescent state by advancing the tail pointer forward one node, finishing
the operation for whichever thread is in the middle of inserting an element.
[7]
LinkedQueue.put
first checks to see if the queue is in the intermediate state before at-
tempting to insert a new element (step
A
). If it is, then some other thread is already in the
process of inserting an element (between its steps
C
and
D
). Rather than wait for that thread
to finish, the current thread helps it by finishing the operation for it, advancing the tail pointer
(step
B
). It then repeats this check in case another thread has started inserting a new element,
advancing the tail pointer until it finds the queue in the quiescent state so it can begin its own
insertion.
The CAS at step
C
, which links the new node at the tail of the queue, could fail if two threads
try to insert an element at the same time. In that case, no harm is done: no changes have
been made, and the current thread can just reload the tail pointer and try again. Once
C
suc-
