并发编程的挑战

上下文切换

任务从保存到再加载的过程就是一次上下文切换
单核处理器通过给每个线程分配CPU时间片来实现多线程
减少上下文切换的方法有无锁并发编程、CAS算法、使用最少线程和使用协程。

死锁

避免死锁

避免一个线程同时获取多个锁
避免一个线程在锁内同时占用多个资源，尽量保证每个锁只占用一个资源
尝试使用定时锁，使用lock.tryLock（timeout）来替代使用内部锁机制
对于数据库锁，加锁和解锁必须在一个数据库连接里，否则会出现解锁失败的情况

资源限制的挑战

概念

资源限制是指在进行并发编程时，程序的执行速度受限于计算机硬件资源或软件资源。

硬件资源限制

带宽的上传/下载速度、硬盘读写速度和CPU的处理速度

软件资源限制

数据库的连接数和socket连接数等

资源限制引发的问题

在并发编程中，将代码执行速度加快的原则是将代码中串行执行的部分变成并发执行
并行会增加上下文切换和资源调度的时间

解决资源限制问题

对于硬件资源限制

采用集群并行执行程序

对于软件资源限制

可以考虑使用资源池将资源复用。比如使用连接池将数据库和Socket连接复用，或者在调用对方webservice接口获取数据时，只建立一个连接

Java并发编程的底层实现原理

volatile的应用

如果对声明了volatile的变量进行写操作，JVM就会向处理器发送一条Lock前缀的指令，将这个变量所在缓存行的数据写回到系统内存
在多处理器下，为了保证各个处理器的缓存是一致的，就会实现缓存一致性协议。每个处理器通过嗅探在总线上传播的数据来检查自己的缓存是否过期，如果过期，将当前缓存行设置成无效状态。后续修改该数据时，重新从系统中把数据读到缓存中。

volatile两条实现原则

Lock前缀指令会引起处理器缓存回写到内存

在多处理器环境中，LOCK#信号确保在声言该信号期间，处理器可以独占任何共享内存；LOCK＃信号一般不锁总线，而是锁缓存

一个处理器的缓存回写到内存会导致其他处理器的缓存无效

处理器使用嗅探技术保证它的内部缓存、系统内存和其他处理器的缓存的数据在总线上保持一致 ;

volatile使用优化

追加字节性能优化（队列集合类LinkedTransferQueue ）

追加64字节能够提高并发编程的效率：因为对于英特尔酷睿i7、酷睿、Atom和NetBurst，以及Core Solo和Pentium M处理器的L1、L2或L3缓存的高速缓存行是64个字节宽，不支持部分填充缓存行，这意味着，如果队列的头节点和尾节点都不足64字节的话，处理器会将它们都读到同一个高速缓存行中。而填充到64字节，避免头节点和尾节点加载到同一个缓存行，使头、尾节点在修改时不会互相锁定。

synchronized的实现原理与应用

Java中锁的三种形式

对于普通同步方法，锁是当前实例对象。
对于静态同步方法，锁是当前类的Class对象。
对于同步方法块，锁是Synchonized括号里配置的对象

JVM实现Synchonized原理

JVM基于进入和退出Monitor对象来实现方法同步和代码块同步，但两者的实现细节不一样
代码块同步是使用monitorenter和monitorexit指令实现的，而方法同步是使用另外一种方式实现的
monitorenter指令是在编译后插入到同步代码块的开始位置，而monitorexit是插入到方法结束处和异常处，JVM要保证每个monitorenter必须有对应的monitorexit与之配对。任何对象都有一个monitor与之关联，当且一个monitor被持有后，它将处于锁定状态。线程执行到monitorenter指令时，将会尝试获取对象所对应的monitor的所有权，即尝试获得对象的锁。

java对象头

synchronized用的锁是存在Java对象头里的。如果对象是数组类型，则虚拟机用3个字宽（Word）存储对象头，如果对象是非数组类型，则用2字宽存储对象头
Java对象头里的Mark Word里默认存储对象的HashCode、分代年龄和锁标记位
锁标志位：00 -- 轻量级锁；10 -- 重量级锁；11 -- GC 标记； 101 -- 偏向锁； 001 -- 无锁

锁升级与对比

锁的四种状态

级别从低到高依次是：无锁状态、偏向锁状态、轻量级锁状态和重量级锁状态，锁可以升级但不能降级。

偏向锁

为了让线程获得锁的代价更低而引入了偏向锁。
当一个线程访问同步块并获取锁时，会在对象头和栈帧中的锁记录里存储锁偏向的线程ID，以后该线程在进入和退出同步块时不需要进行CAS操作来加锁和解锁，只需简单地测试一下对象头的Mark Word里是否存储着指向当前线程的偏向锁。如果测试成功，表示线程已经获得了锁。如果测试失败，则需要再测试一下Mark Word中偏向锁的标识是否设置成1（表示当前是偏向锁）：如果没有设置，则使用CAS竞争锁；如果设置了，则尝试使用CAS将对象头的偏向锁指向当前线程
偏向锁的撤销

