笔记根据实战Java高并发程序设计这本书整理
一、你必须知道的几个概念
1、同步和异步
同步和异步通常用来形容一次方法调用。
同步方法调用一旦开始，调用者必须等到方法调用返回后，才能继续后续的行为。
异步方法调用更像一个消息传递，一旦开始，方法调用就会立即返回，调用者就可以继续后续的操作。而异步方法通常会在另外一个线程中 “真实”地执行。整个过程，不会阻碍调用者的工作。对于调用者来说，异步调用似乎是一瞬间就完成的。如果异步调用需要返回结果，那么当这个异步调用真实完成时，则会通知调用者。
2、并发和并行
并发偏重于多个任务交替执行，而多个任务之间有可能还是串行的，而并行是真正意义上的“同时执行”。
实际上，如果系统内只有一个CPU，而使用多进程或者多线程任务，那么真实环境中这些任务不可能是真实并行的，毕竟一个CPU —次只能执行一条指令，在这种情况下多进程或者多线程就是并发的，而不是并行的(操作系统会不停地切换多个任务)。
真实的并行也只可能出现在拥有多个CPU的系统中(比如多核CPU)。
3、临界区
临界区用来表示一种公共资源或者说共享数据，可以被多个线程使用。但是每一次只能有一个线程使用它，一旦临界区资源被占用，其他线程要想使用这个资源就必须等待。
在并行程序中，临界区资源是保护的对象。
4、阻塞(Blocking)和非阻塞(Non-Blocking)
阻塞和非阻塞通常用来形容多线程间的相互影响。
比如一个线程占用了临界区资源， 那么其他所有需要这个资源的线程就必须在这个临界区中等待。等待会导致线程挂起，这种情况就是阻塞。此时，如果占用资源的线程一直不愿意释放资源，那么其他所有阻塞在这个临界区上的线程都不能工作。
非阻塞的意思与之相反，它强调没有一个线程可以妨碍其他线程执行，所有的线程都会尝试不断前向执行。
5、死锁(Deadlock)、饥饿(Starvation)和活锁(Livelock)
死锁、饥饿和活锁都属于多线程的活跃性问题。如果发现上述几种情况，那么相关线程可能就不再活跃，也就是说它可能很难再继续往下执行了。
死锁应该是最糟糕的一种情况了。
如图：A、B、C、D四辆小车在这种情况下都无法继续行驶了。它们彼此之间相互占用了其
他车辆的车道，如果大家都不愿意释放自己的车道，那么这个状态将永远持续下去，谁都
不可能通过。
饥饿是指某一个或者多个线程因为种种原因无法获得所需要的资源，导致一直无法执行。
- 比如它的线程优先级可能太低，而高优先级的线程不断抢占它需要的资源，导致低优先级线程无法工作。
- 某一个线程一直占着关键资源不放，导致其他需要这个资源的线程无法正常执行，这种情况也是饥饿的一种。
与死锁相比，饥饿还是有可能在未来一段时间内解决的(比如，高优先级的线程己经完成任务，不再疯狂执行)。
如果线程的智力不够， 且都秉承着“谦让”的原则，主动将资源释放给他人使用，那么就会导致资源不断地在两个线程间跳动，而没有一个线程可以同时拿到所有资源正常执行。这种情况就是活锁。
二、 并发级别
由于临界区的存在，多线程之间的并发必须受到控制。根据控制并发的策略，我们可以把并发的级别分为阻塞、无饥饿、无障碍、无锁、无等待几种。
1、阻塞
一个线程是阻塞的，那么在其他线程释放资源之前，当前线程无法继续执行。
当我们使用synchronized关键字或者重入锁时，我们得到的就是阻塞的线程。
synchronized关键字和重入锁都试图在执行后续代码前，得到临界区的锁，如果得不到，线程就会被挂起等待，直到占有了所需资源为止。
2、无饥饿
如果线程之间是有优先级的，那么线程调度的时候总是会倾向于先满足高优先级的线程。也就说是，对于同一个资源的分配，是不公平的！
对于非公平锁来说，系统允许高优先级的线程插队。 这样有可能导致低优先级线程产生饥饿。
但如果锁是公平的，按照先来后到的规则，那么饥饿就不会产生，不管新来的线程优先级多高，要想获得资源，就必须乖乖排队，这样所有的线程都有机会执行。
3、无障碍
无障碍是一种最弱的非阻塞调度。
两个线程如果无障碍地执行，那么不会因为临界区的问题导致一方被挂起。换言之，大家都可以大摇大摆地进入临界区了。那么大家一起修改共享数据，把数据改坏了怎么办呢？
对于无障碍的线程来说，一旦检测到这种情况，它就会立即对自己所做的修改进行回滚，确保数据安全。但如果没有数据竞争发生，那么线程就可以顺利完成自己的工作，走出临界区。
一种可行的无障碍实现可以依赖一个“一致性标记”来实现。线程在操作之前，先读取并保存这个标记，在操作完成后，再次读取，检查这个标记是否被更改过，如果两者是一致的，则说明资源访问没有冲突。如果不一致，则说明资源可能在操作过程中与其他写线程冲突，需要重试操作。而任何对资源有修改操作的线程，在修改数据前，都需要更新这个一致性标记，表示数据不再安全。
4、无锁(Lock-Free)
无锁的并行都是无障碍的。在无锁的情况下，所有的线程都能尝试对临界区进行访问，但不同的是，无锁的并发保证必然有一个线程能够在有限步内完成操作离开临界区。
在无锁的调用中，一个典型的特点是可能会包含一个无穷循环。在这个循环中，线程会不断尝试修改共享变量。如果没有冲突，修改成功，那么程序退出，否则继续尝试修改。
下面就是一段无锁的示意代码，如果修改不成功，那么循环永远不会停止。
while (!atomicVar.compareAndSet(localVar, localVar+1)){
localVar = atomicVar.get();
}5、无等待(Wait-Free)
无锁只要求有一个线程可以在有限步内完成操作，而无等待则在无锁的基础上更进一步扩展。它要求所有的线程都必须在有限步内完成，这样就不会引起饥饿问题。
如果限制这个步骤的上限，还可以进一步分解为有界无等待和线程数无关的无等待等几种，它们之间的区别只是对循环次数的限制不同。
一种典型的无等待结构就是RCU (Read Copy Update)。它的基本思想是，对数据的读可以不加控制，即读线程都是无等待的。但在写数据的时候，先取得原始数据的副本，接着只修改副本数据(这就是为什么读可以不加控制)，修改完成后，在合适的时机回写数据。
三、JMM(Java的内存模型)
JMM的关键技术点都是围绕着多线程的原子性、可见性和有序性来建立的。因此，我们首先必须了解这些概念。
1、原子性（Atomicity）
即一个操作或者多个操作 要么全部执行并且执行的过程不会被任何因素打断，要么就都不执行。
原子性是拒绝多线程操作的，不论是多核还是单核，具有原子性的量，同一时刻只能有一个线程来对它进行操作。简而言之，在整个操作过程中不会被线程调度器中断的操作，都可认为是原子性。例如 a=1是原子性操作，但是a++和a +=1就不是原子性操作。
Java中的原子性操作包括：
- 基本类型的读取和赋值操作，且赋值必须是值赋给变量，变量之间的相互赋值不是原子性操作。
- 所有引用reference的赋值操作
- java.concurrent.Atomic.* 包中所有类的一切操作
2、可见性（Visibility）
可见性是指当一个线程修改了某一个共享变量的值时，其他线程能够立即看得到修改的值。
显然，对于串行程序来说，可见性问题是不存在的。因为你在任何一个操作步骤中修改了某个变量，在后续的步骤中读取这个变量的值时，读取的一定是修改后的新值。
但是这个问题存在于并行程序中。如果一个线程修改了某一个全局变量，那么其他线程未必可以马上知道这个改动。
上图展示了发生可见性问题的一种可能。如果在CPU1和CPU2上各运行了一个线程，它们共享变量t，由于编译器优化或者硬件优化的缘故，在CPU1上的线程将变量t进行了优化，将其缓存在cache中或者寄存器里。在这种情况下，如果在CPU2上的某个线程修改了变量t的实际值，那么CPU1上的线程可能无法意识到这个改动，依然会读取cache中或者寄存器里的数据。因此，就产生了可见性问题。
外在表现为变量t的值被修改，但是CPU1上的线程依然会读到一个旧值。可见性问题也是并行程序开发中需要重点关注的问题之一。
3、有序性（Ordering）
即程序执行的顺序按照代码的先后顺序执行。
在Java内存模型中，为了效率是允许编译器和处理器对指令进行重排序，当然重排序不会影响单线程的运行结果，但是对多线程会有影响。
Java提供volatile来保证一定的有序性。最著名的例子就是单例模式里面的DCL（双重检查锁）。另外，可以通过synchronized和Lock来保证有序性，synchronized和Lock保证每个时刻是有一个线程执行同步代码，相当于是让线程顺序执行同步代码，自然就保证了有序性。
下面来看一个简单的例子：
class OrderExample{
int a = 0;
boolean flag = false;
public void writer() {
a = 1;
flag = true;
}
public void reader() {
if(flag) {
int i = a + 1;
}
}
}假设线程A首先执行writer()方法，接着线程B执行reader()方法，如果发生指令重排，那么线程B在代码第10行时，不一定能看到a己经被赋值为1 了。
确实是一个看起来很奇怪的问题，但是它确实可能存在。
注意：这里说的是可能存在。因为如果指令没有重排，这个问题就不存在了，但是指令是否发生重排、如何重排，恐怕是我们无法预测的。因此，对于这类问题，我认为比较严谨的描述是：线程A 的指令执行顺序在线程B 看来是没有保证的。如果运气好的话，线程B 也许真的可以看到和线程A 一样的执行顺序。
不过这里还需要强调一点，对于一个线程来说，它看到的指令执行顺序一定是一致的 (否则应用根本无法正常工作)。也就是说指令重排是有一个基本前提的，就是保证串行语义的一致性。指令重排不会使串行的语义逻辑发生问题。因此，在串行代码中，大可不必担心。
注意：指令重排可以保证串行语义一致，但是没有义务保证多线程间的语义也一致。
为什么需要指令重排，这里简单的解释一下。
减少中断流水线，提升CPU效率。
来看个例子，如图展示了 A = B + C这个操作的执行过程。写在左边的指令就是汇编指令。LW表示load，其中LW R1,B表示把B的值加载到R1寄存器中。 ADD指令就是加法，把Rl、R2的值相加，并存放到R3中。SW表示store,存储，就是将R3寄存器的值保存到变量A中。
右边就是流水线的情况。注意，在ADD指令上，有一个大叉，表示一个中断。也就是说ADD在这里停顿了一下。为什么ADD会在这里停顿呢？原因很简单，R2中的数据还没有准备好，所以，ADD操作必须进行一次等待。由于ADD的延迟，导致其后所有的指令都要慢一拍。
既然在ADD的时候会停顿一下，那么停顿的时间不如做些有意义的事，会在这里加载对程序没有影响的后面的代码，比如说后面某处定义了一个变量，就可以放在这里加载，因为提前加载变量对程序的结果不会产生影响。
由此可见，指令重排对于提高CPU处理性能是十分必要的。虽然确实带来了乱序的问题，但是这点牺牲是完全值得的。
哪些指令不能重排：Happen-Before规则
虽然Java虚拟机和执行系统会对指令进行一定的重排，但是指令重排是有原则的，并非所有的指令都可以随便改变执行位置，以下罗列了一些基本原则，这些原则是指令重排不可违背的。
- 程序顺序原则：一个线程内保证语义的串行性。
- volatile规则：volatile变量的写先于读发生，这保证了volatile变量的可见性。
- 锁规则：解锁(unlock)必然发生在随后的加锁(lock)前。
- 传递性：A先于B，B先于C，那么A必然先于C。
- 线程的start()方法先于它的每一个动作。
- 线程的所有操作先于线程的终结(Thread.join())。
- 线程的中断（interrupt()）先于被中断线程的代码。
- 对象的构造函数的执行、结束先于finalize()方法。
以程序顺序原则为例，重排后的指令绝对不能改变原有的串行语义，比如：
a = 1;
b = a + 1;由于第2条语句依赖第1条语句的执行结果。如果贸然交换两条语句的执行顺序，那么程序的语义就会修改。因此这种情况是绝对不允许发生的，这也是指令重排的一条基本原则。
其他几条原则也是类似的，这些原则都是为了保证指令重排不会破坏原有的语义结构。