public class: WaitFreeQueue
All Implemented Interfaces:
A wait-free linked list based queue implementation.
While this class conforms to the full Channel interface, only the
poll methods are useful in most
applications. Because the queue does not support blocking
take relies on spin-loops, which can be
This class is adapted from the algorithm described in Simple,
Fast, and Practical Non-Blocking and Blocking Concurrent Queue
Algorithms by Maged M. Michael and Michael L. Scott. This
implementation is not strictly wait-free since it relies on locking
for basic atomicity and visibility requirements. Locks can impose
unbounded waits, although this should not be a major practical
concern here since each lock is held for the duration of only a few
statements. (However, the overhead of using so many locks can make
it less attractive than other Channel implementations on JVMs where
locking operations are very slow.)
|protected volatile Node ||head ||Head of list is always a dummy node * |
|protected volatile Node ||tail ||Pointer to last node on list * |
|protected final Object ||tailLock ||Lock for simulating CAS for tail field * |
|Methods from java.lang.Object:|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait|
|Method from EDU.oswego.cs.dl.util.concurrent.WaitFreeQueue Detail:|
protected synchronized boolean CASHead(Node oldHead,
Simulate CAS for head field, using 'this' lock *
protected boolean CASTail(Node oldTail,
Simulate CAS for tail field *
protected Object extract() throws InterruptedException
Main dequeue algorithm, called by poll, take. *
public boolean offer(Object x,
long msecs) throws InterruptedException
public Object peek()
public Object poll(long msecs) throws InterruptedException
Spin until poll returns a non-null value or time elapses.
if msecs is positive, a Thread.sleep(0) is performed on each iteration
as a heuristic to reduce contention.
public void put(Object x) throws InterruptedException
public Object take() throws InterruptedException
Spin until poll returns a non-null value.
You probably don't want to call this method.
A Thread.sleep(0) is performed on each iteration
as a heuristic to reduce contention. If you would
rather use, for example, an exponential backoff,
you could manually set this up using poll.