偏向锁使用了一种等到竞争出现才释放锁的机制，所以当其他线程尝试竞争偏向锁时，持有偏向锁的线程才会释放锁。偏向锁的撤销，需要等待全局安全点（在这个时间点上没有正在执行的字节码）。它会首先暂停拥有偏向锁的线程，然后检查持有偏向锁的线程是否活着，如果线程不处于活动状态，则将对象头设置成无锁状态；如果线程仍然活着，拥有偏向锁的栈会被执行，遍历偏向对象的锁记录，栈中的锁记录和对象头的Mark Word要么重新偏向于其他线程，要么恢复到无锁或者标记对象不适合作为偏向锁，最后唤醒暂停的线程

关闭偏向锁

偏向锁在应用程序启动后几秒钟后**，jvm关闭延迟：-XX:BiasedLockingStartupDelay=0

JVM关闭偏向锁：-XX:-UseBiasedLocking=false

轻量级锁

轻量级锁加锁

线程在执行同步块之前，jvm会在当前线程的栈帧中创建存储锁记录的空间，并将对象头中的mark word 复制到锁记录中。然后线程尝试使用CAS将对象头中的Mark Word替换为指向锁记录的指针。如果成功，当前线程获得锁，如果失败，表示其他线程竞争锁，当前线程便尝试使用自旋来获取锁

轻量级锁解锁

轻量级解锁时，会使用原子的CAS操作将Displaced Mark Word替换回到对象头，如果成功，则表示没有竞争发生。如果失败，表示当前锁存在竞争，锁就会膨胀成重量级锁

锁的优点比较

原子操作的实现原理

原子操作概念：

不可被中断的一个或一系列操作

多处理器实现原子操作

32位IA-32处理器使用基于对缓存加锁或总线加锁的方式来实现多处理器之间的原子操作
Pentium 6和最新的处理器能自动保证单处理器对同一个缓存行里进行16/32/64位的操作是原子的，但是复杂的内存操作处理器是不能自动保证其原子性的，比如跨总线宽度、跨多个缓存行和跨页表的访问。但是，处理器提供总线锁定和缓存锁定两个机制来保证复杂内存操作的原子性
锁总线

所谓总线锁就是使用处理器提供的一个LOCK＃信号，当一个处理器在总线上输出此信号时，其他处理器的请求将被阻塞住，那么该处理器可以独占共享内存

锁缓存
- 频繁使用的内存会缓存在处理器的L1、L2和L3高速缓存里，那么原子操作就可以直接在处理器内部缓存中进行
- 所谓“缓存锁定”是指内存区域如果被缓存在处理器的缓存行中，并且在Lock操作期间被锁定，那么当它执行锁操作回写到内存时，处理器不在总线上声言LOCK＃信号，而是修改内部的内存地址，并允许它的缓存一致性机制来保证操作的原子性

两种情况下处理器不会使用缓存锁定
- 当操作的数据不能被缓存在处理器内部，或操作的数据跨多个缓存行（cache line）时，则处理器会调用总线锁定
- 第二种情况是：有些处理器不支持缓存锁定。对于Intel 486和Pentium处理器，就算锁定的内存区域在处理器的缓存行中也会调用总线锁定

java如何实现原子操作

Java中可以通过锁和循环CAS的方式来实现原子操作

循环CAS实现原子操作

JDK的并发包里提供了一些类来支持原子操作，如AtomicBoolean（用原子方式更新的boolean值）、AtomicInteger（用原子方式更新的int值）和AtomicLong（用原子方式更新的long值）。这些原子包装类还提供了有用的工具方法，比如以原子的方式将当前值自增1和自减1
CAS实现原子操作的三大问题
- ABA问题：线程1对变量ans进行CAS的时候，线程2也取出ans的值A，修改成B，然后又修改成了A。当线程1打算将修改值写入ans的时候，看到的ans值没有变化。一般这种值的变化没有什么影响，如果变量ans中间值修改需要被感知。可以通过给ans的值添加一个版本号，或是一个boolean状态判断ans值是否被修改过
- 循环时间长、开销大。自旋CAS如果长时间不成功，会给CPU带来非常大的执行开销
- 只能保证一个共享变量的原子操作：JDK提供了AtomicReference类来保证引用对象之间的原子性，就可以把多个变量放在一个对象里来进行CAS操作
使用锁机制实现原子操作
- 锁机制保证了只有获得锁的线程才能够操作锁定的内存区域
- JVM内部实现了很多种锁机制，有偏向锁、轻量级锁和互斥锁
- JVM实现锁的方式都用了循环CAS

java 内存模型

java内存模型的基础

在命令式编程中，线程之间的通信机制有两种：共享内存和消息传递
在共享内存并发模型里，同步是显式进行的
消息传递的并发模型里，同步是隐式进行的
Java的并发采用的是共享内存模型，Java线程之间的通信总是隐式进行，整个通信过程对程序员完全透明
Java中，所有实例域、静态域和数组元素都存储在堆内存中，堆内存在线程之间共享
局部变量（Local Variables），方法定义参数（Java语言规范称之为Formal Method Parameters）和异常处理器参数（ExceptionHandler Parameters）不会在线程之间共享
线程之间的共享变量存储在主内存（Main Memory）中，每个线程都有一个私有的本地内存（Local Memory），本地内存中存储了该线程以读/写共享变量的副本。本地内存是JMM的一个抽象概念，并不真实存在
JMM通过控制主内存与每个线程的本地内存之间的交互，来为Java程序员提供内存可见性保证
重排序是指编译器和处理器为了优化程序性能而对指令序列进行重新排序的一种手段
指令重排序：
- 编译器优化的重排序
- 指令级并行的重排序
- 内存系统的重排序
指令并行重排序和内存系统重排序属于处理器重排序，可能会导致多线程程序出现内存可见性问题
处理器重排序，JMM的处理器重排序规则会要求Java编译器在生成指令序列时，插入特定类型的内存屏障（Memory Barriers，Intel称之为Memory Fence）指令，通过内存屏障指令来禁止特定类型的处理器重排序
内存屏障类型

