转载

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

前言

Java中有各式各样的锁,主流的锁和概念如下:

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

这篇文章主要是为了让大家通过乐观锁和悲观锁出发,理解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
正文到此结束
Loading...