org.amino.ds.lockfree
Class LockFreeQueue<E>

java.lang.Object
  java.util.AbstractCollection<E>
      java.util.AbstractQueue<E>
          org.amino.ds.lockfree.LockFreeQueue<E>

Type Parameters:

E - type of element in the queue

All Implemented Interfaces:

java.lang.Iterable<E>, java.util.Collection<E>, java.util.Queue<E>

public class LockFreeQueue<E>
extends java.util.AbstractQueue<E>
implements java.util.Queue<E>

This is an implementation of a lock-free FIFO queue data structure. The implementation is according to the paper An Optimistic Approach to Lock-Free FIFO Queues by Edya Ladan-Mozes and Nir Shavit, 2004. To gain a complete understanding of this data structure, please first read this paper, available at: http://www.springerlink.com/content/h84dfexjftdal4p4/

First-in-first-out (FIFO) queues are among the most fundamental and highly studied concurrent data structures. The most effective and practical dynamic-memory concurrent queue implementation in the literature is the lock-free FIFO queue algorithm of Michael and Scott, included in the standard Java Concurrency Package. This paper presents a new dynamic-memory lock-free FIFO queue algorithm that performs consistently better than the Michael and Scott queue.

The key idea behind our new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an optimistic doubly-linked list whose pointers are updated using a simple store, yet can be fixed if a bad ordering of events causes them to be inconsistent. It is a practical example of an optimistic approach to reduction of synchronization overhead in concurrent data structures.

Sample performance results here.

The following operations are thread-safe and scalable (but see notes in method javadoc): first, offer, poll, peek

The following operations are not thread-safe: size, iterator

Author:

Xiao Jun Dai

Constructor Summary

LockFreeQueue()
default constructor.

LockFreeQueue(java.util.Collection<? extends E> c)
Constructor with initial collection.

Method Summary

boolean	isEmpty()
java.util.Iterator<E>	iterator()
boolean	offer(E e)
E	peek()
E	poll()
int	size()

Methods inherited from class java.util.AbstractQueue

add, addAll, clear, element, remove

Methods inherited from class java.util.AbstractCollection

contains, containsAll, remove, removeAll, retainAll, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Queue

add, element, remove

Methods inherited from interface java.util.Collection

addAll, clear, contains, containsAll, equals, hashCode, remove, removeAll, retainAll, toArray, toArray

Constructor Detail

LockFreeQueue

public LockFreeQueue()

default constructor.

LockFreeQueue

public LockFreeQueue(java.util.Collection<? extends E> c)

Constructor with initial collection.

Parameters:

c - collection for initialization

Method Detail

isEmpty

public boolean isEmpty()

Specified by:

isEmpty in interface java.util.Collection<E>

Overrides:

isEmpty in class java.util.AbstractCollection<E>

iterator

public java.util.Iterator<E> iterator()

Specified by:

iterator in interface java.lang.Iterable<E>

Specified by:

iterator in interface java.util.Collection<E>

Specified by:

iterator in class java.util.AbstractCollection<E>

size

public int size()

Specified by:

size in interface java.util.Collection<E>

Specified by:

size in class java.util.AbstractCollection<E>

offer

public boolean offer(E e)

Specified by:

offer in interface java.util.Queue<E>

peek

public E peek()

Specified by:

peek in interface java.util.Queue<E>

poll

public E poll()

Specified by:

poll in interface java.util.Queue<E>