|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object EDU.oswego.cs.dl.util.concurrent.WaitFreeQueue
public class WaitFreeQueue
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.)
BoundedLinkedQueue
,
Nested Class Summary | |
---|---|
protected static class |
WaitFreeQueue.Node
List nodes for Queue |
Field Summary | |
---|---|
protected WaitFreeQueue.Node |
head
Head of list is always a dummy node |
protected WaitFreeQueue.Node |
tail
Pointer to last node on list |
protected java.lang.Object |
tailLock
Lock for simulating CAS for tail field |
Constructor Summary | |
---|---|
WaitFreeQueue()
|
Method Summary | |
---|---|
protected boolean |
CASHead(WaitFreeQueue.Node oldHead,
WaitFreeQueue.Node newHead)
Simulate CAS for head field, using 'this' lock |
protected boolean |
CASTail(WaitFreeQueue.Node oldTail,
WaitFreeQueue.Node newTail)
Simulate CAS for tail field |
protected java.lang.Object |
extract()
Main dequeue algorithm, called by poll, take. |
boolean |
offer(java.lang.Object x,
long msecs)
Place item in channel only if it can be accepted within msecs milliseconds. |
java.lang.Object |
peek()
Return, but do not remove object at head of Channel, or null if it is empty. |
java.lang.Object |
poll(long msecs)
Spin until poll returns a non-null value or time elapses. |
void |
put(java.lang.Object x)
Place item in the channel, possibly waiting indefinitely until it can be accepted. |
java.lang.Object |
take()
Spin until poll returns a non-null value. |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected volatile WaitFreeQueue.Node head
protected volatile WaitFreeQueue.Node tail
protected final java.lang.Object tailLock
Constructor Detail |
---|
public WaitFreeQueue()
Method Detail |
---|
protected boolean CASHead(WaitFreeQueue.Node oldHead, WaitFreeQueue.Node newHead)
protected boolean CASTail(WaitFreeQueue.Node oldTail, WaitFreeQueue.Node newTail)
public void put(java.lang.Object x) throws java.lang.InterruptedException
Channel
put
in interface Channel
put
in interface Puttable
x
- the element to be inserted. Should be non-null.
java.lang.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.public boolean offer(java.lang.Object x, long msecs) throws java.lang.InterruptedException
Channel
offer
in interface Channel
offer
in interface Puttable
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.
java.lang.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).protected java.lang.Object extract() throws java.lang.InterruptedException
java.lang.InterruptedException
public java.lang.Object peek()
Channel
peek
in interface Channel
public java.lang.Object take() throws java.lang.InterruptedException
take
in interface Channel
take
in interface Takable
java.lang.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.public java.lang.Object poll(long msecs) throws java.lang.InterruptedException
poll
in interface Channel
poll
in interface Takable
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.
java.lang.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).
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |