CAS和原子类是如何实现的？

本文基于 JDK1.8 编写。

1. 背景

当多个线程对同一个变量进行修改时，可能会产生以下线程安全问题：

• CPU缓存导致的可见性问题。
• 指令重排序导致的有序性问题。
• 线程切换导致的原子性问题。

1.1. 线程不安全的累加器

如下代码，UnsafeCount类是一个累加器：

public class UnsafeCount {
    private int value = 0;

    public void increment() {
        value = value + 1;
    }

    public int get() {
        return value;
    }
}

当两个线程分别调用UnsafeCount#increment方法各5000次时，最终输出的结果为8957，而非预期的10000。

public class UnsafeCountTest {

    @Test
    public void testUnsafeCount() throws Exception {
        UnsafeCount unsafeCount = new UnsafeCount();
        Runnable task = () -> {
            int count = 5000;
            while (count-- > 0) {
                unsafeCount.increment();
            }
        };
        Thread[] threads = new Thread[]{new Thread(task), new Thread(task)};
        Arrays.stream(threads).forEach(Thread::start);
        for (Thread thread : threads) {
            thread.join();
        }
        Assertions.assertEquals(10000, unsafeCount.get());
    }
	/* 	
		Output:
		org.opentest4j.AssertionFailedError: 
		Expected :10000
		Actual   :8957
	*/
}

1.2. 线程安全的累加器

通常来说，添加synchronized内置锁便可保证线程安全，如下代码：

public class SafeCount {
    private int value = 0;

    public synchronized void increment() {
        value = value + 1;
    }

    public synchronized int get() {
        return value;
    }
}

• 通过synchronized保证increment方法的可见性。
• 通过synchronized保证get方法的可见性。

public class SafeCount {
    private volatile int value = 0;

    public synchronized void increment() {
        value = value + 1;
    }

    public int get() {
        return value;
    }
}

• 通过synchronized保证increment方法的可见性。
• 通过volatile保证get方法中value的可见性。

为了更好的性能，可以使用原子类AtomicInteger，其底层使用了CAS，如下代码：

public class SafeCount {
    private AtomicInteger value = new AtomicInteger();

    public void increment() {
        value.getAndIncrement();
    }

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

2. CAS

2.1. 什么是CAS？

CAS（Compare And Swap）是一种无锁算法，相比于基于锁实现的互斥，CAS搭配自旋的方式有更好的性能。CAS的核心思想是：

• 比较变量V的当前值是否和期待值A相等。
• 如果相等则交换为新值B并且返回true。
• 如果不相等则返回false。

CAS的伪代码如下：

V currentValue;
atomic bool compareAndSwap(A expectedValue, B newValue) {
	if currentValue == expectedValue) {
		currentValue = newValue;
		return true;
	}
	return false;
}

CAS搭配自旋实现乐观锁的伪代码如下：

void set(B newValue) {
	do {
		expectedValue = currentValue;
	} while(!compareAndSwap(expectedValue, newValue))
}

以上等效的基于悲观锁的伪代码如下：

sync void set(B newValue) {
	currentValue = newValue;
}

2.2. CAS带来了哪些问题？

CAS搭配自旋实现了高性能的乐观锁，但同时带来了以下几个问题：

• ABA问题。其他线程将原本为A的值修改为B，而后又修改为A，看起来值似乎未发生改变，导致CAS误判。可以通过添加版本号的方式解决ABA问题，确保每次修改都有一个版本。
• 自旋消耗CPU资源。CAS搭配自旋的方式适用于持有锁的时间较短的场景，否则CAS操作会一直返回false，导致一直自旋占用CPU资源。

2.3. Java中的CAS是如何实现的？

Java中的CAS依赖于Unsafe类，其提供了以下几个原生方法：

• unsafe#objectFieldOffset：获取类中字段的偏移量。
• Unsafe#compareAndSwapObject：对类型为Object的值进行CAS操作。
• Unsafe#compareAndSwapInt：对类型为int的值进行CAS操作。
• Unsafe#compareAndSwapLong：对类型为long的值进行CAS操作。

public native long objectFieldOffset(Field obj);

public final native boolean compareAndSwapObject(Object obj, long offset, Object expectedValue, Object newValue);

public final native boolean compareAndSwapInt(Object obj, long offset, int expectedValue, int newValue);

public final native boolean compareAndSwapLong(Object obj, long offset, long expectedValue, long newValue);

以上几个方法由CPU指令保证原子性，也就是执行的过程中不会被其他线程打断。Unsafe类中的很多方法都是原生方法，为JDK中并发工具的实现提供了基础，但为了安全只能在JDK源码中使用，对于开发人员应使用JDK中提供的并发工具。

@CallerSensitive
public static Unsafe getUnsafe() {
	Class var0 = Reflection.getCallerClass();
	if (!VM.isSystemDomainLoader(var0.getClassLoader())) {
		throw new SecurityException("Unsafe");
	} else {
		return theUnsafe;
	}
}

3. 原子类

3.1. AtomicInteger是如何实现的？

AtomicInteger是Java提供的原子类，是线程安全的。执行AtomicInteger#getAndIncrement方法时，会调用Unsafe#getAndAddInt方法，该方法通过while自旋加Unsafe#compareAndSwapInt设置新值。源码如下：

public class AtomicInteger extends Number implements java.io.Serializable {
	private static final long valueOffset;
	
	private volatile int value;
	
	static {
		try {
			// 获取 value 字段的偏移量
			valueOffset = unsafe.objectFieldOffset
				(AtomicInteger.class.getDeclaredField("value"));
		} catch (Exception ex) { throw new Error(ex); }
	}
	
	public final int getAndIncrement() {
		return unsafe.getAndAddInt(this, valueOffset, 1);
	}
	
	public final int get() {
		return value;
	}
	...
}

public final class Unsafe {
	...
	public final int getAndAddInt(Object obj, long valueOffset, int delta) {
		int expectedValue;
		do {
			// 获取期待值
			expectedValue = this.getIntVolatile(obj, valueOffset);
			// CAS 比较当前值是否和期待值相等，如果相等则交换为新值并返回，否则自旋
		} while(!this.compareAndSwapInt(obj, valueOffset, expectedValue, expectedValue + delta));
	
		return expectedValue;
	}
	
	// 原子的 CAS 操作
	public final native boolean compareAndSwapInt(Object obj, long valueOffset, int expectedValue, int newValue);
	...
}

3.2. Java中提供哪些原子类？

Java提供了一系列的线程安全的原子类，在包java.util.concurrent.atomic下。有以下几种：

• 基本类型原子类：
  • AtomicBoolean。
  • AtomicInteger。
  • AtomicLong。
• 引用类型原子类：
  • AtomicReference。
  • AtomicStampedReference。
• 数组类型原子类：
  • AtomicIntegerArray。
  • AtomicLongArray。
  • AtomicReferenceArray。
• 对象属性更新原子类：
  • AtomicIntegerFieldUpdater。
  • AtomicLongFieldUpdater。
  • AtomicReferenceFieldUpdater。
• 累加器：
  • DoubleAccumulator。
  • DoubleAdder。
  • LongAccumulator。
  • LongAdder。