LinkedQueue.java

LinkedQueue.java

/**

* LinkedQueue

* <p/>

* Insertion in the Michael-Scott nonblocking queue algorithm

*

* @author Brian Goetz and Tim Peierls

*/

//ThreadSafe

public class LinkedQueue <E> {

private static class Node <E> {

final E item;

final AtomicReference<LinkedQueue.Node<E>> next;

public Node(E item, LinkedQueue.Node<E> next) {

this.item = item;

this.next = new AtomicReference<LinkedQueue.Node<E>>(next);

}

}

private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);

private final AtomicReference<LinkedQueue.Node<E>> head

= new AtomicReference<LinkedQueue.Node<E>>(dummy);

private final AtomicReference<LinkedQueue.Node<E>> tail

= new AtomicReference<LinkedQueue.Node<E>>(dummy);

public boolean put(E item) {

LinkedQueue.Node<E> newNode = new LinkedQueue.Node<E>(item, null);

while (true) {

LinkedQueue.Node<E> curTail = tail.get();

LinkedQueue.Node<E> tailNext = curTail.next.get();

if (curTail == tail.get()) {

if (tailNext != null) {

// Queue in intermediate state, advance tail

tail.compareAndSet(curTail, tailNext);

} else {

// In quiescent state, try inserting new node

if (curTail.next.compareAndSet(null, newNode)) {

// Insertion succeeded, try advancing tail

tail.compareAndSet(curTail, newNode);

return true;

}

}

}

}

}

}

The LinkedQueue class implements the insertion logic of the Michael-Scott nonblocking queue algorithm, a classic design for lock-free concurrent FIFO queues. It maintains atomic references to both the head and tail of a linked list and starts with a dummy node to simplify edge case handling. When inserting a new item, the algorithm creates a new node and enters a loop that examines the current tail and its next reference. If tail.next is not null, the queue is in an intermediate state—meaning another thread is in the process of inserting a node but hasn't yet advanced the tail pointer. In this case, the current thread helps by moving the tail forward to tail.next, assisting in completing the pending operation. If tail.next is null, the queue is in a quiescent state, ready to accept a new element. The thread attempts to atomically insert the new node at tail.next using CAS and then advances the tail to point to the new node. This cooperative approach ensures system-wide progress without locking, as threads can help each other finish updates, which is a hallmark of nonblocking algorithms.