并发专题（五）CAS与AQS

一、CAS(Compare And Swap)

什么是CAS

CAS(Compare And Swap)，即比较并交换。是解决多线程并行情况下使用锁造成性能损耗的一种机制，无锁的原子操作，CAS操作包含三个操作数——内存位置（V）、预期原值（A）和新值(B)。如果内存位置的值与预期原值相匹配，那么处理器会自动将该位置值更新为新值。否则，处理器不做任何操作。无论哪种情况，它都会在CAS指令之前返回该位置的值。CAS有效地说明了“我认为位置V应该包含值A；如果包含该值，则将B放到这个位置；否则，不要更改该位置，只告诉我这个位置现在的值即可。

在Java中，sun.misc.Unsafe 类提供了硬件级别的原子操作来实现这个CAS4。 java.util.concurrent 包下的大量类都使用了这个 Unsafe.java 类的CAS操作。至于 Unsafe.java 的具体实现这里就不讨论了。

CAS典型应用

java.util.concurrent.atomic 包下的类大多是使用CAS操作来实现的(eg. AtomicInteger.java,AtomicBoolean,AtomicLong)。下面以 AtomicInteger.java 的部分实现来大致讲解下这些原子类的实现。

public class AtomicInteger extends Number implements java.io.Serializable {
    private static final long serialVersionUID = 6214790243416807050L;

    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();

    private volatile int value;// 初始int大小
    // 省略了部分代码...

    // 带参数构造函数，可设置初始int大小
    public AtomicInteger(int initialValue) {
        value = initialValue;
    }
    // 不带参数构造函数,初始int大小为0
    public AtomicInteger() {
    }

    // 获取当前值
    public final int get() {
        return value;
    }

    // 设置值为 newValue
    public final void set(int newValue) {
        value = newValue;
    }

    //返回旧值，并设置新值为　newValue
    public final int getAndSet(int newValue) {
        /**
        * 这里使用for循环不断通过CAS操作来设置新值
        * CAS实现和加锁实现的关系有点类似乐观锁和悲观锁的关系
        * */
        for (;;) {
            int current = get();
            if (compareAndSet(current, newValue))
                return current;
        }
    }

    // 原子的设置新值为update, expect为期望的当前的值
    public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
    }

    // 获取当前值current，并设置新值为current+1
    public final int getAndIncrement() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return current;
        }
    }

    // 此处省略部分代码，余下的代码大致实现原理都是类似的
}

一般来说在竞争不是特别激烈的时候，使用该包下的原子操作性能比使用 synchronized 关键字的方式高效的多(查看getAndSet()，可知如果资源竞争十分激烈的话，这个for循环可能换持续很久都不能成功跳出。不过这种情况可能需要考虑降低资源竞争才是)。
在较多的场景我们都可能会使用到这些原子类操作。一个典型应用就是计数了，在多线程的情况下需要考虑线程安全问题。通常第一映像可能就是:

public class Counter {
    private int count;
    public Counter(){}
    public int getCount(){
        return count;
    }
    public void increase(){
        count++;
    }
}

上面这个类在多线程环境下会有线程安全问题，要解决这个问题最简单的方式可能就是通过加锁的方式,调整如下:

public class Counter {
    private int count;
    public Counter(){}
    public synchronized int getCount(){
        return count;
    }
    public synchronized void increase(){
        count++;
    }
}

这类似于悲观锁的实现，我需要获取这个资源，那么我就给他加锁，别的线程都无法访问该资源，直到我操作完后释放对该资源的锁。我们知道，悲观锁的效率是不如乐观锁的，上面说了Atomic下的原子类的实现是类似乐观锁的，效率会比使用 synchronized 关键字高，推荐使用这种方式，实现如下:

public class Counter {
    private AtomicInteger count = new AtomicInteger();
    public Counter(){}
    public int getCount(){
        return count.get();
    }
    public void increase(){
        count.getAndIncrement();
    }
}

二、AQS(AbstractQueuedSynchronizer)

队列同步器AbstractQueuedSynchronizer（以下简称同步器），是用来构建锁或者其他同步组件的基础框架。

它使用了一个int成员变量表示同步状态。

通过内置的FIFO双向队列来完成获取锁线程的排队工作。

同步器包含两个节点类型的应用，一个指向头节点，一个指向尾节点，未获取到锁的线程会创建节点线程安全（compareAndSetTail）的加入队列尾部。同步队列遵循FIFO，首节点是获取同步状态成功的节点。

未获取到锁的线程将创建一个节点，设置到尾节点。如下图所示：

首节点的线程在释放锁时，将会唤醒后继节点。而后继节点将会在获取锁成功时将自己设置为首节点。如下图所示：

独占式/共享式锁获取

独占式：有且只有一个线程能获取到锁，如：ReentrantLock

共享式：可以多个线程同时获取到锁，如：CountDownLatch

独占式

每个节点自旋观察自己的前一节点是不是Header节点，如果是，就去尝试获取锁。

独占式锁获取流程：

共享锁获取流程：

三、锁的使用用例

ConcurrentHashMap的实现原理及使用（JDK1.7）

ConcurrentHashMap类图（JDK1.7）

ConcurrentHashMap数据结构

结论：JDK1.7中使用ReentrantLock，ConcurrentHashMap使用的锁分段技术。首先将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问。JDK1.8中使用CAS+synchronized，不采用segment而采用node，锁住node来实现减小锁粒度，使用3个CAS操作来确保node的一些操作的原子性。