难度

初级

学习时间

30分钟

适合人群

零基础

开发语言

Java

开发环境

• JDK v11
• IntelliJIDEA v2018.3

友情提示

• 本教学属于系列教学，内容具有连贯性，本章使用到的内容之前教学中都有详细讲解。
• 本章内容针对零基础或基础较差的同学比较友好，可能对于有基础的同学来说很简单，希望大家可以根据自己的实际情况选择继续看完或等待看下一篇文章。谢谢大家的谅解！

1.温故知新

前面在《“全栈2019”Java原子操作第九章：atomic包下原子数组介绍与使用》一章中介绍了什么是原子数组AtomicIntegerArray、AtomicLongArray和AtomicReferenceArray<E>。

在《“全栈2019”Java原子操作第十章：atomic包下字段原子更新器介绍》一章中介绍了什么是字段原子更新器AtomicIntegerFieldUpdater<T>、AtomicLongFieldUpdater<T>和AtomicReferenceFieldUpdater<T,?V>。

在《“全栈2019”Java原子操作第十一章：CAS与ABA问题介绍与探讨》一章中介绍了CAS算法中存在的ABA问题。

在《“全栈2019”Java原子操作第十二章：AtomicStampedReference详解》一章中介绍了什么是带版本号的原子类AtomicStampedReference<V>。

在《“全栈2019”Java原子操作第十三章：AtomicMarkableReference类》一章中介绍了什么是带修改标记的原子类AtomicMarkableReference<V>。

在《“全栈2019”Java原子操作第十四章：高性能高效率的原子类介绍》一章中介绍了高性能高效率的原子类DoubleAccumulator、DoubleAdder、LongAccumulator、LongAdder。

现在介绍高性能原子类是如何实现的。

2.通过LongAdder源码分析高性能原子类是如何实现的

以LongAdder类为例，阅读源码了解实现原理。

LongAdder类的继承结构：

LongAdder的直接父类是Striped64。

Striped64是适用于于并发情况下进行累加运算的类（Java8新增的）。它是抽象的，需要子类去实现它里面的抽象方法才能使用。在高并发情况下，它不光性能强，而且效率也高。

Striped64的子类包括前一章我们介绍到的DoubleAccumulator、DoubleAdder、LongAccumulator和LongAdder四个原子类。

下面我们一起来看看它内部属性有哪些。

在Striped64类中，这四个变量值得注意：

1. static final int NCPU = Runtime.getRuntime().availableProcessors();
2. transient volatile Cell[] cells;
3. transient volatile long base;
4. transient volatile int cellsBusy;

依次来看：

变量NCPU是用来记录当前机器上有多少个可用的CPU。

从该变量可以看出：一旦计算任务繁重，就会充分利用CPU资源。

这也就是为什么Striped64及其子类性能高效率高的原因之一。

变量cells是一个Cell数组。

Cell类相当于是一个低配版的原子类。

为什么这么说呢？

因为Cell类里面有一个用来记录内存值的变量和一个调用底层CAS算法的方法：

可以说，Cell类就是一个嵌入在Striped64类中的原子类。

可它为什么要嵌入在Striped64类中呢？

Striped64类内部需要一个原子类数组，组成数组的原子类一定要轻量，满足基本的原子类要求即可。已有的原子类太重量级，一旦形成数组，内存就是一笔不小的开销，这时就需要一个满足原子类基本要求的且轻量的原子类，Cell类就诞生了，就在Striped64类中，以内部类的形式存在。Cell类里面只有一个用于记录内存值的变量value，和一个利用CAS算法更新值的方法cas。由于它没有过多的功能，Cell类只能在atomic包内使用，不能在包外使用。

Striped64类为什么需要一个原子类数组（Cell数组）呢？