StoreLoad Barriers是一个“全能型”的屏障，它同时具有其他3个屏障的效果
happens-before规则
- 程序顺序规则：一个线程中的每个操作，happens-before于该线程中的任意后续操作
- 监视器锁规则：对一个锁的解锁，happens-before于随后对这个锁的加锁
- volatile变量规则：对一个volatile域的写，happens-before于任意后续对这个volatile域的读
- 传递性：如果A happens-before B，且B happens-before C，那么A happens-before C
- start()规则：如果线程A执行操作ThreadB.start()（启动线程B），那么A线程的ThreadB.start()操作happens-before于线程B中的任意操作
- join()规则：如果线程A执行操作ThreadB.join()并成功返回，那么线程B中的任意操作happens-before于线程A从ThreadB.join()操作成功返回
两个操作之间具有happens-before关系，并不意味着前一个操作必须要在后一个操作之前执行！ happens-before仅仅要求前一个操作（执行的结果）对后一个操作可见，且前一个操作按顺序排在第二个操作之前

 int a = 3;
 int volatile b = 1;
 
 public void write() {
     a = 5;
     b = a;
 }
 
 public void read() {
     System.out.println(a + "--" + b);
 }
 
 // 线程t1 执行write()
 // 线程t2 执行read()
 /**
 程序顺序规则可知，a happens-before b; 所以t2读取的b的值为5，a一定为5
 但是不能确定读取b的时候，b已经被赋予最新值！！！
 */

as-if-serial语义的意思是：不管怎么重排序（编译器和处理器为了提高并行度），（单线程）程序的执行结果不能被改变。编译器、runtime和处理器都必须遵守as-if-serial语义
程序顺序规则

这里A happens-before B ;B happens-before C;A happens-before C; 这里操作A的执行结果不需要对操作B可见；而且重排序操作A和操作B后的执行结果，与操作A和操作B按happens-before顺序执行的结果一致。在这种情况下，JMM会认为这种重排序并不非法（not illegal），JMM允许这种重排序

顺序一致性

JMM对正确同步的多线程程序的内存一致性做了如下保证

如果程序是正确同步的，程序的执行将具有顺序一致性（Sequentially Consistent）——即程序的执行结果与该程序在顺序一致性内存模型中的执行结果相同（同步是指广义上的同步，包括对常用同步原语（synchronized、volatile和final）的正确使用）

顺序一致性内存模型有两大特性
- 一个线程中的所有操作必须按照程序的顺序来执行
- （不管程序是否同步）所有线程都只能看到一个单一的操作执行顺序。在顺序一致性内存模型中，每个操作都必须原子执行且立刻对所有线程可见
临界区：临界区就是在同一时刻只能有一个任务访问的代码区（例如加锁的代码块）
JMM会在退出临界区和进入临界区这两个关键时间点做一些特别处理，使得线程在这两个时间点具有与顺序一致性模型相同的内存视图
对于未同步或未正确同步的多线程程序，JMM只提供最小安全性,保证线程读操作读取到的值不会无中生有.为了实现最小安全性，JVM在堆上分配对象时，首先会对内存空间进行清零，然后才会在上面分配对象（JVM内部会同步这两个操作）
JMM不保证未同步程序的执行结果与该程序在顺序一致性模型中的执行结果一致(原因：保证一致性会影响程序执行性能，保证一致性也没有意义)
JMM不保证对64位的long型和double型变量的写操作具有原子性
处理器与内存之前数据传递通过一系列步骤来完成，称为总线事务（总线事务包括读事务（Read Transaction）和写事务（Write Transaction））
在任意时间点，最多只能有一个处理器可以访问内存。这个特性确保了单个总线事务之中的内存读/写操作具有原子性

volatile的内存语义

即使是64位的long型和double型变量，只要它是volatile变量，对该变量的读/写就具有原子性
如果是多个volatile操作或类似于volatile++这种复合操作，这些操作整体上不具有原子性
volatile变量自身具有下列特性
- 可见性。对一个volatile变量的读，总是能看到（任意线程）对这个volatile变量最后的写入
- 原子性：对任意单个volatile变量的读/写具有原子性，但类似于volatile++这种复合操作不具有原子性
volatile 重排序规则表

volatile写-读内存语义的常见使用模式是：一个写线程写volatile变量，多个读线程读同一个volatile变量。当读线程的数量大大超过写线程时，选择在volatile写之后插入StoreLoad屏障将带来可观的执行效率的提升
由于volatile仅仅保证对单个volatile变量的读/写具有原子性，而锁的互斥执行的特性可以确保对整个临界区代码的执行具有原子性。在功能上，锁比volatile更强大；在可伸缩性和执行性能上，volatile更有优势

锁的内存语义

