EDU.oswego.cs.dl.util.concurrent

Class WaitFreeQueue

Implemented Interfaces:
Channel, Puttable, Takable

public class WaitFreeQueue
extends Object
implements Channel

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,

[ Introduction to this package. ]

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)
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.

Field Details

head

protected WaitFreeQueue.Node head
Head of list is always a dummy node *

tail

protected WaitFreeQueue.Node tail
Pointer to last node on list *

tailLock

protected final Object tailLock
Lock for simulating CAS for tail field *

Method Details

CASHead

protected boolean CASHead(WaitFreeQueue.Node oldHead,
                          WaitFreeQueue.Node newHead)
Simulate CAS for head field, using 'this' lock *

CASTail

protected boolean CASTail(WaitFreeQueue.Node oldTail,
                          WaitFreeQueue.Node newTail)
Simulate 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.
Specified by:
offer in interface Channel
offer in interface Puttable
Parameters:
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.
Returns:
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.
Specified by:
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.
Specified by:
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.
Specified by:
put in interface Channel
put in interface Puttable
Parameters:

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.
Specified by:
take in interface Channel
take in interface Takable