在计算机中，单线程情况下，一个线程去执行一个原子类任务，这样的操作没有任何问题；但是在多线程情况下，三个线程共同去执行一个原子类任务，看起来也没有什么问题，却暴露出线程资源浪费现象：三个线程共同执行一个原子类任务，其中只有一个线程做的事情是有效的，其他两个线程做了无用功，这无疑是一种线程资源浪费，而且还占用了CPU资源。为了解决此类现象，Striped64类定义出原子类数组，尽可能让多线程同时完成更多的原子类任务，高效利用线程资源和CPU资源。

Striped64类中为什么还有一个long类型变量base呢？

在计算机中，计算任务不是总有那么多，也有很少的时候。10000个计算任务和1个计算任务用的线程个数和占的CPU资源是不一样的，针对上述情况，Striped64类分了两种情况：同时要计算的任务很多和同时要计算的任务不多，即高并发和非高并发。

非高并发情况：这时候需要计算的任务可能只有一两个，一个线程完全应付的来，而且也没有用原子类数组的必要，用一个变量足以，这个变量就是base。当计算任务完成直接返回base变量的值即可。

高并发情况：这时候需要计算的任务可能就有10000或者更多，一个线程可以应付的来，但是太慢，这时会支援多个线程共同来完成这些任务。多个线程共同操作一个变量必然会造成线程资源的浪费，而且CPU也被占用着。为了不让线程做没用的忙碌，有必要用原子类数组来装任务结果。当计算任务完成时，返回base与Cell数组中每个Cell对象的value之和。

以add(long x)方法为例来说具体是怎么实现的：

下面一步一步来看。

这一步是判断Cell数组是否已经被初始化。

为什么要判断Cell数组是否已经被初始化？

若Cell数组已被初始化，说明计算任务很多，已启动高并发模式。

若Cell数组没有被初始化，说明计算任务很少，当前线程数量还应付得来。

如果程序来到这一步，说明Cell数组没有被初始化，计算任务不是很多，当前线程数量还应付得来。但是，如果当前线程数量利用CAS算法更新base值失败的话，那就要进入高并发模式，去初始化Cell数组啦。

局部变量uncontended用来记录后面Cell对象调用cas()方法利用CAS算法更新值是否成功。

若成功，则不必进入longAccumulate(long x, LongBinaryOperator fn, boolean wasUncontended)方法；

若不成功，则需要进入longAccumulate(long x, LongBinaryOperator fn, boolean wasUncontended)方法。

longAccumulate(long x, LongBinaryOperator fn, boolean wasUncontended)方法是用来继续更新值的方法。

继续往下看，if语句中条件表达式有四个：

1. cs == null
2. (m = cs.length - 1) < 0
3. (c = cs[getProbe() & m]) == null
4. !(uncontended = c.cas(v = c.value, v + x))

这四个条件表达式它们用“||”符合连接，只要满足其中任意一个，就进入赋值阶段。

“cs == null”：走到这一步，说明cells数组已经不为空了，因为在它之前“(cs = cells) != null”判断过了，所以这里的cells通常来说不会为空。

“(m = cs.length - 1) < 0”：既然Cell数组不为空，那么Cell数组的长度是否为0呢？该步骤就是检查Cell数组长度为0的情况。

“(c = cs[getProbe() & m]) == null”：Cell数组不为空且Cell数组长度也不为0，接下来就该获取其中一个Cell对象，然后进行CAS赋值操作。

问题是该取哪个位置的元素呢？

这个就通过我们的getProbe()方法计算得到的：

getProbe()方法：

通过对当前线程进行hash运算，得到一个hash值。

然后拿着这个hash值和数组最大下标做“&”运算，运算总会得到一个0-最大下标的值，然后取到cells[前面计算好的下标]的元素，最后判断该元素是否为空。

来一个动画演示一下上述操作：

为什么还有判断该元素是否为空？

因为有可能该位置元素前面已经被其他线程算过，所以我们取到已存在的元素时，只需在此基础之上累加即可。

下面就是开始累加的操作：

