Colt 1.0.2

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


Constructor Summary
WaitFreeQueue()
           
 
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.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

WaitFreeQueue

public WaitFreeQueue()
Method Detail

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

Colt 1.0.2

Submit a bug or feature. Check the Colt home page for the latest news.