15.原子变量与非阻塞同步机制

非阻塞算法用底层的原子机器指令（例如比较并交换指令）代替锁来确保数据在并发访问中的一致性。非阻塞算法被广泛地用在操作系统和JVM中实现线程/进程调度机制、垃圾回收机制以及锁和其他并发数据结构。

由于非阻塞算法可以使多个线程在竞争相同的数据时不会发生阻塞，因此它能在粒度更细的层次上进行协调，并且极大地减少调度开销。而且，在非阻塞算法中不存在死锁和其他活跃性问题。在基于锁的算法中，如果一个线程在休眠或自旋的同时持有一个锁，那么其他线程都无法执行下去，而非阻塞算法不会受到单个线程失败的影响。

即使原子变量没有用于非阻塞算法的开发，它们也可以用做一种“更好的volatile类型变量”。原子变量提供了与volatile类型变量相同的内存语义，此外还支持原子的更新操作，从而使他们更加适用于实现计数器、序列发生器和统计数据收集等，同时还能比基于锁的方法提供更高的可伸缩性。

与锁相比，volatile变量是一种更轻量级的同步机制，因为在使用这些变量时不会发生上下文切换或线程调度等操作。然而，volatile变量同样存在一些局限：虽然它们提供了相似的可见性保证，但不能用于构建原子的复合操作。

独占锁是一项悲观技术——它假设最坏的情况，并且只有在确保其他线程不会造成干扰（通过获取正确的锁）的情况下才能执行。对于细粒度的操作，还有另外一种更高效的方法，也是一种乐观的方法，通过这种方法可以在不发生干扰的情况下完成更新操作。这种方法需要借助冲突检查机制来判断在更新过程中是否存在来自其他线程的干扰，如果存在，这个操作将失败，并且可以重试。现在，几乎所有的现代处理器中都包含了某种形式的原子读-改-写指令，例如比较并交换(Compare-and-Swap)或者关联加载/条件存储(Load-Linked/Store-Conditional)。操作系统和JVM使用这些指令来实现锁和并发的数据结构。

在大多数处理器架构中采用的方法是实现一个比较并交换(CAS)指令。CAS包含了3个操作数——需要读写的内存位置V、进行比较的值A和拟写入的新值B。当且仅当V的值等于A时，CAS才会通过原子方式用新值B来更新V的值，否则不会执行任何操作。无论位置V的值是否等于A，都将返回V原有的值。CAS是一项乐观的技术，它希望能成功地执行更新操作，并且如果有另一个线程在最近一次检查后更新了该变量，那么CAS能检测到这个错误。

public class SimulatedCAS {
    private int value;

    public synchronized int get() {
        return value;
    }

    public synchronized int compareAndSwap(int expectedValue, int newValue) {
        int oldValue = value;
        if (oldValue == expectedValue) {
            value = newValue;
        }
        return oldValue;
    }

    public synchronized boolean compareAndSet(int expectedValue, int newValue) {
        return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}

当多个线程尝试使用CAS同时更新同一个变量时，只有一个线程能更新变量的值，而其他线程都将失败。然而，失败的线程并不会被挂起（这与获取锁的情况不同：当获取锁失败时，线程将挂起），而是被告知在这次竞争中失败，并可以再次尝试。由于一个线程在竞争CAS时失败不会阻塞，因此它可以决定是否重新尝试，或者执行一些恢复操作，也或者不执行任何操作。这种灵活性就大大减少了与锁有关的活跃性风险。

public class CasCounter {
    private SimulatedCAS value;

    public int getValue() {
        return value.get();
    }

