第一章 并发编程的挑战
需要了解的一些概念
转自 https://blog.csdn.net/TzBugs/article/details/80921351
（1） 同步VS异步
同步和异步通常用来形容一次方法调用。同步方法调用开始后，调用者必须等待被调用的方法结束后，调用者后面的代码才能执行。而异步调用，指的是，调用者不用管被调用方法是否完成，都会继续执行后面的代码，当被调用的方法完成后会通知调用者。
（2） 并发与并行
并发和并行是十分容易混淆的概念。并发指的是多个任务交替进行，而并行则是指真正意义上的“同时进行”。实际上，如果系统内只有一个CPU，使用多线程时，在真实系统环境下不能并行，只能通过切换时间片的方式交替进行，从而并发执行任务。真正的并行只能出现在拥有多个CPU的系统中。
（3）阻塞和非阻塞
阻塞和非阻塞通常用来形容多线程间的相互影响，比如一个线程占有了临界区资源，那么其他线程需要这个资源就必须进行等待该资源的释放，会导致等待的线程挂起，这种情况就是阻塞，而非阻塞就恰好相反，它强调没有一个线程可以阻塞其他线程，所有的线程都会尝试地往前运行。
（4）临界区
临界区用来表示公共资源或者说是共享数据，可以被多个线程使用。但是每个线程使用时，一旦临界区资源被一个线程占有，那么其他线程必须等待。
并发编程的目的是为了让程序运行得更快。但是，并不是启动更多的线程就能让程序最大限度地并发执行。在进行并发编程时，如果希望通过多线程执行任务让程序运行得更快，会面临非常多的挑战，比如上下文切换的问题、死锁的问题，以及受限于硬件和软件的资源限制问题。
1.1 上下文切换
即使单核处理器也支持多线程执行代码，CPU通过给每个线程分配CPU时间片来实现这个机制。时间片是CPU分配给各个线程的时间，因为时间片非常短，所以CPU通过不停地切换线程执行，让我们感觉多个线程是同时执行的。（时间片一般是几十毫秒）
CPU通过时间片分配算法来循环执行任务，当前任务执行一个时间片后会切换到下一个任务。但是，在切换前会保存上一个任务的状态，以便下次切换回这个任务时，可以再加载这个任务的状态。所以任务从保存到加载的过程就是一次上下文切换。上下文切换会影响多线程的执行速度。
1.1.1 多线程一定快吗？
不一定。例如执行累加，并发执行累加操作不超过百万次时，速度比串行执行累加操作慢。这是因为线程有创建和上下文切换的开销。
1.1.3 如何减少上下文切换？
减少上下文切换的方法有 无锁并发编程、CAS算法、使用最少线程 和 使用协程。
- 无锁并发编程：多线程竞争锁时，会引起上下文切换，所以多线程处理数据时，可以用一些办法来避免使用锁，如将数据的ID按照Hash算法取模分段，不同的线程处理不同段的数据。
- CAS算法
- 使用最少线程：避免创建不需要的线程，比如任务很少，但是创建了很多线程来处理，这样会造成大量线程都处于等待状态。
- 协程：在单线程里实现多任务的调度，并在单线程里维持多个任务间的切换。
1.2 死锁
引起死锁的例子：（线程 t1 和线程 t2 互相等待对方释放锁）
public class DeadLockTest {
private static String A = "A";
private static String B = "B";
public static void main(String[] args) {
new DeadLockTest().deadLock();
}
public static void deadLock() {
Thread t1 = new Thread(new Runnable() {
@Override
public void run() {
synchronized (A) {
try {
Thread.currentThread().sleep(2000);
} catch (Exception e) {
e.printStackTrace();
}
synchronized (B) {
System.out.println("1");
}
}
}
});
Thread t2 = new Thread(new Runnable() {
@Override
public void run() {
synchronized (B) {
synchronized (A) {
System.out.println("2");
}
}tim
}
});
t1.start();
t2.start();
}
}
在一些复杂场景，我们可能会遇到 t1 拿到锁之后，因为一些异常情况没有释放锁（死循环），又或是 t1 拿到一个数据库锁，释放锁的时候抛出了异常，没释放掉。
避免死锁的几个常见方法：
- 避免一个线程同时获取多个锁
- 避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源。
- 尝试使用定时锁，使用 lock.tryLock(timeout) 来代替使用内部锁机制。
- 对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失败的情况。
1.3 资源限制的挑战
（1）什么是资源限制？
资源限制是指在并发编程时，程序的执行速度受限于计算机硬件资源或软件资源。
硬件资源限制有带宽的上传/下载速度、硬盘读写速度和CPU的处理速度。
软件资源限制有数据库的连接数和socket连接数等。
（2）资源限制引发的问题
在并发编程中，将代码执行速度加快的原则是 将代码中串行执行的部分变成并发执行，但如果将某段串行的代码并发执行，因为受限于资源，仍然在串行执行，这时程序不仅不会加快执行，反而会更慢，因为增加了上下文切换和资源调度的时间。
（3）如何解决资源限制的问题？
对于硬件资源限制，可以考虑使用集群并行执行程序。既然单机的资源有限制，那么就让程序在多机上运行。比如使用ODPS、Hadoop或者自己搭建服务器集群，不同的机器处理不同的数据。
对于软件资源限制，可以考虑使用资源池将资源复用。比如使用数据库连接池将数据库和socket连接复用，或者在调用对方webservice接口获取数据时，只建立一个连接。
（4）在资源限制情况下进行并发编程
如何在资源限制的情况下，让程序执行得更快呢？方法就是，根据不同的资源限制调整程序的并发度，比如下载文件程序依赖于两个资源——带宽和硬盘读写速度。有数据库操作时，涉及数据库连接数，如果SQL语句执行非常快，而线程的数量比数据库连接数大很多，则某些线程会被阻塞，等待数据库连接。
第二章 Java并发机制的底层实现原理
Java代码在编译后会变成Java字节码，字节码被类加载器加载到JVM里，JVM执行字节码，最终需要转化为汇编指令在CPU上执行。Java中所使用的并发机制依赖于JVM的实现和CPU的指令。
2.1 volatile的应用
在多线程并发编程中，synchronized和volatile都扮演着重要的角色，volatile是轻量级的sychronized，它在多处理器开发中保证了共享变量的“可见性”。可见性的意思是当一个线程修改一个共享变量时，另外一个线程能读到这个修改的值。 如果volatile变量修饰符使用恰当的话，它比sychronized的使用和执行成本更低，因为它不会引起线程上下文的切换和调度。
2.1.1 volatile的定义与实现原理
定义：如果一个字段被声明成 volatile，Java线程内存模型确保所有线程看到这个变量的值是一致的。
CPU术语：
- 内存屏障：是一组处理器命令，用于实现对内存操作的顺序限制
- 缓冲行 ：CPU高速缓存中可以分配的最小存储单位。处理器填写缓存行时会加载整个缓存行，现代CPU需要执行几百次CPU指令。
- 原子操作：不可中断的一个或一系列操作。
- 缓存行填充：当处理器识别到从内存中读取操作数是可缓存的，处理器读取整个高速缓存行到适当的缓存。
- 缓存命中：如果进行高速缓存行填充操作的内存位置仍然是下次处理器访问的地址时，处理器从缓存中读取操作数，而不是从内存中读取。
- 写命中：当处理器将操作数写回到一个内存缓存的区域时，它首先会检查这个缓存的内存地址是否在缓存行中，如果存在一个有效的缓存行，则处理器将这个操作数写回到缓存。而不是写回到内存，这个操作被称为写命中。
- 写缺失：一个有效的缓存行被写入到不存在的内存区域。
为什么需要“可见性”？
为了提高处理速度，处理器不直接和内存进行通信，而是先将系统内存的数据读到内部缓存后再进行操作，但操作完不知道何时会写到内存。由于写回到内存这个操作的时机是不确定的，所以就可能造成该共享变量已经修改（但并未写回内存），但其他缓存器缓存的值还是旧的，再执行计算操作就会有问题。
volatile 的作用及原理？（两条实现原则）
使用volatile修饰的共享变量，会在编译时增加一个“Lock”的前缀指令，该指令会引发两件事情：
1）将当前处理器缓存行的数据立即写回系统内存。
2）这个写回内存的操作会使其他CPU里缓存了该内存地址的数据无效。
为了提高运行速度，CPU是不和内存直接通信的，而是把系统内存的数据缓存到内部缓存再进行操作，但操作后并不确定何时写回内存，而使用volatile修饰的变量会让CPU将当前缓存行立即写回内存。但即使在写回到内存后，其他CPU里缓存的数据仍然可能是旧值。所以，在多处理器下，就会实现缓存一致性协议来避免这个问题。每个处理器通过嗅探在总线上传播的数据来检查自己的缓存是否过期，当处理器发现自己缓存行对应的内存地址被修改，就会将当前缓存行设置为无效状态，当处理器需要对这个数据进行操作时，会重新从内存中读取（读到处理器缓存中）。
2.1.2 volatile的使用优化
追加字节优化性能：JDK7的并发包里新增一个队列集合类LinkedTransferQueue，它在使用volatile变量时，用一种追加字节的方式来优化队列出队和入队的性能。（将共享变量追加到64字节）
（一个对象的引用占4个子节，它追加了15个变量（共占60字节），再加上父类的value变量，共64字节）
为什么追加64字节能提高并发编程效率？
大部分处理器的L1、L2或L3缓存的高速缓存行是64个字节宽，不支持部分填充缓存行。若队列的头节点和尾节点都不足64字节时，头节点和尾节点会被读取到同一个缓存行中，在多处理器每个处理器都会缓存同样的头、尾节点。当一个处理器试图修改头节点时，需要锁定整个缓存行，那么在缓存一致性协议下，会导致其他处理器不能访问自己缓存中的尾节点（因为他的缓存已经无效，需要重新从内存中读取），而出队入队操作会不停的修改头节点和尾节点，会严重影响性能。所以采用追加到64字节来避免该问题。
【注】虽然追加字节的方式可以提高性能，但并不是所有场景都适用，下面两种情况就不适用：
- 缓存行非64字节宽的处理器
- 共享变量不会被频繁的写。如果共享变量不被频繁写的话，锁的几率也非常小，就没必要通过追加字节的方式来避免相互锁定。
2.2 synchronized 的实现原理与应用
这篇博客写的比较好https://blog.csdn.net/qq_24982291/article/details/78659072
synchronized实现同步的基础：Java中的每一个对象都可以作为锁。具体表现为以下3中形式：
- 对于普通同步方法，锁是当前实例对象。
- 对于静态同步方法，锁是当前类的Class对象。
- 对于同步方法块，锁是synchronized括号里配置的对象。
当一个线程试图访问同步代码块时，它首先必须得到锁，退出或抛出异常时必须释放锁。
synchronized在JVM里是怎么实现的？
每个对象都有一个monitor对象与之关联，JVM基于进入和退出Monitor对象来实现方法同步和代码同步。但两者实现细节不同。代码同步是使用monitorenter、monitorexit（这两个指令必须成对出现）指令实现。方法同步具体细节在JVM规范里并未说明，但通过这两个指令同样可以实现。
monitorenter指令是在编译后插入到同步代码块的开始位置，而monitorexit是插入到方法结束出和异常处，JVM要保证每个monitorenter必须有对应的monitorexit与之配对。任何对象都有一个monitor与之关联，并且一个monitor被持有后，它将处于锁定状态。线程执行到monitorenter指令时，将会尝试获取对象所对应的monitor的所有权，即尝试获得对象的锁。
synchronized用的锁是存在哪里的？
synchronized用到的锁是存在Java对象头里的。
2.2.1 Java对象头
Java对象保存在内存中时，由以下三部分组成：
- 对象头
- 实例数据
- 对齐填充字节
java的对象头由以下三部分组成：
- Mark Word ：存储对象的hashCode和锁信息等。
- 指向类的指针
- 数组长度（只有数组对象才有）
对象头的结构？
https://blog.csdn.net/lkforce/article/details/81128115
Java对象头在32位/64位系统中，分别使用8个字节及16个字节来表示。其中Mark Word占用4个字节（8个字节），Class Metadata Address（主要存储指向对象类型信息的指针）占用4个字节（8个字节）。
Mark Word在32位JVM中的长度是32bit，在64位JVM中长度是64bit。
Mark Word默认存储对象的hashCode、分代年龄、锁标记位。32位JVM的Mark Word默认存储结构：
在运行期间，Mark Word里存储的数据会随着锁标志位的变化而变化。对于不同的锁及其状态而言，4个字节不足以表示其信息，所以按照锁标志位的不同，来存储不同的信息。
2.2.2 锁的升级与对比
在Java SE 1.6中，锁一共有4种状态，级别从低到高依次是：无锁状态、偏向锁状态、轻量级锁状态、重量级锁状态。这几个状态会随着竞争情况逐渐升级。
锁可以升级但不能降级。（目的是为了提高获得锁和释放锁的效率）
（1）偏向锁
（a）偏向锁加锁过程：
当一个线程访问同步块并获取锁时，会在对象头和栈帧中的锁记录存储偏向的线程ID，以后该线程再进入和退出同步块时只需要检测对象头中Mark Word中是否存储当前线程的ID即可，而不需要进行CAS操作来进行加锁和解锁操作。如果测试成功，则获得锁；若测试失败，则检测Mark Word中锁标志位是否设置为01，如果为01，则进行CAS操作将对象头偏向锁存储的线程ID指向当前线程，若不为01，则使用CAS竞争锁。
（b）偏向锁解锁过程：
偏向锁使用一种等到竞争出现才释放锁的机制。偏向锁的撤销，需要等待全局安全点（在这个时间点上没有正在执行的字节码）。它会首先暂停拥有偏向锁的线程，然后检查持有偏向锁的线程是否活着，如果线程不处于活动状态，则将对象头设置成无锁状态；如果线程仍然活着，拥有偏向锁的栈会被执行，遍历偏向对象的锁记录，栈中的锁记录和对象头的Mark Word要么重新偏向于其他线程，要么恢复到无锁或标记对象不适合作为偏向锁，最后唤醒暂停的线程。
（c）关闭偏向锁：
偏向所在Java6和Java7里是默认开启的，但是它在应用程序启动几秒钟后才激活，如果必要刻意使用JVM参数来关闭延迟：-XX:BiasedLockingStartUpDelay=0.或直接关闭偏向锁：-XX:-UseBiasedLocking=false。
（2）轻量级锁
（a）轻量级锁加锁：
线程在执行同步代码块之前，JVM会先在当前线程的栈帧中创建用于存储锁记录的空间，并将对象头中的Mark Word复制到锁记录中（DIsplaced Mark Word）。然后线程尝试使用CAS将对象头中的Mark Word替换为指向锁记录的指针。如果成功，则获得锁。如果失败，则表示有其他线程竞争锁，当前线程尝试使用自旋来获取锁。
（b）轻量级锁解锁：
在解锁时，会使用原子的CAS操作将DIsplaced Mark Word替换回对象头，如果成功，则表示没有竞争发生。如果失败，则表示当前所存在竞争，锁会膨胀为重量级锁。竞争该锁的线程全部会阻塞，知道当前线程释放该锁。
（3）锁的优缺点对比
2.3 原子操作的实现原理
原子操作意思是“不可被中断的一个或一系列操作”。
2.3.1 处理器如何实现原子操作？
（总线加锁 或 缓存加锁）
（1）使用总线锁保证原子性：当一个处理器使用总线时，在总线上输出LOCK#信号，其他处理器使用总线操作该共享内存的请求就会被阻塞，那么该处理器可以独占共享内存，从而保证操作的原子性。
（2）使用缓存锁保证原子性：当一个处理器对缓存行中的共享变量进行操作时，通过缓存一致性协议，让其他处理器中缓存中的该共享变量无效，从而保证操作的原子性。
在同一时刻，我们只需保证对某个内存地址的操作是原子性即可，但总线锁定把CPU和内存之间的通信锁住了，这使得在锁定期间，其他处理器不能操作其他内存地址的数据，所以总线开销比较大，目前处理器在某些场合下使用缓存锁定代替总线锁定来进行优化。（频繁使用的内存会缓存在处理器的L1、L2和L3高速缓存里，那么原子操作就可以直接在处理器内部缓存中进行。）
【注】有两种情况下处理器不会使用缓存锁定：
第一种情况是：当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行时，则处理器会调用总线锁定。
第二种情况是：有些处理器不支持缓存锁定。
2.3.2 Java如何实现原子操作？
（通过 锁 或 循环CAS的方式 实现）
（1）通过循环CAS实现原子操作：循环进行CAS操作直到成功为止。
（2）使用锁机制实现原子操作：保证只有获得锁的线程才能操作锁定的内存区域。 JVM内部实现了很多种锁机制，有偏向锁、轻量级锁和互斥锁。除了偏向锁，JVM实现锁的方式都用了循环CAS，即当一个线程想进入同步块的时候使用循环CAS的方式来获取锁，当它退出同步块的时候使用循环CAS释放锁。
CAS实现原子操作的三大问题：
- ABA问题：若共享变量修改过程为A->B->A，虽然值发生过更改，但使用CAS进行检查时会发现它的值没有发生变化。解决方法是在变量前追加版本号。1A->2B->3A。
- 循环时间长开销大：自旋CAS如果长时间不成功，会给CPU带来很大的开销。
- 只能保证一个共享变量的原子操作：对多个共享变量操作时，循环CAS就无法保证操作的原子性。