最近在看并发编程的相关内容,在分析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》
不赖!真的不赖!