“!(uncontended = c.cas(v = c.value, v + x))”：能进行到这一步，说明Cell对象不为空，那么我们就继续在此基础之上调用cas(v = c.value, v + x)方法利用CAS算法进行赋值。并将赋值是否成功的结果用变量uncontended记录下来，以便在后面运算时做出相应的决策。

假设最后一步cas失败，我们进入到“longAccumulate(x, null, uncontended)”执行步骤中：

longAccumulate(long x, LongBinaryOperator fn, boolean wasUncontended)方法：

方法太长，我们依次分段往下说。

在此之前，了解几个参数的作用：

long x：操作数，比如给原值+1，那么这个1就是操作数。

LongBinaryOperator fn：二元运算，即自定义操作数与原值做什么运算，如加法、减法、乘法、除法等等。

boolean wasUncontended：前面CAS赋值是否成功。

方法最开始需要给当前线程分配操作的Cell对象，待分配的Cell对象被装在Cell数组变量cells中（cells初始值为null）：

合理分配就成了一个问题。若分配不合理，所有线程都操作一个Cell对象，那就没必要建数组，分配Cell对象了。

&算法

Striped64类就采取了一种类似于取余算法的操作：

下面，我们就来简单模拟这一操作。

模拟100个线程和长度为8的Cell数组分配过程：

例子中“i & 7”里面的7是数组最大下标，即数组长度-1。和add(long x)方法源码中的操作一样：

运行程序，执行结果：

从运行结果来看，结果一直是0-7循环，即cells[0]-cells[7]，这样我们每个元素都会被合理取到。

不得不佩服这一设计，很巧妙。

hash值为0时，重新计算

在longAccumulate()方法内部用一个局部变量h来记录当前线程的hash值：

如果h为0的话，则会强制重新再计算一次：

顺便将变量wasUncontended置为true。

避免hash碰撞

用一个局部变量collide来避免hash碰撞情况，当cells数组长度大于CPU数量时，我们就要去重新算一次当前线程的hash值：

目的就是避免发生hash值相同的情况，即hash碰撞。

外层无限循环

外层无需循环用来做CAS赋值操作的，待会分析到里面具体操作时你就会看到。

Cell数组、Cell对象、下标、操作数

用四个临时变量来记录当前线程操作的Cell数组、Cell对象、下标以及操作数：

Cell[] cs：当前线程操作的Cell数组，即cells变量;

Cell c：当前线程操作的Cell对象，该对象从Cell数组分配而来的;

int n：给当前线程分配的下标;

long v：参与运算的操作数；

初始化Cell数组

最初，变量cells还没有被初始：

所以一旦出现高并发情况，第一时间应该是先初始化cells变量：

“cellsBusy == 0”：没有其他线程正在初始化Cell数组。

“cells == cs”：cells数组为null，没有被初始化过。

“casCellsBusy()”：

cellsBusy算是一把非阻塞锁，如果没有线程正在给cells赋值，那么casCellsBusy()方法执行结果就为true；如果已有线程正在给cells赋值，那么casCellsBusy()方法执行结果为false。

当casCellsBusy()方法返回false时，因为是无限循环，所以还得再执行循环体里面的内容，直到cells变量被初始化：

如果拿到给cells变量初始化的锁，那么就可以执行以下内容（即初始化cells变量）：

“if(cs == cells){}”：在上面已经判断过了，这里如果没有问题的话，肯定为true。

“Cell[] rs = new Cell[2];”：创建Cell数组，初始长度为2，默认扩容公式是2^n。

“rs[h & 1] = new Cell(x);”：h为上面说过的当前线程hash值，1为Cell数组长度-1，这里利用&算法给各个线程分配元素。

此处因为是第一个元素，所以直接将操作数作为参数传入Cell对象。

“cells = rs;”：将初始化好的Cell数组赋给cells变量。

“break done;”：结束外层无限循环，第一次赋值到此完成。

