Java多线程系列（三）---CAS

发表于 | 分类于

CAS（Compare and swap或者CompareAndSet）比较和替换是设计并发算法时用到的一种技术。简单来说，比较和替换是使用一个期望值和一个变量的当前值进行比较，如果当前变量的值与我们期望的值相等，就使用一个新值替换当前变量的值。这听起来可能有一点复杂但是实际上你理解之后发现很简单，接下来，让我们跟深入的了解一下这项技术。

CAS的使用场景

在程序和算法中一个经常出现的模式就是“check and act”模式。先检查后操作模式发生在代码中首先检查一个变量的值，然后再基于这个值做一些操作。下面是一个简单的示例：

1
2
3
4
5
6
7
8
9
10
11
12
class MyLock {

    private boolean locked = false;

    public boolean lock() {
        if(!locked) {
            locked = true;
            return true;
        }
        return false;
    }
}

上面这段代码，如果用在多线程的程序会出现很多错误，不过现在请忘掉它。

如你所见，lock()方法首先检查 locked成员变量是否等于 false，如果等于，就将 locked 设为 true。

如果同个线程访问同一个 MyLock 实例，上面的 lock()将不能保证正常工作。如果一个线程检查 locked 的值，然后将其设置为 false，与此同时，一个线程 B 也在检查 locked 的值，又或者，在线程 A 将 locked 的值设为 false 之前。因此，线程 A 和线程 B 可能都看到 locked 的值为 false，然后两者都基于这个信息做一些操作。

为了在一个多线程程序中良好的工作，”check then act” 操作必须是原子的。原子就是说”check“操作和”act“被当做一个原子代码块执行。不存在多个线程同时执行原子块。

下面是一个代码示例，把之前的 lock()方法用 synchronized 关键字重构成一个原子块。

1
2
3
4
5
6
7
8
9
10
11
12
class MyLock {

    private boolean locked = false;

    public synchronized boolean lock() {
        if(!locked) {
            locked = true;
            return true;
        }
        return false;
    }
}

现在 lock()方法是同步的，所以，在某一时刻只能有一个线程在同一个 MyLock 实例上执行它。

原子的 lock 方法实际上是一个”compare and swap“的例子。

原子类的实现

Java提供的原子类是靠 sun 基于 CAS 实现的，CAS 是一种乐观锁。

原子变量类相当于一种泛化的 volatile 变量，能够支持原子的和有条件的读-改-写操作。AtomicInteger 表示一个int类型的值，并提供了 get 和 set 方法，这些 Volatile 类型的int变量在读取和写入上有着相同的内存语义。它还提供了一个原子的 compareAndSet 方法（如果该方法成功执行，那么将实现与读取/写入一个 volatile 变量相同的内存效果），以及原子的添加、递增和递减等方法。AtomicInteger 表面上非常像一个扩展的 Counter 类，但在发生竞争的情况下能提供更高的可伸缩性，因为它直接利用了硬件对并发的支持。

AtomicInteger的实现

AtomicInteger 是一个支持原子操作的 Integer 类，就是保证对 AtomicInteger 类型变量的增加和减少操作是原子性的，不会出现多个线程下的数据不一致问题。如果不使用 AtomicInteger，要实现一个按顺序获取的 ID，就必须在每次获取时进行加锁操作，以避免出现并发时获取到同样的 ID 的现象。

AtomicInteger的使用方法是简单直接的，它的主要内部成员是：
private volatile int value;
注意：它的声明带有volatile，这是必须的，以保证内存可见性。

它的大部分更新方法实现都是类似，我们看一下方法incrementAndGet，代码为：

1
2
3
4
5
6
7
8
public final int incrementAndGet() {
        for (;;) {
            int current = get();
            int next = current + 1;
            if (compareAndSet(current, next))
                return next;
        }
 }

解释一下：代码的主体是个死循环，先获取当前值current，计算期望的值next，然后调用CAS方法进行更新，如果更新没有成功，说明value被别的线程改了，则再去取最新值并尝试更新直到成功为止。

synchronized是悲观的，CAS是乐观的；synchronized是一种阻塞式算法，CAS非阻塞方法。

我们来看一下compareAndSet是怎么实现的：

1
2
3
public final boolean compareAndSet(int expect, int update) {
        return unsafe.compareAndSwapInt(this, valueOffset, expect, update);
}

compareAndSet()方法调用的compareAndSwapInt()方法的声明如下，是一个native方法。

1
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, intvar5);

compareAndSet 传入的为执行方法时获取到的 value 属性值，next 为加 1 后的值， compareAndSet 所做的为调用 Sun 的 UnSafe 的 compareAndSwapInt 方法来完成，此方法为 native 方法，compareAndSwapInt 基于的是 CPU 的 CAS 指令来实现的。所以基于 CAS 的操作可认为是无阻塞的，一个线程的失败或挂起不会引起其它线程也失败或挂起。并且由于 CAS 操作是 CPU 原语，所以性能比较好。

ABA问题

使用CAS方式更新会有一个ABA问题。该问题是指：假设当前值为A，如果另一个线程先将A修改为B，再修改回成A，当前线程的CAS操作无法分辨当前值发生过变化。

解决方法是：使用AtomicStampedReference，在修改值的同时附加一个时间戳，只有时间戳和值都相同才进行修改。