计算机程序的思维逻辑 (70) - 原子变量和CAS
编程爱好者联盟 2017-03-02
从本节开始，我们探讨Java并发工具包java.util.concurrent中的内容，本节先介绍最基本的原子变量及其背后的原理和思维。
原子变量
什么是原子变量？为什么需要它们呢？
在理解synchronized一节，我们介绍过一个Counter类，使用synchronized关键字保证原子更新操作，代码如下：
public class Counter {
private int count;
public synchronized void incr(){
count ++;
}
public synchronized int getCount() {
return count;
}
} 对于count++这种操作来说，使用synchronzied成本太高了，需要先获取锁，最后还要释放锁，获取不到锁的情况下还要等待，还会有线程的上下文切换，这些都需要成本。
对于这种情况，完全可以使用原子变量代替，Java并发包中的基本原子变量类型有：
- AtomicBoolean：原子Boolean类型
- AtomicInteger：原子Integer类型
- AtomicLong：原子Long类型
- AtomicReference：原子引用类型
这是我们主要介绍的类，除了这四个类，还有一些其他的类，我们也会进行简要介绍。
针对Integer, Long和Reference类型，还有对应的数组类型：
- AtomicIntegerArray
- AtomicLongArray
- AtomicReferenceArray
为了便于以原子方式更新对象中的字段，还有如下的类：
- AtomicIntegerFieldUpdater
- AtomicLongFieldUpdater
- AtomicReferenceFieldUpdater
AtomicReference还有两个类似的类，在某些情况下更为易用：
- AtomicMarkableReference
- AtomicStampedReference
你可能会发现，怎么没有针对char, short, float, double类型的原子变量呢？大概是用的比较少吧，如果需要，可以转换为int/long，然后使用AtomicInteger或AtomicLong。比如，对于float，可以使用如下方法和int相互转换：
public static int floatToIntBits(float value) public static float intBitsToFloat(int bits);
下面，我们先来看几个基本原子类型，从AtomicInteger开始。
AtomicInteger
基本用法
AtomicInteger有两个构造方法：
public AtomicInteger(int initialValue) public AtomicInteger()
第一个构造方法给定了一个初始值，第二个的初始值为0。
可以直接获取或设置AtomicInteger中的值，方法是：
public final int get() public final void set(int newValue)
之所以称为原子变量，是因为其包含一些以原子方式实现组合操作的方法，比如：
//以原子方式获取旧值并设置新值 public final int getAndSet(int newValue) //以原子方式获取旧值并给当前值加1 public final int getAndIncrement() //以原子方式获取旧值并给当前值减1 public final int getAndDecrement() //以原子方式获取旧值并给当前值加delta public final int getAndAdd(int delta) //以原子方式给当前值加1并获取新值 public final int incrementAndGet() //以原子方式给当前值减1并获取新值 public final int decrementAndGet() //以原子方式给当前值加delta并获取新值 public final int addAndGet(int delta)
这些方法的实现都依赖另一个public方法：
public final boolean compareAndSet(int expect, int update)
这是一个非常重要的方法，比较并设置，我们以后将简称为CAS。该方法以原子方式实现了如下功能：如果当前值等于expect，则更新为update，否则不更新，如果更新成功，返回true，否则返回false。
AtomicInteger可以在程序中用作一个计数器，多个线程并发更新，也总能实现正确性，我们看个例子：
public class AtomicIntegerDemo {
private static AtomicInteger counter = new AtomicInteger(0);
static class Visitor extends Thread {
@Override
public void run() {
for (int i = 0; i < 100; i++) {
counter.incrementAndGet();
Thread.yield();
}
}
}
public static void main(String[] args) throws InterruptedException {
int num = 100;
Thread[] threads = new Thread[num];
for (int i = 0; i < num; i++) {
threads[i] = new Visitor();
threads[i].start();
}
for (int i = 0; i < num; i++) {
threads[i].join();
}
System.out.println(counter.get());
}
} 程序的输出总是正确的，为10000。
基本原理和思维
AtomicInteger的使用方法是简单直接的，它是怎么实现的呢？它的主要内部成员是：
private volatile int value;
注意，它的声明带有volatile，这是必需的，以保证内存可见性。
它的大部分更新方法实现都类似，我们看一个方法incrementAndGet，其代码为：
public final int incrementAndGet() {
for (;;) {
int current = get();
int next = current + 1;
if (compareAndSet(current, next))
return next;
}
} 代码主体是个死循环，先获取当前值current，计算期望的值next，然后调用CAS方法进行更新，如果当前值没有变，则更新并返回新值，否则继续循环直到更新成功为止。
与synchronized锁相比，这种原子更新方式代表一种不同的思维方式。
synchronized是悲观的，它假定更新很可能冲突，所以先获取锁，得到锁后才更新。原子变量的更新逻辑是乐观的，它假定冲突比较少，但使用CAS更新，也就是进行冲突检测，如果确实冲突了，那也没关系，继续尝试就好了。
synchronized代表一种阻塞式算法，得不到锁的时候，进入锁等待队列，等待其他线程唤醒，有上下文切换开销。原子变量的更新逻辑是非阻塞式的，更新冲突的时候，它就重试，不会阻塞，不会有上下文切换开销。
对于大部分比较简单的操作，无论是在低并发还是高并发情况下，这种乐观非阻塞方式的性能都要远高于悲观阻塞式方式。
原子变量是比较简单的，但对于复杂一些的数据结构和算法，非阻塞方式往往难于实现和理解，幸运的是，Java并发包中已经提供了一些非阻塞容器，我们只需要会使用就可以了，比如：
- ConcurrentLinkedQueue和ConcurrentLinkedDeque：非阻塞并发队列
- ConcurrentSkipListMap和ConcurrentSkipListSet：非阻塞并发Map和Set
这些容器我们在后续章节介绍。
但compareAndSet是怎么实现的呢？我们看代码：
public final boolean compareAndSet(int expect, int update) {
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
} 它调用了unsafe的compareAndSwapInt方法，unsafe是什么呢？它的类型为sun.misc.Unsafe，定义为：
private static final Unsafe unsafe = Unsafe.getUnsafe();
它是Sun的私有实现，从名字看，表示的也是"不安全"，一般应用程序不应该直接使用。原理上，一般的计算机系统都在硬件层次上直接支持CAS指令，而Java的实现都会利用这些特殊指令。从程序的角度看，我们可以将compareAndSet视为计算机的基本操作，直接接纳就好。
实现锁
基于CAS，除了可以实现乐观非阻塞算法，它也可以用来实现悲观阻塞式算法，比如锁，实际上，Java并发包中的所有阻塞式工具、容器、算法也都是基于CAS的 (不过，也需要一些别的支持)。
怎么实现呢？我们演示一个简单的例子，用AtomicInteger实现一个锁MyLock，代码如下：
public class MyLock {
private AtomicInteger status = new AtomicInteger(0);
public void lock() {
while (!status.compareAndSet(0, 1)) {
Thread.yield();
}
}
public void unlock() {
status.compareAndSet(1, 0);
}
} 在MyLock中，使用status表示锁的状态，0表示未锁定，1表示锁定，lock()/unlock()使用CAS方法更新，lock()只有在更新成功后才退出，实现了阻塞的效果，不过一般而言，这种阻塞方式过于消耗CPU，有更为高效的方式，我们后续章节介绍。MyLock只是用于演示基本概念，实际开发中应该使用Java并发包中的类如ReentrantLock。
AtomicBoolean/AtomicLong/AtomicReference
AtomicBoolean/AtomicLong/AtomicReference的用法和原理与AtomicInteger是类似的，我们简要介绍下。
AtomicBoolean
AtomicBoolean可以用来在程序中表示一个标志位，它的原子操作方法有：
public final boolean compareAndSet(boolean expect, boolean update) public final boolean getAndSet(boolean newValue)
实际上，AtomicBoolean内部使用的也是int类型的值，用1表示true, 0表示false，比如，其CAS方法代码为：
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);
} AtomicLong
AtomicBoolean可以用来在程序中生成唯一序列号，它的方法与AtomicInteger类似，就不赘述了。它的CAS方法调用的是unsafe的另一个方法，如：
public final boolean compareAndSet(long expect, long update) {
return unsafe.compareAndSwapLong(this, valueOffset, expect, update);
} AtomicReference
AtomicReference用来以原子方式更新复杂类型，它有一个类型参数，使用时需要指定引用的类型。以下代码演示了其基本用法：
public class AtomicReferenceDemo {
static class Pair {
final private int first;
final private int second;
public Pair(int first, int second) {
this.first = first;
this.second = second;
}
public int getFirst() {
return first;
}
public int getSecond() {
return second;
}
}
public static void main(String[] args) {
Pair p = new Pair(100, 200);
AtomicReference<Pair> pairRef = new AtomicReference<>(p);
pairRef.compareAndSet(p, new Pair(200, 200));
System.out.println(pairRef.get().getFirst());
}
} AtomicReference的CAS方法调用的是unsafe的另一个方法：
public final boolean compareAndSet(V expect, V update) {
return unsafe.compareAndSwapObject(this, valueOffset, expect, update);
} 原子数组
原子数组方便以原子的方式更新数组中的每个元素，我们以AtomicIntegerArray为例来简要介绍下。
它有两个构造方法：
public AtomicIntegerArray(int length) public AtomicIntegerArray(int[] array)
第一个会创建一个长度为length的空数组。第二个接受一个已有的数组，但不会直接操作该数组，而是会创建一个新数组，只是拷贝参数数组中的内容到新数组。
AtomicIntegerArray中的原子更新方法大多带有数组索引参数，比如：
public final boolean compareAndSet(int i, int expect, int update) public final int getAndIncrement(int i) public final int getAndAdd(int i, int delta)
第一个参数i就是索引。看个简单的例子：
public class AtomicArrayDemo {
public static void main(String[] args) {
int[] arr = { 1, 2, 3, 4 };
AtomicIntegerArray atomicArr = new AtomicIntegerArray(arr);
atomicArr.compareAndSet(1, 2, 100);
System.out.println(atomicArr.get(1));
System.out.println(arr[1]);
}
} 输出为：
100 2
FieldUpdater
FieldUpdater方便以原子方式更新对象中的字段，字段不需要声明为原子变量，FieldUpdater是基于反射机制实现的，我们会在后续章节介绍反射，这里简单介绍下其用法，看代码：
public class FieldUpdaterDemo {
static class DemoObject {
private volatile int num;
private volatile Object ref;
private static final AtomicIntegerFieldUpdater<DemoObject> numUpdater
= AtomicIntegerFieldUpdater.newUpdater(DemoObject.class, "num");
private static final AtomicReferenceFieldUpdater<DemoObject, Object>
refUpdater = AtomicReferenceFieldUpdater.newUpdater(
DemoObject.class, Object.class, "ref");
public boolean compareAndSetNum(int expect, int update) {
return numUpdater.compareAndSet(this, expect, update);
}
public int getNum() {
return num;
}
public Object compareAndSetRef(Object expect, Object update) {
return refUpdater.compareAndSet(this, expect, update);
}
public Object getRef() {
return ref;
}
}
public static void main(String[] args) {
DemoObject obj = new DemoObject();
obj.compareAndSetNum(0, 100);
obj.compareAndSetRef(null, new String("hello"));
System.out.println(obj.getNum());
System.out.println(obj.getRef());
}
} 类DemoObject中有两个成员num和ref，声明为volatile，但不是原子变量，不过DemoObject对外提供了原子更新方法compareAndSet，它是使用字段对应的FieldUpdater实现的，FieldUpdater是一个静态成员，通过newUpdater工厂方法得到，newUpdater需要的参数有类型、字段名、对于引用类型，还需要引用的具体类型。
ABA问题
使用CAS方式更新有一个ABA问题，该问题是指，一个线程开始看到的值是A，随后使用CAS进行更新，它的实际期望是没有其他线程修改过才更新，但普通的CAS做不到，因为可能在这个过程中，已经有其他线程修改过了，比如先改为了B，然后又改回为了A。
ABA是不是一个问题与程序的逻辑有关，如果是一个问题，一个解决方法是使用AtomicStampedReference，在修改值的同时附加一个时间戳，只有值和时间戳都相同才进行修改，其CAS方法声明为：
public boolean compareAndSet(
V expectedReference, V newReference, int expectedStamp, int newStamp) 比如：
Pair pair = new Pair(100, 200); int stamp = 1; AtomicStampedReference<Pair> pairRef = new AtomicStampedReference<Pair>(pair, stamp); int newStamp = 2; pairRef.compareAndSet(pair, new Pair(200, 200), stamp, newStamp);
AtomicStampedReference在compareAndSet中要同时修改两个值，一个是引用，另一个是时间戳，它怎么实现原子性呢？实际上，内部AtomicStampedReference会将两个值组合为一个对象，修改的是一个值，我们看代码：
public boolean compareAndSet(V expectedReference,
V newReference,
int expectedStamp,
int newStamp) {
Pair<V> current = pair;
return
expectedReference == current.reference &&
expectedStamp == current.stamp &&
((newReference == current.reference &&
newStamp == current.stamp) ||
casPair(current, Pair.of(newReference, newStamp)));
} 这个Pair是AtomicStampedReference的一个内部类，成员包括引用和时间戳，具体定义为：
private static class Pair<T> {
final T reference;
final int stamp;
private Pair(T reference, int stamp) {
this.reference = reference;
this.stamp = stamp;
}
static <T> Pair<T> of(T reference, int stamp) {
return new Pair<T>(reference, stamp);
}
} AtomicStampedReference将对引用值和时间戳的组合比较和修改转换为了对这个内部类Pair单个值的比较和修改。
AtomicMarkableReference是另一个AtomicReference的增强类，与AtomicStampedReference类似，它也是给引用关联了一个字段，只是这次是一个boolean类型的标志位，只有引用值和标志位都相同的情况下才进行修改。
小结
本节介绍了各种原子变量的用法以及背后的原理CAS，对于并发环境中的计数、产生序列号等需求，考虑使用原子变量而非锁，CAS是Java并发包的基础，基于它可以实现高效的、乐观、非阻塞式数据结构和算法，它也是并发包中锁、同步工具和各种容器的基础。
下一节，我们讨论并发包中的显式锁。
(与其他章节一样，本节所有代码位于 https://github.com/swiftma/program-logic)
----------------
未完待续，查看最新文章，敬请关注微信公众号“老马说编程”(扫描下方二维码)，从入门到高级，深入浅出，老马和你一起探索Java编程及计算机技术的本质。用心原创，保留所有版权。