代码结束之前，在finally代码块中将cellsBusy变量又置为0。

第一次赋值过程分析完成，下面来看后续赋值过程是怎样的。

只拿出局部代码来分析：

“(c = cs[(n - 1) & h]) == null”：取出给当前线程分配的Cell元素，判断当前元素是否为null。

拿上面已经初始化好的Cell数组来说，假如Cell数组情况是这样的：

cells[0] = Cell(value = 1);

cells[1] = null;

正好给当前线程分配的Cell元素为cells[1]，即当前元素为null。

若当前线程持有非阻塞cellsBusy锁，那么就继续执行if语句里面的内容：

创建一个新的Cell对象，并指定初始值为当前操作数x。

这一步给cellsBusy上锁，即将cellsBusy由0变为1，这样其他线程判断cellsBusy==0结果为false，就无法获取到cellsBusy锁。

“(rs = cells) != null”：Cell数组不能为null。

“(m = rs.length) > 0”：Cell数组长度要大于0。

“rs[j = (m - 1) & h] == null”：给当前线程分配位置上不能有已存在的元素。

“rs[j] = r;”：将刚刚新建的Cell对象赋给Cell数组指定位置。

“break done;”：结束外层无限循环。

finally代码块中最后的“cellsBusy = 0;”操作是释放非阻塞锁cellsBusy。

以上是取到元素为null的情况。

下面我们来看看取到元素不为null的情况。

直接调用取到的元素cas方法，如果执行成功，那么整个赋值过程就完成；

如果执行失败，那么重新计算当前线程的hash值：

advanceProbe(int probe)方法：

advanceProbe(int probe)方法的作用是重新计算当前线程的hash值。

为什么要重新计算当前线程hash值？

因为考虑到一个hash值相同的情况，即hash碰撞，所以避免出现此类问题出现，每次循环完都要重新计算一次当前线程的hash值。

整体流程

当所有值赋值完成时，最终返回结果就是：base+cells数组中每个Cell对象的value值之和。

最后，希望大家可以把这个例子照着写一遍，然后再自己默写一遍，方便以后碰到类似的面试题可以轻松应对。

祝大家编码愉快！

GitHub

本章程序GitHub地址：https://github.com/gorhaf/Java2019/tree/master/Thread/atomic/高性能原子类

总结

• Striped64是适用于于并发情况下进行累加运算的类（Java8新增的）。它是抽象的，需要子类去实现它里面的抽象方法才能使用。在高并发情况下，它不光性能强，而且效率也高。
• Striped64的子类包括DoubleAccumulator、DoubleAdder、LongAccumulator和LongAdder四个原子类。
• Cell类是一个嵌入在Striped64类中的原子类。
• 第一阶段：判断当前多线程情况下操作base变量是否失败，若失败则进入高并发模式。
• 第二阶段：初始化Cell数组。
• 第三阶段：根据当前线程hash值计算出当前线程所操作的Cell对象。
• 第四阶段：判断Cell对象元素是否为null，为null创建一个新值给Cell数组，否则利用CAS算法更新值。
• 从第三阶段开始，每个阶段都会重新计算当前线程的hash值。

至此，Java中分析Striped64类相关内容讲解先告一段落，更多内容请持续关注。

答疑

如果大家有问题或想了解更多前沿技术，请在下方留言或评论，我会为大家解答。

上一章

“全栈2019”Java原子操作第十四章：高性能高效率的原子类介绍

下一章

“全栈2019”Java原子操作第十六章：从零手写非阻塞栈数据结构

学习小组

加入同步学习小组，共同交流与进步。

• 方式一：关注头条号Gorhaf，私信“Java学习小组”。
• 方式二：关注公众号Gorhaf，回复“Java学习小组”。

全栈工程师学习计划

关注我们，加入“全栈工程师学习计划”。

版权声明

原创不易，未经允许不得转载！