锁释放与volatile写有相同的内存语义；锁获取与volatile读有相同的内存语义
线程A释放锁，随后线程B获取这个锁，这个过程实质上是线程A通过主内存向线程B发送消息
在常见的intel X86处理器中，CAS是如何同时具有volatile读和volatile写的内存语义的
- 如果程序是在多处理器上运行，就为cmpxchg指令加上lock前缀（Lock Cmpxchg）
- 如果程序是在单处理器上运行，就省略lock前缀（单处理器自身会维护单处理器内的顺序一致性，不需要lock前缀提供的内存屏障效果）
公平锁和非公平锁的内存语义总结
- 公平锁和非公平锁释放时，最后都要写一个volatile变量state
- 公平锁获取时，首先会去读volatile变量
- 非公平锁获取时，首先会用CAS更新volatile变量，这个操作同时具有volatile读和volatile写的内存语义
Java线程之间的通信现在有了下面4种方式
- A线程写volatile变量，随后B线程读这个volatile变量
- A线程写volatile变量，随后B线程用CAS更新这个volatile变量
- A线程用CAS更新一个volatile变量，随后B线程用CAS更新这个volatile变量
- A线程用CAS更新一个volatile变量，随后B线程读这个volatile变量
concurrent包通用化的实现模式
- 首先，声明共享变量为volatile
- 然后，使用CAS的原子条件更新来实现线程之间的同步
- 同时，配合以volatile的读/写和CAS所具有的volatile读和写的内存语义来实现线程之间的通信

final域的内存语义

于final域，编译器和处理器要遵守两个重排序
- 在构造函数内对一个final域的写入，与随后把这个被构造对象的引用赋值给一个引用变量，这两个操作之间不能重排序（写final域的重排序规则禁止把final域的写重排序到构造函数之外）
  - JMM禁止编译器把final域的写重排序到构造函数之外
  - 编译器会在final域的写之后，构造函数return之前，插入一个StoreStore屏障。这个屏障禁止处理器把final域的写重排序到构造函数之外
- 初次读一个包含final域的对象的引用，与随后初次读这个final域，这两个操作之间不能重排序
  - 读final域的重排序规则是，在一个线程中，初次读对象引用与初次读该对象包含的final域，JMM禁止处理器重排序这两个操作（注意，这个规则仅仅针对处理器）。编译器会在读final域操作的前面插入一个LoadLoad屏障
  - 初次读对象引用与初次读该对象包含的final域，这两个操作之间存在间接依赖关系

writer()函数的执行包含两步：1）构造一个FinalExample类型的对象；2）把这个对象的引用赋值给引用变量obj。规则1可以保证先执行第一步，然后执行第二步

读final域的重排序规则可以确保：在读一个对象的final域之前，一定会先读包含这个final域的对象的引用。在这个示例程序中，如果该引用不为null，那么引用对象的final域一定已经被A线程初始化过了

final域为引用类型
- 在构造函数内对一个final引用的对象的成员域的写入，与随后在构造函数外把这个被构造对象的引用赋值给一个引用变量，这两个操作之间不能重排序

双重检查锁

单例案例

单线程案例

 public class UnsafeLazyInitialization {
     private static Instance instance;
     public static Instance getInstance() {
         if (instance == null)
             instance = new Instance();
         return instance;
     }
 }

多线程中标准答案

加粗锁（性能开销大）

 public class SafeLazyInitialization {
     private static Instance instance;
     public synchronized static Instance getInstance() {
         if (instance == null)
             instance = new Instance();
         return instance;
     }
 }

双重检查锁定（错误优化）

 public class DoubleCheckedLocking { // 1
     private static Instance instance; // 2
     public static Instance getInstance() { // 3
         if (instance == null) { // 4:第一次检查
             synchronized (DoubleCheckedLocking.class) { // 5:加锁
                 if (instance == null) // 6:第二次检查
                     instance = new Instance(); // 7:问题的根源出在这里
              } // 8
         } // 9
         return instance; // 10
     } // 11
 }

问题原因：instance = new Instance(); 代码可以分解为下面三行

 memory = allocate(); // 1：分配对象的内存空间
 ctorInstance(memory); // 2：初始化对象
 instance = memory; // 3：设置instance指向刚分配的内存地址

当线程A调用getInstance()方法时，到达步骤4，条件成立，进入并获取锁，但是当执行步骤7的时候，发生了指令重排序：

 memory = allocate(); // 1：分配对象的内存空间
 instance = memory; // 3：设置instance指向刚分配的内存地址
 ctorInstance(memory); // 2：初始化对象

并且当A线程执行到 instance = memory; 没有执行ctorInstance(memory);时，线程B也访问getInstance() 方法，这时候线程B获取的instance 是未成功初始化的。

基于volatile的双重检查锁定

 public class SafeDoubleCheckedLocking {
     private volatile static Instance instance;
     public static Instance getInstance() {
         if (instance == null) {
             synchronized (SafeDoubleCheckedLocking.class) {
                 if (instance == null)
                     instance = new Instance(); // instance为volatile，现在没问题了
             }
         }
         return instance;
     }
 }

基于类初始化的解决方案

 public class InstanceFactory {
     private static class InstanceHolder {
         public static Instance instance = new Instance();
     }
     public static Instance getInstance() {
         return InstanceHolder.instance ; // 这里将导致InstanceHolder类被初始化
     }
 }

