传说中的并发编程ABA问题

什么是ABA问题

ABA并不是一个缩写,更像是一个形象的描述。ABA问题出现在多线程或多进程计算环境中。

首先描述ABA。假设两个线程T1和T2访问同一个变量V,当T1访问变量V时,读取到V的值为A;此时线程T1被抢占了,T2开始执行,T2先将变量V的值从A变成了B,然后又将变量V从B变回了A;此时T1又抢占了主动权,继续执行,它发现变量V的值还是A,以为没有发生变化,所以就继续执行了。这个过程中,变量V从A变为B,再由B变为A就被形象地称为ABA问题了。

上面的描述看上去并不会导致什么问题。T1中的判断V的值是A就不应该有问题的,无论是开始的A,还是ABA后面的A,判断的结果应该是一样的才对。

不容易看出问题的主要还是因为:“值是一样的”等同于“没有发生变化”(就算被改回去了,那也是变化)的认知。毕竟在大多数程序代码中,我们只需要知道值是不是一样的,并不关心它在之前的过程中有没有发生变化;所以,当我需要知道之前的过程中“有没有发生变化”的时候,ABA就是问题了。

现实ABA问题

警匪剧看多了人应该可以快速反应到发生了什么。应用到ABA问题,首先,这里的A和B并不表示被掉的包这个实物,而是掉包过程中的状态的变化。假设一个装有10000W箱子(别管它有多大)放在一个房间里,10分钟后再进去拿出来赎人去。但是,有个贼在这10分钟内进去(别管他是怎么进去的)用一个同样大小的空箱子,把我的箱子掉包了。当我再进去看的时候,发现箱子还在,自然也就以为没有问题了的,就继续拿着桌子上的箱子去赎人了(别管重量对不对)。现在只要知道这里有问题就行了,拿着没钱的箱子去赎人还没有问题么?

这里的变量V就是桌子上是否有箱子的状态。A,是桌子上有箱子的状态;B是箱子在掉包过程中,离开桌子,桌子上没有箱子的状态;最后一个A也是桌子上有箱子的状态。但是箱子里面的东西是什么就不不知道了。

程序世界的ABA问题

在运用CAS做Lock-Free操作中有一个经典的ABA问题:

线程1准备用CAS将变量的值由A替换为B,在此之前,线程2将变量的值由A替换为C,又由C替换为A,然后线程1执行CAS时发现变量的值仍然为A,所以CAS成功。但实际上这时的现场已经和最初不同了,尽管CAS成功,但可能存在潜藏的问题,例如下面的例子:
ABA-1.png

现有一个用单向链表实现的堆栈,栈顶为A,这时线程T1已经知道A.next为B,然后希望用CAS将栈顶替换为B:

head.compareAndSet(A,B);

在T1执行上面这条指令之前,线程T2介入,将A、B出栈,再pushD、C、A,此时堆栈结构如下图,而对象B此时处于游离状态:

ABA-2.png

此时轮到线程T1执行CAS操作,检测发现栈顶仍为A,所以CAS成功,栈顶变为B,但实际上B.next为null,所以此时的情况变为:

ABA-3.png

其中堆栈中只有B一个元素,C和D组成的链表不再存在于堆栈中,平白无故就把C、D丢掉了。

以上就是由于ABA问题带来的隐患,各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记,避免并发操作带来的问题,在Java中,AtomicStampedReference<E>也实现了这个作用,它通过包装[E,Integer]的元组来对对象标记版本戳stamp,从而避免ABA问题,例如下面的代码分别用AtomicInteger和AtomicStampedReference来对初始值为100的原子整型变量进行更新,AtomicInteger会成功执行CAS操作,而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败:

import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.concurrent.atomic.AtomicStampedReference;

public class ABA {
        private static AtomicInteger atomicInt = new AtomicInteger(100);
        private static AtomicStampedReference atomicStampedRef = new AtomicStampedReference(100, 0);

        public static void main(String[] args) throws InterruptedException {
                Thread intT1 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                atomicInt.compareAndSet(100, 101);
                                atomicInt.compareAndSet(101, 100);
                        }
                });

                Thread intT2 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                try {
                                        TimeUnit.SECONDS.sleep(1);
                                } catch (InterruptedException e) {
                                }
                                boolean c3 = atomicInt.compareAndSet(100, 101);
                                System.out.println(c3); // true
                        }
                });

                intT1.start();
                intT2.start();
                intT1.join();
                intT2.join();

                Thread refT1 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                try {
                                        TimeUnit.SECONDS.sleep(1);
                                } catch (InterruptedException e) {
                                }
                                atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                                atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
                        }
                });

                Thread refT2 = new Thread(new Runnable() {
                        @Override
                        public void run() {
                                int stamp = atomicStampedRef.getStamp();
                                try {
                                        TimeUnit.SECONDS.sleep(2);
                                } catch (InterruptedException e) {
                                }
                                boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);
                                System.out.println(c3); // false
                        }
                });

                refT1.start();
                refT2.start();
        }
}

总结

简单说来,在多线程环境中,为了进行性能上的优化,可以设计一些无锁的算法。这里面会需要进行较多的判断,有些判断是十分关键的(比如说CAS中的判断),ABA主要存在这些判断中。有的时候,我们并不只是需要判断变量是不是我们看到的那个值,还需要在执行操作的过程中,判断这个变量是否已经发生了改变。得益于垃圾回收机制,用Java设计无锁算法的时候,可能出现ABA问题的情况还是相对比较少的。

qrcode_for_gh_bf7a27ade681_258.jpg

作者: 小柒

出处: https://blog.52itstyle.com

分享是快乐的,也见证了个人成长历程,文章大多都是工作经验总结以及平时学习积累,基于自身认知不足之处在所难免,也请大家指正,共同进步。

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出, 如有问题, 可邮件(345849402@qq.com)咨询。