并发专题（五）CAS与AQS

爱被打了一巴掌 2023-07-04 12:54 16阅读 0赞

## 一、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成员变量表示同步状态。 ###

![format_png][]

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

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

![format_png 1][]

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

![format_png 2][]

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

![format_png 3][]

AQS定义两种资源共享方式：Exclusive(独占、只有一个线程执行，如ReentrantLock)和Share(共享，多个线程可同时执行，如Semaphore/CountDownLatch)

那什么是独占式？

在谈synchronized的资源共享实现方式的时候，当线程A访问共享资源的时候，其它的线程全部被堵塞，直到线程A读写完毕，其它线程才能申请同步互斥锁从而访问共享资源。如果之前看过我关于synchronized的讨论，这里应该不难理解，为了照顾未了解过的读者，再重新回顾一下。

以RenentrantLock为例，如何知道共享资源是否有线程正在被访问呢？其实，它有一个state变量初始值为0，表示未锁定状态。当线程A访问的时候，state+1，就代表该线程锁定了共享资源，其他线程将无法访问，而当线程A访问完共享资源以后，state-1，直到state等于0，就将释放对共享变量的锁定，其他线程将可以抢占式或者公平式争夺。当然，它支持可重入，那什么是可重入呢？同一线程可以重复锁定共享资源，每锁定一次state+1，也就是锁定多次。说明：锁定多少次就要释放多少次。

什么是共享式呢？

以CountDownLatch为例，共享资源可以被N个线程访问，也就是初始化的时候，state就被指定为N（N与线程个数相等），线程countDown()一次，state会CAS减1，直到所有线程执行完（state=0），那些await()的线程将被唤醒去执行执行剩余动作。

什么是CAS？CAS的定义为Compare-And-Swap，语义为比较并且交换。在深入理解JVM书中，谈到自旋锁，因为锁的堵塞释放对于cpu资源的损害很高，那么自旋锁就是当线程A访问共享资源的时候，其他线程并不放弃对锁的持有，它们在不停循环，不断尝试的获取锁，直到获得锁就停止循环，自旋锁是对于资源共享的一种优化手段，但是它适用于对锁持有时间比较短的情况。

独占式

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

![format_png 4][]

独占式锁获取流程：

![format_png 5][]

共享锁获取流程：

![format_png 6][]

## 三、锁的使用用例 ##

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

![format_png 7][]

ConcurrentHashMap类图（JDK1.7）

![format_png 8][]

ConcurrentHashMap数据结构

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

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS04NGYwYmViN2E4NzQ5MjM5P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzAwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[format_png 1]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS05MmVkOTNjMzJmYWI0Y2U0P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvMTA4MC9mb3JtYXQvd2VicA?x-oss-process=image/format,png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS00ZTZmNjg0YWZkZWFkNWFiP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzAwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[format_png 3]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS1lNTQwYzIxYmY5NjEyNGY4P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvMTA4MC9mb3JtYXQvd2VicA?x-oss-process=image/format,png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS0yMjgzNDFhOGU5NTY1Mjk2P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvMTA4MC9mb3JtYXQvd2VicA?x-oss-process=image/format,png
[format_png 5]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS1jZDNhOWZjYzkyYWE2MGM4P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzAwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS0wMzBkYWZmNjEzYzEzYmM2P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzAwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[format_png 7]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS03NWI2ZjcyNWQ0MDc2NjViP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzAwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png
[format_png 8]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy8xNTQxMDA5MS02OWEwYTVmYzUyNTE2Nzk2P2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXB8aW1hZ2VWaWV3Mi8yL3cvNzAwL2Zvcm1hdC93ZWJw?x-oss-process=image/format,png