JVM在类的初始化阶段（即在Class被加载后，且被线程使用之前），会执行类的初始化。在执行类的初始化期间，JVM会去获取一个锁。这个锁可以同步多个线程对同一个类的初始化
初始化一个类，包括执行这个类的静态初始化和初始化在这个类中声明的静态字段.据Java语言规范，在首次发生下列任意一种情况时，一个类或接口类型T将被立即初始化 :
- T是一个类，而且一个T类型的实例被创建
- T是一个类，且T中声明的一个静态方法被调用
- T中声明的一个静态字段被赋值
- T中声明的一个静态字段被使用，而且这个字段不是一个常量字段
但基于volatile的双重检查锁定的方案有一个额外的优势：除了可以对静态字段实现延迟初始化外，还可以对实例字段实现延迟初始化。

内存模型综述

越是追求性能的处理器，内存模型设计得会越弱。因为这些处理器希望内存模型对它们的束缚越少越好，这样它们就可以做尽可能多的优化来提高性能
最小安全性保证线程读取到的值不会无中生有的冒出来，但并不保证线程读取到的值一定是正确的

java并发编程基础

线程简介

操作系统调度的最小单元是线程
在一个进程里可以创建多个线程，这些线程都拥有各自的计数器、堆栈和局部变量等属性，并且能够访问共享的内存变量
为什么使用多线程
- 更多的处理器核心：一个线程在一个时刻只能运行在一个处理器核心上
- 更快的响应时间：可以使用多线程技术，即将数据一致性不强的操作派发给其他线程处理
- 更好的编程模型：Java为多线程编程提供了良好、考究并且一致的编程模型，使开发人员能够更加专注于问题的解决
线程优先级：在Java线程中，通过一个整型成员变量priority来控制优先级，优先级的范围从1~10，在线程构建的时候可以通过setPriority(int)方法来修改优先级，默认优先级是5，优先级高的线程分配时间片的数量要多于优先级低的线程
Java线程的状态

Java线程状态变迁

Daemon线程是一种支持型线程，因为它主要被用作程序中后台调度以及支持性工作。这意味着，当一个Java虚拟机中不存在非Daemon线程的时候，Java虚拟机将会退出。可以通过调用Thread.setDaemon(true)将线程设置为Daemon线程
Daemon属性需要在启动线程之前设置，不能在启动线程之后设置
Daemon线程被用作完成支持性工作，但是在Java虚拟机退出时Daemon线程中的finally块并不一定会执行

启动和终止线程

线程start()方法的含义是：当前线程（即parent线程）同步告知Java虚拟机，只要线程规划器空闲，应立即启动调用start()方法的线程
理解中断
- 中断可以理解为线程的一个标识位属性，它表示一个运行中的线程是否被其他线程进行了中断操作
- 线程通过方法isInterrupted()来进行判断是否被中断，也可以调用静态方法Thread.interrupted()对当前线程的中断标识位进行复位。如果该线程已经处于终结状态，即使该线程被中断过，在调用该线程对象的isInterrupted()时依旧会返回false
- 从Java的API中可以看到，许多声明抛出InterruptedException的方法（例如Thread.sleep(long millis)方法）这些方法在抛出InterruptedException之前，Java虚拟机会先将该线程的中断标识位清除，然后抛出InterruptedException，此时调用isInterrupted()方法将会返回false
过期的suspend()、resume()和stop()
- suspend()、resume()和stop()方法完成了线程的暂停、恢复和终止工作，不建议使用的原因主要有
  - suspend()方法为例，在调用后，线程不会释放已经占有的资源（比如锁），而是占有着资源进入睡眠状态，这样容易引发死锁问题
  - stop()方法在终结一个线程时不会保证线程的资源正常释放，通常是没有给予线程完成资源释放工作的机会，因此会导致程序可能工作在不确定状态下
父线程通过中断操作和cancel()方法均可使子线程得以终止，更加安全和优雅

线程间通信

任意一个对象都拥有自己的监视器，当这个对象由同步块或者这个对象的同步方法调用时，执行方法的线程必须先获取到该对象的监视器才能进入同步块或者同步方法，而没有获取到监视器（执行该方法）的线程将会被阻塞在同步块和同步方法的入口处，进入BLOCKED状态
等待/通知的相关方法
使用wait()、notify()和notifyAll()时需要先对调用对象加锁
调用wait()方法后，线程状态由RUNNING变为WAITING，并将当前线程放置到对象的等待队列
notify()或notifyAll()方法调用后，等待线程依旧不会从wait()返回，需要调用notify()或notifAll()的线程释放锁之后，等待线程才有机会从wait()返回
notify()方法将等待队列中的一个等待线程从等待队列中移到同步队列中，而notifyAll()方法则是将等待队列中所有的线程全部移到同步队列，被移动的线程状态由WAITING变为BLOCKED
从wait()方法返回的前提是获得了调用对象的锁
等待/通知的经典范式：等待方（消费者）和通知方（生产者）
- 等待方遵循如下原则
  - 获取对象的锁
  - 如果条件不满足，那么调用对象的wait()方法，被通知后仍要检查条件
  - 条件满足则执行对应的逻辑
- 通知方遵循如下原则
  - 获得对象的锁
  - 改变条件
  - 通知所有等待在对象上的线程
