Do not go gentle into that good night ~

JUC-CAS是什么？ 2023-04-11|JUC|Java-并发编程-JUC

CAS面试提问环节：

synchronized、ReentrantLock、CAS全家桶发售

HashMap、Hashtable、ConcurrentHashMap组合拳出击

CAS简介

比较并交换(compare and swap, CAS)，是原子操作的一种。在多线程没有锁的状态下，可以保证多个线程对同一个值的更新。

CAS可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性，产生的数据不一致问题。该操作通过将内存中的值与指定数据进行比较，当数值一样时将内存中的数据替换为新的值。

CAS的特点

CAS结合volatile可以实现无锁并发，适用于线程数少，多核CPU场景下(单核CPU下while自旋纯属浪费时间)。
CAS体现着乐观锁思想（本身并无锁🔒，区别于synchronized）
CAS体现的是无锁并发、无阻塞并发
CAS的原子性 + volatile的可见性，不断的的【比较于交换】保证线程安全
没有用锁🔒来保证线程安全，所以不会阻塞
如果竞争激烈，会导致重试频繁发生，效率下降

CAS原理：自旋–比较-交换

CAS 操作中包含三个操作数 —— 内存位置 (V) 、预期原值 (E) 和新值(N)

这三个字母缩写的含义： Variable：变量；Expect：预期；New：新值

我们都知道，多个线程在访问共享资源的时候，会产生同步问题，所以需要加锁来保证安全。但是，一旦加了锁，同一时刻只能有一个线程获取锁对象，效率自然变低了。

那在多线程场景下，不加锁的情况下来修改值，CAS是怎么自旋的呢？

【用图举例来说明】

现在Data中存放的是num=0，线程A将num=0拷贝到自己的工作内存中计算（做+1操作）E=0，计算的结果为V=1
由于是在多线程不加锁的场景下操作，所以可能此时num会被别的线程修改为其他值。此时需要再次读取num看其是否被修改，记再次读取的值为N
如果被修改，即E != N，说明被其他线程修改过。那么此时工作内存中的E已经和主存中的num不一致了，根据EMSI协议，保证安全需要重新读取num的值。直到E = N才能修改
如果没被修改，即E = N，说明没被其他线程修改过。那门将工作内存中的E=0改为E=1，同时写回主存。将num=0改为num=1

再来一个经典的转账例子：

要在当前状态的余额下减10

什么是ABA问题

举个不恰当的例子🙃。张三和他的女朋友李四分手了，经历了全球变暖以及黄金的贬值的重重考验和磨难后最终又复合。那么，在分手期间，张三是不知道李四有没有重新找过男朋友的。但是，最终的男盆友是自己就行了！这就是ABA问题。

回归到问题本身：

在线程A计算V的时候，可能线程B将num=0改为了num=2，线程C又将num=2改回了num=0(也有可能是线程B或这任意线程)。此时num的值虽然还时0，但是num已经不是一开始的num了。

用一句哲学的话来讲，就是：“世界上没有两片相同的树叶”！

ABA问题怎么解决

CAS是无法解决ABA问题的。解决的策略有哪些呢？

添加版本号

大家在更新手机APP的时候，每次更新时软件都会有版本号。你更新完软件，还是原来的应用，但是版本号就不一样了。

同样，ABA问题也可以这样来求解。

我们把值num加一个版本号tag，当有线程修改的时候，版本号就会发生变化。在读取E的时候，同时将版本号tag也读取上，在比较E=?=N的时候，同时比较tag是否发生了改变。

添加时间戳

添加世时间戳也可以解决。查询的时候把时间戳一起查出来，对的上才修改并且更新值的时候一起修改更新时间，这样也能保证，方法很多但是跟版本号都是异曲同工之妙。

CAS锁升级

针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式：

先使用偏向锁优先同一线程，然后再次获取锁
如果失败，就升级为 CAS 轻量级锁
如果失败就会短暂自旋，防止线程被系统挂起
最后如果以上都失败就升级为重量级锁

CAS的优点与缺点

优点：

在多核CPU且并发量不是很高的时候可以提高效率。

缺点：

如果长时间循环对CPU的开销很大
CAS只能保证对一个变量的操作是原子性的，无法实现对多行代码实现原子性。
ABA问题
不能保证变量的内存可见性。CAS获取共享变量的值时，需要和volatile配合使用，来保证共享变量的可见性

CAS 实现自旋锁

既然用锁或 synchronized 关键字可以实现原子操作，那么为什么还要用 CAS 呢，因为加锁或使用 synchronized 关键字带来的性能损耗较大，而用 CAS 可以实现乐观锁（实际是无锁），它实际上是直接利用了 CPU 层面的指令，所以性能很高。

