什么是CAS(Compare And Swap)算法？

CAS的全称是： Compare And Swap(比较并交换)，CAS是实现并发算法时常用到的技术，Java并发包中的很多类都使用了CAS技术，如ConcurrentHashMap, Atomicinteger原子操作类等等。

CAS操作涉及到3个操作值：当前内存中的值，预估值，即将修改的新值，当且仅当预估值等于内存中的值的时候，才将新的值保存到内存中，否则什么都不做。

CAS(Compare And Swap)技术的作用:

CAS可以将比较和交换转换为原子操作，这个原子操作直接由CPU保证，CAS可以保证共享变量赋值时的原子操作

CAS(Compare And Swap)技术的特点：

CAS是一种非阻塞算法的实现，它能在不使用锁的情况下实现多线程安全，所以CAS也是一种无锁算法。

非阻塞: 一个线程失败或者挂起并不会导致其他线程也失败或者挂起。

讨论i++问题

/**
 * 

# 原子性演示: 讨论i++问题

 * int i = 10
 * i = i++;
 *
 * 其实就是分为三个步骤：读、该、写
 * int temp = i;
 * i = i + 1;
 * i = temp;
 *
 */
public class TestAtomicDemo {
    public static void main(String[] args) {
        AtomicDemo atomicDemo = new AtomicDemo();
        for (int i = 0; i < 20; i++) {
            new Thread(atomicDemo, "线程"+i).start();
        }
    }
}

class AtomicDemo implements Runnable{

//    private int serialNumber = 0;
    /**
     * 在使用volatile关键字，虽然内存可见，但是无法保证原子性
     *
     * 【如何保证其原子性？？】
     * 使用原子变量：在jdk1.5后java.util.concurrent.atomic 包下提供了常用的原子变量
     *
     * 使用原子变量的好处都有啥？
     * 1、原子变量内默认使用volatile修饰变量，保证了内存可见性
     * 2、封装了CAS(Compare-And-Swap)算法保证了数据的原子性
     *
     * CAS(Compare-And-Swap)比较和替换：是操作系统对于并发操作共享数据的一个支持，大致算法思路如下：
     *  CAS算法中使用了三个操作数，分别是[内存值 V]、[预估值 A]、[更新值 B]
     *  当且仅当V==A 时，V==B,否则，将不做任何操作。
     *  CAS算法比Sync同步锁效率高，能进行快速失败
     */
    private  AtomicInteger serialNumber = new AtomicInteger(0);

    @Override
    public void run() {
        try {
            TimeUnit.MICROSECONDS.sleep(200);
            System.out.println(Thread.currentThread().getName() + ":" + getSerialNumber());
        } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
    }

    public int getSerialNumber() {
        //return serialNumber++;
        return serialNumber.getAndIncrement();
    }
}

代码中，使用了AtomicInteger保证多线程自增时的原子性，我们从 serialNumber.getAndIncrement()点进去，阅读源码：

    public final int getAndIncrement() {
        return unsafe.getAndAddInt(this, valueOffset, 1);
    }

从上面代码我们可以的知，getAndIncrement()是通过unsafe类来实现的，那么Unsafe何许人也？

    private static final Unsafe unsafe = Unsafe.getUnsafe();
    private static final long valueOffset;

    static {
        try {
            valueOffset = unsafe.objectFieldOffset
                (AtomicInteger.class.getDeclaredField("value"));
        } catch (Exception ex) { throw new Error(ex); }
    }

    private volatile int value;

Unsafe是可以直接操作内存中的值，而valueOffset实际上通过value得到，values是通过volatile关键字修饰（volatile可以实现内存可见性和禁止指令重排）。

模拟CAS(Compare And Swap)算法

public class TestCompareAndSwap {
    public static void main(String[] args) {
        CompareAndSwap compareAndSwap = new CompareAndSwap();
        for (int i = 0; i < 10; i++) {
            new Thread(() -> {
                int expectedValue = compareAndSwap.get();
                boolean b = compareAndSwap.compareAndSet(expectedValue, (int) Math.random() * 101);
                System.out.println("是否成功:" + b);
            }).start();
        }
    }
}

class CompareAndSwap {
    private int value;

    //  获取内存值
    public synchronized int get(){
        return value;
    }

    /**
     * 

## 比较并交换

     * @param expectedValue 预估值
     * @param newValue 新值
     * @return
     */
    public synchronized int compareAndSwap(int  expectedValue, int newValue){
        int oldValue = value;

        if (oldValue == expectedValue){
            this.value = newValue;
        }

        return oldValue;
    }

    /**
     * 

## 设置值

     * @param expectedValue 预估值
     * @param newValue 新值
     * @return
     */
    public synchronized boolean compareAndSet(int  expectedValue, int newValue){
        return expectedValue == compareAndSwap(expectedValue, newValue);
    }
}

CAS的3个显著缺点:

• 循环时间长时，会导致CPU开销大
• 只能保证一个共享变量的原子操作
• 引出来ABA问题(什么是ABA问题?)

缺点1：循环时间长时，会导致CPU开销大

我们查看sun.misc.Unsafe类源码，发现getAndAddInt使用的是do-while循环！：

    public final int getAndAddInt(Object var1, long var2, int var4) {
        int var5;
        do {
            var5 = this.getIntVolatile(var1, var2);
        } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));

        return var5;
    }

正是因为do-while循环，如果CAS失败！就会异常进行尝试。如果CAS长时间一直不成功，可能会给CPU带来很大的开销！！！

什么是ABA问题?