管道输入/输出流和普通的文件输入/输出流或者网络输入/输出流不同之处在于，它主要用于线程之间的数据传输，而传输的媒介为内存
管道输入/输出流主要包括了如下4种具体实现：PipedOutputStream、PipedInputStream、PipedReader和PipedWriter，前两种面向字节，而后两种面向字符
对于Piped类型的流，必须先要进行绑定，也就是调用connect()方法，如果没有将输入/输出流绑定起来，对于该流的访问将会抛出异常

 PipedWriter out = new PipedWriter();
 PipedReader in = new PipedReader();
 // 将输出流和输入流进行连接，否则在使用时会抛出IOException
 out.connect(in);

Thread.sleep(): 睡眠一段时间
Thread.yield(): 让出一下cpu,进入等待队列中，等待cpu调度
在t1中调用t2.join(): 在t1中调用t2线程，等待t2执行完，再回来执行t1。可以保证线程直接的执行顺序。除了提供join()方法之外，还提供了join(long millis)和join(long millis,int nanos)两个具备超时特性的方法,这两个超时方法表示，如果线程t2在给定的超时时间里没有终止，那么将会从该超时方法中返回如下图
ThreadLocal，即线程变量，是一个以ThreadLocal对象为键、任意对象为值的存储结构

Java中的锁

Lock接口

lock提供了与synchronized关键字类似的同步功能，只是在使用时需要显式地获取和释放锁。虽然它缺少了（通过synchronized块或者方法所提供的）隐式获取释放锁的便捷性，但是却拥有了锁获取与释放的可操作性、可中断的获取锁以及超时获取锁等多种synchronized关键字所不具备的同步特性
Lock接口提供的synchronized关键字不具备的主要特性

lock接口定义了锁获取和释放的基本操作

队列同步器

队列同步器AbstractQueuedSynchronizer ，是用来构建锁或者其他同步组件的基础框架，它使用了一个int成员变量表示同步状态，通过内置的FIFO队列来完成资源获取线程的排队工作
同步器的主要使用方式是继承，子类通过继承同步器并实现它的抽象方法来管理同步状态
同步器既可以支持独占式地获取同步状态，也可以支持共享式地获取同步状态
锁是面向使用者的，它定义了使用者与锁交互的接口（比如可以允许两个线程并行访问），隐藏了实现细节；同步器面向的是锁的实现者，它简化了锁的实现方式，屏蔽了同步状态管理、线程的排队、等待与唤醒等底层操作
同步器提供的如下3个方法来访问或修改同步状态
- getState()：获取当前同步状态
- setState(int newState)：设置当前同步状态
- compareAndSetState(int expect,int update)：使用CAS设置当前状态，该方法能够保证状态设置的原子性
同步器可重写的方法

同步器提供的模板方法

同步器提供的模板方法基本上分为3类：独占式获取与释放同步状态、共享式获取与释放同步状态和查询同步队列中的等待线程情况
独占锁就是在同一时刻只能有一个线程获取到锁，而其他获取锁的线程只能处于同步队列中等待，只有获取锁的线程释放了锁，后继的线程才能够获取锁
同步队列

同步器依赖内部的同步队列（一个FIFO双向队列）来完成同步状态的管理，当前线程获取同步状态失败时，同步器会将当前线程以及等待状态等信息构造成为一个节点（Node）并将其加入同步队列，同时会阻塞当前线程，当同步状态释放时，会把首节点中的线程唤醒，使其再次尝试获取同步状态

同步队列中的节点（Node）用来保存获取同步状态失败的线程引用、等待状态以及前驱和后继节点

同步器拥有首节点（head）和尾节点（tail），没有成功获取同步状态的线程将会成为节点加入该队列的尾部
同步器提供了一个基于CAS的设置尾节点的方法：compareAndSetTail(Node expect,Node update)，它需要传递当前线程“认为”的尾节点和当前节点
同步队列遵循FIFO，首节点是获取同步状态成功的节点，首节点的线程在释放同步状态时，将会唤醒后继节点，而后继节点将会在获取同步状态成功时将自己设置为首节点
设置头节点的方法并不需要使用CAS来保证，因为只有一个线程能够成功获取到同步状态
独占式同步状态获取和释放过程总结

在获取同步状态时，同步器维护一个同步队列，获取状态失败的线程都会被加入到队列中并在队列中进行自旋；移出队列（或停止自旋）的条件是前驱节点为头节点且成功获取了同步状态。在释放同步状态时，同步器调用tryRelease(int arg)方法释放同步状态，然后唤醒头节点的后继节点

重入锁

重入锁ReentrantLock，顾名思义，就是支持重进入的锁，它表示该锁能够支持一个线程对资源的重复加锁
如果在绝对时间上，先对锁进行获取的请求一定先被满足，那么这个锁是公平的，反之，是不公平的
ReentrantLock提供了一个构造函数，能够控制锁是否是公平的
公平的锁机制往往没有非公平的效率高

读写锁

读写锁在同一时刻可以允许多个读线程访问，但是在写线程访问时，所有的读线程和其他写线程均被阻塞
读写锁能够简化读写交互场景的编程方式
Java的等待通知机制，就是当写操作开始时，所有晚于写操作的读操作均会进入等待状态，只有写操作完成并进行通知之后，所有等待的读操作才能继续执行
在读多于写的情况下，读写锁能够提供比排它锁更好的并发性和吞吐量。Java并发包提供读写锁的实现是ReentrantReadWriteLock
ReentrantReadWriteLock展示内部工作状态的方法

