CAS和ABA问题

2019-11-08 03:08:28

字体：大中小

来源：转载

供稿：网友

CAS

CAS全称是CompareAndSwap，是一条CPU的原子指令，其作用是让CPU经过比较后原子地更新某个位置的值，CAS是靠硬件实现的，JVM只是封装了汇编调用，那些AtomicInteger类便是使用了封装汇编的接口。

我们知道synchronized是一种悲观锁，它使得其它需要锁的线程挂起，等待持有锁的线程释放锁。而乐观锁却不加锁，它假设没有冲突去完成某项操作，如果冲突失败就重试，直到成功为止。乐观锁用到的机制就是CAS，Compare and Swap。

以java.util.concurrent.atomic.AtomicInteger为例，我们看一下在没有锁的情况下是如何做到数据一致的。

PRivate volatile int value; public final int get() { return value; } public final int incrementAndGet() { for (;;) { int current = get(); int next = current + 1; if (compareAndSet(current, next)) return next; } } public final boolean compareAndSet(int expect, int update) { return unsafe.compareAndSwapInt(this, valueOffset, expect, update); }

incrementAndGet方法每次从内存中获取value和+1后的结果next，再进行CAS操作，即将value值和最新内存值进行比较。如果一致就更新next，否则重试直到成功为止。

ABA问题

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

这里写图片描述 (1) 现有一个用单向链表实现的堆栈，栈顶为A。这时线程T1已经知道A.next为B，然后希望用CAS将栈顶替换为B：

head.compareAndSet(A,B);

(2) 在T1执行上面这条指令之前，线程T2介入，将A、B出栈，再依次入栈D、C、A，而对象B此时处于游离状态。

(3) 此时轮到线程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失败：

public class ABA { private static AtomicInteger atomicInt = new AtomicInteger(100); private static AtomicStampedReference<Integer> atomicStampedRef = new AtomicStampedReference<Integer>(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) { e.printStackTrace(); } 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) { e.printStackTrace(); } 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(); System.out.println("before sleep : stamp = " + stamp); // stamp = 0 try { TimeUnit.SECONDS.sleep(2); } catch (InterruptedException e) { e.printStackTrace(); } System.out.println("after sleep : stamp = " + atomicStampedRef.getStamp());//stamp = 1 boolean c3 = atomicStampedRef.compareAndSet(100, 101, stamp, stamp + 1); System.out.println(c3); //false } }); refT1.start(); refT2.start(); }}

运行结果：这里写图片描述