EDU.oswego.cs.dl.util.concurrent

Class WaitFreeQueue

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 classWaitFreeQueue.Node
List nodes for Queue *
Field Summary
protected WaitFreeQueue.Nodehead
Head of list is always a dummy node *
protected WaitFreeQueue.Nodetail
Pointer to last node on list *
protected ObjecttailLock
Lock for simulating CAS for tail field *
Method Summary
protected booleanCASHead(WaitFreeQueue.Node oldHead, WaitFreeQueue.Node newHead)
Simulate CAS for head field, using 'this' lock *
protected booleanCASTail(WaitFreeQueue.Node oldTail, WaitFreeQueue.Node newTail)
Simulate CAS for tail field *
protected Objectextract()
Main dequeue algorithm, called by poll, take.
booleanoffer(Object x, long msecs)
Objectpeek()
Objectpoll(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.
voidput(Object x)
Objecttake()
Spin until poll returns a non-null value.

Field Detail

head

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

tail

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

tailLock

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

Method Detail

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()
Main dequeue algorithm, called by poll, take. *

offer

public boolean offer(Object x, long msecs)

peek

public Object peek()

poll

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

put

public void put(Object x)

take

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. If you would rather use, for example, an exponential backoff, you could manually set this up using poll.