线程协作工具类原理（1）：CAS原理

偏执的太偏执、 2023-07-02 05:27 99阅读 0赞

λ java -version
    java version "1.8.0_241"
    Java(TM) SE Runtime Environment (build 1.8.0_241-b07)
    Java HotSpot(TM) 64-Bit Server VM (build 25.241-b07, mixed mode)

# 1 什么是CAS #

**CompareAndSwap**

/**
     * java.util.concurrent.atomic.AtomicInteger#compareAndSet(int, int)
     *
     * @param expectedValue 期望值
     * @param newValue      更新值
     */
    public final boolean compareAndSet(int expectedValue, int newValue) {
    }

@Test
    public void test_atomic_integer() {
        AtomicInteger atomicInteger = new AtomicInteger(5);
        boolean r1 = atomicInteger.compareAndSet(5, 1024);
        System.out.println("r1 => " + r1);      // r1 => true
        System.out.println(atomicInteger);      // 1024
    
        boolean r2 = atomicInteger.compareAndSet(5, 2020);
        System.out.println("r2 => " + r2);      // r2 => false
        System.out.println(atomicInteger);      // 1024
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzk0OTcz_size_16_color_FFFFFF_t_70][]

>  *  并发（运用场合）
>  *  我认为V的值应该是A，如果是的话那我就把它改成B，如果不是A（说明被别人修改过了），那我就不修改了，避免多人同时修改导致出错
>  *  CAS有三个操作数：内存值V、预期值A、要修改的值B，当且仅当预期值A和内存值V相同时，才将内存值修改为B，否则什么都不做。最后返回现在的V值
>  *  CPU的特殊指令

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70][]

**CAS的等价代码（语义）**

/**
     * 模拟CAS操作，等价代码
     */
    public class SimulatedCAS {
        private volatile int value;
        /**
         * 比较并交互
         * @param expectedValue 期待的值
         * @param newValue 新的值
         * @return
         */
        public synchronized int compareAndSwap(int expectedValue, int newValue) {
            int oldValue = value;
            //在此期间没有其他人动过
            if (oldValue == expectedValue) {
                value = newValue;
            }
            return oldValue;
        }
    }

--------------------

# 2 案例演示 #

两个线程竞争，其中一个落败

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1][]

public class TwoThreadsCompetition implements Runnable {
        private volatile int value;
        public synchronized int compareAndSwap(int expectedValue, int newValue) {
            int oldValue = value;
            if (oldValue == expectedValue) {
                value = newValue;
            }
            return oldValue;
        }
        @Override
        public void run() {
            compareAndSwap(0, 1);
        }
        public static void main(String[] args) throws InterruptedException {
            TwoThreadsCompetition r = new TwoThreadsCompetition();
            r.value = 0;
            Thread t1 = new Thread(r,"Thread 1");
            Thread t2 = new Thread(r,"Thread 2");
            t1.start();
            t2.start();
            t1.join();
            t2.join();
            System.out.println(r.value);
        }
    }

--------------------

# 3 应用场景 #

>  *  乐观锁
>  *  并发容器
>  *  原子类

//java.util.concurrent.ConcurrentHashMap#putVal
    final V putVal(K key, V value, boolean onlyIfAbsent) {
            if (key == null || value == null) throw new NullPointerException();
            int hash = spread(key.hashCode());
            int binCount = 0;
            for (Node<K,V>[] tab = table;;) {
                Node<K,V> f; int n, i, fh;
                if (tab == null || (n = tab.length) == 0)
                    tab = initTable();
                else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
                    if (casTabAt(tab, i, null,
                                 new Node<K,V>(hash, key, value, null)))
                        break;                   // no lock when adding to empty bin
                }
    ...

--------------------

# 4 分析在Java中是如何利用CAS实现原子操作的？ #

> 以AtomicInteger为例

>  *  AtomicInteger载Unsafe工具，用来直接操作内存数据
>  *  用Unsafe来实现底层操作
>  *  用volatile修饰value字段，保证可见性

//java.util.concurrent.atomic.AtomicInteger
    static {
    	try {
    		valueOffset = unsafe.objectFieldOffset
    			(AtomicInteger.class.getDeclaredField("value"));
    	} catch (Exception ex) { throw new Error(ex); }
    }
    private volatile int value;

getAndAddInt方法分析

//java.util.concurrent.atomic.AtomicInteger#getAndIncrement
    public final int getAndIncrement() {
    	return unsafe.getAndAddInt(this, valueOffset, 1);
    }
    //sun.misc.Unsafe#getAndAddInt
    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;
    }
    //sun.misc.Unsafe#compareAndSwapInt
    public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

## 4.1 Unsafe类 ##

>  *  Unsafe是CAS的核心类。Java无法直接访问底层操作系统，而是通过本地（native）方法来访问。不过尽管如此，JVM还是开了一个后门，JDK中有一个类Unsafe，它提供了硬件级别的原子操作
>  *  valueOffset表示的是变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的原值的，这样我们就能通过unsafe来实现CAS了

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2][]

> Unsafe类中的compareAndSwapInt方法
> 
>  *  方法中先想办法拿到变量value在内存中的地址。
>  *  通过Atomic::cmpxchg实现**原子性的比较和替换**，其中参数x是即将更新的值，参数e是原内存的值。至此，最终完成了CAS的全过程。

## 4.2 源码分析过程  ##

让我们来看看AtomicInteger是如何通过CAS实现并发下的累加操作的，以AtomicInteger的getAndAdd方法为突破口。

