edu.oswego.cs.dl.util.concurrent
Class WaitFreeQueue
java.lang.Object
|
+--edu.oswego.cs.dl.util.concurrent.WaitFreeQueue
- All Implemented Interfaces:
- Channel, Puttable, Takable
- public class WaitFreeQueue
- extends 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.
- See Also:
BoundedLinkedQueue
,
[ Introduction to this package. ]
Method Summary |
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. |
WaitFreeQueue
public WaitFreeQueue()
offer
public boolean offer(Object x,
long msecs)
throws 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
- Following copied from interface:
edu.oswego.cs.dl.util.concurrent.Channel
- Parameters:
item
- 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).
peek
public 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
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
- Following copied from interface:
edu.oswego.cs.dl.util.concurrent.Channel
- 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 false return).
put
public void put(Object x)
throws 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
- Following copied from interface:
edu.oswego.cs.dl.util.concurrent.Channel
- Parameters:
item
- 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.
take
public Object take()
throws 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
- Following copied from interface:
edu.oswego.cs.dl.util.concurrent.Channel
- 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.
Submit a bug or feature. Check the Colt home page for the latest news.