EDU.oswego.cs.dl.util.concurrent
Class WaitFreeQueue
- Channel, Puttable, Takable
public class WaitFreeQueue
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.)
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) - Place item in channel only if it can be accepted within
msecs milliseconds.
|
Object | peek() - Return, but do not remove object at head of Channel,
or null if it is empty.
|
Object | poll(long msecs) - Spin until poll returns a non-null value or time elapses.
|
void | put(Object x) - Place item in the channel, possibly waiting indefinitely until
it can be accepted.
|
Object | take() - Spin until poll returns a non-null value.
|
tailLock
protected final Object tailLock
Lock for simulating CAS for tail field *
extract
protected Object extract()
throws InterruptedException
Main dequeue algorithm, called by poll, take. *
offer
public boolean offer(Object x,
long msecs)
throws InterruptedException
Place item in channel only if it can be accepted within
msecs milliseconds. The time bound is interpreted in
a coarse-grained, best-effort fashion.
- offer in interface Channel
- offer in interface Puttable
msecs
- the number of milliseconds to wait. If less than
or equal to zero, the method does not perform any timed waits,
but might still require
access to a synchronization lock, which can impose unbounded
delay if there is a lot of contention for the channel.
- true if accepted, else false
peek
public Object peek()
Return, but do not remove object at head of Channel,
or null if it is empty.
- peek in interface Channel
poll
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.
- poll in interface Channel
- poll in interface Takable
put
public void put(Object x)
throws InterruptedException
Place item in the channel, possibly waiting indefinitely until
it can be accepted. Channels implementing the BoundedChannel
subinterface are generally guaranteed to block on puts upon
reaching capacity, but other implementations may or may not block.
- put in interface Channel
- put in interface Puttable
take
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.
- take in interface Channel
- take in interface Takable