EDU.oswego.cs.dl.util.concurrent
public class WaitFreeQueue extends Object implements Channel
While this class conforms to the full Channel interface, only the
put
and poll
methods are useful in most
applications. Because the queue does not support blocking
operations, take
relies on spin-loops, which can be
extremely wasteful.
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.)
See Also: BoundedLinkedQueue
Nested Class Summary | |
---|---|
protected static class | WaitFreeQueue.Node List nodes for Queue * |
Field Summary | |
---|---|
protected WaitFreeQueue.Node | head Head of list is always a dummy node * |
protected WaitFreeQueue.Node | tail Pointer to last node on list * |
protected Object | tailLock Lock for simulating CAS for tail field * |
Method Summary | |
---|---|
protected boolean | CASHead(WaitFreeQueue.Node oldHead, WaitFreeQueue.Node newHead) Simulate CAS for head field, using 'this' lock * |
protected boolean | CASTail(WaitFreeQueue.Node oldTail, WaitFreeQueue.Node newTail) Simulate CAS for tail field * |
protected Object | extract() Main dequeue algorithm, called by poll, take. |
boolean | offer(Object x, long msecs) |
Object | peek() |
Object | poll(long msecs)
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.
|
void | put(Object x) |
Object | take()
Spin until poll returns a non-null value.
|