CAS底层原理与ABA问题

CAS定义

CAS(Compare And Swap)是一种无锁算法。CAS算法是乐观锁的一种实现。CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当预期值A和内存值V相同时，将内存值V修改为B并返回true，否则返回false。

CAS与synchronized

（1）synchronized加锁，同一时间段只允许一个线程访问，能够保证一致性但是并发性下降。

（2）CAS是一个自旋锁算法，使用do-while不断判断（没有加锁），保证一致性和并发性，但是比较消耗CPU资源。使用CAS就可以不用加锁来实现线程安全。

• 原子性保证：CAS算法依赖于rt.jar包下的sun.misc.Unsafe类，该类中的所有方法都是native修饰的，直接调用操作系统底层资源执行相应的任务。
• 内存可见性和禁止指令重排序的保证：AtomicXxx类中的成员变量value是由volatile修饰的：private volatile int value;

CAS算法的缺点

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

• 循环时间长、开销很大。

当某一方法比如：getAndAddInt执行时，如果CAS失败，会一直进行尝试。如果CAS长时间尝试但是一直不成功，可能会给CPU带来很大的开销。

• 只能保证一个共享变量的原子操作。

当操作1个共享变量时，我们可以使用循环CAS的方式来保证原子操作，但是操作多个共享变量时，循环CAS就无法保证操作的原子性，这个时候就需要用锁来保证原子性。

• 存在ABA问题

如果一个线程在初次读取时的值为A，并且在赋值的时候检查该值仍然是A，但是可能在这两次操作，之间有另外一个线程现将变量的值改成了B，然后又将该值改回为A，那么CAS会误认为该变量没有变化过。

CAS底层原理

sum.misc.Unsafe类中有多个方法被native关键字标记，这说明该方法是原生态的方法，它是一个调用非java语言的接口，也就是说这个接口的实现是其他语言实现的。CAS并发原语就是体现在java的sum.misc.Unsafe类中的各个方法，调用这个类中的CAS方法JVM就会通过其他语言生成若干条系统指令，完整这些指令的过程中，是不允许被中断的，所以CAS是一条CUP的原子指令，所以它不会造成数据不一致问题。

多线程情况下，number变量每次++都会出现线程安全问题，AtomicInteger则不会，因为它保证了原子性。

我们进去看，getAndIncrement调用的就是Unsafe类中的getAndAddInt方法，this表示当前对象，valueOffset表示变量值在内存中的偏移量（也就是内存地址）

我们再进入Unsafe类看看var1就是getAndIncrement方法传过来的对象，var2是系统偏移量，这里是使用了do-while循环，一开始循环就通过var1对象和var2偏移量获取期望值var5，进入循环，compareAndSwapInt方法被native关键字标记的，所以他是原子性的 ，var2的值与var的值相等时，则使用新的值var5+var4，返回true，循环条件取反则结束循环，否则如果var2与var5不相等就继续循环，直到条件不满足再跳出循环

java;gutter:true; // unsafe.class public final int getAndAddInt(Object var1, long var2, int var4) { int var5; do { // 获取对象var1，偏移量为var2地址上的值，并赋值给var5 var5 = this.getIntVolatile(var1, var2); /*<em> * 再次获取对象var1，偏移量var2地址上的值，并和var5进行比较： * - 如果不相等，返回false，继续执行do-while循环 * - 如果相等，将返回的var5数值和var4相加并返回 </em>/ } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4)); // 最终总是返回对象var1，偏移量为var2地址上的值，即上述所说的V。 return var5; }</p> <pre><code> ![CAS底层原理与ABA问题](https://johngo-pic.oss-cn-beijing.aliyuncs.com/articles/20230605/1483369-20200717111830994-611949930.png) ABA问题解决方案 使用AtomicStampedReference或者AtomicMarkableReference来解决CAS的ABA问题，思路类似于SVN版本号，SpringBoot热部署中trigger.txt **AtomicStampedReference解决方案：每次修改都会让stamp值加1，类似于版本控制号** ;gutter:true;
package com.raicho.mianshi.mycas;

import java.util.concurrent.atomic.AtomicReference;
import java.util.concurrent.atomic.AtomicStampedReference;

/**
* @author: Raicho
* @Description:
* @program: mianshi
* @create: 2020-07-17 10:19
**/
public class AtomicStampedReferenceABA {
private static AtomicReference ar = new AtomicReference<>(0);
private static AtomicStampedReference asr =
new AtomicStampedReference<>(0, 1);

public static void main(String[] args) {
System.out.println("=============演示ABA问题（AtomicReference）===========");
new Thread(() -> {
ar.compareAndSet(0, 1);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
ar.compareAndSet(1, 0);
System.out.println(Thread.currentThread().getName() + "进行了一次ABA操作");
}, "子线程").start();

try {
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}

boolean res = ar.compareAndSet(0, 100);
if (res) {
System.out.println("main成功修改, 未察觉到子线程进行了ABA操作");
}

System.out.println("=============解决ABA问题（AtomicStampReference）===========");
new Thread(() -> {
int curStamp = asr.getStamp();
System.out.println("t1获取当前stamp: " + curStamp);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
asr.compareAndSet(0, 1, curStamp, curStamp + 1);
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
asr.compareAndSet(1, 0, asr.getStamp(), asr.getStamp() + 1);
}, "t1").start();

new Thread(() -> {
int curStamp = asr.getStamp();
System.out.println("t2获取当前stamp: " + curStamp);
try {
Thread.sleep(5000);
} catch (InterruptedException e) {
e.printStackTrace();
}
boolean result = asr.compareAndSet(0, 100, curStamp, curStamp + 1);
if (!result) {
System.out.println("修改失败! 预期stamp: " + curStamp + ", 实际stamp: " + asr.getStamp());
}
}, "t2").start();
}
}

运行结果：

AtomicMarkableReference：如果不关心引用变量中途被修改了多少次，而只关心是否被修改过，可以使用AtomicMarkableReference：

java;gutter:true; package com.raicho.mianshi.mycas;</p> <p>import java.util.concurrent.atomic.AtomicMarkableReference;</p> <p>/<strong> * @author: Raicho * @Description: * @program: mianshi * @create: 2020-07-17 10:46 </strong>/ public class AtomicMarkableReferenceABA { private static AtomicMarkableReference amr = new AtomicMarkableReference<>(0, false);</p> <pre><code>public static void main(String[] args) { new Thread(() -> { amr.compareAndSet(0, 1, false, true); try { Thread.sleep(1000); } catch (InterruptedException e) { e.printStackTrace(); } amr.compareAndSet(1, 0, true, true); System.out.println("子线程进行了ABA修改!"); }, "子线程").start(); try { Thread.sleep(3000); } catch (InterruptedException e) { e.printStackTrace(); } boolean res = amr.compareAndSet(0, 100, false, true); if (!res) { System.out.println("修改失败! 当前isMarked: " + amr.isMarked()); } } </code></pre> <p>}

运行结果：

参考

知乎：https://zhuanlan.zhihu.com/p/93418208

csdn：https://blog.csdn.net/justry_deng/article/details/83449038

Original: https://www.cnblogs.com/raicho/p/13328780.html
Author: Raicho
Title: CAS底层原理与ABA问题