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.
No comments:
Post a Comment