CAS 是实现自旋锁的基础，CAS 利用 CPU 指令保证了操作的原子性，以达到锁的效果。

这样一来，一个无限循环中，执行一个 CAS 操作，当操作成功，返回 true 时，循环结束；当返回 false 时，接着执行循环，继续尝试 CAS 操作，直到返回 true。

扩展：其实 JDK 中有好多地方用到了 CAS ,尤其是java.util.concurrent包下，比如 CountDownLatch、Semaphore、ReentrantLock 中，再比如 java.util.concurrent.atomic 包下，相信大家都用到过 Atomic* ，比如 AtomicBoolean、AtomicInteger 等。

AtomicBoolean 中的CAS

public class AtomicBoolean implements java.io.Serializable {
    private static final long serialVersionUID = 4654671469794556979L;
    // setup to use Unsafe.compareAndSwapInt for updates
    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicBoolean.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }
    private volatile int value;

    /**
     * Returns the current value.
     *
     * @return the current value
     */
    public final boolean get() {
        return value != 0;
    }
    
    /**
     * Atomically sets the value to the given updated value
     * if the current value {@code ==} the expected value.
     *
     * @param expect the expected value
     * @param update the new value
     * @return {@code true} if successful. False return indicates that
     * the actual value was not equal to the expected value.
     */
    public final boolean compareAndSet(boolean expect, boolean update) {
        int e = expect ? 1 : 0;
        int u = update ? 1 : 0;
        return unsafe.compareAndSwapInt(this, valueOffset, e, u);
    }
}

使用了sun.misc.Unsafe 对象，这个类提供了一系列直接操作内存对象的方法，只是在 jdk 内部使用，不建议开发者使用；
value 表示实际值，可以看到 get 方法实际是根据 value 是否等于0来判断布尔值的，这里的 value 定义为 volatile，因为 volatile 可以保证内存可见性，也就是 value 值只要发生变化，其他线程是马上可以看到变化后的值的；
valueOffset 是 value 值的内存偏移量，用 unsafe.objectFieldOffset 方法获得，用作后面的 compareAndSet 方法；
compareAndSet方法，这就是实现 CAS 的核心方法了，在使用 AtomicBoolean 的这个方法时，只需要传递期望值和待更新的值即可，而它里面调用了 unsafe.compareAndSwapInt(this, valueOffset, e, u) 方法，它是个 native 方法，用 c++ 实现，具体的代码就不贴了，总之是利用了 CPU 的 cmpxchg 指令完成比较并替换，当然根据具体的系统版本不同，实现起来也有所区别，感兴趣的可以自行搜一下相关文章。
CAS 必须借助 volatile 才能读取到共享变量的最新值来实现比较并交换的效果

基础知识之一：锁的类型

锁从宏观上分类，分为悲观锁与乐观锁。

乐观锁

乐观锁是一种乐观思想，即认为读多写少，遇到并发写的可能性低，每次去拿数据的时候都认为别人不会修改，所以不会上锁，但是在更新的时候会判断一下在此期间别人有没有去更新这个数据，采取在写时先读出当前版本号，然后加锁操作（比较跟上一次的版本号，如果一样则更新），如果失败则要重复读-比较-写的操作。

Java中的乐观锁基本都是通过CAS操作实现的，CAS是一种更新的原子操作，比较当前值跟传入值是否一样，一样则更新，否则失败。

Java中乐观锁的案例

ConcurrentHashMap

ConcurrentHashMap是Java中的一个线程安全的哈希表实现，它使用分离锁（Segment）来保证线程安全。每个Segment都是一个独立的哈希表，每个操作只锁定相关的Segment，因此可以支持更高的并发性。

ConcurrentHashMap使用了一种基于CAS的技术来实现乐观锁，它通过比较当前的value和预期的value是否相等来判断是否存在冲突。如果存在，则返回失败；如果不存在，则执行更新操作。

LongAdder

在 JDK1.8 中，Java 提供了一个新的原子类 LongAdder。LongAdder 在高并发场景下会比 AtomicInteger 和 AtomicLong 的性能更好，代价就是会消耗更多的内存空间。

LongAdder 的原理就是降低操作共享变量的并发数，也就是将对单一共享变量的操作压力分散到多个变量值上，将竞争的每个写线程的 value 值分散到一个数组中，不同线程会命中到数组的不同槽中，各个线程只对自己槽中的 value 值进行 CAS 操作，最后在读取值的时候会将原子操作的共享变量与各个分散在数组的 value 值相加，返回一个近似准确的数值。

数据库并发控制

在日常开发中，使用乐观锁最常见的场景就是数据库的更新操作了。

为了保证操作数据库的原子性，我们常常会为每一条数据定义一个版本号，并在更新前获取到它，到了更新数据库的时候，还要判断下已经获取的版本号是否被更新过，如果没有，则执行该操作。

