【并发编程】CAS 和 ABA

古城微笑少年丶 2022-03-19 14:00 240阅读 0赞

# 前言 #

Github：[https://github.com/yihonglei/jdk-source-code-reading][https_github.com_yihonglei_jdk-source-code-reading]（java-concurrent）

# 一 CAS #

在 Java 中可以通过锁和 CAS 的方式来实现原子操作。

JVM 中的 CAS 操作利用处理器提供的 CMPXCHG 来实现。自旋 CAS 实现的基本思路就是循环进行 CAS 操作直到成功为止。

![20190217153140905.jpg][]

CAS 有3个操作数，内存值 V，旧的预期值 A，要修改的新值 B。当且仅当预期值 A 和内存值 V 相同时，将内存值 V 修改为 B，

否则什么都不做。

以下通过CAS实现线程安全计数器。

package com.jpeony.concurrent.casaba;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.atomic.AtomicInteger;
    
    /**
     * CAS实现原子操作
     *
     * @author yihonglei
     */
    public class Counter {
        private AtomicInteger atomicI = new AtomicInteger(0);
        private int i = 0;
    
        public static void main(String[] args) {
            final Counter cas = new Counter();
            List<Thread> ts = new ArrayList<>();
            long start = System.currentTimeMillis();
            for (int j = 0; j < 100; j++) {
                Thread t = new Thread(() -> {
                    for (int i = 0; i < 10000; i++) {
                        cas.count();
                        cas.safeCount();
                    }
                });
                ts.add(t);
            }
    
            for (Thread t : ts) {
                t.start();
            }
    
            // 等待所有线程执行完成
            for (Thread t : ts) {
                try {
                    t.join();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                System.out.println(cas.i);
                System.out.println(cas.atomicI.get());
                System.out.println(System.currentTimeMillis() - start);
            }
        }
    
        /**
         * 使用CAS实现线程安全计数器
         */
        private void safeCount() {
            for (; ; ) {
                int i = atomicI.get();
                boolean suc = atomicI.compareAndSet(i, ++i);
                if (suc) {
                    break;
                }
            }
        }
    
        /**
         * 非线程安全计数器
         */
        private void count() {
            i++;
        }
    }

# 二 ABA 问题 #

什么是ABA问题？先看个图。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70][]

1）A 线程要将18 改为 38；

2）B 线程要将 38 改为 18；

3）C 线程读取 18，误以为该值没有发生过改变；

18-->38-->18，这个就是 ABA 问题。

C 线程想将 A 线程的18 改为 99，但是这里其实是 B 线程的 18，理论上不应该修改成功，但是 C 线程分不清是谁的 18，

所以 C 修改成功，其实是不对的。比如，C 就是喜欢 18 岁的，但是岁月不饶人，A 这把时间线程把 18 的小花变成了 38 的少妇，

但是科技发达啊，B 这个神奇的医院又把这个 38 的少妇整容成了 18 的小花，C 不知道啊，以为是个 18 的小花，

两个人天长地久的在一起，但是事实上 C 想要的是真正 18 的小花，为了让 C 知道 18 是不是真的 18，可以通过标记的方式处理。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1][]

C 线程拿到的 18，发现不是 A 线程的 18，更改不成功，达到预期目标。就是对正常和整容做个标记区分，

C 就能分清是青春的 18 还是整容的 18 了。

从 JDK1.5 开始，Atomic 原子包提供了 AtomicStampedReference 来解决 ABA 问题。

这个类的 compareAndSet 方法首先检查当前引用是否等于预期引用，并且检查当前标志是否等于预期标志，

如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

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

private boolean casPair(Pair<V> cmp, Pair<V> val) {
        return UNSAFE.compareAndSwapObject(this, pairOffset, cmp, val);
    }

public final native boolean compareAndSwapObject(Object var1, long var2, Object var4, Object var5);

**AtomicIntegerABA（ABA 问题实例演示）**

