CAS与ABA

发表于 | 分类于

CAS算法与ABA问题

在学习多线程，总是绕不开CAS的，可以说整个JUC的基础之一就是CAS算法，但是CAS里有个ABA问题，这个关注一下。

CAS算法

CAS(Compare And Swap)，比较并且交换。

在了解CAS之前，先来了解一下乐观锁，悲观锁，这里讲个大概:

  • 乐观锁：乐观地认为每次执行都是成功的，如果失败了，那就重试吧
  • 悲观锁：悲观地认为每次执行都会有问题，因此在每次执行时都会使用锁去让线程进行等待，尽管这会降低性能

而乐观锁就是用到了CAS机制。

CAS算法：

  • 有三个参数，V, E, N。

    V(value)表示内存值

    E(expect)表示期望值

    N(new)表示要更新的值

    具体示例可以看AtomicInteger：

    AtomicInteger的value

    这是AtomicInteger上的value变量，可以看到其上使用volatile去保证内存可见性。而此value就是CAS中的V。

    再看看compareAndSet(int expect, int update)

    AtomicInteger的compareAndSet

    从上图中可以看到里面有几个参数int expect, int update。其中expect就是E，update就是N。从上面文档可以看到，如果expect等于value，那么就把value设置成update的值，否则什么也不做。这里的意思比较微妙，在单线程的条件下，这样比较丝毫没有意义，什么有点多余。但是在多线程的条件下，就不一样了。多线程调度下，CAS算法需要额外给出个期望值，也就是说你期望现在(指的是还没有更改前)在内存里这个value值是什么样的，在CAS算法里将你期望值与实际的内存值进行比较，如果比较结果不一样，那说明你现在的值被别人修改了。你就得重新读取，再次尝试修改。

    1
    2
    3
    4
    5
    6
    if (value == expect) {
        value = update;
        return true;
    } else {
        return false;
    }

    整个过程就类似上面那样。

  • Java具体不实现CAS，而是交由CPU去运行。

    可以看到上面那个图使用的Unsafe类，Unsafe类里面封装的都是native接口，交由其他语言或者别的来实现。

虽然CAS算法很高效，毕竟作为了JUC的基础算法，但是其存在一个很大的弊端，很容易引起ABA问题

ABA问题

关于ABA问题的理解，可以先从下面代码去理解，下面代码中，是用CountDownLatch和volatile去模拟实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.concurrent.CountDownLatch;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicInteger;

public class SimpleTestCAS {

    private static volatile String data = "A";



    private static class UpdateThread_B implements Runnable {

        private final CountDownLatch countDownLatch;

        public UpdateThread_B(CountDownLatch countDownLatch) {
            this.countDownLatch = countDownLatch;
        }

        @Override
        public void run() {

                System.out.println("update_B: 现在我要修改data值");
                data = "B";
                System.out.println("update_B: data值: " + data);
                System.out.println("update_B: 但是我A又反悔了，现在修改回来");
                data = "A";
                System.out.println("update_B: data值: " + data);
                countDownLatch.countDown();

        }
    }

    private static class UpdateThread_A implements Runnable {

        private final CountDownLatch countDownLatch;

        public UpdateThread_A(CountDownLatch countDownLatch) {
            this.countDownLatch = countDownLatch;
        }

        @Override
        public void run() {

            try {
                System.out.println("update_A: 现在data是：" + data);
                System.out.println("update_A: 诶不好，要修改的时候，这时切换了线程，aaaaaaaaaa");
                countDownLatch.await();
                if ("A".equals(data)) {
                    System.out.println("update_A: 现在是data是" + data + "，诶，看来另一个线程没有对他进行修改嘛，那我修改");
                    data = "B";
                } else {
                    System.out.println("update_A: CAS算法过程演示失败");
                }
                System.out.println("update_A: 现在data是："+data);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }

        }
    }

    public static void main(String[] args) {
        CountDownLatch countDownLatch = new CountDownLatch(1);
        ExecutorService executorService = Executors.newCachedThreadPool();
        executorService.execute(new UpdateThread_A(countDownLatch));
        executorService.execute(new UpdateThread_B(countDownLatch));
        executorService.shutdown();
        AtomicInteger atomicInteger;
    }
}

