原子变量与非阻塞算法

java传统上是使用锁来实现线程间的同步。每一个object都有一个内部锁(intrinsic lock)，关键字synchronized实现了锁的互斥。方法Object.wait主动的放弃锁，而方法Object.notify(All)则用来唤醒waiting中的线程。使用synchronized确保线程同步的正确性，但是也容易造成线程的阻塞。

volatile变量与锁相比是更轻量级的同步机制，但仅仅能保证内存的可见性，而不能用于原子化的操作。++i看起来是原子的，而实际上却是取当前值，自增加一，然后回写更新。

使用锁有以下的缺点：

(1)  如果线程持有锁而延迟，会导致其他的线程的等待。

(2)  高优先级的线程阻塞，而低优先级的线程持有锁造成优先级倒置(priority inversion)。

(3)  死锁(dead lock)。

独占锁是一种悲观的技术，总是假设闯入的线程会改变共享的变量。而对于细粒度的操作应该采用的乐观的解决方法。容许其他线程的闯入，但是在需要改变共享变量之前总是要检测其是否被修改。如果没有被修改，则完成更新，否则就放弃更新。CAS(compare and swap)就是这样的一种技术，现在已经被大多数处理器直接支持。

使用CAS的经典场景是：首先从V中读取值A，由A生成新值B，然后使用CAS原子化的把V的值由A改为B。如果V中的值A被改为其他的值，则CAS操作失败。所以在不使用锁的情况下，也可以解决读-写-改的问题。

CAS的模拟：

public class SimulatedCAS {
    private int value;
    
    public synchronized int getValue() { return value; }
    
    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        if (value == expectedValue) 
            value = newValue;
        return value;
    }
    
    public synchronized boolean compare(int expectedValue, int newValue) {
        return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}

 

原子类 

java.util.concurrent.atomic包提供了原子类来实现CAS操作。其中包括：AtomicInteger、AtomicLong、AtomicBoolean、AtomicReference等。

ABA问题

因为在更改 V 之前，CAS 总要询问V 的值是否仍为 A，所以在第一次读取 V 以及对 V 执行 CAS 操作之前，如果将值从 A 改为 B，然后再改回 A，会使基于 CAS 的算法混乱。这类问题称为ABA问题，通常通过将标记或版本编号与要进行CAS操作的每个值相关联，并原子地更新值和标记，来处理这类问题。 AtomicStampedReference 类支持这种方法。

非阻塞算法

许多数据结构的非阻塞版本都已经是实现，以下为Michael-Scott 非阻塞队列算法(CAS)的插入操作说明。

 

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 */;
                }
            }
        }
    }
}

 

每一次插入新的元素到队尾都涉及到两次更新，都是通过CAS完成的：从尾节点链接到新节点(C)，将新节点设置为尾节点(D)。第一步(C)一旦失败会继续while循环直到成功。如果成功则生效，其他线程可见。第二步操作则是设置尾节点。

图1 有两个节点，正常状态的队列

队列总是处在两种状态：正常状态(图1和图3)和中间状态(图2)。在插入之前和第二个CAS之后，队列处在正常状态；在第一个CAS之后，第二个CAS之前，队列处在中间状态。在正常状态下，tail的next节点为null；中间状态下tail的next节点为非null。通过步骤A就可以知道队列的状态。

图2 插入新节点后，中间状态的队列

 在插入新节点前(A)检查队列是否处于中间状态。如果是，则说明有他线程是在插入途中，即(C)和(D)之间。不必等待其完成，直接帮助其完成，把tail节点向前移动(B)。如果有必要(又有其他线程插入新的节点)，则接续向前移动tail节点，直到处于正常状态，再开始自己的插入操作。

图3 插入完成后，有3个节点，正常状态的队列

 总之，如果第一个CAS(C)因两个线程竞争tail节点导致失败，这种情况下没有反生修改，失去CAS的线程载入tail节点再次尝试。如果第二个CAS(D)失败，插入线程不需要重试，其他线程会帮助完成(B)。

 

非阻塞算法比非阻塞算法复杂的多，但是能更细粒度的共享变量，有更好的并发性能。

 

参考：

1. https://www.ibm.com/developerworks/cn/java/j-jtp11234/

2. http://www.ibm.com/developerworks/cn/java/j-jtp04186/

3. java concurrency in practice, Brian Goetz