转载

死磕java concurrent包系列（一）从乐观锁、悲观锁到AtomicInteger的CAS算法

前言

Java中有各式各样的锁，主流的锁和概念如下：

这篇文章主要是为了让大家通过乐观锁和悲观锁出发，理解CAS算法，因为CAS是整个Concurrent包的基础。

乐观锁和悲观锁

首先，java和数据库中都有这种概念，他是一种从线程同步的角度上看的一种广义上的概念：

悲观锁：悲观的认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改。Java中，synchronized关键字和Lock的实现类都是悲观锁。

乐观锁：乐观的认为自己在使用数据时不会有别的线程修改数据，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作（例如报错或者自动重试）。

根据从上面的概念描述我们可以发现：

悲观锁适合写操作多的场景 ，先加锁可以保证写操作时数据正确。
乐观锁适合读操作多的场景 ，不加锁的特点能够使其读操作的性能大幅提升。

从代码层面理解：

悲观锁：

// ------------------------- 悲观锁的调用方式 -------------------------
// synchronized
public synchronized void testMethod() {
    // 操作同步资源
}
// ReentrantLock
private ReentrantLock lock = new ReentrantLock(); // 需要保证多个线程使用的是同一个锁
public void modifyPublicResources() {
    lock.lock();
    // 操作同步资源
    lock.unlock();
}复制代码

乐观锁：

// ------------------------- 乐观锁的调用方式 -------------------------
private AtomicInteger atomicInteger = new AtomicInteger();  // 需要保证多个线程使用的是同一个AtomicInteger
atomicInteger.incrementAndGet(); //执行自增1复制代码

悲观锁基本上比较好理解：就是在显示的锁定资源后再操作同步资源。

那么问题来了：

为什么乐观锁不锁定资源也可以实现线程同步呢？

答案是 CAS

CAS

CAS全称 Compare And Swap（比较与交换），是一种无锁算法：就是在没有锁的情况下实现同步。

CAS相关的三个操作数：

需要读写的内存值 V。
需要进行比较的值 A。
要写入的新值 B。

当且仅当 V 的值等于 A 时，CAS通过原子方式用新值B来更新V的值（“比较+更新”整体是一个原子操作），否则不会执行任何操作。一般情况下，“更新”是一个不断重试的操作。

先看一下基本的定义：

什么是unsafe呢？Java语言不像C，C++那样可以直接访问底层操作系统，但是JVM为我们提供了一个后门，这个后门就是unsafe。unsafe为我们提供了 硬件级别的原子操作 。

至于valueOffset对象，是通过unsafe.objectFieldOffset方法得到，所代表的是 AtomicInteger对象value成员变量在内存中的偏移量 。我们可以简单地把valueOffset理解为value变量的内存地址。

死磕java concurrent包系列（一）从乐观锁、悲观锁到AtomicInteger的CAS算法

接下来看incrementAndGet：

// ------------------------- JDK 8 -------------------------
// AtomicInteger 自增方法
public final int incrementAndGet() {
  return unsafe.getAndAddInt(this, valueOffset, 1) + 1;
}

// Unsafe.class
public final int getAndAddInt(Object var1, long var2, int var4) {
  int var5;
  do {
      var5 = this.getIntVolatile(var1, var2);
  } while(!this.compareAndSwapInt(var1, var2, var5, var5 + var4));
  return var5;
}复制代码

getAndAddInt方法的入参：var1是aotmicInteger对象，var2是valueOffset，var4是1；它本质上在循环获取对象aotmicInteger中的偏移量（即valueoffset）处的值var5，然后判断内存的值是否等于var5；如果相等则将内存的值设置为var5+1；否则继续循环重试，直到设置成功时再推出循环。

CAS操作封装在 compareAndSwapInt 方法内部，在JNI里是借助于一个CPU指令完成的，属于原子操作，可以保证多个线程都能够看到同一个变量的修改值。后续JDK通过CPU的cmpxchg指令，去比较寄存器中的 A 和内存中的值 V。如果相等，就把要写入的新值 B 存入内存中。如果不相等，就将内存值 V 赋值给寄存器中的值 A。然后通过Java代码中的while循环再次调用cmpxchg指令进行重试，直到设置成功为止。

这里native方法比较多，如果觉得不太好理解，我们可以通俗的总结一下：

循环体当中做了三件事：

1.获取当前值。（通过volatile关键字保证可见性）

2.计算出目标值：本例子中为当前值+1

3.进行CAS操作，如果成功则跳出循环，如果失败则重复上述步骤。

CAS的问题

ABA问题

什么是ABA呢？

因为CAS中的当前值和目标值都是随机的，假设内存中有一个值为A的变量，存储在地址V当中：

内存地址V→A

