在运用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
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 {<br /> Thread intT1 = new Thread(new Runnable() {<br /> @Override<br /> public void run() {<br /> atomicInt.compareAndSet(100, 101);<br /> atomicInt.compareAndSet(101, 100);<br /> }<br /> });
Thread intT2 = new Thread(new Runnable() {<br /> @Override<br /> public void run() {<br /> try {<br /> TimeUnit.SECONDS.sleep(1);<br /> } catch (InterruptedException e) {<br /> }<br /> boolean c3 = atomicInt.compareAndSet(100, 101);<br /> System.out.println(c3); // true<br /> }<br /> });
intT1.start();<br /> intT2.start();<br /> intT1.join();<br /> intT2.join();
Thread refT1 = new Thread(new Runnable() {<br /> @Override<br /> public void run() {<br /> try {<br /> TimeUnit.SECONDS.sleep(1);<br /> } catch (InterruptedException e) {<br /> }<br /> atomicStampedRef.compareAndSet(100, 101, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);<br /> atomicStampedRef.compareAndSet(101, 100, atomicStampedRef.getStamp(), atomicStampedRef.getStamp() + 1);<br /> }<br /> });
Thread refT2 = new Thread(new Runnable() {<br /> @Override<br /> public void run() {<br /> int stamp = atomicStampedRef.getStamp();<br /> try {<br /> TimeUnit.SECONDS.sleep(2);<br /> } catch (InterruptedException e) {<br /> }<br /> boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1);<br /> System.out.println(c3); // false<br /> }<br /> });
refT1.start();<br /> refT2.start();<br /> }<br />}
转载:http://blog.hesey.net/2011/09/resolve-aba-by-atomicstampedreference.html