CAS 乐观锁在平常使用时比较受限，它只能保证单个变量操作的原子性，当涉及到多个变量时，CAS 就无能为力了。

悲观锁

悲观锁是就是悲观思想，即认为写多，遇到并发写的可能性高，每次去拿数据的时候都认为别人会修改，所以每次在读写数据的时候都会上锁，这样别人想读写这个数据就会block直到拿到锁。Java中的悲观锁就是Synchronized, AQS框架下的锁则是先尝试cas乐观锁去获取锁，获取不到，才会转换为悲观锁，如RetreenLock。

Java中的锁机制

在 Java 中主要2种加锁机制:

synchronized 关键字
java.util.concurrent.Lock （Lock是一个接口，ReentrantLock是该接口一个很常用的实现）

这两种机制的底层原理存在一定的差别

synchronized 关键字通过一对字节码指令 monitorenter/monitorexit 实现，这对指令被 JVM 规范所描述。
java.util.concurrent.Lock 通过 Java 代码搭配sun.misc.Unsafe 中的本地调用实现的

基础知识之二：Java线程阻塞的代价

java的线程是映射到操作系统原生线程之上的，如果要阻塞或唤醒一个线程就需要操作系统介入，需要在户态与核心态之间切换，这种切换会消耗大量的系统资源，因为用户态与内核态都有各自专用的内存空间，专用的寄存器等，用户态切换至内核态需要传递给许多变量、参数给内核，内核也需要保护好用户态在切换时的一些寄存器值、变量等，以便内核态调用结束后切换回用户态继续工作。

如果线程状态切换是一个高频操作时，这将会消耗很多CPU处理时间；
如果对于那些需要同步的简单的代码块，获取锁挂起操作消耗的时间比用户代码执行的时间还要长，这种同步策略显然非常糟糕的。

synchronized会导致争用不到锁的线程进入阻塞状态，所以说它是java语言中一个重量级的同步操纵，被称为重量级锁，为了缓解上述性能问题，JVM从1.6开始，引入了轻量锁与偏向锁，默认启用了自旋锁，他们都属于乐观锁。

明确java线程切换的代价，是理解java中各种锁的优缺点的基础之一。

基础知识之三：Mark word

Java对象结构

在讲到锁之前，先来简单了解一下Java的对象结构。Java的对象结构主要包括对象头，实例数据，对齐填充三大部分。

对象头

对象头中存储了对象的Mark word，类型指针（元数据指针，指向方法区中的类元信息）和数组长度（只有当前对象为数组对象时才会有）。而Mark word又包括对象的Hashcode码，对象的分代年龄，对象的偏向锁ID，获取偏向锁的时间戳，锁标志位等。

Mark word主要用于存储对象自身运行时的数据，并且Mark word字段的长度与JVM的位数有关，32位的JVM虚拟机中Mark word占用32位的存储空间，64位的JVM虚拟机中占用64位的储存空间。

以32位的JVM虚拟机为例：

是否是偏向锁表示：当值为0时，标记对象没有开启偏向锁，值为1表示开启了偏向锁。

锁标志位表示：当前线程拥有的锁，不同状态下拥有的锁不同。

对象分代年龄表示：当JVM发生GC垃圾回收时，新生代未被回收的对象在Eden区和Survivor之间的复制，每次复制是的分代年龄+1，默认情况下分代年龄达到15会被移到老年代区域，当然这个参数也可以自行设置。

对象的Hashcode值：主要存储对象的Hashcode值。

线程ID：表示在偏向锁状态下，持有偏向锁的线程编号。

指向栈中锁记录的指针：在轻量级锁状态下，指向栈中所记录的指针。

指向（互斥量）重量级锁的指针：在重量级锁状态下，指向对象监视器Monitor的指针。

实例数据

实例数据主要存储了对象的成员变量信息，比如成员变量的具体值，父类成员变量的具体值等。

对象填充

在HotSpot虚拟机中，对象的起始地址必须为8的整数倍，如果当前对象的实例变量占用的储存空间不是8的整数倍，则需要使用填充数据来保证对齐。

基础知识之四：JVM锁升级机制

synchronized 关键字之锁的升级（偏向锁->轻量级锁->重量级锁）

synchronized详解：https://juejin.cn/post/6977744582725681182

前面提到过， synchronized 代码块是由一对 *monitorenter/moniterexit * 字节码指令实现， monitor 是其同步实现的基础， Java SE1.6 为了改善性能，使得 JVM 会根据竞争情况，使用如下 3 种不同的锁机制

偏向锁（Biased Lock ）
轻量级锁（ Lightweight Lock）
重量级锁（Heavyweight Lock）

