Class WaitFreeQueue
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:
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprotected static final class
List nodes for Queue -
Field Summary
FieldsModifier and TypeFieldDescriptionprotected WaitFreeQueue.Node
Head of list is always a dummy nodeprotected WaitFreeQueue.Node
Pointer to last node on listprotected final Object
Lock for simulating CAS for tail field -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected boolean
CASHead
(WaitFreeQueue.Node oldHead, WaitFreeQueue.Node newHead) Simulate CAS for head field, using 'this' lockprotected boolean
CASTail
(WaitFreeQueue.Node oldTail, WaitFreeQueue.Node newTail) Simulate CAS for tail fieldprotected Object
extract()
Main dequeue algorithm, called by poll, take.boolean
Place item in channel only if it can be accepted within msecs milliseconds.peek()
Return, but do not remove object at head of Channel, or null if it is empty.poll
(long msecs) Spin until poll returns a non-null value or time elapses.void
Place item in the channel, possibly waiting indefinitely until it can be accepted.take()
Spin until poll returns a non-null value.
-
Field Details
-
head
Head of list is always a dummy node -
tail
Pointer to last node on list -
tailLock
Lock for simulating CAS for tail field
-
-
Constructor Details
-
WaitFreeQueue
public WaitFreeQueue()
-
-
Method Details
-
CASHead
Simulate CAS for head field, using 'this' lock -
CASTail
Simulate CAS for tail field -
put
Description copied from interface:Channel
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 interfaceChannel
- Specified by:
put
in interfacePuttable
- Parameters:
x
- the element to be inserted. Should be non-null.- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case the element is guaranteed not to be inserted. Otherwise, on normal return, the element is guaranteed to have been inserted.
-
offer
Description copied from interface:Channel
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 interfaceChannel
- Specified by:
offer
in interfacePuttable
- Parameters:
x
- the element to be inserted. Should be non-null.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
- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case the element is guaranteed not to be inserted (i.e., is equivalent to a false return).
-
extract
Main dequeue algorithm, called by poll, take.- Throws:
InterruptedException
-
peek
Description copied from interface:Channel
Return, but do not remove object at head of Channel, or null if it is empty. -
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.- Specified by:
take
in interfaceChannel
- Specified by:
take
in interfaceTakable
- Returns:
- some item from the channel. Different implementations may guarantee various properties (such as FIFO) about that item
- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case state of the channel is unchanged.
-
poll
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 interfaceChannel
- Specified by:
poll
in interfaceTakable
- Parameters:
msecs
- the number of milliseconds to wait. If less than or equal to zero, the operation 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:
- some item, or null if the channel is empty.
- Throws:
InterruptedException
- if the current thread has been interrupted at a point at which interruption is detected, in which case state of the channel is unchanged (i.e., equivalent to a null return).
-