非阻塞算法

fyjava

以下内容摘自 http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html?S_TACT=105AGX02&S_CMP=EDU
 
1. 使用CAS的非阻塞计数器
public class NonblockingCounter {    private AtomicInteger value;    public int getValue() {        return value.get();    }    public int increment() {        int v;        do {            v = value.get();        }         while (!value.compareAndSet(v, v + 1));        return v + 1;    }}  
2. 使用Treiber算法的非阻塞栈
public class ConcurrentStack<E> {    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();    public void push(E item) {        Node<E> newHead = new Node<E>(item);        Node<E> oldHead;        do {            oldHead = head.get();            newHead.next = oldHead;        } while (!head.compareAndSet(oldHead, newHead));    }    public E pop() {        Node<E> oldHead;        Node<E> newHead;        do {            oldHead = head.get();            if (oldHead == null)                 return null;            newHead = oldHead.next;        } while (!head.compareAndSet(oldHead,newHead));        return oldHead.item;    }    static class Node<E> {        final E item;        Node<E> next;        public Node(E item) { this.item = item; }    }} 
3. Michael-Scott的非阻塞队列算法
public class LinkedQueue <E> {    private static class Node <E> {        final E item;        final AtomicReference<Node<E>> next;        Node(E item, Node<E> next) {            this.item = item;            this.next = new AtomicReference<Node<E>>(next);        }    }    private AtomicReference<Node<E>> head        = new AtomicReference<Node<E>>(new Node<E>(null, null));    private AtomicReference<Node<E>> tail = head;    public boolean put(E item) {        Node<E> newNode = new Node<E>(item, null);        while (true) {            Node<E> curTail = tail.get();            Node<E> residue = curTail.next.get();            if (curTail == tail.get()) {                if (residue == null) /* A */ {                    if (curTail.next.compareAndSet(null, newNode)) /* C */ {                        tail.compareAndSet(curTail, newNode) /* D */ ;                        return true;                    }                } else {                    tail.compareAndSet(curTail, residue) /* B */;                }            }        }    }}