用AtomicStampedReference解决ABA问题

在运用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>也实现了这个作用,它通过包装[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();
	}
}

用AtomicStampedReference解决ABA问题》上有7条评论

  1. 各种乐观锁的实现中通常都会用版本戳version来对记录或对象标记,避免并发操作带来的问题。

    而加上版本戳的AtomicStampedReference对于ABA问题会执行CAS失败。

    前面说到用版本戳version来对记录或对象标记可以避免并发操作带来的问题,
    后面又说加上版本戳的AtomicStampedReference会执行CAS失败。

    不能理解作者文字描述的准确性和意思。以及AtomicStampedReference到底是为了避免ABA,还是为了产生ABA(这个显然是不希望发生的)。

    [回复]

    Hesey 回复:

    发生ABA的时候利用时间戳快速失败,和数据库乐观锁是一样的。作用是让你意识到发生了问题,而不是把问题掩盖。

    [回复]

    Brian 回复:

    这个有问题,AtomicStampedReference atomicStampedRef = new AtomicStampedReference(1000, 0);当Integer的值大于127的时候就会有问题,感觉是jdk的一个bug,你可以自己试一下,结果没有改变
    atomicStampedRef.compareAndSet(1000, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
    System.out.println(atomicStampedRef.getReference().longValue());
    atomicStampedRef.compareAndSet(101, 1000, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
    System.out.println(atomicStampedRef.getReference().longValue());

    [回复]

  2. lz的例子很直观,赞!
    是这样的,我觉得这个程序作为演示当然是没有问题的,提两个小建议。
    1. 但是线程执行过程中,到底发生了什么,谁也不知道。所以其实在refT2中sleep(2),在refT1中sleep(1),不如直接用单线程来演示就ok了吧。
    int stamp = atomicStampedRef.getStamp();
    atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
    atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);
    boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);

    2. 其实这里的解决ABA问题,个人认为,不仅仅是解决了对于数值出现ABA问题,也解决了地址的ABA问题。也就是说,刚刚释放了地址,马上被回收使用,那么如果不用stamp,也会出现ABA的状况。
    http://en.wikipedia.org/wiki/ABA_problem

    谢谢!

    [回复]

  3. Pingback引用通告: CAS 操作的实现原理 | 心静志远

  4. Pingback引用通告: Java CAS 和ABA问题 | 菜鸟飞翔

  5. Pingback引用通告: JAVA CAS – w1100n

发表评论

电子邮件地址不会被公开。