运行结果：

TestCAS的结果

ABA问题可以简述如下：

CAS算法在整个过程中，存在两个时刻，一个是取出内存值时刻，一个是比较然后修改。前者与后者之间的时间差会导致ABA问题的出现。即在CAS取出内存值A的时候，由于线程调度，别的线程也取出了A，但是别的线程将其修改为B之后，又将其修改回A。这时回到CAS算法线程，此时CAS算法比较，发现内存值与期望值一样，于是将其修改。但是实际上内存值已经发生了变化，只是变化的结果还是回到原来的数值。

具体例子，可以参考这个博文，里面对ABA问题有生动形象的例子：https://www.cnblogs.com/549294286/p/3766717.html

那怎样才能避免ABA问题呢？总不能放着不管吧。

答案就是使用版本号！！！！！！！！！！！！！

在变量前追加版本号，每次变量更新时把版本号加1，那么A-B-A就变成了1A-2B-3A。而实际上Java里面也是使用了版本戳stamp。

JDK从1.5开始就使用了AtomicStampedReference来解决ABA问题

AtomicStampedReffence-API

上面文档说到，AtomicStampedReference内部维护了一个对象引用以及一个整型版本戳(实际上叫什么我不是很清楚，但基本一个意思，就是用一个可以标记其变化的数)，使得其可以以原子形式更新。内部通过创建一个内部对象表示被装箱的pairs

这里指的internal objects就是指一个内部类Pair，里面boxed 的pairs就是[reference，integer]。reference指的就是对象引用(下面的V，基本类型会装箱成包装类型)，而integer指的就是版本戳stamp。

AtomicStampedReference的pair

上面的T跟V是同一个类型。

Ok，关于AtomicStampedReference的内容就说这么多，具体内部实现看下Java里面的代码。知道AtomicStampedReference可以解决ABA问题，但是怎么解决？Talk is cheap，show your code。

通过对上面那个博客的一番研读之后，发现其测试代码设计的不是特别严谨。

以下是笔者代码，使用控制变量法23333333333(虽然严格来说不是)。就尽量控制AtomicInteger测试与AtomicStampedReference测试的代码尽量保持一样而已。

AtomicInteger测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
// AtomicInteger测试线程B
class TestAtomicIntegerThread_１ implements Runnable {

    private CountDownLatch countDownLatch;

    private AtomicInteger atomicInteger;

    public TestAtomicIntegerThread_１(CountDownLatch countDownLatch, AtomicInteger 	atomicInteger) {
        this.countDownLatch = countDownLatch;
        this.atomicInteger = atomicInteger;
    }

    @Override
    public void run() {
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("切换到B线程，B线程CAS两次");
        atomicInteger.compareAndSet(1, 0);
        System.out.println("B线程第一次CAS："+atomicInteger.get());
        atomicInteger.compareAndSet(0, 1);
        System.out.println("B线程第二次CAS："+atomicInteger.get());
    }
}

// AtomicInteger测试线程A
class TestAtomicIntegerThread_２ implements Runnable {

    private CountDownLatch countDownLatch;

    private AtomicInteger atomicInteger;

    public TestAtomicIntegerThread_２(CountDownLatch countDownLatch, AtomicInteger atomicInteger) {
        this.countDownLatch = countDownLatch;
        this.atomicInteger = atomicInteger;
    }
    @Override
    public void run() {
        System.out.println("模仿一下CAS从内存取值");
        System.out.println("A线程刚从内存取出值，此时发生了线程切换");
        try {
            countDownLatch.countDown();
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("别的线程执行完毕，切换回来后，A线程继续刚刚没有完成的任务");
        boolean result = atomicInteger.compareAndSet(1, 0);
        System.out.println("A线程CAS: " + atomicInteger.get());
        System.out.println("A线程结果: " + result);
    }
}

public class TestABA {
    public static void main(String[] args) {
        CountDownLatch countDownLatch = new CountDownLatch(1);
        AtomicInteger atomicInteger = new AtomicInteger(1);
        ExecutorService executorService = Executors.newCachedThreadPool();
        executorService.execute(new TestAtomicIntegerThread_２(countDownLatch, atomicInteger));
        executorService.execute(new TestAtomicIntegerThread_１(countDownLatch, atomicInteger));
        executorService.shutdown();
    }
}

测试结果

AtomicInteger测试结果

测试分析

代码中模拟了一种情景。就是在A线程取内存值时，发生了线程切换，此时B线程也取值，并CAS了两次。最后切换回A线程。此时A线程CAS成功。

AtomicStampedReference测试用例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// AtomicStampedReference_1的模拟B线程
class TestAtomicStampedReference_1 implements Runnable {

