Knowledge/1 使用/volatile + CAS 无锁编程模式.md

无锁编程（Lock-Free Programming）是一种通过原子操作（如CAS）而非传统锁机制实现线程安全的技术，volatile保证可见性，CAS保证原子性，二者结合构成经典的无锁编程模式。

一、核心组件原理

1. volatile 的作用

// volatile 保证可见性和有序性
private volatile int value;

// 主要特性：
// 1. 可见性：写操作立即刷新到主内存
// 2. 有序性：禁止指令重排序
// 3. 不保证原子性（需要CAS补充）

2. CAS (Compare-And-Swap)

// 伪代码表示CAS操作
boolean compareAndSwap(int expectedValue, int newValue) {
    if (this.value == expectedValue) {
        this.value = newValue;
        return true;
    }
    return false;
}

// Java中的原子类底层实现
// sun.misc.Unsafe 类的CAS操作
public final native boolean compareAndSwapInt(
    Object o, long offset, int expected, int x);

二、典型实现模式

1. 无锁计数器

public class LockFreeCounter {
    private volatile int value;
    
    public void increment() {
        int oldValue;
        do {
            oldValue = value;  // volatile读，获取最新值
        } while (!compareAndSet(oldValue, oldValue + 1));
    }
    
    // 模拟CAS操作（实际使用AtomicInteger或Unsafe）
    private synchronized boolean compareAndSet(int expected, int newValue) {
        if (value == expected) {
            value = newValue;
            return true;
        }
        return false;
    }
}

2. 使用AtomicInteger的实现

import java.util.concurrent.atomic.AtomicInteger;

public class AtomicCounter {
    private AtomicInteger count = new AtomicInteger(0);
    
    public void increment() {
        int oldValue;
        do {
            oldValue = count.get();
        } while (!count.compareAndSet(oldValue, oldValue + 1));
    }
    
    // 简化写法
    public void incrementSimple() {
        count.getAndIncrement();  // 内部也是CAS实现
    }
}

三、复杂数据结构示例

1. 无锁栈

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeStack<T> {
    private static class Node<T> {
        T value;
        Node<T> next;
        
        Node(T value) {
            this.value = value;
        }
    }
    
    private AtomicReference<Node<T>> top = new AtomicReference<>();
    
    public void push(T value) {
        Node<T> newHead = new Node<>(value);
        Node<T> oldHead;
        do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));
    }
    
    public T pop() {
        Node<T> oldHead;
        Node<T> newHead;
        do {
            oldHead = top.get();
            if (oldHead == null) {
                return null;
            }
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));
        
        return oldHead.value;
    }
}

2. 无锁队列（Michael-Scott队列）

import java.util.concurrent.atomic.AtomicReference;

public class LockFreeQueue<T> {
    private static class Node<T> {
        T value;
        AtomicReference<Node<T>> next;
        
        Node(T value) {
            this.value = value;
            this.next = new AtomicReference<>(null);
        }
    }
    
    private AtomicReference<Node<T>> head;
    private AtomicReference<Node<T>> tail;
    
    public LockFreeQueue() {
        Node<T> dummy = new Node<>(null);
        head = new AtomicReference<>(dummy);
        tail = new AtomicReference<>(dummy);
    }
    
    public void enqueue(T value) {
        Node<T> newNode = new Node<>(value);
        Node<T> currentTail;
        Node<T> currentTailNext;
        
        while (true) {
            currentTail = tail.get();
            currentTailNext = currentTail.next.get();
            
            if (currentTail == tail.get()) {
                if (currentTailNext == null) {
                    // 尝试链接新节点
                    if (currentTail.next.compareAndSet(null, newNode)) {
                        // 尝试移动tail指针
                        tail.compareAndSet(currentTail, newNode);
                        return;
                    }
                } else {
                    // 帮助其他线程完成操作
                    tail.compareAndSet(currentTail, currentTailNext);
                }
            }
        }
    }
}

四、应用场景与最佳实践

1. 适用场景

// 1. 高并发计数器
// 2. 状态标志位
// 3. 累积统计信息
// 4. 实现无锁数据结构
// 5. 线程池的工作窃取

2. 最佳实践

