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

非阻塞算法：使用低层原子化的机器指令取代锁，比如比较并交换，从而保证数据在并发访问下的一致性。

非阻塞算法广泛用于操作系统和JVM中的线程和进程调度、垃圾回收以及实现锁和其他的并发数据结构。

与锁相比：非阻塞算法的设计和实现都更加复杂，但是它们在可伸缩性和活跃度上占有很大的优势。

非阻塞算法可以让多个线程在竞争相同的资源时不会发生阻塞，所以他能在更精化的层面上调整粒度，并能大大减少调度的开销。（它对死锁和其他活跃度问题具有免疫性）

使用原子变量类，能够能高效地构建非阻塞算法。（Atomic）

13.1锁的劣势

  1. **对于基于锁，并且操作上过度细分的累，当频繁地发生锁的竞争时，调度与真正用于工作的开销间的比值会很不可观**。(也就是，同一时间，请求同一个锁的线程太多)
  3. **volatile变量**与锁相比是更轻的同步机制，应为它们**不会引起上下文的切换和线程调度**。但是它们**不能用于构建原子化的复合操作**。因为**volatile只提供了可见性保证**。（所以不能用它去实现计数器之列）
  5. 加锁还有其他缺点。当一个线程正在等待锁时，他不能做任何其他事情，如果一个线程在持有锁的情况下发生了延迟，那么其他所有需要该锁的线程都不能前进了。**如果阻塞的线程是优先级很高的线程，持有锁的线程优先级较低，那么就会造成性能风险，被称为优先级倒置**。
  7. **加锁对于细分的操作而言，是重量级的**。

13.2硬件对并发的支持

  1. **独占锁**是一项**悲观**的技术——**它假设最坏的情况**（如果你不锁门，就会有线程闯入，破坏秩序）。
  3. 对于细粒度的操作，有另外一种选择通常更加有效——**乐观**的解决方法。这个乐观的方法依赖于**冲突监测**，从而能判定更新过程中是否存在来自于其他成员的干涉，**在冲突发生的情况下，操作失败，并会重试（也可能不重试）**。（宽恕比准许更有效率）
  5. 针对多**处理器系统**设计的处理器提供了特殊的**指令**，用来管理**并发访问**的共享数据：**原子化的测试并设置、获取并增加、交换、比较并交换、加载链接/存储条件**。操作系统和JVM使用这些指令来实现锁和并发的数据结构。

13.2.1比较并交换

  1. 大多数处理器使用的架构方案都实现了**比较并交换(CAS)指令**。
  3. **CAS有3个操作数**：**内存位置V、旧的预期值A、新值B**。
  5.     **当且仅当V符合旧预期值A时，CAS用新值B原子化地更新V的值，否则它什么都不做。在任何一种情况下，都会返回V的真实值**。
  7. 理解：我认为V的值应该是A，如果是，那么将其赋值为B，如果不是，则不修改，并告诉我应该为多少？
  9. **CAS**是一项**乐观**的技术——它抱着成功的希望进行更新，并且**如果另一个线程在上次检查后更新了该变量，它能够发现错误**。
  11. 当**多个线程**试图使用CAS同时更新相同变量时，**其中一个会胜出**，并更新变量，**其他的会失败**，**失败的线程不会挂起(但是没有获取锁的线程就会被挂起)**，它们会被告知这一次赛跑失败，但**允许再尝试**。
  13. 使用CAS的典型模式：首先从V读取A，由A 生成B，然后使用CAS原子化地把V由A变成B，因为CAS能够发现来自其他线程的干扰，所以即使不使用锁，它也能够原子化地实现读写改问题。
//模拟CAS操作
@ThreadSafe
public class SimulatedCAS{
    @GuardedBy("this")
    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))
    }
}

13.2.2非阻塞计数器

示例：

//CasCounter不会发生阻塞，如果其他线程同时更新计数器，它会进行数次重试。
@ThreadSafe
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;
    }
}