### 4.2.1 getAndAdd方法 ###

public final int getAndAdd(int delta) {    
        return unsafe.getAndAddInt(this, valueOffset, delta);
    }

可以看出，这里使用了Unsafe这个类，这里需要简要介绍一下Unsafe类。Unsafe是CAS的核心类。Java无法直接访问底层操作系统，而是通过本地（native）方法来访问。不过尽管如此，JVM还是开了一个后门，JDK中有一个类Unsafe，它提供了硬件级别的原子操作。

### 4.2.2 Unsafe类 ###

### 4.2.3 AtomicInteger加载Unsafe工具，用来直接操作内存数据 ###

public class AtomicInteger extends Number implements java.io.Serializable {
        // 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;
        public final int get() {return value;}
    }

在AtomicInteger数据定义的部分，我们还获取了unsafe实例，并且定义了valueOffset。再看到static块，懂类加载过程的都知道，static块的加载发生于类加载的时候，是最先初始化的，这时候我们调用unsafe的objectFieldOffset从Atomic类文件中获取value的偏移量，那么valueOffset其实就是记录value的偏移量的。

valueOffset表示的是变量值在内存中的偏移地址，因为Unsafe就是根据内存偏移地址获取数据的原值的，这样我们就能通过unsafe来实现CAS了。value是用volatile修饰的，保证了多线程之间看到的value值是同一份。

### 4.2.4 接下来继续看Unsafe的getAndAddInt方法的实现 ###

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

我们看var5获取的是什么，通过调用unsafe的getIntVolatile(var1, var2)，这是个native方法，其实就是获取var1中，var2偏移量处的值。var1就是AtomicInteger，var2就是我们前面提到的valueOffset，这样我们就从内存里获取到现在valueOffset处的值了。

现在重点来了，compareAndSwapInt（var1, var2, var5, var5 + var4）其实换成compareAndSwapInt（obj, offset, expect, update）比较清楚，意思就是如果obj内的value和expect相等，就证明没有其他线程改变过这个变量，那么就更新它为update，如果这一步的CAS没有成功，那就采用自旋的方式继续进行CAS操作。

Unsafe的getAndAddInt方法分析：自旋 + CAS，在这个过程中，通过compareAndSwapInt比较并更新value值，如果更新失败，重新获取，然后再次更新，直到更新成功。

--------------------

# 5 缺点 #

> CAS也有不好的地方
> 
>  *  自旋时间过长
>  *  只能保证一个共享变量的原子操作
>  *  ABA问题

//AtomicStampedReference：解决CAS的ABA问题
    //java.util.concurrent.atomic.AtomicStampedReference#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)));
    }

/**
     * ABA问题演示
     */
    public class ABADemo {
        private static final AtomicReference<Integer> aba = new AtomicReference<>(100);
        public static void main(String[] args) {
            new Thread(() -> {
                // A -> B -> A
                aba.compareAndSet(100, 115);
                aba.compareAndSet(115, 100);
    
            }, "t1").start();
            new Thread(() -> {
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException ignored) {}
    
                boolean res = aba.compareAndSet(100, 1024);
                System.out.println(Thread.currentThread().getName() + " => res=" + res + ",aba=" + aba);
                // t2 => res=true,aba=1024
            }, "t2").start();
        }
    }

/**
     * ABA问题解决
     */
    public class ABADemo {
        private static final AtomicStampedReference<Integer> noAba = new AtomicStampedReference<>(100, 1);
        public static void main(String[] args) {
            //
            new Thread(() -> {
                // 拿到版本号
                int stamp = noAba.getStamp();
                System.out.println(Thread.currentThread().getName() + "第1次版本号: " + stamp);
                try {
                    TimeUnit.SECONDS.sleep(1);
                } catch (InterruptedException ignored) {}
                // A -> B -> A
                noAba.compareAndSet(100, 101, noAba.getStamp(), noAba.getStamp() + 1);
                System.out.println(Thread.currentThread().getName() + "第2次版本号: " + noAba.getStamp());
                noAba.compareAndSet(101, 100, noAba.getStamp(), noAba.getStamp() + 1);
                System.out.println(Thread.currentThread().getName() + "第3次版本号: " + noAba.getStamp());
                System.out.println(Thread.currentThread().getName() + " => stamp=" + noAba.getStamp() + ",noAba=" + noAba.getReference());
            }, "t3").start();
            //
            new Thread(() -> {
                // 拿到版本号
                int stamp = noAba.getStamp();
                System.out.println(Thread.currentThread().getName() + "第1次版本号: " + stamp);
                try {
                    TimeUnit.SECONDS.sleep(3);
                } catch (InterruptedException ignored) {}
                boolean res = noAba.compareAndSet(100, 1024, stamp, stamp + 1);
                System.out.println(Thread.currentThread().getName() + " => res=" + res + ",stamp=" + noAba.getStamp() + ",noAba=" + noAba.getReference());
    
            }, "t4").start();
        }
    }
    //t3第1次版本号: 1
    //t4第1次版本号: 1
    //t3第2次版本号: 2
    //t3第3次版本号: 3
    //t3 => stamp=3,noAba=100
    //t4 => res=false,stamp=3,noAba=100

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzk0OTcz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200929221241634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNzk0OTcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200127102209371.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200127103313602.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200127111019694.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly95dWFueXUuYmxvZy5jc2RuLm5ldA==,size_16,color_FFFFFF,t_70