深入理解--CAS算法原理

悠悠 2022-12-10 14:42 132阅读 0赞

# 1、CAS介绍 #

CAS：Compare and Swap，即比较再交换,而。在java.util.atomic包下，找一个原子操作类AtomicInteger源码如下：

*  valueOffset (该变量在内存中的偏移地址)
 *  expect（预期值）
 *  update（新值）

/**
         * Atomically sets the value to the given updated value
         * if the current value {@code ==} the expected value.
         *
         * @param expect the expected value
         * @param update the new value
         * @return {@code true} if successful. False return indicates that
         * the actual value was not equal to the expected value.
         */
        public final boolean compareAndSet(int expect, int update) {
            return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
        }

根据源码可以得出：首先根据变量的偏移地址当且变量在内存中值，与预期值相等，则将变量在内存中的值改为新值。这个操作是原子的。

## 2、CAS原理 ##

关键点： Unsafe类+CAS自旋锁

（1）Unsafe类，源码如下：

// setup to use Unsafe.compareAndSwapInt for updates
        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;

1.1 Unsafe是CAS的核心类，由于java方法无法直接访问底层系统，需要通过本地(native)方法来访问，Unsafe相当于一个后门，基于该类可以直接操作特定内存的数据。

1.2 Unsafe类存在于`sun.misc`包中，其内部方法操作像C指针一样直接操作内存，因为CAS操作执行依赖于Unsafe类。

1.3 Unsafe类中的所有方法都是native修饰的，也就是说Unsafe类中的方法都直接调用操作系统底层资源执行相应任务。

1.4 变量value被volatile修饰，保证多个线程之间内存可见。

（2）变量valueOffset，表示该变量在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的。

//this:当前对象
    //valueOffset：内存偏移量
     public final int getAndIncrement() {
            return unsafe.getAndAddInt(this, valueOffset, 1);
     }
    //var1 AtomicInteger对象本身
    //var2 该对象值的引用地址
    //var4 需要变动的值
    //var5 用var1 var2找出主内存中真实的值
    //用该对象当前值与var5比较，如果相同，更新var5+var4返回true，如果不同，继续取值比较，直到更新完成
    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;
    }

getAndIncrement()底层调用unsafe类方法，传入三个参数，unsafe.getAndAddInt() 底层使用CAS思想，如果比较成功加1，如果比较失败重新获得，再比较一次，直至成功。

## 3、CAS缺点： ##

3.1 循环时间长开销大（由于是自旋锁，若CAS失败，则会一直尝试）

3.2 只能保证一个共享变量的原子操作。（对多个共享变量操作时，循环CAS无法保证操作的原子性，只能加锁来保证）

3.3 存在ABA问题

## 4、ABA问题解决方案 ##

由于CAS，需要在操作值的时候检查下值有没有发生变化，如果没有发生变化则更新，但是如果一个值原来是A，变成了B，又变成了A，那么使用CAS进行检查时会发现它的值没有发生变化，但是实际上却变化了。由于CAS类似于乐观锁，即每次去拿数据的时候都认为别人不会修改，所以不会上锁，这就是ABA问题。

**解决方案 ** ：在更新的时候会判断一下在此期间别人有没有去更新这个数据。因此解决方案也可以跟乐观锁一样

*  使用版本号机制，如手动增加版本号字段。具体如下：

在变量前面追加上版本号，每次变量更新的时候把版本号加一，那么A－B－A 就会变成1A-2B－3A

*  jdk1.5开始，Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。其中compareAndSet方法作用：

先检查当前引用是否等于预期引用，并且检查当前的标志是否等于预期标志，如果全部相等，则以原子方式将该应用和该标志的值设置为给定的更新值。源码如下：

/**
         * Atomically sets the value of both the reference and stamp
         * to the given update values if the
         * current reference is {@code ==} to the expected reference
         * and the current stamp is equal to the expected stamp.
         *
         * @param expectedReference the expected value of the reference
         * @param newReference the new value for the reference
         * @param expectedStamp the expected value of the stamp
         * @param newStamp the new value for the stamp
         * @return {@code true} if successful
         */
        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)));
        }

## 5、循环时间长开销大 ##

由于自旋CAS，如果长时间不成功，会给CPU带来非常大的执行开销。

**解决方案**

*  当循环次数超过一定时间或者一定次数时，return退出。JDK8新增的LongAddr,和ConcurrentHashMap类似的方法。当多个线程竞争时，将粒度变小，将一个变量拆分为多个变量，达到多个线程访问多个资源的效果，最后再调用sum把它合起来。