Java并发编程之原子变量和CAS算法
一、简介
原子变量最主要的一个特点就是所有的操作都是原子的，synchronized关键字也可以做到对变量的原子操作。只是synchronized的成本相对较高，需要获取锁对象，释放锁对象，如果不能获取到锁，还需要阻塞在阻塞队列上进行等待。而如果单单只是为了解决对变量的原子操作，建议使用原子变量。关于原子变量的介绍，主要涉及以下内容：
- 原子变量的基本概念
- 通过AtomicInteger了解原子变量的基本使用
- 通过AtomicInteger了解原子变量的基本原理
- AtomicReference的基本使用
- 使用FieldUpdater操作非原子变量的字段属性
- 经典的ABA问题的解决
一、原子变量的基本概念
原子变量保证了该变量的所有操作都是原子的，不会因为多线程的同时访问而导致脏数据的读取问题。我们先看一段synchronized关键字保证变量原子性的代码：
public class Counter {
private int count;
public synchronized void addCount(){
this.count++;
}
}
简单的count++操作，线程对象首先需要获取到Counter 类实例的对象锁，然后完成自增操作，最后释放对象锁。整个过程中，无论是获取锁还是释放锁都是相当消耗成本的，一旦不能获取到锁，还需要阻塞当前线程等等。
对于这种情况，我们可以将count变量声明成原子变量，那么对于count的自增操作都可以以原子的方式进行，就不存在脏数据的读取了。Java给我们提供了以下几种原子类型：
AtomicInteger和AtomicIntegerArray：基于Integer类型
AtomicBoolean：基于Boolean类型
AtomicLong和AtomicLongArray：基于Long类型
AtomicReference和AtomicReferenceArray：基于引用类型
在本文的余下内容中，我们将主要介绍AtomicInteger和AtomicReference两种类型，AtomicBoolean和AtomicLong的使用和内部实现原理几乎和AtomicInteger一样。
二、AtomicInteger的基本使用
首先看它的两个构造函数：
private volatile int value;
public AtomicInteger(int initialValue) {
value = initialValue;
}
public AtomicInteger() {}
可以看到，我们在通过构造函数构造AtomicInteger原子变量的时候，如果指定一个int的参数，那么该原子变量的值就会被赋值，否则就是默认的数值0。
也有获取和设置这个value值的方法：
public final int get()
public final void set(int newValue)
当然，这两个方法并不是原子的，所以一般也很少使用，而以下的这些基于原子操作的方法则相对使用的频繁，至于它们的具体实现是怎样的，我们将在本文的后续小节中进行简单的学习。
//基于原子操作，获取当前原子变量中的值并为其设置新值
public final int getAndSet(int newValue)
//基于原子操作，比较当前的value是否等于expect，如果是设置为update并返回true，否则返回false
public final boolean compareAndSet(int expect, int update)
//基于原子操作，获取当前的value值并自增一
public final int getAndIncrement()
//基于原子操作，获取当前的value值并自减一
public final int getAndDecrement()
//基于原子操作，获取当前的value值并为value加上delta
public final int getAndAdd(int delta)
下面我们实现一个计数器的例子，之前我们使用synchronized实现过，现在我们使用原子变量再次实现该问题。
//自定义一个线程类
public class MyThread extends Thread {
public static AtomicInteger value = new AtomicInteger();
@Override
public void run(){
try {
Thread.sleep((long) ((Math.random())*100));
//原子自增
value.incrementAndGet();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
//main函数中启动100条线程并让他们启动
public static void main(String[] args) throws InterruptedException {
Thread[] threads = new Thread[100];
for (int i=0;i<100;i++){
threads[i] = new MyThread();
threads[i].start();
}
for (int j=0;j<100;j++){
threads[j].join();
}
System.out.println("value:"+MyThread.value);
}
多次运行会得到相同的结果：
很显然，使用原子变量要比使用synchronized要简洁的多并且效率也相对较高。
三、AtomicInteger的内部基本原理
AtomicInteger的实现原理有点像我们的包装类，内部主要操作的是value字段，这个字段保存就是原子变量的数值。value字段定义如下：
private volatile int value;
首先value字段被volatile修饰，即不存在内存可见性问题。由于其内部实现原子操作的代码几乎类似，我们主要学习下incrementAndGet方法的实现。
在揭露该方法的实现原理之前，我们先看另一个方法：
public final boolean compareAndSet(int expect, int update{
return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}
compareAndSet方法又被称为CAS，该方法调用unsafe的一个compareAndSwapInt方法，这个方法是native，我们看不到源码，但是我们需要知道该方法完成的一个目标：比较当前原子变量的值是否等于expect (原来数据)，如果是则将其修改为update（修改后数据）并返回true，否则直接返回false。当然，这个操作本身就是原子的，较为底层的实现。
public final int incrementAndGet() {
return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}
方法体是一个死循环，current获取到当前原子变量中的值，由于value被修饰volatile，所以不存在内存可见性问题，数据一定是最新的。然后current加一后赋值给next，调用我们的CAS原子操作判断value是否被别的线程修改过，如果还是原来的值，那么将next的值赋值给value并返回next，否则重新获取当前value的值，再次进行判断，直到操作完成。
incrementAndGet方法的一个很核心的思想是，在加一之前先去看看value的值是多少，真正加的时候再去看一下，如果发现变了，不操作数据，否则为value加一。
但是在jdk1.8以后，做了一些优化，但是最后还是调用的compareAndSwapInt方法。但基本思想还是没变。
四、AtomicReference的基本使用
对于一些自定义类或者字符串等这些引用类型，Java并发包也提供了原子变量的接口支持。AtomicReference内部使用泛型来实现的。
private volatile V value;
public AtomicReference(V initialValue) {
value = initialValue;
}
public AtomicReference() {}
有关其他的一些原子方法如下：
//获取并设置value的值为newvalue
public final V getAndSet(V newValue) {
return (V)unsafe.getAndSetObject(this, valueOffset, newValue);
}
AtomicReference中少了一些自增自减的操作，但是对于value的修改依然是原子的。
五、使用FieldUpdater操作非原子变量的字段属性
FieldUpdater允许我们不必将字段设置为原子变量，利用反射直接以原子方式操作字段。例如：
//定义一个计数器public class Counter {
private volatile int count;
public int getCount() {
return count;
}
public void addCount(){
AtomicIntegerFieldUpdater<Counter> updater = AtomicIntegerFieldUpdater.newUpdater(Counter.class,"count");
updater.getAndIncrement(this);
}
}
然后我们创建一百个线程随机调用同一个Counter对象的addCount方法，无论运行多少次，结果都是一百。这种方式实现的原子操作，对于被操作的变量不需要被包装成原子变量，但是却可以直接以原子方式操作它的数值。
六、CAS算法
CAS（compare and swap, 比较并交换），是原子操作的一种，可用于在多线程编程中实现不被打断的数据交换操作，从而避免多线程同时改写某一数据时由于执行顺序不确定性以及中断的不可预知性产生的数据不一致问题。 是一种无锁的非阻塞算法的实现。
简单来说，CAS可以保证多线程对数据写操作时数据的一致性。
CAS的思想：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。 这是一种乐观锁的思路，它相信在它修改之前，没有其它线程去修改它。
模拟代码：
/**
* 默认CAS
*/
public class CompareAndSwap {
// 内存值
private volatile int value = 0;
// 返回内存值
public synchronized int getValue() {
return value;
}
/**
* 如果预估值与原来的值一样，则修改内存为新的值，否则，不做处理。 无论是否修改，都返回原来的内存值。
**/
public synchronized int compareAndSwap(int expectedValue, int newValue) {
int oldValue = value;
System.out.println("old:" + oldValue + ",expectedValue:" + expectedValue + ",newValue:" + newValue);
if (expectedValue == oldValue) {
value = newValue;
}
return oldValue;
}
// 如果更新成功，新的內存值和預估值相等。
public synchronized boolean compareAndSet(int expectedValue, int newValue) {
return expectedValue == compareAndSwap(expectedValue, newValue);
}
}
//测试CAS算法
@Test
public void TestCompareAndSwap(){
final CompareAndSwap cas = new CompareAndSwap();
for (int i = 0; i < 10; i++) {
new Thread(new Runnable() {
public void run() {
int expectedValue = cas.getValue();
boolean b = cas.compareAndSet(expectedValue, new Random().nextInt());
System.err.println(">>>>>>" + b);
}
}).start();
}
}
输出结果：
七、CAS的缺点
CAS虽然很高效的解决了原子操作问题，但是它还是存在三个缺点：
1. 循环时间长开销很大。 我们可以看到getAndAddInt方法执行时，如果CAS失败，会一直进行尝试。如果CAS长时间一直不成功，可能会给CPU带来很大的开销
2. 只能保证一个共享变量的原子操作。 当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作，但是对多个共享变量操作时，循环CAS就无法保证操作的原子性，这个时候就可以用锁来保证原子性。
3. ABA问题。
八、经典的ABA问题
我们的原子变量都依赖一个核心的方法，那就是CAS。这个方法最核心的思想就是，更改变量值之前先获取该变量当前最新的值，然后在实际更改的时候再次获取该变量的值，如果没有被修改，那么进行更改，否则循环上述操作直至更改操作完成。假如一个线程想要对变量count进行修改，实际操作之前获取count的值为A，此时来了一个线程将count值修改为B，又来一个线程获取count的值为B并将count修改为A，此时第一个线程全然不知道count的值已经被修改两次了，虽然值还是A，但是实际上数据已经是脏的。
这就是典型的ABA问题，一个解决办法是，对count的每次操作都记录下当前的一个时间戳，这样当我们原子操作count之前，不仅查看count的最新数值，还记录下该count的时间戳，在实际操作的时候，只有在count的数值和时间戳都没有被更改的情况之下才完成修改操作。
public static void main(String[] args){
int count=0;
int stamp = 1;
AtomicStampedReference reference = new AtomicStampedReference(count,stamp);
int next = count++;
reference.compareAndSet(count, next, stamp, stamp);
}
AtomicStampedReference 的CAS方法要求传入四个参数，该方法的内部会同时比较count和stamp，只有这两个值都没有发生改变的前提下，CAS才会修改count的值。
上述我们介绍了有关原子变量的最基本内容，最后我们比较下原子变量和synchronized关键字的区别。
从思维模式上看，原子变量代表一种乐观的非阻塞式思维，它假定没有别人会和我同时操作某个变量，于是在实际修改变量的值的之前不会锁定该变量，但是修改变量的时候是使用CAS进行的，一旦发现冲突，继续尝试直到成功修改该变量。
而synchronized关键字则是一种悲观的阻塞式思维，它认为所有人都会和我同时来操作某个变量，于是在将要操作该变量之前会加锁来锁定该变量，进而继续操作该变量。
下一篇： Linux内核mmap机制