    public int increment() {
        int v;
        do {
            v = value.get();
        } while (v != value.compareAndSwap(v, v+1));
        return v+1;
    }
}

虽然Java语言的锁定语法比较简洁，但JVM和操作在管理锁时需要完成的工作却并不简单。在实现锁定时需要遍历JVM中一条非常复杂的代码路径，并可能导致操作系统级的锁定、线程挂起以及上下文切换等操作。在最好的情况下，在锁定时至少需要一次CAS，因此虽然在使用锁时没有用到CAS，但实际上也无法节约任何执行开销。另一方面，在程序内部执行CAS时不需要执行JVM代码、系统调用或线程调度操作。在应用级上看起来超长的代码路径，如果加上JVM和操作系统中的代码调用，那么事实上却变得更短。CAS的主要缺点是，它将使调用者处理竞争问题（通过重试、回退、放弃），而在锁中能自动处理竞争问题。（线程在获得锁之前一直阻塞）。

在Java5.0中引入了底层的支持，在int、long和对象的引用等类型上都公开了CAS操作，并且JVM把它们编译为底层硬件提供的最有效方法。

共有12个原子变量类，可分为4组：标量类（Scalar）、更新器类、数组类以及复合变量类。最常用的原子变量就是标量类：AtomicInteger、AtomicLong、AtomicBoolean以及AtomicReference。所有这些类都支持CAS，此外，AtomicInteger和AtomicLong还支持算术运算。（要想模拟其他基本类型的原子变量，可以将short或byte等类型与int类型进行转换，以及使用floatToIntBits或doubleToLongBits来转换浮点数）

原子数组类（只支持Integer、Long和Reference版本）中的元素可以实现原子更新。原子数组类为数组的元素提供了volatile类型的访问语义，这是普通数组所不具备的特性——volatile类型的数组仅在数组引用上具有volatile语义，而在其元素上则没有。

原子的标量类扩展了Number类，但并没有扩展一些基本类型的包装类，例如Integer或Long。事实上，它们也不能进行扩展：基本类型的包装类是不可修改的，而原子变量类是可修改的。在原子变量类中同样没有重新定义hashCode或equals方法，每个实例都是不同的。与其他可变对象相同，它们也不宜用作基于散列的容器中的键值。

public class CasNumberRange {
    private static class IntPair {
        final int lower;
        final int upper;

        public IntPair(int lower, int upper) {
            this.lower = lower;
            this.upper = upper;
        }
    }

    private final AtomicReference<IntPair> values = new AtomicReference<>(new IntPair(0, 0));

    public int getLower() {
        return values.get().lower;
    }

    public int getUpper() {
        return values.get().upper;
    }

    public void setLower(int i) {
        while (true) {
            IntPair oldv = values.get();
            if (i > oldv.upper) {
                throw new IllegalArgumentException("Cant set lower to " + i + " > upper");
            }
            IntPair newv = new IntPair(i, oldv.upper);
            if (values.compareAndSet(oldv, newv)) {
                return;
            }
        }
    }

    public void setUpper(int i) {
        while (true) {
            IntPair oldv = values.get();
            if (i < oldv.lower) {
                throw new IllegalArgumentException("Cant set upper to " + i + " < lower");
            }
            IntPair newv = new IntPair(oldv.lower, i);
            if (values.compareAndSet(oldv, newv)) {
                return;
            }
        }
    }
}

创建非阻塞算法的关键在于，找出如何将原子修改的范围缩小到单个变量上，同时还要维护数据的一致性。

public class ConcurrentStack<E> {
    private static class Node<E> {
        public final E item;
        public Node<E> next;

        public Node(E item) {
            this.item = item;
        }
    }

    AtomicReference<Node<E>> top = new AtomicReference<>();

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

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

public class LinkedQueue<E> {
    private static class Node<E> {
        final E item;
        final AtomicReference<Node<E>> next;

        public Node(E item, Node<E> nex) {
            this.item = item;
            this.next = new AtomicReference<>(nex);
        }
    }

    private final Node<E> dummy = new Node<>(null, null);
    private final AtomicReference<Node<E>> head = new AtomicReference<>(dummy);
    private final AtomicReference<Node<E>> tail = new AtomicReference<>(dummy);

    public boolean put(E item) {
        Node<E> newNode = new Node<>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> tailNext = curTail.next.get();
            if (curTail == tail.get()) {
                if (tailNext != null) {
                    // 队列处于中间状态，推进尾节点
                    tail.compareAndSet(curTail, tailNext);
                } else {
                    // 队列处于稳定状态，尝试插入新节点
                    if (curTail.next.compareAndSet(null, newNode)) {
                        tail.compareAndSet(curTail, newNode);
                        return true;
                    }
                }
            }
        }
    }
}

原子的域更新器类表示现有volatile域的一种基于反射的“视图”，从而能够在已有的volatile域上使用CAS。在更新器类中没有构造函数，要创建一个更新器对象，可以调用newUpdater工厂方法，并制定类和域的名字。

ABA问题有一个相对简单的解决方案：不是更新某个引用的值，而是更新两个值，包括一个引用和一个版本号。即使这个值由A变为B，然后又变为A，版本号也是不同的。AtomicStampedReference以及AtomicMarkableReference支持在两个变量上执行原子的条件更新。AtomicStampedReference将更新一个“对象——引用”二元组，通过在引用加上“版本号”，从而避免ABA问题。类似的，AtomicMarkableReference将更新一个"对象引用——布尔值"二元组，在某些算法中将通过这种二元组使节点保存在链表中的同时又将其标记为“已删除的节点”。

非阻塞算法通过底层的并发原语（例如比较并交换而不是锁）来维护线程的安全性。这些底层的并发原语通过原子变量类向外公开，这些类也用做一种“更好的volatile变量”，从而为整数和对象引用提供原子的更新操作。