CAS的计数器，性能上圆圆超过了基于锁的计数器，即使只有很小的竞争，或者不存在竞争。

获取非竞争锁的快速路径，通常至少需要一个CAS加上一个锁相关的细节琐事。所以，基于锁的计数器最好的情况也要比基于CAS的一般情况做更多是事情。

13.2.3JVM对CAS的支持

在Java5.0后，引入了底层的支持，将int、long和对象的引用暴露给CAS操作，并且JVM把他们编译为底层硬件提供的最有效的方法。

在支持CAS的平台上，运行时把它们编排成恰当的机器指令。

如果CAS式的指令不可用，JVM会使用自旋锁。

这些底层的JVM支持，用于那些具有原子化变量的类。

13.3原子变量类

更新原子变量的快速路径，比锁的快速路径更快。慢速路径绝对会比锁的慢速路径更快，因为它不会引起线程的挂起和重新调度。

AtomicInteger 代表了一个int值，并提供了get和set方法，它们与读取和写入可变的int有着相同的内存语义。它同样提供了一个compareAndSet方法(如果该方法成功返回，其内存效果和同时读取并写入一个volatile变量是一样的)，以及原子化的插入、递增、递减等方法。

**原子变量类共有12个**，分成**四组**：**计量器、域更新器、数组、以及复合变量**。

最常用的原子变量是**计量器**：AtomicInteger、AtomicLong、AtomicBoolean、AtomicReference。（它们都支持CAS，对于short或byte，把他们的值强制转成int，对于浮点数，使用floatToIntBits或doubleToLongBits）。

**原子化的数组类**：**只有Integer、Long、Reference**，它的**元素是可以被原子化地更新的**。原子数组类为数组的元素提供了volatile的访问语义。（**volatile类型的数组只针对数组的引用具有volatile语义，而不是它的元素**）。

**原子化的计量器类扩展于Number，它们并没有扩展基本类型的包装类**。

13.3.1性能比较：锁与原子变量

示例：

//使用ReentrantLock 实现随机数字生成器
@ThreadSafe
public class ReentrantLockPseudoRandom extends PseudoRandom{
    private final Lock lock = new ReentrantLock(false);
    private int seed;

    ReentrantLockPseudoRandom(int seed){
        this.seed = seed;
    }

    public int nextInt(int n){
        lock.lock();
        try{
            int s = seed;
            seed = calculateNext(s);
            int remainder = s % n;
            return remainder > 0 ? remainder : remainder + n;
        }finally{
            lock.unlock();
        }
    }
}


//使用AtomicInteger实现随机数字生成器
@ThreadSafe
public class AtomicPseudoRandom extends PseudoRandom{
    private AtomicInteger seed;

    AtomicPseudoRandom(int seed){
        this.seed = new AtomicInteger(seed);
    }

    public int nextInt(int n){
        while(true){
            int s = seed.get();
            int nextSeed = calculateNext(s);
            if(seed.compareAndSet(s,nextSeed)){
                int remainder = s % n;
                return remainder > 0 ? remainder : remainder + n;
            }
        }
    }
}

经过测试可以发现，在激烈的竞争下，锁略微胜过原子变量，但是在真实的竞争条件下，原子变量会胜过锁。在中低程度的竞争下，原子化提供更好的可伸缩性，高强度下，锁更好的帮助我们避免竞争。

13.4非阻塞算法

基于锁的算法会带来一些活跃度失败的风险。

**一个线程的失败或挂起不应该影响其他线程的失败或挂起，这样的算法被称为非阻塞算法**。

如果算法的每一步骤中都有一些线程能够继续执行，那么这样的算法称为**锁自由**。

在线程间使用CAS进行协调，这样的算法如果能构建正确的化，它即使非阻塞的，又是锁自由的。

好的非阻塞算法已经在多种常见的数据结构上现身，包括栈、队列、优先级队列、哈希表。