读写锁的自定义同步器需要在同步状态（一个整型变量）上维护多个读线程和一个写线程的状态，使得该状态的设计成为读写锁实现的关键
读写锁通过位运算迅速确定读和写的各自状态
读状态是所有线程获取读锁次数的总和，而每个线程各自获取读锁的次数只能选择保存在ThreadLocal中
锁降级指的是写锁降级成为读锁
当前线程获取写锁完成数据准备之后，再获取读锁，随后释放写锁，完成锁降级。这是为了保证数据的可见性
RentrantReadWriteLock不支持锁升级
当需要阻塞或唤醒一个线程的时候，都会使用LockSupport工具类来完成相应工作
LockSupport提供的阻塞和唤醒方法

Condition

Condition定义了等待/通知两种类型的方法，当前线程调用这些方法时，需要提前获取到Condition对象关联的锁。Condition对象是由Lock对象（调用Lock对象的newCondition()方法）创建出来的，换句话说，Condition是依赖Lock对象的
Condition的（部分）方法以及描述

有界队列是一种特殊的队列，当队列为空时，队列的获取操作将会阻塞获取线程，直到队列中有新增元素，当队列已满时，队列的插入操作将会阻塞插入线程，直到队列出现“空位”
每个Condition对象都包含着一个队列（以下称为等待队列），该队列是Condition对象实现等待/通知功能的关键
如果一个线程调用了Condition.await()方法，那么该线程将会释放锁、构造成节点加入等待队列并进入等待状态
同步队列和等待队列中节点类型都是同步器的静态内部类AbstractQueuedSynchronizer.Node
Condition更新尾节点没有使用CAS保证，原因在于调用await()方法的线程必定是获取了锁的线程，也就是说该过程是由锁来保证线程安全的

java并发容器和框架

ConcurrentHashMap的实现原理与使用

ConcurrentHashMap是线程安全且高效的HashMap （在并发编程中使用HashMap可能导致程序死循环。而使用线程安全的HashTable效率又非常低下）
多线程会导致HashMap的Entry链表形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry
HashTable容器使用synchronized来保证线程安全，但在线程竞争激烈的情况下HashTable 的效率非常低下
ConcurrentHashMap所使用的锁分段技术：将数据分成一段一段地存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问
HashTable容器在竞争激烈的并发环境下表现出效率低下的原因是所有访问HashTable的线程都必须竞争同一把锁
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁（ReentrantLock）HashEntry则用于存储键值对数据。
一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁
为了能通过按位与的散列算法来定位segments数组的索引，必须保证segments数组的长度是2的N次方（power-of-two size）
segments数组的长度最大为65536
HashTable容器的get方法是需要加锁的，ConcurrentHashMap的get操作不加锁，原因是它的get方法里将要使用的共享变量都定义成volatile类型，如用于统计当前Segement大小的count字段和用于存储值的HashEntry的value
ConcurrentHashMap的put操作，需要加锁，插入步骤：第一步判断是否需要对Segment里的HashEntry数组进行扩容，第二步定位添加元素的位置，然后将其放在HashEntry数组里
创建一个容量是原来容量两倍的数组，然后将原数组里的元素进行再散列后插入到新的数组里。为了高效，ConcurrentHashMap不会对整个容器进行扩容，而只对某个segment进行扩容
ConcurrentHashMap的做法是先尝试2次通过不锁住Segment的方式来统计各个Segment大小，如果统计的过程中，容器的count发生了变化，则再采用加锁的方式来统计所有Segment的大小
ConcurrentHashMap 使用modCount变量，在put、remove和clean方法里操作元素前都会将变量modCount进行加1，那么在统计size前后比较modCount是否发生变化，从而得知容器的大小是否发生变化

ConcurrentLinkedQueue

实现一个线程安全的队列有两种方式：
- 一种是使用阻塞算法，另一种是使用非阻塞算法。使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现。
- 非阻塞的实现方式则可以使用循环CAS的方式来实现
ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部；当我们获取一个元素时，它会返回队列头部的元素。它采用了“wait-free”算法（即CAS算法）来实现
ConcurrentLinkedQueue由head节点和tail节点组成，每个节点（Node）由节点元素（item）和指向下一个节点（next）的引用组成，节点与节点之间就是通过这个next关联起来
入队（原理）
- 第一是将入队节点设置成当前队列尾节点的下一个节点
- 第二是更新tail节点，如果tail节点的next节点不为空，则将入队节点设置成tail节点，如果tail节点的next节点为空，则将入队节点设置成tail的next节点，所以tail节点不总是尾节点
入队（多线程源码）
- 第一是定位出尾节点（通过tail结点寻找尾节点）
- 第二是使用CAS算法将入队节点设置成尾节点的next节点，如不成功则重试
为何不让tail节点永远作为队列的尾节点
- 每次入队都使用循环CAS更新tail节点，效率比较低。使用hops变量来控制并减少tail节点更新的频率：当tail节点和尾节点的距离大于等于常量HOPS的值（默认等于1）时才更新tail节点，tail和尾节点的距离越长，使用CAS更新tail节点的次数就会越少，但是距离越长带来的负面效果就是每次入队时定位尾节点的时间就越长，因为循环体需要多循环一次来定位出尾节点，但是这样仍然能提高入队的效率，因为从本质上来看它通过增加对volatile变量的读操作来减少对volatile变量的写操作，而对volatile变量的写操作开销要远远大于读操作，所以入队效率会有所提升
出队
- 当head节点里有元素时，直接弹出head节点里的元素，而不会更新head节点。只有当head节点里没有元素时，出队操作才会更新head节点。这种做法也是通过hops变量来减少使用CAS更新head节点的消耗，从而提高出队效率
- 首先获取头节点的元素，然后判断头节点元素是否为空，如果为空，表示另外一个线程已经进行了一次出队操作将该节点的元素取走，如果不为空，则使用CAS的方式将头节点的引用设置成null，如果CAS成功，则直接返回头节点的元素，如果不成功，表示另外一个线程已经进行了一次出队操作更新了head节点，导致元素发生了变化，需要重新获取头节点

