基础概念

同步 Synchronous & 异步 Asynchronous

同步和异步通常用来形容一次方法调用。

• 同步方法：调用一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。
• 异步方法：调用更像是一个消息传递，一旦开始，方法调用就会立即返回，调用者就可以继续后续的操作。而异步方法通常会在另一个线程中“真实”地执行。整个过程，不会阻碍调用者的工作。
  对于调用者来说，异步调用似乎是一瞬间就完成的。如果异步调用需要返回结果，那么当这个异步调用真实完成时，则会通知调用者。

并发 Concurrency & 并行 Parallelism

• 并发：多个任务交替执行，而多个任务之间可能还是串行的。但对于外部观察者来说，看卡里像是并行执行的错觉。
• 并行：真正意义上的“同时执行”。

真实的并行只可能出现在拥有多个 CPU 的系统中。

临界区

临界区用来表示一种公共资源或者说是共享数据，可以被多个线程使用。但是每一次，只能有一个线程使用它，一旦临界区资源被占用，其他线程要想使用这个资源，就必须等待。

在并行程序中，临界区资源是保护的对象。

阻塞 Blocking & 非阻塞 Non-Blocking

阻塞和非阻塞通常用来形容多线程间的相互影响。

• 阻塞：当一个线程占用了临界区资源，那么其他所有需要这个资源的线程就必须在这个临界区中进行等待。等待会导致线程挂起，这种情况就是阻塞。
• 非阻塞：强调没有一个线程可以妨碍其他线程执行。所有线程都会尝试不断前向执行。

死锁 Deadlock & 饥饿 Starvation & 活锁 Livelock

这三个都属于多线程的活跃性问题。

• 死锁：指各个线程都互相占用了其他线程的资源，大家都不愿意释放资源，这个状态将永远维持下去。
• 饥饿：指某一个或者多个线程因为种种原因无法获得所需要的资源，导致一直无法执行。比如它的线程优先级过低。
• 活锁：指线程都秉承着“谦让”的原则，主动将资源释放给他人执行，那么就会出现资源不断在两个线程中跳动，而没有一个线程可以同时拿到所有资源而正常执行。

并发级别

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

阻塞 Blocking

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

这些线程回试图在执行后续代码前，得到临界区的锁，如果得不到，线程就会被挂起等待，知道占有了所需资源为止。

无饥饿 Starvation-Free

如果线程之间时有优先级的，那么线程调度的时候总是会倾向于满足高优先级的线程。但如果锁时公平的，满足先来后到，那么饥饿就不会产生，不管新来的线程优先级多高，想要获得资源，就必须乖乖排队。所有线程都有机会执行。

无障碍 Obstruction-Free

无障碍是一种最弱的非阻塞调度。两个线程如果是无障碍地执行，那么他们不会因为临界区地问题导致一方被挂起。

如果出现两个线程一起修改共享数据的情况，一旦检测到，就会立即对所做的修改进行回滚，确保数据安全。

如果说阻塞的控制方式是悲观策略。那么无障碍就是乐观策略。

为了保证至少又一个线程能够在有限的时间内完成自己的操作，一种可行的无障碍实现，可以依赖一个“一致性标记”来实现。线程在操作之前，先读取并保存这个标记，在操作完成后，再次读取，检查这个标记是否被更改过，如果两者是一致的，则说明资源访问没有冲突。如果不一致，则说明资源可能在操作过程中与其他写线程冲突，需要重试操作，而任何对资源有修改操作的线程，在修改数据之前，都需要更新这个一致性标记，表示数据不再安全。

无锁 Lock-Free

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

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

// 示例：如果修改不成功，那么循环永远不会停止。
while (!atomicVar.compareAndSet(localVar, localVar+1)) {
	localVar = atomicVar.get();
}

无等待 Wait-Free

无锁只要求有一个线程可以在有限步内完成操作，而无等待则要求所有线程都必须在有限步内完成，这样就不会引起饥饿问题。

如果限制这个步骤上限，还可以进一步分解为有界无等待和线程数无关的无等待几种，它们之间的区别知识对循环次数的限制不同。

一种典型的无等待结构就是 RCU（Read-Copy-Update）。

• 对数据的读不加控制。这样所有的读线程都是无等待的。
• 写数据时，先取得原始数据的副本，接着只修改副本数据，修改完成后，在合适的时机回写数据。

有关并行的两个重要定律

将串行程序改造为并发，可以提高程序整体性能，但是究竟能提高多少？用下面两个定律解答。

Amdahl 定律

加速比定义：加速比 = 优化前系统耗时 / 优化后系统耗时
$$\begin{array}{l}{T}_n=T_1(F+\frac{1}{n}(1-F))\\ \\ 加速比=\frac{T_1}{T_n}=\frac{1}{F+\frac{1}{n}(1-F)}\end{array}$$

其中，n 表示处理器个数，T 表示时间，$T_1$ 表示优化前耗时，$T_n$ 表示使用 n 个处理器优化后的耗时。F 表示串行比例，1-F 表示并行比例。

根据这个公式，如果 CPU 处理器数量趋于无穷，那么加速比与系统的串行化率成反比，如果系统中必须有 50% 的代码串行执行，那么系统的最大加速比为 2。

注意：根据上述描述，使用多核 CPU 优化，效果取决于 CPU 的数量以及系统中的串行化程序的比重。CPU 数量越多，串行化比重越低，则优化效果越好。仅提高 CPU 数量而不降低程序的串行化比重，也无法提高系统性能。

Gustafson 定律

$$\begin{array}{l}执行时间：a+b\\ \\ 总执行时间：a+n\ast b\\ \\ 加速比：\frac{a+n\ast b}{a+b}\\ \\ 定义串行比例：F=\frac{a}{a+b}\\ \\ \begin{array}{rl}加速比S(n)& =\frac{a+n\ast b}{a+b}\\ & =\frac{a}{a+b}+\frac{n\ast b}{a+b}\\ & \\ & =n-F(n-1)\end{array}\end{array}$$
其中，a 为串行时间，b 为并行时间，n 为处理器个数。

综上，可以发现，如果串行化比例很小，并行化比例很大，那么加速比就是处理器的个数，是换一个角度去描述。

区别对比

Amdahl 强调：当串行比例一定时，加速比是由上限的，不管堆叠多少个 CPU 参与计算，都不能突破这个上限。

Gustafson 强调：如果可被并行化的代码所占比重足够多，那么加速比就能随着 CPU 的数量线性增长。

Java 内存模型（JMM）

原子性（Atomicity）

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

对于32位系统来说，long型数据的读写不是原子性的（因为long有64位）。

可见性（Visibility）

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

有序性（Ordering）

在并发时，程序的执行可能会出现乱序。有序性问题的原因是因为程序在执行时，可能会进行指令重排，重排后的指令与原指令的顺序未必一致。
指令重排：指令流水线排满时是最高效的，如果中断再排满就会损失很多效率，所以为了防止流水线中断就会进行指令重排。

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

• 程序顺序原则：一个线程内保证语义的串行性；
• volatilt规则：volatile变量的写，先发生于读，这保证了volatile变量的可见性；
• 锁规则：解锁（unlock）必然发生再随后的加锁（lock）前；
• 传递性：A先于B，B先于C，那么A必然先于C；
• 线程的start()方法先于它的每一个动作；
• 线程的所有操作先于线程的终结（Thread.join()）；
• 线程的中断（interrupt()）先于被中断线程的代码；
• 对象的构造函数执行、结束先于finalize()方法。