13.4.1非阻塞栈

实现同等功能前提下，非阻塞算法被认为是比基于锁的算法更加复杂。

创建非阻塞算法的前提是为维护数据的一致性，解决如何**把原子化范围缩小到一个唯一变量**。

比如：在链式容器类中，优势你可以不必再进行状态转换了，而把它变为对段都链接的修改，进而，你可以使用一个AtomicReference来表达每一个必须被原子更新的链接。

示例：

@ThreadSafe
public class ConcurrentStack<E>{
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();

    public void push(E item){
        Node<E> newHead = new Node<E>(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 == null){
                return null;
            }
            newHead = oldHead.next;
        }while(!top.compareAndSet(oldHead,newHead));
    }

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

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

这个示例阐释了非阻塞算法的所有特性：一些任务的完成具有不确定性，并可能必须重做。

在ConcurrentStack等中用到的非阻塞算法，其线程安全性源于：compareAndSet既能提供原子性，又能提供可见性保证，加锁也同样如此。

13.4.2非阻塞链表

构建非阻塞算法的窍门是：**缩小原子化的范围到唯一的变量**。

一个链接队列比栈更加复杂，因为它需要支持**首尾的快速访问**。为了实现，它会维护独立的队首指针和队尾指针。两个指针初始时都指向队列的末尾节点：当前最后一个元素的next指针，即队尾指针。**在成功加入新元素时，两个节点都需要原子化更新**。

思路：

  • 在多步更新中，确保数据结构总能处于一致状态。

    • 这样，如果线程B到达时发现线程A在更新中，B可以分辨操作已部分完成，这样直到不能立即开始自己的更新。B开始等待直到A完成更新。、

  • 确保如果B到达时发现数据结构正在被A修改，在数据结构中应该又足够多的信息，说明需要B来替代A完成更新。

    • 如果B“帮助”A完成其操作，那么B可以进行自己的操作，而不用等待A的操作完成。当A恢复后试图完成其操作，会发现B已经替它完成了。

示例：

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

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

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

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

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

13.4.3原子化的域更新器

示例：

private class Node<E>{
    private final E item;
    private volatile Node<E> next;

    public Node(E item){
        this.item = item;
    }
}
//Node的next域是通过使用nextUpdater的compareAndSet方法实现的
private static AtomicReferenceFieldUpdater<Node, Node> nextUpdater = AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "next");

原子化的域更新器类（在Integer、Long、Reference版本中可用），代表着已存在的volatile域基于反射的“视图”，使得CAS能够用于已有的volatile域。

更新器类没有构造函数，为了创建，你可以调用newUpdater的工厂方法，声明类和域的名称。域更新器类并不依赖特定的实例，它可以用于更新目标类任何实例的目标域。

一般情况下，普通的原子变量表现已经可以了。只有当你想要保存现有类的串行化形式时，原子化的域更新器才会有用。

13.4.4ABA问题

ABA问题：在某些算法中，把V的值由A转换为B，再转换为A，仍然记为一次改变。

ABA问题是因为在算法中误用比较并交换而引起的反常现象，节点被循环使用。（主要存在于不能被垃圾回收的环境中）

算法如果进行自身链接节点对象的内存管理，那么可能出现ABA问题。

解决方法：更新一对值，包括引用和版本号，不仅仅更新值的引用，版本号也随之更新。

AtomicStampedReference（以及它的同系AtomicMarkableReference）提供了一对变量原子化的条件更新。AtomicStampedReference更新对象引用的整数对，允许“版本化”引用是能够避免ABA问题的。

总结

非阻塞算法通过使用低层级并发原语，比如比较并交换，取代了锁。

原子变量类向用户提供了这些低层继原语。同时提供了整数类和对象引用的原子化更新操作。

非阻塞算法能够很好的预防活跃度失败。（但是设计和实现很困难）