    private CountDownLatch countDownLatch;

    private AtomicStampedReference<Integer> atomicStampedReference;

    public TestAtomicStampedReference_1(CountDownLatch countDownLatch, AtomicStampedReference<Integer> atomicStampedReference) {
        this.countDownLatch = countDownLatch;
        this.atomicStampedReference = atomicStampedReference;
    }

    @Override
    public void run() {
        try {
            countDownLatch.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("切换到B线程，B线程CAS两次");
        atomicStampedReference.compareAndSet(1, 0, atomicStampedReference.getStamp(), atomicStampedReference.getStamp()+1);
        System.out.println("B线程第一次CAS："+atomicStampedReference.getReference() + "　Stamp: " + atomicStampedReference.getStamp());
        atomicStampedReference.compareAndSet(0, 1, atomicStampedReference.getStamp(), atomicStampedReference.getStamp()+1);
        System.out.println("B线程第二次CAS："+atomicStampedReference.getReference() + " Stamp: " + atomicStampedReference.getStamp());
    }
}

// AtomicStampedReference_2的模拟A线程
class TestAtomicStampedReference_2 implements Runnable {

    private CountDownLatch countDownLatch;

    private AtomicStampedReference<Integer> atomicStampedReference;

    public TestAtomicStampedReference_2(CountDownLatch countDownLatch, AtomicStampedReference<Integer> atomicStampedReference) {
        this.countDownLatch = countDownLatch;
        this.atomicStampedReference = atomicStampedReference;
    }

    @Override
    public void run() {
        System.out.println("模拟一下CAS内存取值");
        int stamp = atomicStampedReference.getStamp();
        System.out.println("A线程刚从内存取出值，此时发生了线程切换");
        try {
            countDownLatch.countDown();
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("别的线程执行完毕，切换回来后，A线程继续刚刚没有完成的任务");
        boolean result = atomicStampedReference.compareAndSet(1, 0, stamp, stamp + 1);
        System.out.println("A线程CAS："+atomicStampedReference.getReference() + " Stamp: " + atomicStampedReference.getStamp());
        System.out.println("A线程结果: " + result);
    }
}

public class TestABA {

    private static AtomicStampedReference<Integer> atomicStampedReference = new AtomicStampedReference<Integer>(1, 0);

    public static void main(String[] args) {
        CountDownLatch countDownLatch = new CountDownLatch(1);
        AtomicInteger atomicInteger = new AtomicInteger(1);
        ExecutorService executorService = Executors.newCachedThreadPool();
        executorService.execute(new TestAtomicStampedReference_1(countDownLatch, atomicStampedReference));
        executorService.execute(new TestAtomicStampedReference_2(countDownLatch, atomicStampedReference));
        executorService.shutdown();
    }

}

测试结果

AtomicStampedReference的测试结果

测试分析

由于AtomicStampedReference的compareAndSet的方法中加入了stamp，因此必须模拟A线程的一开始的stamp，这也是跟AtomicInteger的最大的不同之处。由于加入了stamp，所以每次更新就会更新stamp，因此最后执行结果必然是false。

小结

最后CAS与ABA问题也告一段落了，这个ABA问题是我在看Exchanger的时候提到，然后就好奇ABA问题是什么。然后一通研究发现是这样一回事。最后网上有很多博客都写得不错。不过在看别人博客时一开始先边看博客，边看Java文档，一定要看Java文档！！！！！！！！！！然后最后形成了自己的思维之后，开始考虑这个博客是否写得足够全面，例子是否足够说服这一个问题。

参考资料

Java的CAS和ABA问题: https://www.cnblogs.com/549294286/p/3766717.html

-------------本文结束感谢您的阅读-------------
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多