CAS自旋锁

 我们常说的 CAS 自旋锁是什么

CAS与ABA问题

回顾JAVA中的CAS

用AtomicStampedReference解决ABA问题

 

Java 8对CAS机制的优化

悲观锁，乐观锁CAS、原子操作类的应用与浅析及Java8对其的优化

 

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();
}

 

CAS 实现自旋锁

既然用锁或 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 开销很大；

 

 

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来对记录或对象标记，避免并发操作带来的问题，并发包下倒是有 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();
        }
}

 。。