09.非阻塞同步

非阻塞并发算法

非阻塞算法使用底层的原子机器指令代替锁来确保数据在并发访问中的一致性。
非阻塞算法被广泛用于在OS和JVM中实现线程、进程调度机制、垃圾回收机制以及锁和其他并发结构。

非阻塞同步方案和锁同步方案对比
非阻塞算法可以使多个线程在竞争相同的数据时不会发生阻塞（本质上是可以安全的基于原子指令的轮询），因此它能在更细粒度的层次上进行协调，可以减少调度的开销。在非阻塞算法中不存在死锁等活跃性问题。

基于锁的同步机制使用的是系统的互斥量，在一个锁被释放之前，所有需要此锁的线程必须等待（阻塞或者自旋等待），如果一个线程在休眠或自旋的同时持有一个锁，那么其他线程可能无法继续下去。

CAS

比较并交换（compareAndSwipe）是处理器提供的原子操作指令，它利用的是内存单元访问的互斥性，使得在多处理器系统依然能保证其原子性，即不可同时执行，一个指令周期完成，不可中断。所以这个指令是并发安全的。
CAS的功能可以使用以下代码表达：

int compare_and_swap(int *word,int testval,int newval){
    int oldval;
    oldval = *word;
    if(oldval == testval){
        *word =newval;
    }
    return oldval;
}

CAS是一种乐观的技术，它希望能够成功地执行更新操作，并且如果有另一个线程最近更新了变量，它可以检测出来。
当多个线程使用CAS同时更新同一个变量时，只有其中一个线程能够成功执行，其他的线程都将失败，并且失败的线程不会阻塞，它们能够判断出有更新，继而可以再次尝试或者执行一些恢复操作。不会造成阻塞，也就不会导致死锁等活跃性问题。

CAS的性能

CAS的性能会随着处理器数量的不同变化很大，在单个CPU的系统中，CAS通常只要很少的时钟周期，因为不需要处理器之间的同步，在多CPU的系统中，由于需要在处理器之间进行同步控制，时钟周期会相对更多，开销也就相对高一些。

一个经验法则：在大多数处理器上，在无竞争的锁获取和释放的“快速代码路径”上的开销，大概是CAS的两倍。

JVM对CAS的支持

在Java5之前，如果不编写明确的代码，就无法执行CAS。Java5引入对底层的支持，在int、long和引用上公开了CAS操作，并且jvm把他们编译成底层硬件提供的最有效方法。在支持CAS的平台上，运行时会编译成相应的机器指令，不支持的情况下JVM会使用自旋锁。
Java5中引入的原子变量类，使用了CAS，在java.util.concurrent包中的大多数类都使用类这些原子类；
在Java1.6的锁优化技术中，偏向锁和轻量级锁使用的CAS算法来优化锁的性能。

基于原子变量类实现非阻塞栈

public class ConcurrentStack<E>{
    AtomicReference<Node<E>> top = new AtomicReference<>();
    public void push(E e){
        Node<E> newHead = new Node(e);
        Node<E> oldHead;
        do{
            oldHead = top.get();
            newHead.next = oldHead;
        }while(!top.compareAndSet(oldHead,newHead));

    }

    public Node<E> pop(){
        Node<E> oldHead；
        Node<E> newHead；
        do{
            oldHead= top.get();
            if(oldHead == null)
                return null;
            newHead = oldHead.next;
        while (!top.compareAndSet(oldHead,newHead));
        return oldHead.item;
        }
    }

    private class Node<E>{
        public final E item;
        public Node<E> next;
        public Node(E item){
            this.item = item;
        }
    }
}

compareAndSet的实现伪代码：

public synchronized boolean compareAndSet(int expectVal,int newVal){
    return (expectVal == compareAndSwap(expectVal,newVal));
}

ConcurrentStack能保证并发安全，因为compareAndSet能保证原子性和可见性。在这个类中，唯一的共享变量时top，当一个线程需要改变栈的状态时，调用compareAndSet方法，这个方法与写入volatile变量有着相同的内存语义。

参考资料

[1] Java并发编程实战

09.非阻塞同步