| java.lang.Object
 EDU.oswego.cs.dl.util.concurrent.WaitFreeQueue
| WaitFreeQueue | | public class WaitFreeQueue implements Channel(Code) | | A wait-free linked list based queue implementation.
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
See Also: LinkedQueue
See Also: [ Introduction to this package. ] |
| Inner Class :final protected static class Node | |
| Method Summary | |
| protected synchronized boolean | CASHead(Node oldHead, Node newHead)
| | protected boolean | CASTail(Node oldTail, Node newTail)
| | protected Object | extract()
Main dequeue algorithm, called by poll, take. | | public boolean | offer(Object x, long msecs)
| | public Object | peek()
| | public Object | poll(long msecs)
Spin until poll returns a non-null value or time elapses. | | public void | put(Object x)
| | public Object | take()
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. |
| head | | protected volatile Node head(Code) | | Head of list is always a dummy node *
|
| tail | | protected volatile Node tail(Code) | | Pointer to last node on list *
|
| tailLock | | final protected Object tailLock(Code) | | Lock for simulating CAS for tail field *
|
| CASHead | | protected synchronized boolean CASHead(Node oldHead, Node newHead)(Code) | | Simulate CAS for head field, using 'this' lock *
|
| CASTail | | protected boolean CASTail(Node oldTail, Node newTail)(Code) | | Simulate CAS for tail field *
|
| poll | | public Object poll(long msecs) throws InterruptedException(Code) | | 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.
|
| take | | public Object take() throws InterruptedException(Code) | | 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.
|
|
|