Java高并发理论基础

并发级别

由于临界区的存在，多线程之间的并发必须受到控制。根据控制并发的策略，我们可以把并发的级别分为 阻塞、无饥饿、无障碍、无锁、无等待 几种。

阻塞

一个线程是阻塞的，那么在其他线程释放资源之前，当前线程无法继续执行。当我们使用sychronized关键字或者重入锁时，我们得到的就是阻塞的线程。

sychronized关键字和重入锁（ReentrantLock）都试图在执行后续代码之前，得到临界区的锁，如果得不到，线程就会被挂起等待，直到占有了所需资源为止。

无饥饿

如果线程之间是有优先级的，那么线程调度的时候总是倾向于满足高优先级的线程。即，对于同一个资源的分配，是不公平的。

对于非公平锁，系统允许高优先级的线程插队，这样有可能导致低优先级线程产生饥饿。

如果锁是公平的，按照先来后到的原则，那么饥饿就不会产生。所有线程都有机会执行。

无障碍

无障碍是一种最弱的非阻塞调度（乐观锁）。两个线程无障碍的执行，那么不会因为临界区的问题导致一方被挂起，对于无障碍的线程来说，双方共同修改临界区的资源，如果一方把资源修改坏，会立即对自己所做的修改进行回滚，确保数据安全。

阻塞的控制方式属于悲观策略，无障碍（非阻塞）的调度就是一种乐观策略。

一种可行的无障碍实现可以依赖一个“一致性标记”（版本号或者CAS机制都依赖于这种实现），线程在操作之前，先读取并保存这个标记，在操作完成后，再次读取，检查这个标记是否被更改过，如果两者一致，则说明资源访问没有冲突。如果不一致，则重试操作。

无锁

无锁的并行都是无障碍的。在无锁的情况下，所有的线程都能尝试对临界区进行访问，但不同的是，无锁的并发保证必然有一个线程能够在有限步内完成操作离开临界区。

在无锁的调用中，一个典型的特点是可能会 包含一个无穷循环。在这个循环中，线程会不断尝试修改共享变量。如果没有冲突，修改成功，程序退出，否则继续尝试修改。 但无论如何，无锁的并行总能保证有一个线程是可以胜出的。

如下：
在这里插入图片描述

无等待

无锁只要求有一个线程可以在有限步骤内完成操作，而无等待要求所有线程必须在有限步骤内完成。这样就不会引起饥饿问题。如果限制这个步骤的上限，还可以进一步分解为有界无等待和线程数无关的无等待几种。

一种典型的无等待结构是RCU(Read Copy Update).他的基本思想是，对数据的读不加控制，在写数据的时候，先取得原始数据的副本，接着只修改副本数据，修改完成后，在合适的时机写回数据。（COW 写时复制）

Java内存模型（JMM）

JMM的关键技术点都是围绕着多线程的原子性、可见性和有序性来建立的。

原子性

原子性指一个操作是不可中断的。即使在多个线程在一起执行的时候，一个操作一旦开始就不会被其他线程干扰。

可见性

可见性是指当一个线程修改了某一个共享变量的时候，其他线程是否能够立即知道这个修改。

在CPU1和CPU2上各运行一个线程，他们共享变量t，由于编译器优化或者硬件优化的缘故，在CPU1上的线程将变量t缓存到cache或者寄存器中，在这种情况下，CPU2上的线程对共享变量做了修改，CPU1上的线程无法意识到这种改动，依然会读取缓存值。因此，产生了可见性问题。

有序性

有序性问题的原因是程序在执行时，可能会进行指令重排，重排后的指令与原本的顺序未必一致。

串行执行的线程不存在指令重排问题，但是多线程间可能会存在，且是否发生指令重排不可预见。

为什么会发生指令重排

之所以发生指令重排，完全是出于性能考虑。一条指令执行是可以分为很多步骤，如下

取址IF
译码和取寄存器操作数ID
执行或者有效地址计算EX
存储器访问MEM
写回WB

在CPU实际工作中，汇编指令也需要多个步骤依次执行。由于每个步骤都可能使用不同的硬件来完成，如取址时用到PC寄存器或者存储器。执行时用到ALU（算术逻辑单元）。为了提高性能，发明了流水线技术来执行指令。
在这里插入图片描述
可以看出，当第二条指令执行时，指令一并未执行完成，有了流水线，CPU才能真正高效的执行。但是，流水线总是害怕被中断。流水线满载时，性能确实相当不错，但是 一旦中断，所有的硬件设备都会进入一个停顿期，再次满载又需要几个周期。因此，性能损失就很大，所以，必须想办法尽量不让流水线中断。之所以需要指令重排，就是为了尽量减少中断流水线。

示例如下：

执行操作

a = b+c;
d = e-f;

指令重排前执行过程
在这里插入图片描述
由于ADD、SUB操作都需要等待上一条指令的结果，因此，在这里插入了不少停顿。通过将LW Rf，f和LW Re,e移动到前面执行即可。因为先加载e和f对程序是没有影响的，既然在Add的时候要停顿一下，那么停顿的时间不如去做点有意义的事情，指令重排后如下：
在这里插入图片描述
由此可见，指令重排对于CPU处理性能是十分必要的。