package com.jpeony.concurrent.casaba;
    
    import org.slf4j.Logger;
    import org.slf4j.LoggerFactory;
    
    import java.util.concurrent.atomic.AtomicInteger;
    
    /**
     * ABA 问题演示
     *
     * @author yihonglei
     */
    public class AtomicIntegerABA {
        private final static Logger logger = LoggerFactory.getLogger(AtomicIntegerABA.class);
        private static AtomicInteger atomicInt = new AtomicInteger(18);
    
        public static void main(String[] args) throws InterruptedException {
            // 线程A 18-->38
            Thread threadA = new Thread(new Runnable() {
                @Override
                public void run() {
                    logger.info("===ThreadA begin===");
                    atomicInt.compareAndSet(18, 38);
                    logger.info("===ThreadA end===");
                }
            });
    
            // 线程B 38-->18
            Thread threadB = new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        threadA.join();
                        logger.info("===ThreadB begin===");
                        atomicInt.compareAndSet(38, 18);
                        logger.info("===ThreadB end===");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
    
            // 线程C 18-->99
            Thread threadC = new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        threadB.join();
                        logger.info("===ThreadC begin===");
                        boolean c = atomicInt.compareAndSet(18, 99);
                        logger.info("c={}", c);
                        logger.info("atomicInt.get()={}", atomicInt.get());
                        logger.info("===ThreadC end===");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
    
            threadA.start();
            threadB.start();
            threadC.start();
    
            threadC.join();
        }
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2][]

从运行结果可以看到，线程 C 将分不清 18 是不是线程 A 的 18，根据 CAS 算法，将 18 更新为 99 了，

而我们的本意是只有 18 是 A 的 18 时，C 线程才进行更新，否则不处理。

**AtomicStampedABA（通过打标记解决ABA问题）**

package com.jpeony.concurrent.casaba;
    
    import java.util.concurrent.atomic.AtomicStampedReference;
    
    /**
     * 增加标记，解决ABA问题
     *
     * @author yihonglei
     */
    public class AtomicStampedABA {
        private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference(18, 0);
    
        public static void main(String[] args) throws InterruptedException {
            // 线程A 18-->38(18-0 --> 38-1)
            Thread threadA = new Thread(new Runnable() {
                @Override
                public void run() {
                    System.out.println("===ThreadA begin===");
                    atomicStampedRef.compareAndSet(18, 38, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                    System.out.println("===ThreadA end===");
                }
            });
    
            // 线程B 38-->18(38-1 --> 18-2)
            Thread threadB = new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        threadA.join();
                        System.out.println("===ThreadB begin===");
                        atomicStampedRef.compareAndSet(38, 18, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                        System.out.println("===ThreadB end===");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
    
            // 线程C 18-->99(18-0 --> 99-1，但是atomicStampedRef里面现在的18是18-2，多以更新失败，18已经不是初始化时的18了)
            Thread threadC = new Thread(new Runnable() {
                @Override
                public void run() {
                    try {
                        threadB.join();
                        System.out.println("===ThreadC begin===");
                        boolean c = atomicStampedRef.compareAndSet(18, 99, 0, 1);
                        System.out.println(c);
                        System.out.println("===ThreadC end===");
                    } catch (InterruptedException e) {
                        e.printStackTrace();
                    }
                }
            });
    
            threadA.start();
            threadB.start();
            threadC.start();
    
            threadC.join();
        }
    }

运行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 3][]

从运行结果可以知道，通过标记，C 线程从内存里面拿到的不是A线程的 18，所以更新失败。

# 三 CAS 缺陷 #

## 1、ABA 问题 ##

ABA 问题使用版本号解决。

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

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

## 3、只能保证一个共享变量的原子操作 ##

当对一个共享变量执行操作时，我们可以使用循环 CAS 的方式来保证原子操作，但是对多个共享变量操作时，

循环 CAS 就无法保证操作的原子性，这个时候就可以用锁。

# 四 使用锁机制实现原子操作 #

锁机制保证了只有获得锁的线程才能够操作锁定的内存区域。JVM 内部实现了很多锁机制，有偏向锁、

轻量级锁和互斥锁（重量级锁）。在 JVM 内部锁实现方式除了偏向锁，其余均使用了循环 CAS，即当一个线程想进入

同步快的时候使用循环 CAS 的方式来获取锁，当它退出同步块的时候使用了循环 CAS 释放锁。

[https_github.com_yihonglei_jdk-source-code-reading]: https://github.com/yihonglei/jdk-source-code-reading
[20190217153140905.jpg]: /images/20220319/0bdca3fe54154e599b62b6a285393c61.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70]: /images/20220319/a37cc2d106ab4146b8bf0341e5823cd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 1]: /images/20220319/3b4faa06ce454381a77453b07a9fb796.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 2]: /images/20220319/3b48f225349a4edd9c3da1d10cad6ae5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lobF9qeHk_size_16_color_FFFFFF_t_70 3]: /images/20220319/f63abb608eb846d48b38551a415c9ad0.png