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

川长思鸟来 2023-07-06 11:34 7阅读 0赞

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去改变状态符，成功则获取锁成功，失败则进入等待队列，等待被唤醒。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaXBmZWlfY3Nkbg_size_16_color_FFFFFF_t_70][]

如图示，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：延时队列

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaXBmZWlfY3Nkbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200219035634265.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NoaXBmZWlfY3Nkbg==,size_16,color_FFFFFF,t_70