AtomicStampedReference

梦里梦外; 2022-02-28 04:44 132阅读 0赞

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

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

现有一个用单向链表实现的堆栈，栈顶为A，这时线程T1已经知道A.next为B，然后希望用CAS将栈顶替换为B：  
head.compareAndSet(A,B);  
在T1执行上面这条指令之前，线程T2介入，将A、B出栈，再pushD、C、A，此时堆栈结构如下图，而对象B此时处于游离状态：  
此时轮到线程T1执行CAS操作，检测发现栈顶仍为A，所以CAS成功，栈顶变为B，但实际上B.next为null，所以此时的情况变为：  
其中堆栈中只有B一个元素，C和D组成的链表不再存在于堆栈中，平白无故就把C、D丢掉了。

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

private static AtomicInteger at = new AtomicInteger(100);
        private static AtomicStampedReference asr = new AtomicStampedReference(100, 0);
    
        public static void main(String[] args) throws InterruptedException {
            Thread t1 = new Thread(() -> {
                try {
                    TimeUnit.SECONDS.sleep(1);
                    at.compareAndSet(100, 101);
                    at.compareAndSet(101, 100);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            t1.start();
    
            Thread t2 = new Thread(() -> {
                try {
                    TimeUnit.SECONDS.sleep(2);
                    boolean b = at.compareAndSet(100, 101);
                    System.out.println("AtomicInteger " + b);//AtomicInteger true
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            t2.start();
    
            Thread t3 = new Thread(() -> {
                try {
                    TimeUnit.SECONDS.sleep(1);
                    asr.compareAndSet(100, 101, asr.getStamp(), asr.getStamp() + 1);
                    asr.compareAndSet(101, 100, asr.getStamp(), asr.getStamp() + 1);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            t3.start();
    
            Thread t4 = new Thread(() -> {
                try {
                    int stamp = asr.getStamp();
                    System.out.println("stamp = " + stamp);
                    TimeUnit.SECONDS.sleep(2);
                    boolean b = asr.compareAndSet(100, 101, stamp, stamp + 1);
                    System.out.println("AtomicStampedReference " + b);//AtomicStampedReference false
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            });
            t4.start();
    
        }

stamp = 0  
AtomicInteger true  
AtomicStampedReference false