CAS

首先，先说下悲观锁和乐观锁，悲观锁，每次操作都先上锁，比如独占锁synchronized就是一种悲观锁；乐观锁就是每次不加锁而是假设没有冲突而去完成某项操作，如果因为冲突失败就重试，直到成功为止。乐观锁所用到的机制就是CAS。

CAS：compare and swap

CAS包括三个值：内存地址、期待原值、新值。即当赋值的时候，首先compare，即对比目前的值和期待原值是否一样，如果一样，则更新原值，否则，不更新原值，重新获取。

看一个例子。

例子

public class Counter {
    private AtomicInteger mAtomicInteger = new AtomicInteger(0);
    private int i = 0;
    public static void main(String []args) {
        final Counter cas = new Counter();
        List<Thread> ts = new ArrayList<>(600);
    
        for(int j = 0; j < 100; j++) {
            Thread thread = new Thread(new Runnable() {
                public void run() {
                    for(int i = 0; i < 1000; i++) {
                        cas.count();
                        cas.safeCount();
                    }
                }
            });
            ts.add(thread);
        }
    
        for(Thread thread : ts) {
            thread.start();
        }
    
        //等待子线程都执行完了之后再打印结果
        for(Thread thread : ts) {
            try {
                thread.join();
            } catch(InterruptedException e) {
                e.printStackTrace();
            }
        }
    
        System.out.println(cas.i);
        System.out.println(cas.mAtomicInteger.get());
    }

    private void safeCount() {
        for(;;) {
            int i = mAtomicInteger.get();
            boolean suc = mAtomicInteger.compareAndSet(i, ++i);
            if (suc) {
                break;
            }
        }
    }

    private void count() {
        i++;
    }
}

这个是一个计数器，期待结果是100000，但是，如果直接i++会发现，结果不是100000，原因比较好理解，修改值的时候包括三步：
1、读取i
2、i = i + 1
3、把计算得到的i写入
这个过程明显不是原子操作的，所以导致值不对。
再看使用CAS方式来实现的，即：

for(;;) {
    int i = mAtomicInteger.get();
    boolean suc = mAtomicInteger.compareAndSet(i, ++i);
    if (suc) {
        break;
    }
}

这个非常有意思，compareAndSet传入的一个期待原值一个新值，如果原值和期待原值不一致，就返回false，如果一致，就修改并返回true。如果一致不成功就不断重试，直到成功。

所以其实这里是通过循环CAS来实现的不加锁的原子操作。

ABA问题

CAS操作的是存在着一个经典的ABA问题，这个问题可以从下面的例子引入。

public class ABA {
    private static AtomicInteger atomicInt = new AtomicInteger(100);

    public static void main(String[] args) throws InterruptedException {
        Thread intT1 = new Thread(new Runnable() {
            @Override
            public void run() {
                atomicInt.compareAndSet(100, 101);
                atomicInt.compareAndSet(101, 100);
            }
        });

        Thread intT2 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                boolean c3 = atomicInt.compareAndSet(100, 101);
                System.out.println(c3); //true
            }
        });

        intT1.start();
        intT2.start();
        intT1.join();
        intT2.join();
    }
}

打印结果是true。

这里初始值是100，线程1把100改成101再改成100，线程2认为100就是期待原值，所以线程2在执行的时候，不知道1已经执行了。所以返回了true。但是实际上2的期待原值100已经不是现在的100了。

ABA问题的解决思路就是加上版本号，即从A->B->A变成1A->2B->3A，这样一来只有版本号和值相等，才认为相等。

从Java1.5开始，java.util.concurrent.atomic包里面引入了带标记的AtomicStampedReference类解决了这个问题。

还是先看这个例子的更新版。

public class ABA {
    private static AtomicStampedReference<Integer> atomicStampedRef = new AtomicStampedReference<Integer>(100, 0);

    public static void main(String[] args) throws InterruptedException {
        Thread refT1 = new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
            }
        });

        Thread refT2 = new Thread(new Runnable() {
            @Override
            public void run() {
                int stamp = atomicStampedRef.getStamp();
                try {
                    TimeUnit.SECONDS.sleep(2);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);
                System.out.println(c3); //false
            }
        });

        refT1.start();
        refT2.start();
    }
}

打印结果是false。
这里compareAndSet方法做了两件事，一个是先检查当前引用是否等于预期引用，并且检查当前版本号是否等于预期版本号，如果相等则进行更新。