无锁的Compare and Swap(CAS)操作是一种高效的并发编程技术,通过原子性的比较和交换操作,实现了无锁的线程同步。在我之前的文章《简单理解CAS》
CAS(Compare and Swap)是一种无锁并发算法,用于解决并发编程中的原子性操作问题。它是一种基于硬件指令的原子操作,能够在多线程环境下实现数据的原子性操作,而不需要使用传统的锁机制。
CAS(V, E, N)操作包括三个参数:
JDK中实现的compareAndSet():
/**
* 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(int expect, int update) {
// valueOffset: 内存中的值
// expect: 期望的值
// update: 更新的值
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
当V == E值时,才会将N赋值给V;如果V!=E时,说明已经有别的线程做了更新,当前线程什么都不做(一般是一种自旋的操作,不断的重试-----也是自旋锁)。
CAS操作是一个原子性操作,它在执行过程中不会被其他线程中断。因此,当多个线程同时执行CAS操作时,只有一个线程能够成功执行操作,其他线程将会失败。失败的线程可以选择重试操作或采取其他策略。
CAS操作的原理是基于底层硬件的支持,通常是通过处理器提供的原子性指令来实现的。这些指令可以保证对共享变量的读取和更新操作是原子性的,不会被其他线程干扰。
在执行CAS操作时,硬件会比较内存地址V的当前值和期望值A,并根据比较结果来决定是否更新内存地址V的值。
CAS操作的优势在于它避免了传统锁机制的开销,如线程阻塞和上下文切换。它能够在无锁的情况下实现原子性操作,提供更高的并发性能和更低的延迟。
在Java中,CAS操作主要通过java.util.concurrent.atomic包下的原子类来实现,如AtomicInteger、AtomicLong等。这些原子类封装了CAS操作,提供了一种线程安全的方式来操作共享变量,避免了手动使用锁的复杂性。
CAS(V, E, N)工作方式基于以下几个基本操作。
在执行CAS操作时,处理器提供了特定的原子指令,如compareAndSet,用于执行比较和交换操作。这些原子指令可以确保对共享变量的读取和更新是原子性的,不会被其他线程干扰。
示例:
import java.util.concurrent.atomic.AtomicInteger;
public class CASExample {
private static AtomicInteger counter = new AtomicInteger(0);
public static void main(String[] args) {
Thread thread1 = new Thread(() -> {
for (int i = 0; i < 1000; i++) {
int oldValue = counter.get();
int newValue = oldValue + 1;
while (!counter.compareAndSet(oldValue, newValue)) {
// 如果CAS操作失败,则重试
oldValue = counter.get();
newValue = oldValue + 1;
}
}
});
Thread thread2 = new Thread(() -> {
for (int i = 0; i < 1000; i++) {
int oldValue = counter.get();
int newValue = oldValue - 1;
while (!counter.compareAndSet(oldValue, newValue)) {
// 如果CAS操作失败,则重试
oldValue = counter.get();
newValue = oldValue - 1;
}
}
});
thread1.start();
thread2.start();
try {
thread1.join();
thread2.join();
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("Counter value: " + counter.get());
}
}
相对于传统的锁机制,它具有以下几个优势:
按照惯例,以上概念性的内容我们读完之后。要开始看CAS本质的东西了。从compareAndSet的实现来看,他调用的是:
unsafe.compareAndSwapInt(this, valueOffset, expect, update);
那么unsafe是啥?
在Java中,sun.misc.Unsafe是一个强大的、直接操作内存和执行低级别操作的工具类。它提供了一些底层操作,可以绕过Java语言的限制,直接操作内存,实现一些高级特性。
Unsafe类中的方法可以用于执行一些不安全的操作,比如直接操作内存、分配和释放内存、对象的创建和销毁、线程挂起和恢复等。它可以被认为是一种"黑魔法",因为它绕过了Java语言的安全性和限制,提供了对底层操作的直接控制。
在CAS操作中,compareAndSwapXXX系列方法就是用Unsafe类来进行的。这些方法可以直接操作内存中的值,并在满足特定条件时进行原子性的更新。通过Unsafe类提供的CAS操作,可以实现无锁算法,避免使用传统的锁机制,提高并发性能。
从unsafe实现的几个cas相关操作方法来看,使用了native方法,来间接访问硬件底层的功能。native具体方法使用C++实现。sun.misc.Unsafe提供了三个CAS操作,从方法名即可看出,分别针对Object类型、int类型和long类型。
public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);
需要注意的是,Unsafe类的使用需要谨慎,因为它绕过了Java的安全检查和内存模型,可能导致不可预测的结果和潜在的安全问题。在一般情况下,应该优先使用高级抽象和标准库提供的线程安全机制,只有在特定需求下,且对其使用有深入的了解和必要的安全措施时,才应考虑使用Unsafe类。
CAS固然性能很强,但是ABA问题是经常被提及的。什么是ABA问题?
ABA问题是指在CAS操作过程中,共享变量的值从A经过一系列操作变为B,然后再经过一系列操作又恢复为A。这样的操作序列可能导致CAS操作无法察觉到中间值的变化,从而造成意外的结果。
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicStampedReference;
/**
* 贵宾卡充值案例模拟。
* 当余额不足20的时候,充值20
* 另一条线程,当金额大于10的时候,消费10
* @author Shamee loop
* @date 2023/6/17
*/
public class ABAProblemExample {
static AtomicReference<Integer> money = new AtomicReference<>(15);
public static void main(String[] args) {
for (int i = 0; i < 3; i++) {
Integer m = money.get();
new Thread() {
public void run() {
while (true) {
if (m < 20) {
if (money.compareAndSet(m, m + 20)) {
System.out.println("余额小于20,充值成功。余额=" + money.get());
break;
}
} else {
System.out.println("余额大于20,无需充值");
break;
}
}
}
}.start();
new Thread() {
public void run() {
while (true) {
Integer m = money.get();
if (m > 10) {
System.out.println("余额大于10");
if (money.compareAndSet(m, m - 10)) {
System.out.println("消费10元,余额=" + money.get());
break;
}
} else {
System.out.println("余额不足");
break;
}
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}.start();
}
}
}
执行结果:
这里多充值了一次20。原因就是账户余额被反复修改,修改后值等于原来的值,误以为没有被修改过,所以导致CAS无法正确判断当前数据状态。
对象内部多维护一个版本号,每次操作的同时版本号+1;CAS原子操作时,不只是判断值的状态,也判断版本号是否等于原来的版本号;就算值相等,版本号不等,也判断为被线程修改过。
Java提供了AtomicStampedReference类,它在CAS操作中使用了额外的标记(stamp)来区分不同的操作序列,避免了ABA问题的出现。
/**
* @author Shamee loop
* @date 2023/6/20
*/
import java.util.concurrent.atomic.AtomicStampedReference;
public class ABAProblemSolutionExample {
static AtomicStampedReference<Integer> money = new AtomicStampedReference<>(15, 0);
public static void main(String[] args) {
Integer stamp = money.getStamp();
for (int i = 0; i < 3; i++) {
Integer m = money.getReference();
new Thread() {
public void run() {
while (true) {
if (m < 20) {
if (money.compareAndSet(m, m + 20, stamp, stamp + 1)) {
System.out.println("余额小于20,充值成功。余额=" + money.getReference());
break;
}
} else {
System.out.println("余额大于20,无需充值");
break;
}
}
}
}.start();
new Thread() {
public void run() {
while (true) {
Integer m = money.getReference();
Integer stamp = money.getStamp();
if (m > 10) {
System.out.println("余额大于10");
if (money.compareAndSet(m, m - 10, stamp, stamp + 1)) {
System.out.println("消费10元,余额=" + money.getReference());
break;
}
} else {
System.out.println("余额不足");
break;
}
}
try {
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}.start();
}
}
}
执行结果:
类似版本号机制,这里对象内部不仅维护了对象值,还维护了一个时间戳。当对应的值被修改时,同时更新时间戳。当CAS进行比较时,不仅要比较对象值,也要比较时间戳是否满足期望值,两个都满足,才会进行更新操作。
查看源码java.util.concurrent.atomic.AtomicStampedReference#compareAndSet:
/**
* Atomically sets the value of both the reference and stamp
* to the given update values if the
* current reference is {@code ==} to the expected reference
* and the current stamp is equal to the expected stamp.
*
* @param expectedReference the expected value of the reference
* @param newReference the new value for the reference
* @param expectedStamp the expected value of the stamp
* @param newStamp the new value for the stamp
* @return {@code true} if successful
*/
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
}