CAS和原子操作

这节课继续从操作系统底层学习Java的并发编程。原子操作是整个并发体系的基石，锁和无锁设计，都需要原子操作。分布式一致性也需要原子操作。这节课就和大家一起把这部分知识弄清楚。

原子操作部分有不少的面试题，其中比较典型的如下：

竞争条件是怎么产生的？解决竞争条件有哪些方法？
原子操作是如何实现的？
Java的CAS是如何实现的？
CAS的ABA问题是怎么回事?
AtomicInterger类是如何实现的？
AtomicStampedReference解决什么问题？内部如何实现？

原子操作

原子（atomic）操作，就是操作不可分。什么操作不可再分呢？比如一个CPU指令，不存在执行了一半这种情况。

举例：请大家跟我思考一个问题： i++是不是一个原子操作。

i++ 是3个原子操作组合而成的：

读取i的值
计算i+1
写入新的值

像这样的操作，可以被打断，也可能只执行了一半。那么在并行环境中，可能会造成风险。

‌

竞争条件

接下来，我们说说具体的风险——竞争条件。竞争条件(race condition)，也叫做竞争灾难(race hazard)，是指，多个程序并发执行时，最终执行结果，受控于执行时的精准时序。

举个例子，比如两个线程并发执行 i++ 。那么可以有多种顺序，比如下面这个顺序，假设执行前 i=0 ：

线程1 ： 读取i的值
线程2 ： 读取i的值
线程1 ： 计算i+1，得到1
线程2 ： 计算i+1，得到1
线程1 ： 写入1
线程2 ： 写入1

虽然两个线程都执行了 i++ ，但是最终导致竞争条件，也就是结果i=1。为什么没有得到正确的结果？ —— 因为计算顺序不受控；也因为 i++ 不是一个原子操作。

如果 i++ 是一个原子操作，那么并发的话，就不会产生竞争条件。关键就是 i++ 还可以再分，它是3条原子操作——读、计算、写。

竞争条件是一件非常糟糕的事情，大家可以把上面的程序想象成两个自动提款机。如果用户同时操作两个自动提款机，可能用户的余额就会被算错。把上面的操作理解成商品的库存，那么同时操作减库存，就可能把库存算错。

上面两个线程发生竞争的区域（访问共享资源i )，我们称为临界区（critical section)。

解决竞争的办法

既然竞争条件有很多危害，那么如何解决竞争条件呢？还是以i++为例，可以有这样几类办法：

减少竞争：用ThreadLocal为每个线程创建一个变量 i 。相当于每个线程分别计算，最后才汇总。
想法把 i++ 实现成一个原子操作
不允许两个线程同时进入临界区——或者叫让临界区互斥(mutual exclusion)

减少竞争

ThreadLocal就是一个减少竞争的方案。比如说有300篇文章需要统计词频，我们开3个线程工作。如果用一个HashMap存储结果，会有竞争条件的问题。可以考虑用3个线程，并行工作。

Enter a caption for this image (optional)

每个线程拥有一个属于自己的HashMap<String, Integer>对象，用于数词频。当3个线程都完成后，利用Thread.join找一个同步点，在主线程将3个HashMap合并。

后面我们会学到，同步3个线程在一个同步点，这种设计叫做内存屏障（Barrier）。具体参考同步器部分的讲解。

很多情况，大家需要思考，我到底需不需要设计竞争？如果可以不竞争，当然更好。空间换时间，减少了很多操作负担。

‌

实现原子操作

‌