哪些指令不能重排：Happen-Before规则

Java虚拟机和执行系统会对指令进行一定的重排，但是指令重排是有原则的，并非所有的指令都可以随便改变执行位置。以下罗列了一些基本原则：

程序顺序原则：一个线程内保证语义的串行性。
volatile原则：volatile变量的写先于读发生，这保证了volatile变量的可见性（当一个线程修改volatile变量时，新的值会被立即刷新到主内存中，并且其他线程能够立即看到这个更新）
锁规则：解锁必然发生在随后的加锁前。
传递性：A先于B，B先于C，那么A必然先于C。
线程的start()方法先于他的每一个动作。
线程的所有操作先于线程的终结（Thread.join()）
线程的中断先于被中断线程的代码
对象的构造函数的执行、结束先于finalize()方法。

Unsafe类

Unsafe类中的重要方法

Unsafe类提供了硬件级别的原子性操作，Unsafe类中的方法都是native方法。核心方法如下

boolean compareAndSwapLong(Object var1, long offset, long expect, long update): 比较对象obj中偏移量为offset的变量的值是否与expect相等，相等则使用update值更新，然后返回true，否则返回false。
void park(boolean isAbsolute,long time) 方法：阻塞当前线程，其中参数isAbsolute等于false且time等于0表示一直阻塞。time大于0表示等待指定的time后，阻塞线程会被唤醒。其他线程调用了当前阻塞线程的interrupt方法或者unpark方法，阻塞的线程都会返回。
void upark(Object thread)方法：唤醒调用park后阻塞的线程。

伪共享

什么是伪共享

为了解决计算机系统中主内存和CPU之间的运行速度差，会在CPU和主内存之间添加一级或者多级高速缓冲存储器。这个Cache一般是被集成到CPU内部的，所以也叫CPU cache。

下图展示了两级Cache结构：
在这里插入图片描述
在Cache内部，数据是按行存储的，其中每一行称为一个Cache行。Cache行是Cache和主内存进行数据交换的单位，Cache行大小一般为2的幂次数字节。

当CPU访问某个变量时，首先会去看CPU Cache内是否有该变量，如果有则直接从中获取，否则就去主内存里面获取该变量，然后把该变量所在内存区域的一个cache行大小的内存复制到cache中。由于存放到cache行的是内存块而不是单个变量，所以可能会把多个变量存放到一个cache行中。当多个线程同时修改一个缓存行里面的多个变量时，由于同时只能有一个线程操作缓存行，所以相比将每个变量都放入一个缓存行，性能会有所下降，这就是伪共享。

在这里插入图片描述
在该图中，变量x和y同时被放到了CPU一级和二级缓存，当线程1使用CPU1对变量x进行更新时，首先会修改CPU1的一级共享变量x所在的缓存行，这时候在缓存一致性协议下，CPU2中变量x对应的缓存行失效。那么线程2在写入变量x时就只能去二级缓存里找，这就破坏了一级缓存。而一级缓存比二级缓存更快，这也说明了多个线程不可能同时去修改自己所使用的CPU中相同缓存行里面的变量。更坏的情况是，如果CPU只有一级缓存，则会导致频繁的访问主内存。

为何会出现伪共享

伪共享的产生是因为多个变量被放入了一个缓存行中，并且多个线程同时去写入缓存行中不同的变量。为何多个变量会被放入一个缓存行呢？因为缓存与内存交换数据的单位就是缓存行，当CPU要访问的变量没有在缓存中找到时，根据程序运行的局部性原理，会把该变量所在内存中大小为缓存行的内存放入缓存行。

long a;
long b;
long c;
long d;

如上代码声明了4个long变量，假设缓存行的大小为32字节，那么当CPU访问变量a时，发现该变量没有在缓存中，就会去主内存把变量a以及内存地址附近的b、c、d放入缓存行。当创建数组时，数组里面的多个元素也会被放入同一个缓存行。

在正常情况下，但线程访问时将数组元素放入一个或者多个缓存行对代码执行是有利的，因为数组元素都在缓存中，代码执行会更快。

但是，在多线程情况下，一个缓存行中的多个变量修改就会竞争缓存行，从而降低程序性能。

如何避免伪共享

在JDK8之前一般是通过字节填充的方式来避免该问题，也就是创建一个变量时使用填充字段填充该变量所在的缓存行，如下：

public final static class FilledLong{public volatile long value = 0l;public long p1,p2,p3,p4,p5,p6;
}

假如缓存行为64字节，那么在FilledLong里面填充6个long类型变量，每个long类型占8字节，加上value的8字节，以及类对象的对象头占用8字节，所以一个FilledLong对象实际会占用64字节。这样就正好可以放入一个缓存行。

JDK8提供了sun.misc.Contended注解，用来解决伪代码共享问题。如下：

@sun.msic.Contended
public final static class FilledLong{public volatile long value = 0l;
}

@sun.msic.Contended默认情况下只用于Java核心类，如果用户类路径下的类使用这个注解，需要添加JVM参数 -XX:-RestrictContended.填充的宽度默认为128，要自定义宽度则可以设置-XX:ContendedPaddingWidth参数。