java中的CAS乐观锁

最近，总是听到同事在面试的时候问候选人java中的锁相关的知识，大部分同学在问到CAS的时候会有些一知半解；

1. 原子操作

说到原子操作，会想到数据库事务中的原子性，道理都差不多，指一行或多行代码要么都执行成功或失败。
比如：i++这行代码，在执行的过程中会分为三步去执行：

1.取出i的值；
2.将i的值+1;
3.将+1后的赋值给i;

在单线程的情况下，这种操作不会有问题，但是多线程的情况下呢：

出现了线程B的结果将线程A的结果覆盖的情况；那就可以说i++不是原子操作；

可以本地验证下是不是这样的：

private static int count = 0;
public static void add() {
    try {
        Thread.sleep(10);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    count++;
}
public static void main(String[] args) throws InterruptedException {
    CountDownLatch countDownLatch = new CountDownLatch(100);
    for(int i=0;i<100;i++){
        new Thread(() -> {
            add();
            countDownLatch.countDown();
        }).start();
    }
    countDownLatch.await();
    System.out.println("计算结果(Count)："+count);
}

我这里面运行的结果：计算结果(Count)：92

2.什么是CAS

Conmpare And Swap，比较和交换，实现多线程同步的原子指令。 它将内存位置的内容与给定值进行比较，只有在相同的情况下，将该内存位置的内容修改为新的给定值。 原子性保证新值基于最新信息计算; 如果该值在同一时间被另一个线程更新，则写入将失败。

上面这段话为官方解释用语，什么意思呢？
CAS操作包括三个操作数：

1. 内存位置 V
2. 预期原值 A
3. 新值 B

如果内存位置V与预期原值A相等，则认为没有被其它线程修改过，认为是安全的，那么处理器会自动将内存位置V的值更新为新值B；
如果内存位置V与预期原值A不相等，则处理器不做任何操作；

3.Java中的CAS实现

java中的CAS锁是通过Unsafe类实现，但是方法都是native；查看openJDK可以在里面找到Unsafe.cpp源码，最后调用的是：Atomic:comxchg()；

对于cmpxchg指令，程序会根据当前处理器的类型来决定是否为cmpxchg指令添加lock前缀。如果是多处理器，就为cmpxchg指令加上lock前缀（lock cmpxchg）。反之，就省略lock前缀；

关于lock前缀：
1.确保对内存的读-改-写操作原子执行。
2.禁止该指令与之前和之后的读和写指令重排序。
3.把写缓冲区中的所有数据刷新到内存中。

上面的示例代码通过CAS来实现：

private static AtomicInteger count = new AtomicInteger(0);

public static void add() {
    try {
        Thread.sleep(10);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    count.incrementAndGet();
}
public static void main(String[] args) throws InterruptedException {
    CountDownLatch countDownLatch = new CountDownLatch(100);
    for(int i=0;i<100;i++){
        new Thread(() -> {
            add();
            countDownLatch.countDown();
        }).start();
    }
    countDownLatch.await();
    System.out.println("计算结果(Count)："+count.get());
}

无论运行多少次，结果都是：100

4.CAS中的ABA问题

假如现有两个线程：线程1与线程2，count=1；
线程1：将count+1；
线程2：将count+1，count-1;

ABA问题，就是线程1与线程2在执行的过程中，线程2将值由之前的A改为了B又改为了A，但此时线程1以为A还是之前的值，没有其它线程改变过，则线程1也做更新；

ABA模拟代码：

private static AtomicInteger count = new AtomicInteger(0);
public static void main(String[] args) throws InterruptedException {
    Thread threadA = new Thread(() -> {
        try {
            Thread.sleep(2000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        // 让它加1
        int expectNum = count.get();
        int updateNum = expectNum + 1;

        boolean result = count.compareAndSet(expectNum, updateNum);
        System.out.println("操作成功/失败："+ result+";count="+count.get());
    });
    Thread threadB = new Thread(() -> {
        try {
            Thread.sleep(20);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        count.incrementAndGet(); // +1
        count.decrementAndGet(); // -1
    });

    threadA.start();
    threadB.start();
}

这里的输出结果：操作成功/失败：true;count=1

解决ABA问题：
产生这种问题的原因是A-B-A时，没有一个标识来标记第一个A和第三个A是不是同一个A，如果能够加个版本号A1-2B-3A，每次变量更新的时候把版本号加一，这样就可以解决这个问题；

Java里面提供了AtomicStampedReference来解决这个问题；

private static AtomicStampedReference<Integer> reference = new AtomicStampedReference(new Integer(0), 1);
public static void main(String[] args) {
    Thread threadA = new Thread(() -> {
        Integer expectedReference = reference.getReference();
        Integer updateReference = expectedReference + 1;
        Integer expectedStamp = reference.getStamp();
        Integer updateStamp = expectedStamp + 1;

        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        boolean result = reference.compareAndSet(expectedReference, updateReference, expectedStamp, updateStamp);
        System.out.println("操作成功/失败：" + result + ";count=" + reference.getReference());
    });
    Thread threadB = new Thread(() -> {
        try {
            Thread.sleep(20);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        // +1
        Integer expectedReference1 = reference.getReference();
        Integer expectedStamp1 = reference.getStamp();
        reference.compareAndSet(expectedReference1, expectedReference1 + 1, expectedStamp1, expectedStamp1 + 1);

        System.out.println("1:"+reference.getReference()+":"+reference.getStamp());

        // -1
        Integer expectedReference2 = reference.getReference();
        Integer expectedStamp2 = reference.getStamp();
        reference.compareAndSet(expectedReference2, expectedReference2 - 1, expectedStamp2, expectedStamp2 + 1);
        System.out.println("2:"+reference.getReference()+":"+reference.getStamp());

    });

    threadA.start();
    threadB.start();
}