上面几种锁都是JVM自己内部实现，当我们执行synchronized同步块的时候jvm会根据启用的锁和当前线程的争用情况，决定如何执行同步操作。这三种机制的切换是根据竞争激烈程度进行，在几乎无竞争的条件下，会使用偏向锁，在轻度竞争的条件下，会由偏向锁升级为轻量级锁，在重度竞争的情况下，会升级到重量级锁。

synchronized的执行过程：

检测Mark Word里面是不是当前线程的ID，如果是，表示当前线程处于偏向锁
如果不是，则使用CAS将当前线程的ID替换Mard Word，如果成功则表示当前线程获得偏向锁，置偏向标志位1
如果失败，则说明发生竞争，撤销偏向锁，进而升级为轻量级锁。
当前线程使用CAS将对象头的Mark Word替换为锁记录指针，如果成功，当前线程获得锁
如果失败，表示其他线程竞争锁，当前线程便尝试使用自旋来获取锁。
如果自旋成功则依然处于轻量级状态。
如果自旋失败，则升级为重量级锁。

详细图

简略图

JUC-Monitor 2023-04-11|JUC|Java-并发编程-JUC

内置锁在Java中被抽象为监视器锁（monitor）。在JDK 1.6之前，监视器锁可以认为直接对应底层操作系统中的互斥量（mutex）。这种同步方式的成本非常高，包括系统调用引起的内核态与用户态切换、线程阻塞造成的线程切换等。因此，后来称这种锁为“重量级锁”。在JDK1.6之前，使用synchronized是一个开销很大的操作，当然在1.6之后的版本中引入了不同级别的锁机制对synchronized底层进行了优化。

Monitor

Monitor 被翻译为监视器或管程

每个 Java 对象都可以关联一个 Monitor 对象，Monitor 也是 class，其实例存储在堆中，如果使用 synchronized 给对象上锁（重量级）之后，该对象头的 Mark Word 中就被设置指向 Monitor 对象的指针，这就是重量级锁

工作流程：

开始时 Monitor 中 Owner 为 null
当 Thread-2 执行 synchronized(obj) 就会将 Monitor 的所有者 Owner 置为 Thread-2，Monitor 中只能有一个 Owner，obj 对象的 Mark Word 指向 Monitor，把对象原有的 MarkWord 存入线程栈中的锁记录中（轻量级锁部分详解）
在 Thread-2 上锁的过程，Thread-3、Thread-4、Thread-5 也执行 synchronized(obj)，就会进入 EntryList BLOCKED（双向链表）
Thread-2 执行完同步代码块的内容，根据 obj 对象头中 Monitor 地址寻找，设置 Owner 为空，把线程栈的锁记录中的对象头的值设置回 MarkWord
唤醒 EntryList 中等待的线程来竞争锁，竞争是非公平的，如果这时有新的线程想要获取锁，可能直接就抢占到了，阻塞队列的线程就会继续阻塞
WaitSet 中的 Thread-0，是以前获得过锁，但条件不满足进入 WAITING 状态的线程（wait-notify 机制）

注意：

synchronized 必须是进入同一个对象的 Monitor 才有上述的效果
不加 synchronized 的对象不会关联监视器，不遵从以上规则

字节码层面

代码：

public static void main(String[] args) {
    Object lock = new Object();
    synchronized (lock) {
        System.out.println("ok");
    }
}
0: 	new				#2					// new Object
3: 	dup
4: 	invokespecial 	#1 		// invokespecial <init>:()V，非虚方法
7: 	astore_1 							// lock引用 -> lock
8: 	aload_1								// lock （synchronized开始）
9: 	dup										// 一份用来初始化，一份用来引用
10: astore_2 							// lock引用 -> slot 2
11: monitorenter 					// 【将 lock对象 MarkWord 置为 Monitor 指针】
12: getstatic 		#3			// System.out
15: ldc 			#4					// "ok"
17: invokevirtual 	#5 		// invokevirtual println:(Ljava/lang/String;)V
20: aload_2 							// slot 2(lock引用)
21: monitorexit 					// 【将 lock对象 MarkWord 重置, 唤醒 EntryList】
22: goto 30
25: astore_3 							// any -> slot 3
26: aload_2 							// slot 2(lock引用)
27: monitorexit 					// 【将 lock对象 MarkWord 重置, 唤醒 EntryList】
28: aload_3
29: athrow
30: return
Exception table:
    from to target type
      12 22 25 		any
      25 28 25 		any
LineNumberTable: ...
LocalVariableTable:
    Start Length Slot Name Signature
    	0 	31 		0 args [Ljava/lang/String;
    	8 	23 		1 lock Ljava/lang/Object;

说明：

通过异常 try-catch 机制，确保一定会被解锁
方法级别的 synchronized 不会在字节码指令中有所体现