编辑“︁CAS原理”︁

= CAS原理 =

'''比较并交换'''（Compare-And-Swap，简称CAS）是一种无锁编程的核心技术，广泛应用于多线程环境下的原子操作。它通过硬件指令（如x86的`CMPXCHG`）实现，能够在不使用锁的情况下保证操作的原子性。

== 基本概念 ==
CAS操作包含三个参数：
* '''内存位置（V）'''：需要更新的变量地址
* '''预期原值（A）'''：线程认为变量当前的值
* '''新值（B）'''：希望设置的新值

操作逻辑用伪代码表示为：
<syntaxhighlight lang="java">
if (V == A) {
    V = B;
    return true;
} else {
    return false;
}
</syntaxhighlight>

当且仅当内存值V等于预期值A时，处理器才会将V更新为B，否则不执行任何操作。整个操作是一个'''原子过程'''。

=== 数学表示 ===
CAS操作可以用以下公式描述：
<math>CAS(V, A, B) = \begin{cases} 
V \leftarrow B & \text{if } V = A \\
\text{no-op} & \text{otherwise}
\end{cases}</math>

== 工作原理 ==
<mermaid>
sequenceDiagram
    participant Thread1
    participant Memory
    Thread1->>Memory: 读取V的值(A)
    Thread1->>Memory: 计算新值(B)
    Thread1->>Memory: CAS(V,A,B)
    alt V == A
        Memory-->>Thread1: 成功(True)
        Memory->>Memory: 更新为B
    else V != A
        Memory-->>Thread1: 失败(False)
    end
</mermaid>

== Java实现示例 ==
Java通过`java.util.concurrent.atomic`包提供CAS支持。以下是`AtomicInteger`的典型用法：

<syntaxhighlight lang="java">
import java.util.concurrent.atomic.AtomicInteger;

public class CASExample {
    public static void main(String[] args) {
        AtomicInteger atomicInt = new AtomicInteger(0);
        
        // 初始值: 0
        System.out.println("初始值: " + atomicInt.get());
        
        // 成功案例：预期值0匹配当前值
        boolean success1 = atomicInt.compareAndSet(0, 1);
        System.out.println("CAS(0,1)结果: " + success1 + ", 当前值: " + atomicInt.get());
        
        // 失败案例：预期值0不匹配当前值1
        boolean success2 = atomicInt.compareAndSet(0, 2);
        System.out.println("CAS(0,2)结果: " + success2 + ", 当前值: " + atomicInt.get());
    }
}
</syntaxhighlight>

'''输出结果：'''
<pre>
初始值: 0
CAS(0,1)结果: true, 当前值: 1
CAS(0,2)结果: false, 当前值: 1
</pre>

== ABA问题 ==
CAS操作存在'''ABA问题'''：如果一个值从A变成B又变回A，CAS会误认为没有变化。解决方案：
* 添加版本号（如`AtomicStampedReference`）
* 使用布尔标记

=== 版本号解决方案示例 ===
<syntaxhighlight lang="java">
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABASolution {
    public static void main(String[] args) {
        AtomicStampedReference<Integer> atomicRef = new AtomicStampedReference<>(100, 0);
        
        int[] stampHolder = new int[1];
        int value = atomicRef.get(stampHolder);
        int stamp = stampHolder[0];
        
        // 模拟ABA场景
        atomicRef.compareAndSet(value, 101, stamp, stamp+1);
        atomicRef.compareAndSet(101, 100, stamp+1, stamp+2);
        
        // 带版本号的CAS可以检测到中间变化
        boolean success = atomicRef.compareAndSet(100, 103, 0, 1);
        System.out.println("CAS是否成功: " + success);  // 输出false
    }
}
</syntaxhighlight>

== 性能特点 ==
* '''优点'''：
  * 无锁设计减少线程上下文切换
  * 高并发场景下性能优于同步锁
* '''缺点'''：
  * 自旋消耗CPU（长时间不成功时）
  * 只能保证单个变量的原子性
  * 存在ABA问题

== 实际应用场景 ==
1. '''计数器实现'''：如`AtomicInteger`的递增操作
2. '''非阻塞数据结构'''：ConcurrentLinkedQueue等并发集合
3. '''乐观锁控制'''：数据库版本控制、缓存更新

=== 自旋锁实现示例 ===
<syntaxhighlight lang="java">
public class SpinLock {
    private AtomicBoolean locked = new AtomicBoolean(false);
    
    public void lock() {
        while (!locked.compareAndSet(false, true)) {
            // 自旋等待
        }
    }
    
    public void unlock() {
        locked.set(false);
    }
}
</syntaxhighlight>

== 底层实现 ==
现代处理器通常提供CAS指令：
* x86: `CMPXCHG`指令
* ARM: `LDREX/STREX`指令对
Java通过JNI调用这些硬件指令，在HotSpot VM中对应实现为：
<syntaxhighlight lang="c++">
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END
</syntaxhighlight>

== 最佳实践 ==
1. 简单原子操作优先使用原子类（`AtomicInteger`等）
2. 复杂场景考虑`LongAdder`（高并发计数）
3. 需要版本控制时使用`AtomicStampedReference`
4. 避免长时间自旋，可结合少量休眠

== 参见 ==
* 内存屏障（Memory Barrier）
* 乐观锁与悲观锁
* Java内存模型（JMM）

[[Category:计算机科学]]
[[Category:面试技巧]]
[[Category:Java并发编程]]