Java多线程–基础概念

必须知道的几个概念

同步和异步

同步方法一旦开始，调用者必须等到方法调用返回后，才能执行后续行为；而异步方法调用，一旦开始，方法调用就立即返回，调用者不用等待就可以继续执行后续行为。

更具体地说，同步调用就是调用者调用当前方法后，就一直等待着该方法执行完毕并返回结果；而异步调用是调用者调用方法后，可以不用等待，直接开始其他行为的执行，等到某一个时间点原来的方法执行结束后要返回结果，会通知调用者。

并发和并行

• 并发是多个任务交替执行，可以被中断，但是任何时候只有一个任务在执行。比如单核CPU交替执行不同的指令。
• 并行是真正的同时执行，比如多核CPU，每个CPU在同一时刻执行一个命令，那么在这一时刻就有多条指令被同时执行了。

临界区

可以被多个线程使用的公共资源或共享资源。但是每一次只能有一个线程使用它，一旦临界区资源被（某一个线程）占用，其他线程若想要使用这个资源，就必须等待。

阻塞和非阻塞

某一个线程占用了临界区资源，其他想要使用这个资源的线程就必须等待，等待导致线程挂起，这就是阻塞。非阻塞与之相反：没有一个线程可以妨碍其他线程的执行。

死锁、饥饿和活锁

死锁。都占用着对方想要的资源不释放，如A占用B想要的不释放，B也占用着A的不释放，形成了“环”。

饥饿。一个或者多个线程无法获得所需的资源，迟迟不能得到执行。饥饿有如下两种情况：

• 当前线程的优先级过低，高优先级的线程不断抢占它所需的资源，导致低优先级的线程无法得到执行。
• 某一个线程一直占用着资源不释放，导致其他线程都无法得到执行。

饥饿有可能在未来的一段时间内解决，比如低优先级的线程终于拿到了资源，或者线程执行完成不再一直占用资源了。

活锁。线程都主动礼让，将资源释放给其他线程使用。比如A将资源给B，B也礼让给A，就导致了资源在A、B之间跳动，从而没有一个线程可以拿到资源。就好像“踢皮球”。

并发级别

• 阻塞。其他线程释放资源之前，当前线程无法继续执行。在试图执行后续代码之前，必须要先得到临界区的锁，如果得不到，线程就会被挂起等待。
• 无饥饿。如果线程之间有优先级，那么线程调度时总是倾向于满足高优先级的线程，即对同一个资源的分配是不公平的。对于不公平的锁，高优先级的线程可以插队到低优先级线程之前。低优先级的线程就容易产生饥饿。如果资源分配是公平的，那么不论优先级，严格遵循先来后到，饥饿就不会产生。
• 无障碍。此时所有线程都可以进入临界区，就有可能在同一时刻多个线程修改同一共享变量，导致将数据修改得面目全非。对于无障碍的线程来说，一旦检测到这种情况就会被已做的修改进行回滚，确保数据的安全。一种无障碍的实现可以通过设置一个“一致性标志”来实现：线程在操作之前，先读取并保存这个标记，等操作完成之后，再次读取，检查标记是否被修改过，如果两者一致说明对资源的访问没有冲突；否则存在冲突，任何对资源有修改操作的线程，在修改数据之前，先更新这个标记，以表明数据不再安全。无障碍可能出现如下现象：没有一个线程能走出临界区。
• 无锁。无锁的并行都是无障碍的。和 无障碍不同的是，无锁的并发保证必然会有一个线程能在有限步内完成操作离开临界区。
• 无等待。无锁只要求有一个线程可以在有限步内完成操作，而无等待要求所有的线程都必须在有限步内完成，这样就避免了饥饿问题。一种典型的无等待结构是RCU(Read-Copy-Update)，基本思想是对数据的读操作不加控制，因此所有的读线程都是无等待的，不会引发冲突；在写数据时，先取得原始数据的副本，接着只修改副本（没有直接修改原始数据，所以读操作才可以不加以控制），修改完副本后，在合适的时机回写数据。

两个关于并行的定律

Amdahl定律

$$T_n = T_1(F + 1/n(1-F))$$

即

$$T_n = \frac{1}{F+1/n(1-F)}$$

$T_n$定义为加速比

加速比 = 优化前系统耗时 / 优化后系统耗时

其中$n$是处理器的个数，F是串行化比例。即必须串行的步骤数 / 总步骤数，$F = 1$表示所有步骤只能串行完成，加速比为1（没有加速）；$F = 0$表示所有步骤可以由多核同时执行，加速比为处理器个数$n$。

可以看出Amdahl定律优化效果取决于处理器的个数，以及串行化比例。CPU越多，串行化比例越低，优化效果越好。一味的增加CPU的个数，不降低串行化比例的化，也无法提高系统性能。

Guastafon定律

$$s(n) = n – F(n – 1)$$

$S(n)$和上面一样表示加速比，$n$和$F$的意义也与上面相同。

Amdahl定律强调：当串行比例F固定时，加速比是有上限的，无论增加多少CPU都不能突破该上限（上限可以计算极限得到）

Gustafson定律强调：当串行化比例F固定时，只要串行化比例足够小（可并行化的代码比重足够大），那么加速比可以随着CPU的数量线性增长。（F是常数时，S(n)是n的一次函数）

JMM（Java内存模型）

原子性

原子性指一个操作不可中断：一个线程一旦开始，直到执行完成都不会被其他线程干扰。

可见性

可见性指当一个线程修改了某个共享变量的值，其他线程是否能立即知道这个修改。串行中不存在可见性问题，因为某个线程修改了某个值，在后续步骤中，其他线程读取到这个值时，一定时修改后的值了。在并行程序中，如编译器优化的原因，在CPU1上对变量a进行了优化，将其缓存在cache或寄存器中，此时如果CPU2修改了a的实际值，CPU1可能无法意识到a已经被修改，依然会读取缓存里的旧值。

除了编译器优化，指令重排以及编辑器优化都可能产生可见性问题。

有序性

代码不按照本来的顺序执行，即写在前面的代码跑到了后面去执行。指令的执行顺序乱了，这就是有序性问题。

程序在执行时，可能会进行指令重排，重排后的顺序依然保持着串行语义一致，但不保证在并行下语义也一致。

之所以要进行指令重排，是出于优化的考虑，为了减少中断流水线，即中断产生的等待时间，提高CPU处理性能。

Happen-Before规则

有些指令是可以重排的，有些指令是不可重排的。下面是一些基本原则：

• 程序顺序原则：一个线程内保证语义的串行性，比如第二条语句依赖第一条语句的结果，那么就不能先执行第二条再执行第一条。
• volatile原则：volatile变量的写先于读，着保证了volatile变量的可见性
• 锁规则：先解锁，后续步骤再加锁。加锁不能重排到解锁之前，这样加锁行为无法获得锁（刚加上就解了）
• 传递性：A先于B，B先于C，那么A先于C
• 线程的start()先于它的每个动作
• 线程的所有操作先于线程的终结(Tread.join())
• 线程的中断(interrupt())先于被中断线程的代码
• 对象的构造函数执行、结束先于finalize()方法。

by @sunhaiyu

2018.4.10