public class OptimizedCASUsage {
    // 1. 减少CAS失败率：使用局部变量缓存
    public void optimizedIncrement(AtomicInteger counter) {
        int oldValue;
        int newValue;
        do {
            oldValue = counter.get();  // volatile读
            newValue = oldValue + 1;
        } while (!counter.compareAndSet(oldValue, newValue));
    }
    
    // 2. 指数退避策略减少竞争
    public void incrementWithBackoff(AtomicInteger counter) {
        int delay = 1;
        while (true) {
            int oldValue = counter.get();
            if (counter.compareAndSet(oldValue, oldValue + 1)) {
                break;
            }
            // 失败后指数退避
            LockSupport.parkNanos(delay);
            delay = Math.min(delay * 2, 1000000); // 最大1ms
        }
    }
}

3. 性能优化技巧

// 1. 使用LongAdder替代AtomicLong（高并发写场景）
import java.util.concurrent.atomic.LongAdder;

public class HighPerformanceCounter {
    private LongAdder adder = new LongAdder();
    
    public void increment() {
        adder.increment();  // 内部使用分段CAS
    }
    
    public long sum() {
        return adder.sum();
    }
}

// 2. 使用Striped64思想减少竞争
// 3. 考虑缓存行填充避免伪共享
@sun.misc.Contended
class PaddedAtomicLong extends AtomicLong {
    // 自动填充缓存行
}

五、注意事项与陷阱

1. ABA问题

// 解决方案：使用版本戳或标记指针
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABASolution {
    private AtomicStampedReference<Integer> ref = 
        new AtomicStampedReference<>(0, 0);
    
    public void update(int newValue) {
        int[] stampHolder = new int[1];
        int oldValue;
        int oldStamp;
        
        do {
            oldValue = ref.get(stampHolder);
            oldStamp = stampHolder[0];
        } while (!ref.compareAndSet(
            oldValue, newValue, 
            oldStamp, oldStamp + 1));
    }
}

2. 自旋消耗CPU

// 解决方案：限制自旋次数或使用退避策略
public class SpinLimit {
    private static final int MAX_SPINS = 1000;
    
    public boolean casWithSpinLimit(AtomicInteger atomic) {
        int spins = 0;
        int oldValue;
        do {
            if (spins++ > MAX_SPINS) {
                Thread.yield();  // 让出CPU
                spins = 0;
            }
            oldValue = atomic.get();
        } while (!atomic.compareAndSet(oldValue, oldValue + 1));
        return true;
    }
}

3. 内存顺序问题

// 使用VarHandle提供更精细的内存顺序控制
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;

public class VarHandleExample {
    private int value;
    private static final VarHandle VALUE_HANDLE;
    
    static {
        try {
            VALUE_HANDLE = MethodHandles.lookup()
                .findVarHandle(VarHandleExample.class, "value", int.class);
        } catch (Exception e) {
            throw new Error(e);
        }
    }
    
    public void atomicUpdate() {
        // 使用acquire-release语义
        VALUE_HANDLE.getAndAddAcquire(this, 1);
    }
}

六、性能对比示例

public class LockVsCASBenchmark {
    private final Object lock = new Object();
    private int lockCounter = 0;
    private AtomicInteger casCounter = new AtomicInteger(0);
    
    // 锁实现
    public void incrementWithLock() {
        synchronized (lock) {
            lockCounter++;
        }
    }
    
    // CAS实现
    public void incrementWithCAS() {
        casCounter.incrementAndGet();
    }
    
    // 测试结果通常：
    // 低竞争：锁性能更好（锁偏向优化）
    // 中等竞争：二者相当
    // 高竞争：CAS性能更好（避免上下文切换）
}

总结

volatile + CAS无锁编程模式的核心优势：

1. 高性能：避免线程阻塞和上下文切换
2. 可伸缩性：竞争不会导致性能急剧下降
3. 避免死锁：没有锁的获取顺序问题

使用建议：

• 简单操作用AtomicXxx类
• 复杂数据结构用AtomicReference + 循环CAS
• 高并发写场景考虑LongAdder、ConcurrentLinkedQueue等
• 始终监控CAS失败率，过高说明竞争激烈
• Java 9+优先使用VarHandle替代Unsafe

这种模式是现代高并发框架（如Disruptor、Netty、Akka）的基石，理解它对于编写高性能并发程序至关重要。