⭐ 题目日期：

美团 - 2024/12/23

📝 题解：

CAS（比较并交换）是一种用于实现多线程同步的原子操作，广泛应用于无锁编程中。其核心过程如下：

---

1. 操作步骤

CAS操作通过以下三个步骤完成，且整个过程是原子性的（由硬件指令直接支持，如x86的CMPXCHG）：

1. 读取内存值
   从指定的内存位置（V）中读取当前值（Current Value）。

2. 比较值与预期值
   检查内存中的当前值是否等于预期的旧值（Expected Value，即操作开始前读取的值）。

3. 条件交换

   • 若相等：将内存值更新为新值（New Value），返回操作成功。
   • 若不相等：不进行任何修改，返回操作失败。

---

2. 伪代码表示

function CAS(V, Expected, New):
    if *V == Expected:
        *V = New
        return true
    else:
        return false

• 参数说明：
  • V：需要修改的内存地址。
  • Expected：预期内存中的旧值。
  • New：要写入的新值。

---

3. 硬件支持与原子性

• CPU指令：
  x86架构通过CMPXCHG指令实现CAS，确保操作在单个指令周期内完成，不会被线程调度打断。
• Java实现：
  JVM通过sun.misc.Unsafe类的compareAndSwapInt/Long/Object等本地方法，调用底层CPU指令。

---

4. 典型应用场景

（1）无锁数据结构

• 无锁队列/栈：通过CAS实现线程安全的插入和删除操作。
• 计数器：如AtomicInteger的原子递增操作。

  AtomicInteger count = new AtomicInteger(0);
  count.incrementAndGet(); // 内部基于CAS

（2）乐观锁

• 数据库版本控制：更新前检查版本号是否匹配。
• 缓存更新：确保缓存一致性。

---

5. 关键问题与解决方案

（1）ABA问题

• 问题描述：
  线程A读取内存值为A，此时线程B将值改为B后又改回A。线程A的CAS操作误认为值未变，导致逻辑错误。
• 解决方案：
  • 版本号标记：每次修改递增版本号（如AtomicStampedReference）。
  • 时间戳：记录修改时间，避免值回退。

（2）高竞争下的性能问题

• 问题：多线程频繁CAS失败导致大量重试（忙等待），CPU资源浪费。
• 解决方案：
  • 退避策略：失败后随机等待再重试（如指数退避）。
  • 队列化请求：将竞争线程排队，按序执行（如MCS锁）。

---

6. CAS与锁的对比

特性	CAS	锁（如synchronized）
实现方式	无锁，基于原子指令	基于互斥和线程阻塞
竞争处理	忙等待（自旋）	线程挂起，上下文切换
适用场景	低/中度竞争，短操作	高竞争，长临界区
性能开销	低（无上下文切换）	高（上下文切换与调度）
编程复杂度	高（需处理ABA问题与重试逻辑）	低（语法简单）

---

7. Java中的CAS示例

// 使用AtomicInteger实现线程安全计数器
public class Counter {
    private AtomicInteger value = new AtomicInteger(0);

    public void increment() {
        int oldValue;
        do {
            oldValue = value.get();
        } while (!value.compareAndSet(oldValue, oldValue + 1));
    }

    public int get() {
        return value.get();
    }
}

• 说明：compareAndSet在底层调用CAS指令，失败时循环重试（自旋锁）。

---

总结

• CAS核心：通过原子操作实现无锁同步，避免线程阻塞。
• 优点：高性能（低竞争时）、无死锁风险。
• 缺点：需处理ABA问题，高竞争时性能下降。
• 适用场景：计数器、状态标志、无锁数据结构等短操作场景。

理解CAS的机制及其局限性，有助于在并发编程中合理选择同步策略。