CAS算法

原创文章，转载请注明原文章地址，谢谢！

CAS（Compare And Swap）

• CAS是一条CPU并发原语，其功能是判断内存中某个位置的值是否为预期值，如果是则更改为新的值，这个过程是原子性的。
• CAS并发原语体现在Java中sun.misc.Unsafe类中的方法。调用Unsafe类中的CAS方法，JVM会实现出CAS汇编指令，依赖于硬件，实现原子操作。
• 原语属于操作系统用语范畴，是由若干条指令组成的，用于完成某个功能的一个过程，并且原语的执行必须是连续的，在执行的过程中不允许被中断。即CAS是一条CPU的原子指令，不会造成所谓的数据不一致问题。

Unsafe

• CAS的核心类，由于Java方法无法直接访问底层系统，需要通过本地native方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。
• Unsafe类存在于sun.misc包中，其内部方法操作可以像C的指针一样直接操作内存，因为Java中CAS操作的执行依赖于Unsafe类的方法。
• Unsafe类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务。

AtomicInteger.getAndAddInt()源码

• 变量valueOffset，表示该变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的。
• 变量value用volatile修饰，保证了多线程之间的内存可见性。

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

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;
}

Unsafe类中的compareAndSwapInt，是一个本地方法，该方法的实现位于unsafe.cpp中。

CAS的缺点

• 循环时间长开销大。如果CAS失败，会一直进行尝试，如果CAS长时间一直不成功，可能会给CPU带来大的开销。
• 只能保证一个共享变量的原子操作。
• ABA问题。CAS算法实现的前提需要取出内存中某个时刻的数据并在当下时刻比较并替换，那么在这个时间差内会导致数据的变化。

解决ABA问题

• AtomicStampedReference，每次修改都会让stamp值加1，类似于版本控制号。
• AtomicMarkableReference，如果不关心引用变量中途被修改了多少次，而只关心是否被修改过。

ABA问题演示

public class Test {
    private static AtomicInteger index = new AtomicInteger(10);
    public static void main(String[] args) {
        new Thread(() -> {
            index.compareAndSet(10, 11);
            index.compareAndSet(11, 10);
            System.out.println(Thread.currentThread().getName() + " 10->11->10");
        }, "张三").start();

        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(2);
                boolean result = index.compareAndSet(10, 12);
                System.out.println(Thread.currentThread().getName() + " 执行结果：" + result + " 修改后的值是：" + index.get());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }, "李四").start();
    }
}

执行结果是

张三 10->11->10
李四 执行结果：true 修改后的值是：12

使用AtomicStampedReference解决ABA问题

public class Test {
    private static AtomicInteger index = new AtomicInteger(10);
    private static AtomicStampedReference<Integer> stampedReference = new AtomicStampedReference<>(10, 1);
    public static void main(String[] args) {
        new Thread(() -> {
            System.out.println(Thread.currentThread().getName() + " 第1次版本号：" + stampedReference.getStamp());
            stampedReference.compareAndSet(10, 11, stampedReference.getStamp(), stampedReference.getStamp() + 1);
            System.out.println(Thread.currentThread().getName() + " 第2次版本号：" + stampedReference.getStamp());
            stampedReference.compareAndSet(11, 10, stampedReference.getStamp(), stampedReference.getStamp() + 1);
            System.out.println(Thread.currentThread().getName() + " 第3次版本号：" + stampedReference.getStamp());
        }, "张三").start();

        new Thread(() -> {
            try {
                TimeUnit.SECONDS.sleep(2);
                System.out.println(Thread.currentThread().getName() + " 第1次版本号：" + stampedReference.getStamp());
                boolean result = stampedReference.compareAndSet(10, 12, stampedReference.getStamp(), stampedReference.getStamp() + 1);
                System.out.println(Thread.currentThread().getName() + " 修改是否成功：" + result + " 当前版本号是：" + stampedReference.getStamp());
                System.out.println(Thread.currentThread().getName() +  " 当前实际值是：" + stampedReference.getReference());
            } catch (Exception e) {
                e.printStackTrace();
            }
        }, "李四").start();
    }
}

执行结果是

张三 第1次版本号：1
张三 第2次版本号：2
张三 第3次版本号：3
李四 第1次版本号：3
李四 修改是否成功：true 当前版本号是：4
李四 当前实际值是：12

compareAndSet方法

public boolean compareAndSet(V   expectedReference,
                             V   newReference,
                             int expectedStamp,
                             int newStamp) {
    Pair<V> current = pair;
    return
            expectedReference == current.reference &&
                    expectedStamp == current.stamp &&
                    ((newReference == current.reference &&
                            newStamp == current.stamp) ||
                            casPair(current, Pair.of(newReference, newStamp)));
}

• expectedReference：表示预期值。
• newReference：表示要更新的值。
• expectedStamp：表示预期的时间戳。
• newStamp：表示要更新的时间戳。

博客内容仅供自已学习以及学习过程的记录，如有侵权，请联系我删除，谢谢！