我们常说的 CAS 自旋锁是什么
CAS与ABA问题
回顾JAVA中的CAS
用AtomicStampedReference解决ABA问题
CAS(Compare and swap),即比较并交换 ,也是实现我们平时所说的 【自旋锁或乐观锁】的核心操作。
CAS有3个操作数, 内存值V,旧的预期值A,要修改的新值B 。当且仅当预期值A和内存值V相同时,将内存值V修改为B,否则什么都不做。
public final boolean compareAndSet(boolean expect, boolean update)
它的实现很简单, 【就是用 一个预期的值 和 内存值 进行比较,如果两个值相等,就用预期的值替换内存值,并返回 true。否则,返回 false】 。
任何技术的出现都是为了解决某些特定的问题, CAS 要解决的问题就是保证原子操作 。原子操作是什么,原子就是最小不可拆分的,原子操作就是最小不可拆分的操作,也就是说操作一旦开始,就不能被打断,知道操作完成。在多线程环境下,原子操作是保证线程安全的重要手段。举个例子来说,假设有两个线程在工作,都想对某个值做修改,就拿自增操作来说吧,要对一个整数 i 进行自增操作,需要基本的三个步骤:
1、读取 i 的当前值;
2、对 i 值进行加 1 操作;
3、将 i 值写回内存;
假设两个进程都读取了 i 的当前值,假设是 0,这时候 A 线程对 i 加 1 了,B 线程也 加 1,最后 i 的是 1 ,而不是 2。这就是因为自增操作不是原子操作,分成的这三个步骤可以被干扰。如下面这个例子,10个线程,每个线程都执行 10000 次 i++ 操作,我们期望的值是 100,000,但是很遗憾,结果总是小于 100,000 的。
static int i = 0; public static void add() { i++; } private static class Plus implements Runnable { @Override public void run() { for ( int k = 0; k < 10000; k++ ) { add(); } } } public static void main( String[] args ) throws InterruptedException { Thread[] threads = new Thread[10]; for ( int i = 0; i < 10; i++ ) { threads[i] = new Thread( new Plus() ); threads[i].start(); } for ( int i = 0; i < 10; i++ ) { threads[i].join(); } System.out.println( i ); }
既然这样,那怎么办。没错,也许你已经想到了,可以加锁或者利用 synchronized 实现,例如,将 add() 方法修改为如下这样:
public synchronized static void add(){ i++; }
或者,加锁操作,例如下面使用 ReentrantLock (可重入锁)实现。
private static Lock lock = new ReentrantLock(); public static void add(){ lock.lock(); i++; lock.unlock(); }
既然用锁或 synchronized 关键字可以实现原子操作,那么为什么还要用 CAS 呢,因为 【加锁或使用 synchronized 关键字带来的性能损耗较大】 ,而用 【CAS 可以实现乐观锁】 ,它实际上是直接利用了 CPU 层面的指令,所以性能很高。
上面也说了,CAS 是实现自旋锁的基础, 【CAS 利用 CPU 指令保证了操作的原子性 ,以达到锁的效果】 ,至于自旋呢,看字面意思也很明白,自己旋转,翻译成人话就是循环, 【一般是用一个无限循环实现。这样一来,一个无限循环中,执行一个 CAS 操作,当操作成功,返回 true 时,循环结束;当返回 false 时,接着执行循环,继续尝试 CAS 操作,直到返回 true】 。
其实 JDK 中有好多地方用到了 CAS ,尤其是java.util.concurrent包下,比如 CountDownLatch、Semaphore、ReentrantLock 中,再比如 java.util.concurrent.atomic 包下,相信大家都用到过 Atomic* ,比如 AtomicBoolean、AtomicInteger 等。
这里拿 AtomicBoolean 来举个例子,因为它足够简单。
public class AtomicBoolean implements java.io.Serializable { private static final long serialVersionUID = 4654671469794556979L; // setup to use Unsafe.compareAndSwapInt for updates private static final Unsafe unsafe = Unsafe.getUnsafe(); private static final long valueOffset; static { try { valueOffset = unsafe.objectFieldOffset(AtomicBoolean.class.getDeclaredField("value")); } catch (Exception ex) { throw new Error(ex); } } private volatile int value; public final boolean get() { return value != 0; } public final boolean compareAndSet(boolean expect, boolean update) { int e = expect ? 1 : 0; int u = update ? 1 : 0; return unsafe.compareAndSwapInt(this, valueOffset, e, u); } }
这里面又几个关键方法和属性。
1、使用了 sun.misc.Unsafe 对象 ,这个类 提供了一系列 直接操作内存对象 的方法 ,只是在 jdk 内部使用,不建议开发者使用;
2、value 表示实际值,可以看到 get 方法实际是根据 value 是否等于0来判断布尔值的,这里的 value 定义为 volatile,因为 volatile 可以保证内存可见性,也就是 value 值只要发生变化,其他线程是马上可以看到变化后的值的;下一篇会讲一下 volatile 可见性问题,欢迎关注
3、valueOffset 是 value 值的内存偏移量,用 unsafe.objectFieldOffset 方法获得,用作后面的 compareAndSet 方法;
4、 compareAndSet 方法,这就是实现 CAS 的核心方法了,在使用这个方法时,只需要传递期望值和待更新的值即可 ,而它里面调用了 unsafe.compareAndSwapInt(this, valueOffset, e, u) 方法,它是个 native 方法,用 c++ 实现,具体的代码就不贴了,总之是利用了 CPU 的 cmpxchg 指令完成比较并替换,当然根据具体的系统版本不同,实现起来也有所区别,感兴趣的可以自行搜一下相关文章。
CAS 适合简单对象的操作,比如布尔值、整型值等;
CAS 适合冲突较少的情况, 如果太多线程在同时自旋,那么长时间循环会导致 CPU 开销很大 ;
线程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来对记录或对象标记 ,避免并发操作带来的问题,并发包下倒是有 AtomicStampedReference 提供了根据版本号判断的实现,可以解决一部分问题。它通过包装[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(); } }
。。