CAS(Compare And Swap 或者 Compare And Set）是一种常见的实现原子操作的方法，通常CAS操作CPU会在指令级别支持——其实就是由硬件直接将CAS实现为一个CPU指令。

CAS的目标是设置某个内存地址的值，简单理解就是设置某个变量的值。但是CAS要求指令的使用方必须知道这个地方原来的值。

举个例子：比如说小明的支付宝余额是10000元，某个时刻小明并发的买了两个东西，一个是1000元，一个2000元，假设服务端启动两个线程来处理这两笔扣款。假设每个线程，有两个原子操作：

读取余额
完成扣款

为了简化设计，我们假设余额，就是内存中的一个数字。这样可以帮我们省去讨论数据库的实现，让模型简化。

如果正常执行，会发生竞争条件：

线程1：读取余额(10000)
线程2：读取余额(10000)
线程1：设置余额=9000（扣1000款）
线程2：设置余额=8000（扣2000款）

这样，少扣了小明1000的余额。如果是CAS，那么CAS要求线程知道当前的余额，我们来看下CAS操作：

线程1：读取余额(10000)
线程2：读取余额(10000)
线程1： cas扣款(当前=10000，目标=9000)，得到9000
线程2： cas扣款(当前=10000, 目标=8000）,当前余额和期望不符（内存中的余额已经被更新成了9000），拒绝这笔交易。

CAS可以用下面这个函数表示:

cas(&oldValue, expectedValue, targetValue)

这里我用的是伪代码，我们用 & 符号代表这里取内存地址。注意CAS是CPU提供的原子操作。因此上面的比较和设置值的过程，是原子的，也就是不可中断，不会执行一半。

比如想用cas更新 i 的值，而且知道 i 是100，想更新成 101 。那么就可以这样做:

cas(&i, 100, 101)

如果在这个过程中，有其他线程把 i 更新为 101 ，这次调用会返回false，否则返回true。

所以 i++ 程序可以等价的修改为:

// i++等价程序
cas(&i, i, i+1)

上面程序执行时，其实是3条指令：

读取i 
计算i+1
CAS操作：比较i和i'的值是否相等，如果是，更新目标值

上面的变量 i 只读取了一次，可以看做编译器的优化，否则应该读取两次。

假设 i=0 ，考虑两个线程分别执行一次这个程序，尝试构造竞争条件:

线程1 ： 读取i
线程2 ： 读取i
线程1 ： 计算i+1，得到1
线程2 ： 计算i+1, 得到1
线程1 ： cas(&i, 0, 1)，成功，i=1
线程2 ： cas(&i, 0, 1), 失败，返回false

大家可以看到通过这种方式，cas解决了一部分问题，cas找到了竞争条件，并返回了false。但是还是无法计算出正确的结果。

如果要完全解可以考虑这样去实现：

while(!cas(&i, i, i+1)){
  // 什么都不做
}

这样如果cas返回false，那么会尝试再读一次i的值，直到cas成功。

TAS指令

Test-And-Set也是CPU提供的一种指令。当然通常CPU不会同时提供CAS和TAS。TAS可以看做一个CAS的特例。通常服务器CPU都提供了CAS。还有一个方案是TAS指令，有的CPU没有提供CAS(大部分服务器是提供的），提供一种Test-And-Set指令(TAS)。TAS指令的目标是设置一个内存地址的值为1，它的工作原理和CAS相似。它首先比较内存地址的数据和1的值，如果内存地址是0，那么把这个地址置1。如果是1，那么失败。

所以TAS可以看做一个特殊版的 cas ，可以这样来理解：

tas(&lock) {
  return cas(&lock, 0, 1)
}

互斥

还有一类方法，俗称为锁(lock)。锁的目标是帮助线程实现在临界区互斥，一个线程进入临界区前，把临界区上锁，这样其他线程就无法进入临界区了。复习下，临界区是访问共享资源的程序，在临界区可能会发生竞争条件。

互斥，就是让最多只有一个线程可以进入临界区——也就是执行临界区的程序。当临界区使用完毕，这个线程再把临界区解锁。通过这种方式，我们实现了临界区的互斥（Mutual Exclusion)。

锁可以用 tas 或者 cas 来实现。‌

下面 i++ 代码是临界区，我们通过 enter 和 leave 为临界区上锁。Java的锁更复杂一些，我们将在后面的课程讨论。

enter();
i++;
leave();

可以考虑用 cas 实现 enter 和 leave 函数。下面是一种可能的实现的伪代码：

int lock = 0;
enter(){  
  while( !cas(&lock, 0, 1) ) { // 什么也不做  }
}

leave(){  
  lock = 0;
}

&符号是取地址，如果在Java中想要操作地址，反射的性能是不够的，需要用到一个非常底层的库叫做UnSafe。有关UnSafe，我们后面介绍。

多个线程竞争一个整数的lock变量，0代表目前没有线程进入临界区，1代表目前有线程进入临界区。利用 cas 原子指令我们可以对临界区进行管理。如果一个线程利用cas将lock设置为1，那么另一个线程就会一直执行 cas 操作，直到锁被释放。

Java的CAS

Java有一个底层类，叫做UnSafe——jdk.internal.misc.Unsafe。这个类提供很多底层操作，比如 cas 。Java的CAS能力原子UnSafe提供的一系列CAS函数，具体大家可以参考UnSafe的代码，这个类几乎没有文档，只有一篇Blog：http://mishadoff.github.io/blog/java-magic-part-4-sun-dot-misc-dot-unsafe/。

从源码中我们可以看到很多cas相关的函数，具体这些函数大家平时用不到，面试官也不会细问区别，感兴趣可以深入了解。

Java的CAS能力不是Java语言实现的，而是由底层的c++语言实现的。c++语言实现的cas能力，也不一定能够完全映射到一个CPU指令。在x68/x64的机器上（绝大多数服务器）上，有对应的指令叫做CMPXCHG。在ARM机器上（Android）等，有时候找不到完全对应的指令，需要程序实现。具体这里不展开了，所以大多数服务端朋友可以认为Java 提供的CAS可以直接对应到一条CPU指令。

CAS的ABA问题

CAS有个ABA的问题。‌CAS是基于操作方对数据的的理解（操作方必须知道数据是多少）来进行控制的。‌

因此会产生ABA问题的演示：

value=A

// Thread1
cas(&value, A, B);

// Thread2
cas(&value, A, B);
cas(&value, B, A)

线程1想把value从A更新为B。线程2连续使用cas操作把value从A更新到B，然后更新为A。当线程1读取了A的值后，假设线程2开始执行，将value从A更新到B，再回到A。最终，线程1将value更新到B。

从结果看，没有问题，value经历了A->B->A->B的更新过程。但是从安全角度，这样不可能控，因为线程A傻傻的以为值没有被更新过。‌

这里有一些哲学问题，比如：朋友钱包的钱，我偷偷拿走了100，晚上再趁朋友没注意放100到里面，算不算偷窃？

举例子：ABA造成库存算错

假设你想设计一个幂等的库存服务，现在有人并发调用了两次你的服务，想把库存从100减少到99。你用两个线程承接这个调用，并用cas更新库存，会发生什么情况？

// Thread 1 ： 成功 
cas(&库存, 100, 99);

// Thread 2: 失败
cas(&库存, 100, 99)

从上面结果看，没有问题，因为第二次失败了。即便第二次成功，问题也不大，服务实现了幂等。但是如果，有第三个线程在1,2之间增加了库存会发生什么？

Thread 1： 读取库存， 100
Thread 1:  计算接下来的库存 99
Thread 2： 读取库存， 100
Thread 2: 计算接下来的库存 99
Thread 1： cas,更新库存 -> 99
Thread 3:  读取库存 -> 99
Thread 3： 计算库存 -> 100(增加库存)
Thread 3:  cas更新库存 -> 100
Thread 2:  cas更新库存 -> 99

本来Thread2 应该会失败的，经过图中的顺序，Thread2成功了，最终把库存改为了99。这样服务的幂等性就失效了。本来期望无论调用多少次修改库存100->99，期望结果都是99。但是在增加了库存的基础上，最后结果应该是100才对，结果还是99。

想解决这个问题以考虑为库存增加一个版本。线程1修改后，版本是1。线程3修改后，版本是2。线程2发现版本已经前进了好几个，就主动放弃这次更新操作。

举例子：栈的更新问题

再举一个例子，这个例子对于并发数据结构开发非常有帮助。假设用链表实现一个支持并发的栈，那么可以考虑用cas操作实现链表的操作。

push(node){  
  // 这句没有并发风险  
  node.next = list.head;    
  // 将head指向node  
  while(!cas(&list.head, list.head, node)){}
}

pop(node){  
   // 这三句没有竞争条件  
   ListNode current = list.head;  
   if(current == null) {return null;}    
   // 尝试用cas操作将head指向next
   // 相当于删除了头部节点
   while(!cas(&list.head, list.head, list.head.next)){}  
   return current;
}

上面的push方法在链表头部增加一个节点。 pop方法去掉头部的节点。‌

假设现在链表中是：head->A->B->C。

线程1执行操作 pop() ，期望链表之后变成 head->B->C 。

线程2执行两次pop操作，再push(A)，期望链表之后变成 head->A->C 。

考虑这样的执行顺序:

// Thread1执行pop被中断
ListNode current = list.head;  // 得到节点：A
if(current == null) {
  return null;
}

执行CAS操作前读取: list.head.next-> (实际是B)
中断

// Thread2 开始执行
pop();
pop();
push(A);

// Thread 1 继续执行
while(!cas(&list.head, list.head, list.head.next)){

当Thread2执行结束后，链表是 head->A-C ，因为链表的head依然指向A。因此pop操作中的 cas 对比成功，可以执行。但是线程A中的 list.head.next 实际是B。这样，经过线程1更新完结果是 head->B->…… ，这样被删除的节点B又回来了。

Java中Atomic操作

Java中的Atomic操作就是基于CAS实现的，比如说AtomicInteger的写入就需要CAS操作。AtomicInteger内部需要维护一个状态，实际的程序AtomicInteger内部有一个value 变量。关于volatile，大家可以参考4.7 内存一致性模型——volatile和happens-before关系。

private volatile int value;
public final int get() {
    return value;
}
public final void set(int newValue) {
    value = newValue;
}

上面get set 都是简单的原子操作，故不需要cas 。但是AtomicInteger提供的自增方法，就不是简单的原子操作了，因此需要用到cas 保证原子性。

下图截取了AtomicInteger底层调用Unsafe的将值自增1的方法。实际上是利用do-while 循环不停执行cas操作。

 public final int getAndAddInt(Object o, long offset, int delta) {
        int v;
        do {
            v = getIntVolatile(o, offset);
        } while (!weakCompareAndSetInt(o, offset, v, v + delta));
        return v;
    }
}

另外，为了让大家方便的使用AtomicInteger去进行原子更新，AtomicInteger也封装了cas操作：

public final boolean compareAndSet(int expectedValue, int newValue) {
    return U.compareAndSetInt(this, VALUE, expectedValue, newValue);
}

下面这4个原子操作类，基本实现一直，只不过其中的value 类型不同，接口和能力大同小异：

AtomicBoolean
AtomicInteger
AtomicLong
AtomicReference

Java ABA问题的方案

为了解决ABA问题，Java还提供了2个类。

AtomicMarkableReference
AtomicStampedReference

解决ABA问题最核心的就是要进行版本控制。让此A非彼A。

比如增加版本号：A(版本0)， B(版本1)， C(版本2)。像这种情况，有自增的版本，自然就不会有任何疑问。下面就是一个每次版本+1的cas操作，这种我们也称为乐观锁。有关乐观锁，我们会在后续章节讨论。

while(cas(&version, version, version + 1) ) {
}

对于ABA问题，就是要让cas 不仅仅只判断数据本身，更新方还必须知道当前版本号是多少。版本号，最简单的就是用boolean。比如：A(版本 false) B（版本false）A（版本true)——想办法让A和A的版本有差异。因为(值,版本)，构成了一对Pair，因此Java中使用了一个内部类Pair来完成这个工作：

public boolean compareAndSet(V expectedReference,
                   V  newReference,
                    boolean expectedMark,
                    boolean newMark) {
    Pair<V> current = pair;
    return
        expectedReference == current.reference &&
        expectedMark == current.mark &&
        ((newReference == current.reference &&
          newMark == current.mark) ||
         casPair(current, Pair.of(newReference, newMark)));
}

图中代码取自AtomicMarkableReference ,它使用了casPair 直接将(值，版本)作为一个整体更新。AtomicStampedReference 的方法类似，只不过它的版本是整数。

总结

这节课我们学习了原子操作（包括CAS）。CAS是一个原子操作，有点像乐观锁。CAS要求使用方必须知道原来的值，才能更新值。如果使用方不知道原来的值，使用方就会被拒绝更新。当然，使用方可以选择再进行一次读取，保持和最新版本的值的一致。这种设计巧妙的解决了我们需要的原子操作，在这个基础上Java提供了大量的原子操作，内部实现都大同小异。就是采用CAS进行更新，因此不再一一介绍了。

CAS和原子操作 ​

原子操作 ​

竞争条件 ​

解决竞争的办法 ​

减少竞争 ​

实现原子操作 ​

TAS指令 ​

互斥 ​

Java的CAS ​

CAS的ABA问题 ​

Java中Atomic操作 ​

Java ABA问题的方案 ​

总结 ​