JUC并发编程_深入理解CAS

- - CAS 的基本原理
  - CAS 的优缺点
  - Java 中的 CAS 实现
  - 原子引用 AtomicStampedReference 解决 ABA 问题

CAS 的基本原理

CAS 属于乐观锁的一种实现方式

比较（Compare）：检查内存位置的值是否等于预期原值。
执行（Swap）：如果相等，则将该位置值更新为新值。
原子性：上述两个步骤作为一个整体是原子的，不可中断。

CAS 的优缺点

优点：

非阻塞算法：CAS是一种非阻塞算法，它不会造成线程挂起或阻塞，因此不会引起线程上下文切换，从而减少了系统的开销。
高并发：在多线程环境下，CAS能有效避免使用锁（Locks）带来的问题，如死锁、线程饥饿等，从而提高了系统的并发性能。

缺点：

ABA问题：如果某个线程将内存位置的值从A改为B，然后又改回A，此时另一个线程使用CAS进行检查时会认为该值没有变化，但实际上它已经变化过了。
循环时间长开销大：如果CAS操作一直不成功，那么它会一直进行重试，这会增加CPU的开销。
只能保证一个共享变量的原子操作：CAS操作只能保证单个共享变量的原子操作，对于多个共享变量，CAS无法保证其原子性。

Java 中的 CAS 实现

在Java中，CAS主要通过 java.util.concurrent.atomic 包下的类来实现，如 AtomicInteger 、AtomicLong 、AtomicReference 等。这些类提供了 compareAndSet 方法，该方法就是 CAS 操作的 Java 实现。

例如，AtomicInteger 的 compareAndSet 方法签名如下：

public final boolean compareAndSet(int expect, int update)

该方法会尝试将当前值设置为 update，但条件是当前值等于 expect。如果当前值等于 expect，则成功更新并返回 true；否则不更新并返回 false。

import java.util.concurrent.atomic.AtomicInteger;
public class CASDemo {
	// CAS compareAndSwap: 比较并交换
	public static void main(String[] args) {
		AtomicInteger atomicInteger = new AtomicInteger(2020);
		// public final boolean compareAndSet(int expect, int update)
		// 如果是期望的值就更新，否则不更新
		System.out.println(atomicInteger.compareAndSet(2020, 2021));
		System.out.println(atomicInteger.get());
		// 通过自旋锁进行自增
		atomicInteger.getAndIncrement()
		System.out.println(atomicInteger.compareAndSet(2020, 2021));
		System.out.println(atomicInteger.get());
	}
}

getAndIncrement 方法的底层是通过 自旋锁 的方式实现的（循环时间长开销大）

public final int getAndIncrement() {
	return unsafe.getAndAddInt(this, valueOffset, 1);
}

public final int getAndAddInt(Object var1, long var2, int var4) {
	int var5;
	do {
		var5 = this.getIntVolatile(var1, var2);
	} while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
		return var5;
    }
}

原子引用 AtomicStampedReference 解决 ABA 问题

解决ABA问题的一种常见且有效的方法是使用带有版本号或时间戳的原子操作，这样可以确保在比较并交换（CAS）操作时，不仅能检查值是否相等，还能检查该值自上次读取以来是否未被其他线程修改过。

在 Java 中，java.util.concurrent.atomic 包提供了 AtomicStampedReference 类，它正是为了解决ABA问题而设计的，它在设置值的时候，除了要校验预期原值，还要校验版本号是否变更。

public boolean compareAndSet(V expectedReference, V newReference, int expectedStamp, int newStamp)

import java.util.concurrent.atomic.AtomicStampedReference;  

public class ABASolution {  
    public static void main(String[] args) {
    	// 使用AtomicStampedReference 定义共享变量（初始值1，版本号0）
        AtomicStampedReference<Integer> ref = new AtomicStampedReference<>(1, 0);  
        
        // 尝试将值从1更新为2  
        int[] expectedStamp = {ref.getStamp()};  
        int expectedValue = ref.getReference();  
        boolean resultA = ref.compareAndSet(expectedValue, 2, expectedStamp[0], expectedStamp[0] + 1);  

        // 尝试将值从1（但实际上是2，因为已经更新了）更新回1  
        // 这里预期原值和实际值不一致，预期原版本号也与实际版本号不一致，返回失败。
        boolean resultB1 = ref.compareAndSet(1, 1, expectedStamp[0], expectedStamp[0] + 1); 

        // 正确操作：应重新获取最新的版本号  
        int currentStamp = ref.getStamp();  
        boolean resultB2 = ref.compareAndSet(2, 1, currentStamp, currentStamp + 1);
    }  
}