java中的阻塞队列

阻塞队列（BlockingQueue）是一个支持两个附加操作的队列
- 支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满
- 支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空
阻塞队列就是生产者用来存放元素、消费者用来获取元素的容器
通知模式：就是当生产者往满的队列里添加元素时会阻塞住生产者，当消费者消费了一个队列中的元素后，会通知生产者当前队列可用

Fork/Join框架

Fork就是把一个大任务切分为若干子任务并行的执行，Join就是合并这些子任务的执行结果，最后得到这个大任务的结果
工作窃取算法

一个较大的任务，可以分割成若干个互补依赖的子任务，为了减少线程间的竞争，把这些子任务分别放到不同的队列里，并为每个队列创建一个单独的线程来执行队列里的任务，线程和队列一一对应。有的线程会先把自己队列里的任务干完，而其他线程对应的队列里还有任务等待处理。干完活的线程与其等着，不如去帮其他线程干活，于是它就去其他线程的队列里窃取一个任务来执行而在这时它们会访问同一个队列，所以为了减少窃取任务线程和被窃取任务线程之间的竞争，通常会使用双端队列，被窃取任务线程永远从双端队列的头部拿任务执行，而窃取任务的线程永远从双端队列的尾部拿任务执行

工作窃取算法的优点：充分利用线程进行并行计算，减少了线程间的竞争
工作窃取算法的缺点：在某些情况下还是存在竞争，比如双端队列里只有一个任务时。并且该算法会消耗了更多的系统资源，比如创建多个线程和多个双端队列

Java中的线程池

线程池的好处
- 降低资源消耗。通过重复利用已创建的线程降低线程创建和销毁造成的消耗
- 提高响应速度。当任务到达时，任务可以不需要等到线程创建就能立即执行
- 提高线程的可管理性。线程是稀缺资源，如果无限制地创建，不仅会消耗系统资源，还会降低系统的稳定性，使用线程池可以进行统一分配、调优和监控
线程池的实现原理
ThreadPoolExecutor执行execute方法分下面4种情况
- 如果当前运行的线程少于corePoolSize，则创建新线程来执行任务（注意，执行这一步骤需要获取全局锁）
- 如果运行的线程等于或多于corePoolSize，则将任务加入BlockingQueue
- 如果无法将任务加入BlockingQueue（队列已满），则创建新的线程来处理任务（注意，执行这一步骤需要获取全局锁）
- 如果创建新线程将使当前运行的线程超出maximumPoolSize，任务将被拒绝，并调用RejectedExecutionHandler.rejectedExecution()方法
- ThreadPoolExecutor采取上述步骤的总体设计思路，是为了在执行execute()方法时，尽可能地避免获取全局锁（那将会是一个严重的可伸缩瓶颈）。在ThreadPoolExecutor完成预热之后（当前运行的线程数大于等于corePoolSize），几乎所有的execute()方法调用都是执行步骤2，而步骤2不需要获取全局锁

Executor框架

Java的线程既是工作单元，也是执行机制。从JDK 5开始，把工作单元与执行机制分离开来。工作单元包括Runnable和Callable，而执行机制由Executor框架提供
Executor框架的两级调度模型
- 在上层，Java多线程程序通常把应用分解为若干个任务，然后使用用户级的调度器（Executor框架）将这些任务映射为固定数量的线程
- 在底层，操作系统内核将这些线程映射到硬件处理器上
Executor框架主要由3大部分组成
- 任务。包括被执行任务需要实现的接口：Runnable接口或Callable接口
- 任务的执行。包括任务执行机制的核心接口Executor，以及继承自Executor的ExecutorService接口。Executor框架有两个关键类实现了ExecutorService接口
- 异步计算的结果。包括接口Future和实现Future接口的FutureTask类
Executor是一个接口，它是Executor框架的基础，它将任务的提交与任务的执行分离开来
ThreadPoolExecutor是线程池的核心实现类，用来执行被提交的任务
ScheduledThreadPoolExecutor是一个实现类，可以在给定的延迟后运行命令，或者定期执行命令。ScheduledThreadPoolExecutor比Timer更灵活，功能更强大
Future接口和实现Future接口的FutureTask类，代表异步计算的结果
Runnable接口和Callable接口的实现类，都可以被ThreadPoolExecutor或ScheduledThreadPoolExecutor执行。间的区别是Runnable不会返回结果，而Callable可以返回结果
Executor框架的使用示意图

java多线程并发任务笔记