此时有三个线程想使用CAS的方式更新这个变量值，每个线程的执行时间有略微的偏差。线程1和线程2已经获得当前值，线程3还未获得当前值。

线程1：获取到了A，计算目标值，期望更新为B

线程2：获取到了A，计算目标值，期望更新为B

线程3：还没有获取到当前值

接下来，线程1先一步执行成功，把当前值成功从A更新为B；同时线程2因为某种原因被阻塞住，没有做更新操作；线程3在线程1更新之后，获得了当前值B。

内存地址V→B

线程1：获取到了A， 成功更新为B

线程2：获取到了A，计算目标值，期望更新为B， Block

线程3： 获取当前值B ，计算目标值，期望更新为A

线程2仍然处于阻塞状态，线程3继续执行，成功把当前值从B更新成了A。

内存地址V→A

线程1：获取到了A，成功更新为B，已返回

线程2：获取到了A，计算目标值，期望更新为B， Block

线程3：获取当前值B， 成功更新为A

最后，线程2终于恢复了运行状态，由于阻塞之前已经获得了“当前值”A，并且经过compare检测，内存地址V中的实际值也是A，所以成功把变量值A更新成了B。

内存地址V→B

线程1：获取到了A，成功更新为B，已返回

线程2：获取到了“当前值”A，成功更新为B

线程3：获取当前值B，成功更新为A，已返回

这个过程中，线程2获取到的变量值A是一个旧值，尽管和当前的实际值相同，但内存地址V中的变量已经经历了A->B->A的改变。

可这样的话看起来好像也没毛病。

接下来我们来结合实际的场景分析它：

我们假设有一个CAS原理的ATM，小明有100元存款，要取钱50元。

由于提款机硬件出了点小问题，提款操作被同时提交两次，两个线程都是获取当前值100元，要更新成50元。理想情况下，应该一个线程更新成功，另一个线程更新失败，小明的存款只被扣一次。

存款余额：100元

ATM线程1：获取当前值100，期望更新为50

ATM线程2：获取当前值100，期望更新为50

线程1首先执行成功，把余额从100改成50。线程2因为某种原因阻塞了。 这时候，他的妈妈刚好给小明汇款50元 。

存款余额：50元

ATM线程1：获取当前值100，成功更新为50

ATM线程2：获取当前值100，期望更新为50，Block

线程3（他妈来存钱了）：获取当前值50，期望更新为100

线程2仍然是阻塞状态，线程3执行成功，把余额从50改成100。

存款余额：100元

ATM线程1：获取当前值100，成功更新为50，已返回

ATM线程2：获取当前值100，期望更新为50，Block

线程3（他妈来存钱了）：获取当前值50，成功更新为100

线程2恢复运行，由于阻塞之前已经获得了“当前值”100，并且经过compare检测，此时存款实际值也是100，所以成功把变量值100更新成了50。

存款余额：50元

ATM线程1：获取当前值100，成功更新为50，已返回

ATM线程2：获取“当前值”100，成功更新为50

线程3（他妈来存钱了）：获取当前值50，成功更新为100，已返回

这下问题就来了，小明的50元钱白白没有了，原本线程2应当提交失败，小灰的正确余额应该保持为100元，结果由于ABA问题提交成功了。

如何解决ABA问题呢

思路和乐观锁差不多，采用版本号就行了，在compare阶段不仅要比较期望值A和地址V中的实际值，还要比较版本号是否一致。

我们仍然以最初的例子来说明一下，假设地址V中存储着变量值A，当前版本号是01。线程1获得了当前值A和版本号01，想要更新为B，但是被阻塞了。

版本号01：内存地址V→A

线程1：获取当前值A，版本号01，期望更新为B

这时候发生ABA问题，内存中的值发生了多次改变，最后仍然是A，版本号提升为03

版本号03：内存地址V→A

线程1：获取当前值A，版本号01，期望更新为B

随后线程1恢复运行，发现版本号不相等，所以更新失败。

具体的可以参考java中的 AtomicStampedReference它用版本号比较做了CAS机制。

总结

CAS原理差不多了，它虽然高效，但是有如下问题：

1、ABA问题，可以通过版本号解决

2、循环时间长，开销比较大：如果并发量相当高，CAS操作长时间不成功时，会导致其一直自旋，带来CPU消耗比较大

补充一下自旋锁和非自旋锁的概念：

死磕java concurrent包系列（一）从乐观锁、悲观锁到AtomicInteger的CAS算法

CAS作为concurrent包基础中的基础，在战胜并发编程的旅途中有着举足轻重的地位，接下来我们将基于CAS讲解，Concurrent包中最基础的组件，我们常用的ReetrantLock SemaPhore LinkedBlockingQueue ArrayBlockingQueue都是基于它实现的。它就是 AQS。

原文 https://juejin.im/post/5c021da16fb9a049e65ffcbf

正文到此结束