java.lang.Object
org.ematgine.utils.concurrent.WaitFreeQueue
- All Implemented Interfaces:
- Channel, Puttable, Takable
- public class WaitFreeQueue
- extends java.lang.Object
- implements Channel
A wait-free linked list based queue implementation,
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.)
The main advantage of this implementation over
LinkedQueue
is that it does not strictly prohibit multiple concurrent
puts and/or multiple concurrent takes, but instead retries
these actions upon detection of interference.
Performance depends in part on the locking and scheduling
policies of the Java VM.
On at least some VMs, this implementation tends to perform well in
producer/consumer applications in which the queue is
hardly ever empty for long periods, normally because both the producers
and consumers are constantly active, and especially so on
multiple-CPU machines. However, it is a poor choice for
applications in which there is so much activity that
internal contention-based retries predominate computation, or
in which take() may be expected to have to wait
for items to appear. The blocking take() operation performs a busy-wait
spin loop, which can needlessly eat up CPU time, especially
on uniprocessors. It would be a better idea in this case to
use an otherwise similar (and usually at least as efficient)
LinkedQueue or BoundedLinkedQueue.
|
Nested Class Summary |
protected static class |
WaitFreeQueue.Node
Node class for linked list. |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
head_
protected final WaitFreeQueue.Node head_
- head_ and tail_ are used only as counted pointers,
not as nodes. They intially both point to a dummy empty node.
tail_
protected final WaitFreeQueue.Node tail_
WaitFreeQueue
public WaitFreeQueue()
insert
protected void insert(java.lang.Object x)
throws java.lang.InterruptedException
extract
protected java.lang.Object extract()
throws java.lang.InterruptedException
take
public java.lang.Object take()
throws java.lang.InterruptedException
- Spin until poll returns a non-null value.
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
poll
public java.lang.Object poll(long msecs)
throws java.lang.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
put
public void put(java.lang.Object x)
throws java.lang.InterruptedException
- 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 interface Channel
offer
public boolean offer(java.lang.Object x,
long msecs)
throws java.lang.InterruptedException
- 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 interface Channel
peek
public java.lang.Object peek()
- Description copied from interface:
Channel
- Return, but do not remove object at head of Channel,
or null if it is empty.
- Specified by:
peek in interface Channel
JAVADOC | 
SOURCE | 
DOWNLOAD | NESTED | FIELD | CONSTR | METHOD