搞定Java多线程：并发容器核心原理 CAS AQS

Java 在多线程并发编程的时候，不可避免的有资源的同步问题，Java 有很多同步手段，但是追根到底核心原理就两类：CAS和AQS。

一、CAS(Compare and Swap)

1、CAS

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

2、CAS 的底层原理

比较并交换，它是一条CPU并发原语。判断内存某个位置的值是否为预期值，如果是更改为新值，这个过程是原子的。原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行过程中不允许被中断，也就是说CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。

CAS的底层实现把握好两点：Unsafe类（存在rt.jar中）+ CAS自旋锁。使用了处理器提供的CMPXCHG指令实现。

Unsafe类是CAS的核心类，由于java方法无法直接访问底层系统，需要通过本地(native)方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。Unsafe类存在于sun.misc包中，其内部方法操作可以像C的指针一样直接操作内存，类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务。

3、CAS 的 三大问题

CAS虽然很高效的解决原子操作，但是CAS仍然存在三大问题。

• ABA 问题
• 循环时间长开销大
• 只能保证一个共享变量的原子操作

1）ABA 问题

CAS，包含三个值：内存位置（V）、预期原值（A）和新值(B)。当V==A时，则V=B更新成功。但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。

解决方案：可以对每个值添加一个版本号来判断。在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B-3A。从Java1.5开始JDK的atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法作用是首先检查当前引用是否等于预期引用，并且当前标志是否等于预期标志，如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

2）循环时间长开销大

CAS比较与替换，预期值与内存值比较，true就更新新值，false就不进行任何操作，这是个死循环，比较的过程会一直执行。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销。

如果JVM能支持处理器提供的pause指令那么效率会有一定的提升，pause指令有两个作用，第一它可以延迟流水线执行指令（de-pipeline）,使CPU不会消耗过多的执行资源，延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零。第二它可以避免在退出循环的时候因内存顺序冲突（memory order violation）而引起CPU流水线被清空（CPU pipeline flush），从而提高CPU的执行效率。

3）只能保证一个共享变量的原子操作

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性。

解决方案：这个时候就可以用锁，或者有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如有两个共享变量i＝2,j=a，合并一下ij=2a，然后用CAS来操作ij。从Java1.5开始JDK提供了AtomicReference类来保证引用对象之间的原子性，可以把多个变量放在一个对象里来进行CAS操作。

4、基于 CAS 的并发容器

• ConcurrentHashMap：并发版 HashMap

• CopyOnWriteArrayList：并发版 ArrayList

• CopyOnWriteArraySet：并发 Set

• ConcurrentLinkedQueue：并发队列 (基于链表)

• ConcurrentLinkedDeque：并发队列 (基于双向链表)

• ConcurrentSkipListMap：基于跳表的并发 Map

• ConcurrentSkipListSet：基于跳表的并发 Set

二、AQS(AbstractQueuedSynchronizer)

1、AQS

AQS（AbstractQuenedSynchronizer）抽象的队列式同步器。是除了java自带的synchronized关键字之外的锁机制。

AQS的核心思想是：如果被请求的共享资源空闲，则将当前请求资源的线程设置为有效的工作线程，并将共享资源设置为锁定状态，如果被请求的共享资源被占用，那么就需要一套线程阻塞等待以及被唤醒时锁分配的机制，这个机制AQS是用CLH队列锁实现的，即将暂时获取不到锁的线程加入到队列中。

• CLH（Craig，Landin，and Hagersten）队列是一个虚拟的双向队列，虚拟的双向队列即不存在队列实例，仅存在节点之间的关联关系。

AQS是JDK下提供的一套用于实现基于FIFO等待队列的阻塞锁和相关的同步器的一个同步框架，实际就三个元素 ：。

• 被执行资源状态：要不就是0，要不是1，要不比1大。0的时候代表没线程执行，1的时候说明被执行了，比1大代表被重入了（就是被当前的执行者反复来回的获得执行权）。
• 当前执行者：就是取得被执行资源的执行权，可重入，除非把资源释放，后面等着的执行者获取不到执行权（需要一直释放到0）。
• 后面的排队等待着：一个双向队列，其中的节点在自旋等待执行权。

2、AQS的实现原理

AQS的实现主要在于维护一个volatile int state（代表共享资源）和一个FIFO线程等待队列（多线程争用资源被阻塞时会进入此队列）。队列中的每个节点是对线程的一个封装，包含线程基本信息，状态，等待的资源类型等。

AQS是将每一条请求共享资源的线程封装成一个CLH锁队列的一个结点（Node），来实现锁的分配。用大白话来说，AQS就是基于CLH队列，用volatile修饰共享变量state，线程通过CAS去改变状态符，成功则获取锁成功，失败则进入等待队列，等待被唤醒。

如图示，AQS维护了一个volatile int state和一个FIFO线程等待队列，多线程争用资源被阻塞的时候就会进入这个队列。state就是共享资源，其访问方式有如下三种：getState()，setState()，compareAndSetState()。

AQS 定义了两种资源共享方式：

• Exclusive：独占，只有一个线程能执行，如ReentrantLock
• Share：共享，多个线程可以同时执行，如Semaphore、CountDownLatch、ReadWriteLock，CyclicBarrier

不同的自定义的同步器争用共享资源的方式也不同。

3、基于 AQS 的并发容器

• ArrayBlockingQueue：阻塞队列 (基于数组)

• LinkedBlockingQueue：阻塞队列 (基于链表)

• LinkedBlockingDeque：阻塞队列 (基于双向链表)

• PriorityBlockingQueue：线程安全的优先队列

• SynchronousQueue：读写成对的队列

• LinkedTransferQueue：基于链表的数据交换队列

• DelayQueue：延时队列