03-14 CAS（一）

什么是CAS

CAS（CompareAndSwap，比较并交换），通常指的是这样一种原子操作：针对一个变量，首先比较它的内存值与期望值是否相同，如果相同，就给它赋一个新值。
CAS可以看做是乐观锁（对比数据库的悲观、乐观锁）的一种实现方式，Java原子类中的递增操作就通过CAS自旋实现的。
CAS是一种无锁算法，在不使用锁（没有线程被阻塞）的情况下实现多线程之间的变量同步

CAS应用

CAS 操作是由 Unsafe 类提供支持的，该类定义了三种针对不同类型变量的 CAS 操作

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);
public final native boolean compareAndSwapLong(Object var1, long var2, long var4, long var6);

例如compareAndSwapInt 方法接收 4 个参数，分别是：对象实例、内存偏移量、字段期望值、字段新值。该方法会针对指定对象实例中的相应偏移量的字段执行 CAS 操作。

public class CASTest {
    public static void main(String[] args) {
        Entity entity = new Entity();
        Unsafe unsafe = UnsafeFactory.getUnsafe();
        long fieldOffset = UnsafeFactory.getFieldOffset(unsafe, Entity.class, "x");
        System.out.println("fieldOffset:" + fieldOffset);
        boolean successful;
        // 4个参数分别是：对象实例、字段的内存偏移量、字段期望值、字段新值
        successful = unsafe.compareAndSwapInt(entity, fieldOffset, 0, 3);
        System.out.println(successful + "\t" + entity.x);
        successful = unsafe.compareAndSwapInt(entity, fieldOffset, 3, 5);
        System.out.println(successful + "\t" + entity.x);
        //这里不会成功，因为上面cas已经把x的值改为5了
        successful = unsafe.compareAndSwapInt(entity, fieldOffset, 3, 7);
        System.out.println(successful + "\t" + entity.x);
    }
}
class UnsafeFactory {
    public static Unsafe getUnsafe() {
        try {
            Field field = Unsafe.class.getDeclaredField("theUnsafe");
            field.setAccessible(true);
            return (Unsafe) field.get(null);
        } catch (Exception e) {
            e.printStackTrace();
        }
        return null;
    }
    public static long getFieldOffset(Unsafe unsafe, Class clazz, String fieldName) {
        try {
            return unsafe.objectFieldOffset(clazz.getDeclaredField(fieldName));
        } catch (Exception e) {
            throw new Error(e);
        }
    }
}
class Entity {
    public int x;
}

CAS缺陷

• 自旋 CAS 长时间地不成功，则会给 CPU 带来非常大的开销
• 只能保证一个共享变量原子操作
• ABA 问题

  cas的自旋是怎样实现的

  就是类似这样，用个do while或者for(;;)循环，用当前取到的值和内存中真实的值做比较，如果不一致，则把新的内存值赋值给var5，然后继续比较，直到能把新值写入成功为止。
  

ABA问题

什么是ABA问题

当有多个线程对一个原子类进行操作的时候，某个线程在短时间内将原子类的值A修改为B，又马上将其修改为A，此时其他线程不感知，还是会修改成功

public static void main(String[] args) {
        AtomicInteger atomicInteger = new AtomicInteger(1);
        new Thread(new Runnable() {
            @Override
            public void run() {
                int value = atomicInteger.get();
                //阻塞1s
                LockSupport.parkNanos(1000000000L);
                if (atomicInteger.compareAndSet(value, 3)) {
                    System.out.println("thread1 update from " + value + " to 3");
                } else {
                    System.out.println("thread1 update fail");
                }
            }
        }, "thread1").start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                int value = atomicInteger.get();
                //在这里先把value修改为2
                if (atomicInteger.compareAndSet(value, 2)) {
                    System.out.println("thread2 update from " + value + " to 2");
                    value = atomicInteger.get();
                    System.out.println("thread2 read value:" + value);
                    //在这里再把value修改为1
                    if (atomicInteger.compareAndSet(value, 1)) {
                        System.out.println("thread2 update from " + value + " to 1");
                    }
                }
            }
        }, "thread2").start();
    }

上面代码可以看出来，thread2已经对value修改过2次，但是thread1还是能修改成功，是因为cas只是判断你最终的值是否和我的预期值一致，一致就能修改，不管你过程有修改过多少次。

ABA问题的解决方案

数据库有个锁 称为乐观锁，是一种基于数据版本实现数据同步的机制，每次修改一次数据，版本就会进行累加。
同样，Java也提供了相应的原子引用类AtomicStampedReference

reference即我们实际存储的变量，stamp是版本，每次修改可以通过+1保证版本唯一性。这样就可以保证每次修改后的版本也会往上递增

public static void main(String[] args) {
        // Pair.reference(变量)值为1, Pair.stamp(版本)为1
        AtomicStampedReference atomicStampedReference = new AtomicStampedReference(1, 1);
        new Thread(new Runnable() {
            @Override
            public void run() {
                int[] stampHolder = new int[1];
                int value = (int) atomicStampedReference.get(stampHolder);
                int stamp = stampHolder[0];
                System.out.println("thread1 read value:" + value + ",stamp:" + stamp);
                // 阻塞1s
                LockSupport.parkNanos(1000000000L);
                if (atomicStampedReference.compareAndSet(value, 3, stamp, stamp + 1)) {
                    System.out.println("thread1 update " + value + " to 3");
                } else {
                    System.out.println("thread1 update fail");
                }
            }
        }, "thread1").start();
        new Thread(new Runnable() {
            @Override
            public void run() {
                int[] stampHolder = new int[1];
                int value = (int) atomicStampedReference.get(stampHolder);
                int stamp = stampHolder[0];
                System.out.println("thread2 read value:" + value + ",stamp:" + stamp);
                if (atomicStampedReference.compareAndSet(value, 2, stamp, stamp + 1)) {
                    System.out.println("thread2 update " + value + " to 2");
                    value = (int) atomicStampedReference.get(stampHolder);
                    stamp = stampHolder[0];
                    System.out.println("thread2 read value:" + value + ",stamp:" + stamp);
                    if (atomicStampedReference.compareAndSet(value, 1, stamp, stamp + 1)) {
                        System.out.println("thread2 update " + value + " to 1");
                    }
                }
            }
        }, "thread2").start();
    }

可以看到这时候的thread1修改不成功，就算这时候的期望值和内存值都一致。因为AtomicStampedReference有个版本stamp的概念，提供了类似乐观锁的功能，会去比较版本号。