[Java]无锁操作与CAS

最近在看并发编程的相关内容，在分析ConcurrentHashMap（JDK 1.8版本）源码时，发现其效率高的很重要的原因之一，就是使用了CAS无锁操作——Compare and swap操作。之前不是很了解CAS操作，于是今天详细研究了一下CAS操作。

在介绍CAS之前，先来看一个多线程的例子。

class Increment implements Runnable{
    private static volatile int value = 0;

    public static int getValue() {
        return value;
    }

    @Override
    public void run() {
        for (int i = 0; i < 10000; ++i) {
            value++;
        }
    }
}
class AtomicIntegerStudy {
    private static final int THREADS_COUNT = 20;

    public static void test01() {
        Thread[] threads = new Thread[THREADS_COUNT];
        for (int i = 0; i < THREADS_COUNT; ++i) {
            threads[i] = new Thread(new Increment());
            threads[i].start();
        }

        for (int i = 0; i < THREADS_COUNT; ++i) {
            try {
                threads[i].join();
            } catch (Exception e) {

            }
        }

        System.out.println("result: " + Increment.getValue());
        /* 命令行输出
        result: 76777

        注：无论如何是一个小于200,000的数字
         */
    }
}

有过多线程基础的同学都能看出，AtomicIntegerStudy.test01()最终的结果一定不是200,000。多个线程修改Increment类中的value变量时，一定会有相互覆盖的情况，所以最后的结果一定是小于200,000的。如何能够得到正确的结果呢？首先想到的肯定是加锁。不过加锁肯定会使得程序的执行效率变低。但是如果将成员变量改成AtomicInteger类进行自增运算，就可以得到正确的结果了，而且还没有加锁。看看下面的例子。
class AtomicIntegerIncrement implements Runnable {
    private static AtomicInteger value = new AtomicInteger(0);

    public static int getValue() {
        return value.get();
    }

    @Override
    public void run() {
        for (int i = 0; i < 10000; ++i) {
            value.getAndIncrement();
        }
    }
}

class AtomicIntegerStudy {
    private static final int THREADS_COUNT = 20;

    public static void test02() {
        Thread[] threads = new Thread[THREADS_COUNT];
        for (int i = 0; i < THREADS_COUNT; ++i) {
            threads[i] = new Thread(new AtomicIntegerIncrement());
            threads[i].start();
        }

        for (int i = 0; i < THREADS_COUNT; ++i) {
            try {
                threads[i].join();
            } catch (Exception e) {

            }
        }

        System.out.println("result: " + AtomicIntegerIncrement.getValue());
        /* 命令行输出
        result: 200000

        注：一定是200,000
         */
    }
}

AtomicInteger类在此就不详述了。但是此类能够在并发的条件下，得到正确的结果，就是因为其getAndIncrement方法最终调用了compareAndSwapInt方法更新其中的值。
好了，下面我们就来介绍一下CAS操作。
CAS操作都在sun.misc.Unsafe类中，以compareAndSwap开头。其所有方法都是native，并且都是原子操作。这也为并发条件下保证每一次更新不会相互覆盖带来了可能。
那么CAS到底原理是什么呢？我们以compareAndSwapInt方法为例，分析一下。
首先来看下这个函数的函数签名：
public final native boolean compareAndSwapInt(Object o, long offset, int expected, int x);

其中，offset是目标成员变量在对象o中的偏移，expected是此成员变量期望的值（只有当成员变量等于expected值时，才会更新成员变量），x是变更后的值。更新成功返回true，失败返回false。
还是以一个例子来看一下compareAndSwapInt的实际用法。
class CompareAndSwapIntStudy {
    static class Target {
        public volatile int value = 1;
    }

    private static Unsafe getUnsafe() throws IllegalAccessException, NoSuchFieldException {
        Field field = Unsafe.class.getDeclaredField("theUnsafe");
        field.setAccessible(true);
        return (Unsafe) field.get(null);
    }

    public static void compareAndSwapIntTest() {
        Target t = new Target();
        System.out.println("原始value值:" + t.value);
        try {
            /*
            注：此处Unsafe不能直接通过new运算符以及Unsafe.getUnsafe()获得实例。
            1）Unsafe的构造方法是private的，无法通过new得到（实际是个单例模式）
            2）Unsafe.getUnsafe()被设计成只能从引导类加载器（bootstrap class loader）加载
             */
            Unsafe unsafe = getUnsafe();
            long valueOffset = unsafe.objectFieldOffset(
                    Target.class.getDeclaredField("value"));
            System.out.println("first time swap(1, 2) return: " +
                    unsafe.compareAndSwapInt(t, valueOffset, 1, 2));
            System.out.println("after first time swap(1, 2) value: " +
                    t.value);
            System.out.println("second time swap(1, 2) return: " +
                    unsafe.compareAndSwapInt(t, valueOffset, 1, 2));
            System.out.println("after second time swap(1, 2) value: " +
                    t.value);
        } catch (Exception e) {
            e.printStackTrace();
        }
        /* 命令行输出
            原始value值:1
            first time swap(1, 2) return: true
            after first time swap(1, 2) value: 2
            second time swap(1, 2) return: false
            after second time swap(1, 2) value: 2
         */
    }
}

CAS的用法就介绍到这儿。
引申阅读：

Unsafe的用法：《Java Magic. Part 4: sun.misc.Unsafe》